edu.isi.stella
Class HashSet

java.lang.Object
  extended by edu.isi.stella.Stella_Object
      extended by edu.isi.stella.StandardObject
          extended by edu.isi.stella.AbstractCollection
              extended by edu.isi.stella.AbstractDictionary
                  extended by edu.isi.stella.Dictionary
                      extended by edu.isi.stella.KeyValueMap
                          extended by edu.isi.stella.HashSet

public class HashSet
extends KeyValueMap

Full-featured set class that supports eqlP or equalP equality tests, O(1) insert and memberP operations & O(N) intersection etc. operations even for large numbers of entries by using a hash table, light-weight KV-CONS representation for small sets and iteration even if the set is represented by a hash table. The only minor drawback right now is that this wastes a value slot per entry, since we piggy-back off KEY-VALUE-MAP's, however, that wastes at most 25% space.


Field Summary
 
Fields inherited from class edu.isi.stella.KeyValueMap
crossoverPoint, equalTestP, initialSize, theMap
 
Constructor Summary
HashSet()
           
 
Method Summary
 Cons consify()
          Collect all entries of self into a cons list and return the result.
 KeyValueMap copy()
          Return a copy of the set self.
 HashSet difference(HashSet otherset)
          Return the set difference of self and otherset as a new set (i.e., all elements that are in self but not in otherset).
 int equalHashCode()
          Return an equalP hash code for self.
 boolean equivalentSetsP(HashSet otherset)
          Return true if every element of self occurs in otherset and vice versa.
 void insert(Stella_Object value)
          Add value to the set self unless it is already a member.
 HashSet intersection(HashSet otherset)
          Return the set intersection of self and otherset as a new set.
 boolean memberP(Stella_Object renamed_Object)
          Return TRUE iff renamed_Object is a member of the set self.
static HashSet newHashSet()
           
 boolean objectEqualP(Stella_Object y)
          Return TRUE iff sets x and y are HASH-SET's with equivalent members.
 Stella_Object pop()
          Remove and return an arbitrary element of the set self.
 Surrogate primaryType()
          Returns the primary type of self.
 AbstractCollection remove(Stella_Object value)
          Destructively remove value from the set self if it is a member and return self.
 HashSet removeIf(java.lang.reflect.Method testP)
          Destructively remove all elements of the set self for which 'test?' evaluates to TRUE.
 boolean subsetP(HashSet otherset)
          Return true if every element of self also occurs in otherset.
 HashSet substitute(Stella_Object renamed_New, Stella_Object old)
          Destructively replace old with renamed_New in the set self unless renamed_New is already a member.
 HashSet subtract(HashSet otherset)
          Return the set difference of self and otherset by destructively removing elements from self that also occur in otherset.
 HashSet union(HashSet otherset)
          Return the set union of self and otherset as a new set.
 
Methods inherited from class edu.isi.stella.KeyValueMap
accessKeyValueMapSlotValue, allocateIterator, clear, emptyP, insertAt, length, lookup, newKeyValueMap, nonEmptyP, removeAt
 
Methods inherited from class edu.isi.stella.AbstractDictionary
dictionary
 
Methods inherited from class edu.isi.stella.StandardObject
arrayTypeSpecifierP, baseTypeToTypeSpec, cantOverwriteActiveCollectionSlot, compatibleParameterTypesP, computeAnchoredTypeSpec, computeRelativeTypeSpec, conformingTypeSpecP, copyWrappedLiteral, cppNonPointerTypeP, cppReferenceTypeP, cppReferencizeType, cppTranslateAndPointerizeTypeSpec, cppTranslateAndReferencizeTypeSpec, cppTranslateTypeSpec, cppTypeWithoutInteriorPointersP, dropSlotValue, extractParameterType, extractRequiredArgumentValues, getSlot, hashCode_, idlTranslateTypeSpec, inverseSlotDemon, javaLiteralP, javaNativeLiteralWrapperNames, javaSpecialSetterName, javaTranslateArrayOfTypeSpec, javaTranslateTypeSpec, javaTranslateTypeSpecForFunction, javaTranslateTypeSpecHelper, javaYieldClassObjectArrayExpression, javaYieldClassObjectExpression, javaYieldFullyQualifiedTypeName, javaYieldTranslatedClassAndMethodNames, listifyTypeSpec, lookupClTypeFromStellaType, objectEqlP, putSlotValue, readSlotValue, runConstructorDemons, runDestructorDemons, runSlotDemons, runSlotGuardDemonsP, standardObjectP, subTypeSpecOfP, twoArgumentLeastCommonSupertype, typeSpecToBaseType, typeSpecToClass, typeToWalkedNullValueTree, validateTypeSpecifier, voidP, walkTypeSpecIsNativeTypeP, writeSlotValue, yieldTypeSpecTree
 
Methods inherited from class edu.isi.stella.Stella_Object
_, accessInContext, addPropertyValue, amPm, anchoredTypeSpecifierP, andOrNotTreeP, applyCoercionMethod, atomicExpressionP, bindToSurrogateP, booleanP, bootstrapIsaP, bquotify, cast, characterP, chooseSortPredicate, clConditionalizeTypeDeclarationTree, clTranslateAtomicTree, clTranslateATree, clTranslateBooleanTest, clTranslatePlainBooleanTest, clTranslateVerbatimBodySymbols, clYieldTypedExpressionTree, coerceATree, coerceEvaluatedTree, coerceMvTree, coerceOptionValue, coerceToBoolean, coerceToFloat, coerceToHashSet, coerceToModule, coerceToModuleName, coerceToString, coerceToSymbol, coerceToXmlElement, coerceValueToBoolean, coerceValueToFloat, coerceValueToString, coerceValueToType, coercibleP, collectFeatureList, collectKeyValueList, commonLispSymbolP, computeExpressionType, consifyListsAndIterators, consP, consTreeMatchP, convertToLiteral, copyConsTree, cppArgumentIsStreamP, cppBinaryOperatorP, cppBlockP, cppMaybeOutputStatementWithParentheses, cppOperatorP, cppOutputAtomicExpression, cppOutputLiteral, cppOutputOneActualParameter, cppOutputStatement, cppOutputTypedEntity, cppPrognifyStatement, cppPrognP, cppStatementToList, cppStreamIsStandardOutputP, cpptrans, cppTranslateAtomicTree, cppTranslateATree, cppTranslatedArrayTypeP, csValueP, dateDivider, dateTimeDivider, day, dealWithAmPm, dealWithEra, dealWithNoonMidn, decrementReferenceCount, defaultOptionHandler, defineSystem, defmodule, deletedP, describe, describeObject, describeTersely, destructureMethodNameTree, deUglifyParseTree, either, eqlP, eqlToBooleanP, eqlToCharacterP, eqlToFloatP, eqlToIntegerP, eqlToLongIntegerP, eqlToStringP, equalConsTreesP, equalP, era, estimatedEvaluationCost, evaluate, evaluateArgumentTree, evaluateAtomicTree, evaluateCommand, expandBquoteTree, filterModuleP, floatP, free, get, getObject, getProperty, hashlist, hashMemoizedArguments, helpBquotify, helpClTranslateATree, helpCoerceATree, helpLptrans, helpPrintOutline, helpTransformBooleanProceduralExpression, helpWalkATree, homeModule, hour, idlOutputAtomicExpression, idlOutputLiteral, idlOutputStatement, idlTranslateAtomicTree, idlTranslateATree, illegalTreeP, implodePathname, incrementallyTranslate, incrementReferenceCount, inlineUnwrapBoolean, inlineWrapBoolean, inModule, integerP, isaP, javaBinaryOperatorP, javaBlockP, javaEndOfLineTokenP, javaHelpOutputPrintStream, javaMaybeOutputStatementWithParentheses, javaOperatorP, javaOutputLiteral, javaOutputStatement, javaPrognP, javaStreamIsStandardOutputP, javaSymbolCaseP, javaTranslateAtomicTree, javaTranslateATree, javaTranslateWithNativeWrapper, jptrans, keywordP, legalTokenizerFromStateP, legalTokenizerStateP, legalTokenizerToStateP, literalEqlP, logLevelLE, longIntegerP, lptrans, makeEvaluatableBquoteTree, makeFileNameFromRelativePath, makeMemoizedValueEntry, makeMemoizedValueEntryn, matchConsTree, methodSlotP, minute, month, nameToString, nilP, noonMidn, numberWrapperToFloat, objectHashCode, one, oneI, onlyIf, parametricTypeSpecifierP, parseArrayDimensionsSpec, parseOptions, parseTokenizerCharacterSpec, parseTokenizerStateModifiers, permanentCopy, permanentify, permanentifyForm, po, prettyPrintLiteral, primaryClass, printObject, printOutline, printStellaCode, printStellaDefinition, printUndefinedSuperClasses, proceduralExpressionP, ptrans, publicSlots, registerRecycledItem, runOptionHandlerP, safeEqualHashCode, safeHashCode, safePrimaryType, safeYieldTypeSpecifier, searchConsTreeP, searchConsTreeWithFilterP, searchForObject, secondp, setProperty, sideEffectFreeExpressionP, simplifyBquoteTree, specialp, stella_Increment, stellaClassP, stellaCollectionP, stellaNeedToCompileP, stellaNeedToTranslateP, stellaObjectP, stellify, storageSlotP, stringifyInModule, stringP, substituteConsTree, substituteOnce, surrogateP, surrogatify, sweep, symbolCaseP, symbolP, sysTree, targetLanguageType, taxonomyIsaP, timeDivider, timeMultiply, tokenizerIncludeSpecP, tokenizerToStateAlias, tokenizerToStateName, toString, traceIf, traceKeywordP, transientifyForm, transientObjectP, transientSymbolP, translateWalkedTree, treeSize, treeToTrees, trueOptionP, tryToEvaluate, typeP, typify, unmake, unregisterRecycledItem, updateInContext, valuesTreeP, variableExpressionP, verbatimStringP, verbatimTreeP, vetOptions, vrletExpressionP, walkAtomicTree, walkATree, walkCollectionTree, walkDontCallMeTree, walkedExpressionExpression, walkedExpressionType, walkExpressionTree, walkMvExpressionTree, walkMvTree, walkStatement, walkTopLevelExpression, walkWithoutTypeTree, warnAboutUnknownSourceType, weekday, withinContext, withinModule, withinWorld, withStellaTokenizer, withSystemDefinition, withTokenizer, wrapperP, wrapWhereTest, xmlAttributeP, xmlBaseAttributeP, xmlCdataFormP, xmlCdataP, xmlDeclarationFormP, xmlDeclarationP, xmlDoctypeFormP, xmlElementFormP, xmlElementP, xmlGlobalAttributeP, xmlLocalAttributeP, xmlnsAttributeP, xmlProcessingInstructionFormP, xmlProcessingInstructionP, xmlTagCase, year, yieldCondTest, yieldCondTestOrTests, yieldHardcodedCaseSymbolIdOrIds, yieldInCursorClausesForArgumentList, yieldInCursorClausesForGeneralCollection, yieldInCursorClausesForVector, yieldTypeSpecifier, zone, zoneMinute
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Constructor Detail

HashSet

public HashSet()
Method Detail

newHashSet

public static HashSet newHashSet()

equalHashCode

public int equalHashCode()
Return an equalP hash code for self. Note that this is O(N) in the number of elements of self.

Overrides:
equalHashCode in class KeyValueMap
Returns:
int

objectEqualP

public boolean objectEqualP(Stella_Object y)
Return TRUE iff sets x and y are HASH-SET's with equivalent members. Uses an eqlP test by default or equalP if equalTestP of self is TRUE. This is equivalent to calling equivalentSetsP.

Overrides:
objectEqualP in class KeyValueMap
Parameters:
y -
Returns:
boolean

subtract

public HashSet subtract(HashSet otherset)
Return the set difference of self and otherset by destructively removing elements from self that also occur in otherset. Uses an eqlP test by default or equalP if equalTestP of self is TRUE.

Parameters:
otherset -
Returns:
HashSet

difference

public HashSet difference(HashSet otherset)
Return the set difference of self and otherset as a new set (i.e., all elements that are in self but not in otherset). Uses an eqlP test by default or equalP if equalTestP of self is TRUE.

Parameters:
otherset -
Returns:
HashSet

union

public HashSet union(HashSet otherset)
Return the set union of self and otherset as a new set. Uses an eqlP test by default or equalP if equalTestP of self is TRUE.

Parameters:
otherset -
Returns:
HashSet

intersection

public HashSet intersection(HashSet otherset)
Return the set intersection of self and otherset as a new set. Uses an eqlP test by default or equalP if equalTestP of self is TRUE.

Parameters:
otherset -
Returns:
HashSet

equivalentSetsP

public boolean equivalentSetsP(HashSet otherset)
Return true if every element of self occurs in otherset and vice versa. Uses an eqlP test by default or equalP if equalTestP of self is TRUE.

Parameters:
otherset -
Returns:
boolean

subsetP

public boolean subsetP(HashSet otherset)
Return true if every element of self also occurs in otherset. Uses an eqlP test by default or equalP if equalTestP of self is TRUE.

Parameters:
otherset -
Returns:
boolean

consify

public Cons consify()
Collect all entries of self into a cons list and return the result.

Overrides:
consify in class KeyValueMap
Returns:
Cons

copy

public KeyValueMap copy()
Return a copy of the set self. All entries are freshly allocated, however, the values are not copied themselves (similar to what we do for lists, etc.).

Overrides:
copy in class KeyValueMap
Returns:
KeyValueMap

substitute

public HashSet substitute(Stella_Object renamed_New,
                          Stella_Object old)
Destructively replace old with renamed_New in the set self unless renamed_New is already a member. Uses an eqlP test by default or equalP if equalTestP of self is TRUE.

Parameters:
renamed_New -
old -
Returns:
HashSet

pop

public Stella_Object pop()
Remove and return an arbitrary element of the set self. Return NULL if the set is empty. Performance note: for large sets implemented via hash tables it takes O(N) to empty out the set with repeated calls to pop, since the emptier the table gets, the longer it takes to find an element. Therefore, it is usually better to use iteration with embedded removals for such cases.

Returns:
Stella_Object

removeIf

public HashSet removeIf(java.lang.reflect.Method testP)
Destructively remove all elements of the set self for which 'test?' evaluates to TRUE. testP takes a single argument of type OBJECT and returns TRUE or FALSE. Returns self.

Parameters:
testP -
Returns:
HashSet

remove

public AbstractCollection remove(Stella_Object value)
Destructively remove value from the set self if it is a member and return self. Uses an eqlP test by default or equalP if equalTestP of self is TRUE.

Parameters:
value -
Returns:
AbstractCollection

insert

public void insert(Stella_Object value)
Add value to the set self unless it is already a member. Uses an eqlP test by default or equalP if equalTestP of self is TRUE.

Parameters:
value -

memberP

public boolean memberP(Stella_Object renamed_Object)
Return TRUE iff renamed_Object is a member of the set self. Uses an eqlP test by default or equalP if equalTestP of self is TRUE.

Parameters:
renamed_Object -
Returns:
boolean

primaryType

public Surrogate primaryType()
Description copied from class: Stella_Object
Returns the primary type of self. Gets defined automatically for every non-abstract subclass of OBJECT.

Overrides:
primaryType in class KeyValueMap
Returns:
Surrogate