|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
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
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 java.lang.Object |
---|
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait |
Constructor Detail |
---|
public HashSet()
Method Detail |
---|
public static HashSet newHashSet()
public int equalHashCode()
equalP
hash code for self
. Note that this
is O(N) in the number of elements of self
.
equalHashCode
in class KeyValueMap
public boolean objectEqualP(Stella_Object y)
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
.
objectEqualP
in class KeyValueMap
y
-
public HashSet subtract(HashSet otherset)
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.
otherset
-
public HashSet difference(HashSet otherset)
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.
otherset
-
public HashSet union(HashSet otherset)
self
and otherset
as a new set.
Uses an eqlP
test by default or equalP
if equalTestP
of self
is TRUE.
otherset
-
public HashSet intersection(HashSet otherset)
self
and otherset
as a new set.
Uses an eqlP
test by default or equalP
if equalTestP
of self
is TRUE.
otherset
-
public boolean equivalentSetsP(HashSet otherset)
self
occurs in otherset
and vice versa.
Uses an eqlP
test by default or equalP
if equalTestP
of self
is TRUE.
otherset
-
public boolean subsetP(HashSet otherset)
self
also occurs in otherset
.
Uses an eqlP
test by default or equalP
if equalTestP
of self
is TRUE.
otherset
-
public Cons consify()
self
into a cons list and return the result.
consify
in class KeyValueMap
public KeyValueMap copy()
self
. All entries are freshly
allocated, however, the values are not copied themselves (similar to what we
do for lists, etc.).
copy
in class KeyValueMap
public HashSet substitute(Stella_Object renamed_New, Stella_Object old)
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.
renamed_New
- old
-
public Stella_Object pop()
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.
public HashSet removeIf(java.lang.reflect.Method testP)
self
for which
'test?' evaluates to TRUE. testP
takes a single argument of type OBJECT and
returns TRUE or FALSE. Returns self
.
testP
-
public AbstractCollection remove(Stella_Object value)
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.
value
-
public void insert(Stella_Object value)
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.
value
- public boolean memberP(Stella_Object renamed_Object)
renamed_Object
is a member of the set self
.
Uses an eqlP
test by default or equalP
if equalTestP
of self
is TRUE.
renamed_Object
-
public Surrogate primaryType()
Stella_Object
self
.
Gets defined automatically for every non-abstract subclass of OBJECT.
primaryType
in class KeyValueMap
|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |