common
Class IndexedHashSet

java.lang.Object
  java.util.AbstractCollection<E>
      java.util.AbstractSet
          common.IndexedHashSet

All Implemented Interfaces:

IndexedSet, java.lang.Cloneable, java.lang.Iterable, java.util.Collection, java.util.Set

public class IndexedHashSet
extends java.util.AbstractSet
implements IndexedSet, java.lang.Cloneable

Implementation of the IndexedSet interface that stores objects in a list, and uses a HashMap to map objects to their indices. Indices are assigned to objects consecutively as they are added. When an object is removed, the last element is swapped in to fill its index; thus, removing an element that is not the last one may change the index of the last element. Getting the element at a given index takes constant time.

Nested Class Summary

Nested classes/interfaces inherited from interface common.IndexedSet

IndexedSet.EmptyIndexedSet

Field Summary

Fields inherited from interface common.IndexedSet

EMPTY_INDEXED_SET

Constructor Summary

IndexedHashSet()
Creates a new, empty IndexedSet.

IndexedHashSet(java.util.Collection c)
Creates a new IndexedSet whose elements are those in the given collection, ordered according to the collection's iterator order.

Method Summary

boolean	add(java.lang.Object o) Adds the given object to this IndexedSet, with an index equal to the previous size of the set.
void	clear()
java.lang.Object	clone()
boolean	contains(java.lang.Object o)
java.lang.Object	get(int index) Returns the object with the specified index in this IndexedSet.
int	indexOf(java.lang.Object o) Returns the index of the given object in this IndexedSet, or -1 if this IndexedSet does not contain the given object.
java.util.Iterator	iterator()
static void	main(java.lang.String[] args) Test program.
boolean	remove(java.lang.Object o) Removes the given object from this IndexedSet if it was present.
int	size()

Methods inherited from class java.util.AbstractSet

equals, hashCode, removeAll

Methods inherited from class java.util.AbstractCollection

addAll, containsAll, isEmpty, retainAll, toArray, toArray, toString

Methods inherited from class java.lang.Object

finalize, getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface java.util.Set

addAll, containsAll, equals, hashCode, isEmpty, removeAll, retainAll, toArray, toArray

Constructor Detail

IndexedHashSet

public IndexedHashSet()

Creates a new, empty IndexedSet.

IndexedHashSet

public IndexedHashSet(java.util.Collection c)

Creates a new IndexedSet whose elements are those in the given collection, ordered according to the collection's iterator order.

Method Detail

size

public int size()

Specified by:

size in interface java.util.Collection

Specified by:

size in interface java.util.Set

Specified by:

size in class java.util.AbstractCollection

iterator

public java.util.Iterator iterator()

Specified by:

iterator in interface java.lang.Iterable

Specified by:

iterator in interface java.util.Collection

Specified by:

iterator in interface java.util.Set

Specified by:

iterator in class java.util.AbstractCollection

contains

public boolean contains(java.lang.Object o)

Specified by:

contains in interface java.util.Collection

Specified by:

contains in interface java.util.Set

Overrides:

contains in class java.util.AbstractCollection

add

public boolean add(java.lang.Object o)

Adds the given object to this IndexedSet, with an index equal to the previous size of the set. Does nothing if the object was already in this set.

Specified by:

add in interface java.util.Collection

Specified by:

add in interface java.util.Set

Overrides:

add in class java.util.AbstractCollection

Returns:

true if the object was not already in this set

remove

public boolean remove(java.lang.Object o)

Removes the given object from this IndexedSet if it was present. If the given object was in the set but not at the end, this operation changes the index of the last element so it is equal to the previous index of this element.

Specified by:

remove in interface java.util.Collection

Specified by:

remove in interface java.util.Set

Overrides:

remove in class java.util.AbstractCollection

Returns:

true if the object was in this set

clear

public void clear()

Specified by:

clear in interface java.util.Collection

Specified by:

clear in interface java.util.Set

Overrides:

clear in class java.util.AbstractCollection

get

public java.lang.Object get(int index)

Returns the object with the specified index in this IndexedSet.

Specified by:

get in interface IndexedSet

Throws:

java.lang.IndexOutOfBoundsException - if the index is out of range (index < 0 || index >= size())

indexOf

public int indexOf(java.lang.Object o)

Returns the index of the given object in this IndexedSet, or -1 if this IndexedSet does not contain the given object.

Specified by:

indexOf in interface IndexedSet

clone

public java.lang.Object clone()

Overrides:

clone in class java.lang.Object

main

public static void main(java.lang.String[] args)

Test program.