chord.util
Class IndexSet<T>

java.lang.Object
  chord.util.IndexSet<T>

Type Parameters:

T - The type of objects in the set.

All Implemented Interfaces:

java.lang.Iterable<T>

public class IndexSet<T>
extends java.lang.Object
implements java.lang.Iterable<T>

Implementation for indexing a set of objects by the order in which the objects are added to the set.

Maintains an array list and a hash set.

Provides O(1) access to the object at a given index by maintaining an array list.

Provides O(1) membership testing for a given object by maintaining a hash set.

Author:

Mayur Naik (mhn@cs.stanford.edu)

Field Summary

protected java.util.HashSet<T>	hset
protected java.util.List<T>	list

Constructor Summary

IndexSet()

IndexSet(int size)

Method Summary

boolean	add(T val) Adds a given object, unless it already exists, in O(1) time.
void	clear() Remove all elements from the set.
boolean	contains(java.lang.Object val)
java.util.Iterator<T>	iterator()
int	size()

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

list

protected final java.util.List<T> list

hset

protected final java.util.HashSet<T> hset

Constructor Detail

IndexSet

public IndexSet(int size)

IndexSet

public IndexSet()

Method Detail

clear

public void clear()

Remove all elements from the set.

contains

public boolean contains(java.lang.Object val)

add

public boolean add(T val)

Adds a given object, unless it already exists, in O(1) time.

Parameters:

val - An object.

Returns:

true iff the given object did not already exist and was successfully added.

size

public int size()

iterator

public java.util.Iterator<T> iterator()

Specified by:

iterator in interface java.lang.Iterable<T>