Class LazyColl

java.lang.Object
  |
  +--java.util.AbstractCollection
        |
        +--LazyColl

All Implemented Interfaces:

java.util.Collection

public class LazyColl

extends java.util.AbstractCollection

A class representing an array which automatically sorts itself as needed for efficient lookup of elements. It is intended to be used in situations where there are a series of additions (with no lookups) followed by many lookups (with no additions). It implements Collection as it is neither a true List nor a Set (it allows duplicates, and in that sense is like a multiset). The additional requirement it adds to Collection is that its elements must be comparable, and that the compare operation be compatible with equals() to maintain substitutability with Collection. The comparison operation is by default implemented by Comparable.compareTo, but can be implemented by a user-provided Comparator object instead. If no Comparator object is provided, the objects passed to add() must implement Comparable. If one of these two conditions is true, this documentation calls the objects "comparable". Operations which depend on element ordering run in O(n log n) worst case time, but O(log n) time if the collection is already sorted. Methods without comments are identical to the Collection interface specification, but with the above restrictions.

Constructor Summary

LazyColl()

LazyColl(java.util.Collection other)

LazyColl(java.util.Collection other, java.util.Comparator cmp)

LazyColl(java.util.Comparator cmp)

Method Summary

boolean	add(java.lang.Object o) Adds an element to the collection.
void	checkOK() Checks invariants for the class; throws exception if they are violated.
boolean	contains(java.lang.Object o) Tells if collection contains an object equivalent to the given one.
java.lang.Object	find(java.lang.Object o) Finds match (in Comparable sense) for the given object; returns matching object or null if not found.
java.util.Iterator	iterator() Returns an iterator to the contained elements.
static void	main(java.lang.String[] args) Unit tests for LazyColl.
boolean	remove(java.lang.Object o) Removes an object equivalent to the given one.
int	size()

Methods inherited from class java.util.AbstractCollection

addAll, clear, containsAll, isEmpty, removeAll, retainAll, toArray, toArray, toString

Methods inherited from class java.lang.Object

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

Methods inherited from interface java.util.Collection

equals, hashCode

Constructor Detail

LazyColl

public LazyColl()

LazyColl

public LazyColl(java.util.Collection other)

LazyColl

public LazyColl(java.util.Comparator cmp)

LazyColl

public LazyColl(java.util.Collection other,
                java.util.Comparator cmp)

Method Detail

size

public int size()

Overrides:

size in class java.util.AbstractCollection

add

public boolean add(java.lang.Object o)

Adds an element to the collection. Runs in O(log n) time.

Overrides:

add in class java.util.AbstractCollection

Parameters:

o - Element to add (must be comparable)

Returns:

true to indicate the collection was modified, false otherwise.

contains

public boolean contains(java.lang.Object o)

Tells if collection contains an object equivalent to the given one.

Overrides:

contains in class java.util.AbstractCollection

Parameters:

o - Element to search for (must be comparable)

iterator

public java.util.Iterator iterator()

Returns an iterator to the contained elements. Elements are always in sorted order.

Overrides:

iterator in class java.util.AbstractCollection

remove

public boolean remove(java.lang.Object o)

Removes an object equivalent to the given one.

Overrides:

remove in class java.util.AbstractCollection

Parameters:

o - Element to search for (must be comparable)

find

public java.lang.Object find(java.lang.Object o)

Finds match (in Comparable sense) for the given object; returns matching object or null if not found.

Parameters:

o - Object (must be comparable)

Returns:

The found object or null if no match found

checkOK

public void checkOK()

Checks invariants for the class; throws exception if they are violated.

main

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

Unit tests for LazyColl.