edu.isi.stella
Class HashSet

java.lang.Object
  edu.isi.stella.Stella_Object
      edu.isi.stella.StandardObject
          edu.isi.stella.AbstractCollection
              edu.isi.stella.AbstractDictionary
                  edu.isi.stella.Dictionary
                      edu.isi.stella.KeyValueMap
                          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