# Overview of the `collections` Package

by Doug Lea.

This overview is intended to accompany version 0.96b of the package of code (tar.gz format) (zip format) and documentation for the java collection classes. Please send comments and questions to dl@cs.oswego.edu.

(Note: This package is fairly stable and in routine use. However, there may continue to be minor changes.)

### Contents

1. Collections
2. Updatable Collections
3. Immutable Collections
4. Exceptions
5. Enumerations
6. Checked Classes
7. Links to Source Code
8. ToDo List
9. Version History

## Collections

Collections are objects that hold other objects that are accessed, placed, and maintained under some set of rules. There are many different ways you could classify these different rules. This package uses one of the simplest, splitting them into four main categories, (Sets, Bags, Seqs, Maps), plus a few `mixin' variants. Top-level functionality is described entirely via `interfaces`, not `classes`. This allows some mixing and matching of capabilities at the implementation level, and also enables you to add your own alternative implementations of this functionality that will interoperate with the versions provided in this package.

As a user of the `collection` package, you do not need to know a lot about data structures, but you do need to know what kinds of access and placement rules you want in a particular situation. The basic choices are:

- Sets contain at most one occurrence of any element.
- Bags may contain multiple occurrences of any element.
- Seqs are ordered, and have elements that are accessible via array-like indices.
- Maps associate unique keys with each element.
- ElementSorted Collections maintain elements in order with respect to a given Comparator (sorting) function; KeySorted collections maintain them in order of their keys. (Any of the above kinds of collections may be element-sorted, but only Maps can be key-sorted.)

The base interface `Collection` reflects commonalities across all of these of kinds of rules. For reasons described below, all of the interfaces in the following diagram describe classes/objects that need not even be updatable (modifiable), so restrict themselves to operations that report properties of Collections or build new Collections with various properties.

Collection
  Collection is the base interface for all collection classes defined in this package. Every collection can:
  - Report its `size` and whether it `isEmpty`.

  - Report whether it `canInclude` a given value. In general Collections hold Objects. Elements may be subclasses of Object, but not builtin scalars like int. You can, however, use numbers as elements via the java.lang.Number class (or rather its subclasses) to ``wrap'' the numbers as number-holding objects first. For example:

         void addFloat(UpdatableBag b, float f) {
           b.add(new Float(f));
         }

    Also, null is never a valid element, so canInclude(null) is always false. Operations screen for nulls, and raise exceptions upon attempts to add them to collections (but NOT when testing for their presence). This can be annoying, but is the most defensible policy. One reason that nulls are excluded is that some collection operations intrinsically rely upon operations Object.equals and Object.hashCode, neither of which apply to nulls.

    Any given collection may make stronger demands on the kinds of elements it will accept, and report this via `canInclude`. Most implementation classes support a constructor with an argument supplying an element screener (an object of type Predicate) that checks whether a value is considered to be a potentially legal element of the collection. For example, you could supply a screener that requires that all elements be Strings (using `instanceof'). Screeners provide a more flexible variant of constraints found in languages with parameterized types, although without any kind of compile time guarantees that clients won't try to place inappropriate elements into collections, thus causing exceptions.

  - Report whether it `includes` a given element. Equality is always tested using Object.equals(Object other).

  - Report the number of `occurrencesOf` a given element it holds.

  - Produce an enumeration of its `elements`. The enumeration returned is of type CollectionEnumeration, a stronger kind of enumeration than java.util.Enumeration.

  - Perform `checkImplementation`, that checks the consistency and properties of the internal state of a collection implementation object. `Collection` is a subinterface of ImplementationCheckable, which is in turn a subinterface of Assertable, the base interface for classes with an `assert` method that can be used to help track down errors.

  - Report whether it has the `sameStructure` as another Collection, c; that is whether c has the same size and the same elements() arranged in a compatible way. This is a form of equality test, but is not named `equals` (and thus does not override Object.equals) since it is not always the sense of equality that you would want to apply to collections.

  - Build a new Collection that is just like self except `excluding` (i.e., removing all `occurrencesOf`) a given element. This does not alter the Collection itself, it just makes a new one. This operation is a lot like subtraction of numbers. When you say `a - b` for two numbers `a` and `b`, you get a new number that represents the difference between them without changing `a` or `b`. The `excluding` operation has the same kind of effect. By convention, all such creational methods are named with gerunds (e.g., including, excluding, adding).

    If you want a collection in which you actually change the contents of the current collection rather than building a new one, you'll need an UpdatableCollection with an `exclude` operation, described below. But even without using UpdatableCollections, you can still create series of collections, each one differing them the previous one by virtue of not including a given element via code like:

                Collection excludingElements(Collection c, Enumeration e) {
                  while (e.hasMoreElements())
                    c = c.excluding(e.nextElement());
                  return c;
                }

    For many implementations of Collection, this is a ridiculously slow way to do it. However, as described below, others (the Incr classes) are tuned to do this reasonably efficiently.

  - Build a new Collection that is just like self except `removingOneOf` (i.e., removing at most one occurrence of) a given element.

  - Build a new Collection that is just like self except `replacingOneOf` (i.e., at most one occurrence of) some old value with a new value.

  - Build a new Collection that is just like self except `replacingAllOf` (i.e., all occurrences of) some old value with a new value.

  - Build a `duplicate` of self -- an independent copy of the collection, but not necessarily its elements. Elements themselves are not necessarily cloned. (Note: `duplicate` is simply the externally callable version of method `java.lang.Object.clone()`.)
  - Support Serialization. All Collections, as well as other auxiliary classes and interfaces are declared to implement `java.io.Serializable`.
  - Also, while it cannot be stated in the interface, each collection implementation supports:
    1. A default constructor, initializing it to an empty (and unscreened) collection;
    2. Synchronization. As a rule, all operations (even ``read-only'' operations) within implementation classes are declared as synchronized.
Sets
  Sets are collections in which the number of occurrences of any object is at most one. They support an operation that causes `includes` to be true; i.e., adding an element only if it is not present.
Bags
  Bags may contain multiple occurrences of each element. Bags can do anything that Sets can and more, except that they do not intrinsically guarantee that the number of occurrences of any element is at most one. (However, you can always use a Bag in a way that `manually' enforces that the number of occurrences is at most one.)
Seqs
  Seqs maintain elements in sequential order. They are sequential lists that can be accessed by positional indices ranging from 0..size()-1. Other Collections that are not Seqs may guarantee some kind of sequential ordering of elements, but don't support access of these elments via indices.
Maps
  Maps are collections in which each element has a key. Any kind of Object may serve as a key for an element. (While you could use regular Collections in which each element holds a pair, Maps are generally simpler, more efficient, and contain operations useful under the interpretation that the pairs represent keyed elements.)

  Maps also serve as a way to use a certain field of objects of some class as a key for purposes of storing in a collection. For example, supposing you want to use some accessor prop() defined in your class as the basis for entering and finding elements, you could use a Map, entering pairs of (x.prop(), x).

ElementSortedCollections
  A mixin for collections that always maintain elements in sorted order with respect to a give Comparator Note: SortedCollections rely on the ordering properties of elements NOT to change once they have been placed in the collection. They cannot in general deal with cases where you change any of their elements behind their backs in ways that break their sort order. (See however, implementation checks that can help you discover if this occurred.)

  ElementSorted Collections provide a different way to use properties of objects as their access keys. You can define your class to implement interface Keyed, with a method key() that returns the key (for example it might just return prop()). Then use a Comparator that compares on keys(). The DefaultComparator class does this automatically before trying to perform comparsions, but you can write your own Comparator that does this in a more specialized and efficient way.)

KeySortedCollections
  A mixin for Maps that always maintain keys in sorted order

## UpdatableCollections

Updatable collections are `normal' mutable collections. They:

- Allow insertion, removal, and/or replacement of elements in accordance with their element semantics. Some such operations (like clear, take) are common to all updatable classes.
- Maintain a `version number' that changes upon each successful modification.
- Produce elements() enumerations that contain consistency checks, invalidating the enumeration if the base collection has been changed during the course of a traversal.

UpdatableSets
  Updatable collections maintaining Set semantics. They support an `include' operation that adds an element if not present, plus a version that includes all elements from a supplied Eunumeration.
UpdatableBags
  Updatable collections with an add(v) operation, that adds an occurrence of v to the collection, and addIfAbsent that only conditionally adds the element.
UpdatableSeqs
  Seqs with standard indexed update operations (insertAt, replaceAt, removeAt). They also support method `insertElementsAt(int index, Enumeration e)` that adds all elements of e, in order, at position index. UpdatableSeqs also support special (often more efficient) methods operating on the front and back of the sequence,
UpdatableMaps
  Maps with update operations, principally putAt(key, element) and removeAt(key).
SortableCollections
  A `mixin' for collections that support a sort operation that accepts a Comparator. The difference between Sorted and Sortable is that (Element- or Key-) SortedCollections are always in sorted order, while Sortable ones may be sorted (via sort(Comparator cmp)), but may then be altered in ways so they are no longer sorted.

Generally, implementations are written at the point in the interface hierarchy that they most naturally support. They mainly use classic data structure implementation techniques, with an emphasize safety and correctness, but with enough efficiency that you will not usually have to build your own special-case data structures.

Currently, there are no `wrapped' implementation types that allow one implementation to serve as another kind of collection. You can always build these yourself. For example, it's possible to have an RBTree serve as the underlying implementation for a Set by making, say, an RBSet class holding a reference to an RBTree, and forwarding include as addIfAbsent, and so on. Similarly, there are not any Seq-like classes (like Stack or Queue) that ONLY support operations on the front or back, since you can just use UpdatableSeqs for such purposes merely by not using those other operations; or if you like, making a special class holding an UpdatableSeq and forwarding it only selected messages.

The reason there are so many different implementation types it that, in the collections business, it's not the case that one size fits all. Different Implementations have different time/space tradeoffs, and different operations they are particularly good and bad at. The basic strategy for building a collection package is to force all of these implementations to share common interfaces, so that only the person doing the initial construction of a collection object that will be passed around and used polymorphically has to care about these issues. If you do not care, just use the ones handed out by DefaultImplementations, which makes pretty reasonable choices. If you do care, be sure to look over the time complexities listed in the documentation for each implementation class.

Forcing implementations to share common interfaces is a standard OO trick, but sometimes leads to classes providing methods that they'd almost rather not support. For example LinkedLists support indexed access of the elements of the list. This is pretty slow. You'd only use a LinkedList if you only rarely need to access by index.

All current implementations are subclasses of UpdatableImpl a convenient abstract class that provides default implementations of many UpdatableCollection operations.

Also, all current UpdatableCollection classes implement constructive operations (`excluding`, `adding`, etc) by cloning full copies, which is not very fast.

Current implementations include:

HashedSets implement UpdatableSet
  Standard implementation of hash tables of single elements.
RBTrees implement UpdatableBag, ElementSortedCollection
  Implementation of red-black trees, a form of balanced sorted binary search tree.
LinkedLists implement UpdatableSeq, SortableCollection
  Standard implementation of linked lists.
CircularLists implement UpdatableSeq
  Standard implementation of double-linked circluar lists.
Dynarrays implement UpdatableSeq, SortableCollection
  Buffered array that dynamically resizes when necessary.
LinkedBuffers implement UpdatableBag
  An expandable list of array-based buffers.
HashedMaps implement Map
  Hash Table of keyed elements,
LLMaps implement Map
  LinkedLists of (key, element) pairs supporting Map operations.
RBMaps implement Map, KeySortedCollection
  Red-Black trees of keyed elements

These implementation classes contain only methods described in their interfaces, plus, in most cases, a few special `tuning' methods that let you override default properties of the underlying data structures. These include:

- Hash tables: methods to determine and set the number of `buckets` and the `loadFactorThreshold`.
- Linked buffers: methods to determine and set the `chunkSize` for buffers.
- Dynarrays: methods to determine and set the `capacity` of the underlying arrays
- Red-black trees: methods to reset the `elementComparator` or `keyComparator` used for ordering.

Many of the implementation classes themselves rely on yet lower-level classes of basic data structures. These classes are also made public in this package, so that you can use them as the building-blocks of other Collection implementations. They currently include:

Cell
  A simple box holding an Object
LLCell
  Cells with next-pointers. Each cell knows how to do basic linked list operations like insert another LLCell after itself.
LLPair
  An extension of LLCell in which each node has a key
CLCell
  A cell with next- and prev- pointers, and operations so that objects maintain themselves in proper circular list order.
RBCell
  A cell with red-black-tree pointers and color, and methods to add new RBCells, properly rebalancing the tree it is in upon insertion. And so on
RBPair
  RBCells with keys.

## Immutable Collections.

Immutable versions of collections are those that GUARANTEE not to support mutations. This is a stronger claim than is made by Collection, since any object known only to be a Collection MAY be coercible to Updatable. But an Immutable version is not. This makes Immutable classes exceedingly safe.

In Java, the concept of immutablity is best expressed as an in-the-small design pattern consisting of:

1. A base interface describing some non-mutative functionality, for example our `Collection`, `Set`, etc., interfaces.
2. Implementation classes that are `final`, and support only the operations described in the interface. The use of `final` means that when you think you have an immutable object, you really do -- it's not of some subclass that supports mutable operations as well.
3. The use of the interface `Immutable` just to give a name to this property, so that, by convention, such classes declare `implements Immutable`. The actual interface `Immutable` is a null interface, listing no operations at all.

The `collections` package currently contains four implementation classes using this scheme. IncrSets IncrBags IncrSeqs IncrMaps are all implementation subclasses of abstract class IncrImpl that uses a `negative delta' algorithm to do lazy copying of collections formed via creational update methods. This algorithm can be applied to any kind of underlying UdatableCollection, so the Incr classes do not actually perform the underlying updates (they rely on UpdatableCollections supplied within constructors), they just arrange to do it with a minumum of actual copying. They normally update in a `lazy' fashion, making copies only when necessary. However, when you are using a received Immutable Collection as the basis for a very extensive set of update operations (none of which should be applied to the original), it is sometimes more efficient to build an UpdatableCollection, add all of the elements of the received ImmutableCollection to it, and then work off that. (Also, the benefits of lazy updates are not always worth their costs for small-sized collections. For those with only a few elements, it is probably better to just make copies.)

There are two standard usage patterns for Immutable Collections:

1. As a much stronger analog of C++ `pass by const reference'; i.e., passing an updatable collection in a way that is guaranteed not to modify it. Each of the Immutable classes supports a constructor that allows you to use an UpdatableCollection in an immutable fashion. For example, suppose you have a HashedSet hs, (an implementation of UpdatableSet), and want to send it safely to some method `SomeClass.someMethod(Set s)`. You can do this via `c.someMethod(new IncrSet(hs))`. Note, however, that constancy guarantees can only hold so long as you don't modify hs during the course of the call, as might happen if someMethod creates a new thread using hs and then returns, so that you then continue on modifying hs. If this is a potenital problem, use the next option.

2. As representations of pure functional values (as used for example in languages like ML). Even though they are immutable, Immutable Collections still support constructive operations that create new collections differing from their arguments only in that they add, remove, or replace a given element. Each of the classes contain a default constructor that initializes them to use an appropriate DefaultImplementations object.

One of the main reasons for supporting all of the operations that make Immutable Collections possible is to provide tools that help keep threads from stomping on each others collections. This can be a serious problem in multithreaded Java programs. Synchronization (which is supported by all implementation classes) helps, but not enough to avoid some common errors. Immutable collections help even more. They let you pass around values that cannot be modified at all in other threads without you having to make full copies of them when you don't need to. This is the same reasoning that led to Java having two classes for Strings: `String` for pure immutable strings, and `StringBuffer` for updatable ones.

## Exceptions

Collection methods are defined to throw only a small number of exception types:

java.util.NoSuchElementException
  Thrown for attempts to access elements that do not exist.
IllegalElementExceptions (a subclass of IllegalArgumentException)
  Thrown for attempts place null or invalid elements.
CorruptedEnumerationExceptions (A subclass of NoSuchElementException)
  Thrown for attempts to access elements in enumerations that have been detectably compromised because the collection serving as the base of the collection has been modified in the course of traversal.
ImplementationErrors (a subclass of Error)
  Thrown for detected failures due to coding errors (i.e., cases in which internal consistency checks or required postconditions fail).
java.lang.IllegalArgumentException
  Thrown for other bad arguments.

Except for operations that accept Enumerations as arguments (for example UpdatableSeq.addElementsAt), exception throws generated from Collection operations are always accompanied by state ``rollbacks''. That is, they leave the object in a behaviorally equivalent state as it was before the operation commenced. (Operations accepting Enumerations may rollback, but do not promise to.)

## Enumerations

Enumerations are the ``common currency'' of collections. Enumerations are generally ``lightweight'' and simple to use, not only within this package, but also across other Java classes that use the `java.util.Enumeration` interface. Because Collection methods use Enumerations as the basic element access construct, classes in this package are generally compatible with other existing Java collection classes. (Although by necessity, there is some duplication. For example, Dynamic array implementations are very similar to java.util.Vector, but different enough that they needed to be redone from scratch.)

All `Collection` classes actually produce `CollectionEnumerations` to report elements. CollectionEnumeration is a subinterface of the standard `java.util.Enumeration` that adds two methods: `corrupted` which reports true if the enumeration is detectably corrupted because of mutative operations occurring during traversals, and `numberOfRemainingElements`, which reports the number of elements yet to be traversed.

While they are handy, Enumerations sometimes require a bit of care. Any `CollectionEnumeration` produced by an `UpdatableCollection` can become `corrupted` if an update operation on the collection is performed during a traversal. The standard implementation of `CollectionEnumeration` classes is very conservative, and reports corruption if there is any change in the elements() set (as reflected by `version` changes). Thus, any attempt to obtain a `nextElement` can fail, raising a CorruptedEnumerationException. (Enumerations produced from `Immutable` collections can only fail in this way if they were constructed around an UpdatableCollection that remains asynchronously accessible via other means even after it has been wrapped within an Immutable Collection. As discussed elsewhere, while it is impossible to enforce, Immutable Collections should never be used in this way to begin with.)

Corruption exceptions occurring during operations such as `Bag.addElements()` are particularly tricky to revover from. Upon exceptions, these operations do not necessarily ``roll back'' to the state they were in before the operation, so recovery is hard to manage. (Although you can at least look at `numberOfRemainingElements` to find out how many elements were not processed.) If you are worried about such problems, set up your own code to manually traverse enumerations and perform the inner operations, but recovering in special ways upon exception.

You sometimes need to adjust standard algorithms to avoid the possibility of CorruptedEnumerationExceptions. For example, if you want to traverse through s.elements() for `Set s` and add other new elements depending on what's there, you CANNOT do it via code like:

      void f(UpdatableSet s) { // DO NOT DO THIS
        Enumeration e = s.elements();
        while (e.hasMoreElements())
          if (someProperty(e.nextElement()))
            s.include(someNewObject()); // will cause exception for nextElement
      }

One alternative is to place new elements in an auxilliary collection during the traversal; for example:

      void f(UpdatableSet s) {
        UpdatableBag aux = new LinkedBuffer();
        Enumeration e = s.elements();
        while (e.hasMoreElements())
          if (someProperty(e.nextElement()))
            aux.add(someNewObject());
        s.includeElements(aux.elements()); // add them all at once
      }

Or, you could instead use an ImmutableSet, returning the ultimate result:

      Set f(Set s) {
        Enumeration e = s.elements();
        while (e.hasMoreElements())
          if (someProperty(e.nextElement()))
            s = s.including(someNewObject());
        return s;
      }

Another alternative is to use a `Seq` instead of Sets or Bags when you need to use such algorithms, and use indexing instead of element() traversals. For example:

      void f(UpdatableSeq s) {
        int originalSize = s.size();
        for (int i = 0; i < originalSize; ++i)
          if (someProperty(s.at(i))
            s.insertLast(someNewObject());
      }

Very few collection operations deal with other collections. Most instead deal with Enumerations. For example, there is no such operation as `UpdatableSet.union(Set s)` to union in the elements of another `Set s`. Instead there is `UpdatableSet.includeElements(Enumeration e)` that can be used to the same effect (via `includeElements(s.elements())`), but can also be used to include any set of Objects traversable from an any kind of Enumeration.

It is probably good practice to design methods and classes that use the `collections` package to also take Enumerations as arguments and return them as results instead of only accepting other collections. This increases the range of application of your classes.

Several specialized Enumeration classes are available to make it easier to deal in Enumerations rather than Collections or other special data structures. They include:

ArrayEnumeration
  A utility class that allows you to traverse arrays as enumerations. For example:

        Object arr[] = { new Float(1.0f), new Float(2.0f) }
        Dynarray s = ...
        s.insertElementsAt(0, new ArrayEnumeration(arr));

FilteringEnumeration
  A class that allows you to ignore elements in an enumeration that don't meet some criterion (expressed as a Predicate). For example, if you want to screen out everything but Panel objects from a collection coll that might hold things other than Panels, write something of the form:

        Enumeration e = coll.elements();
        Enumeration panels = new FilteringEnumeration(e, new IsPanel());
        while (panels.hasMoreElements())
         doSomethingWith((Panel)(panels.nextElement()));

  To use this, you will also need to write a little class of the form:

        class IsPanel implements Predicate {
         boolean predicate(Object v) { return (v instanceof Panel); }
        }

MappingEnumeration
  A class that allows you to transform elements from other enumerations before they are seen by their `consumers' by invoking an arbitrary Function) on each `nextElement` access. For example, if you want to process only the parent() fields of java.awt.Component elements held by a collection coll you could write something of the form:

        Enumeration e = coll.elements();
        Enumeration parents = new MappingEnumeration(e, new ParentFunction());
        while (parents.hasMoreElements())
         doSomethingWith((Container)(parents.nextElement()));

  To use this, you will also need to write a little class of the form:

        class ParentFunction implements Function {
         Object function(Object v) {
           if (v instanceOf Component) return ((Component)v).getParent();
           else return null;
         }
        }

  (You might also interpose a FilteringEnumeration here to screen out the resulting nulls.)

  All this requires too much set-up to be reasonable in most situations, but is invaluable in others.

InterleavingEnumeration
  A class that allows you to combine the elements of two different enumerations as if they were one enumeration before they are seen by their `consumers'. This sometimes allows you to avoid having to use a Collection object to temporarily combine two sets of Collection elements() that need to be collected together for common processing.

  The elements are revealed (via nextElement()) in a purely interleaved fashion, alternating between the first and second enumerations unless one of them has been exhausted, in which case all remaining elements of the other are revealed until it too is exhausted.

  For example, if you want to process together the elements of two Collections a and b, you could write something of the form:

        Enumeration items = new InterleavingEnumeration(a.elements(), b.elements());
        while (items.hasMoreElements())
         doSomethingWith(items.nextElement());

## Checked Collections

A semiformal notation is used to try to nail down interfaces. This is not an exercise in formal methods. (In fact the best way formally specify interfaces and operations in `open' systems like Java is not a completely solved issue.) It is instead an attempt to be as unambiguous as possible about the effects of operations, which is easier to do with a bit of formalism. In fact, the main reason for spelling these out is to form a basis for testing. Nearly all claims made about operations in interfaces are tested for in corresponding Checked classes. So you can be reasonably sure that any claim made has been verified to hold, at least in the cases actually tested.

Checked versions of each of the major Updatable interfaces exist -- CheckedSet CheckedBag CheckedSeq CheckedMap . Each one `wraps' a normal collection object, and for each operation, asks the inner collection to perform it, checks as best it can that the effects match the specification, and then returns any results. When you have any doubt about any implementation, you can wrap it in a Checked version and watch for ImplementationError exceptions. (This is likely to slow down your program by a few orders of magnitude!)

Implementation classes are for the most part just informally documented, but contain links to the fuller descriptions of the methods they implement. However, each implementation class also supports a `checkImplementation` operation, that tests for internal representational consistency. While this is usually required only for testing purposes, it can come in handy in other situations as well. For example, it can help you discover whether someone changed the ordering property of an element in a `SortedCollection` or changed it in a way that no longer passes `canInclude` for most other collections.

Constructs used in the class documentation include:

- `return condition` to describe postconditions and effects true upon return of a method.
- `PREV(obj)` within a return condition to refer to the state of an object at the onset of a method.
- `OUT(message)` to describe messages that are sent to other objects as required aspects of functionality, or referrred to in describing the effects of other methods. And similarly `IN(message)` for messages that are received.
- `foreach (int i in lo .. hi) predicate(i)` to means that predicate holds for each value of i.
- `foreach (SomeClass x) predicate(x)` to means that predicate holds for each instance of SomeClass
- `foreach (Object x in e) predicate(x)` to mean that the predicate holds for each element obtained via nextElement() for Enumeration e.
- `let v = expr in ...` to give a name to an expression.
- `-->` to means `implies'.
- ``Behaviorally equivalent to `{ code segment }`'' to document convenience or specialized methods that can be defined in terms of the effects of more primitive methods.
- ``No spurious effects'', meaning that the changes or results listed are the only behavioral effects on any visible object. In particular, that an operation does not otherwise affect the size() or elements() of the collection(s), and does not invoke any methods (except for `equals` and `hashCode`) on the elements held in the collection.

## Links to Source Code

Note: All of the code in this package carries the following header:

      Originally written by Doug Lea and released into the public domain.
      Thanks for the assistance and support of Sun Microsystems Labs, Agorics
      Inc, Loral, and everyone contributing, testing, and using this code.

This means that you can use it for any purpose whatsoever, with no restrictions.

- ArrayEnumeration.java
- Assertable.java
- Bag.java
- BinaryFunction.java
- CEImpl.java
- CLCell.java
- CLEnumeration.java
- Cell.java
- CheckedBag.java
- CheckedCollection.java
- CheckedMap.java
- CheckedSeq.java
- CheckedSet.java
- CircularList.java
- Collection.java
- CollectionEnumeration.java
- Comparator.java
- CorruptedEnumerationException.java
- DAEnumeration.java
- DefaultComparator.java
- DefaultImplementations.java
- Dynarray.java
- ElementSortedCollection.java
- FilteringEnumeration.java
- Function.java
- HTEnumeration.java
- HTPairEnumeration.java
- HashTableParams.java
- HashedMap.java
- HashedSet.java
- IllegalElementException.java
- Immutable.java
- ImplementationCheckable.java
- ImplementationError.java
- IncrBag.java
- IncrCollectionEnumeration.java
- IncrImpl.java
- IncrMap.java
- IncrSeq.java
- IncrSet.java
- InterleavingEnumeration.java
- KeySortedCollection.java
- Keyed.java
- LBEnumeration.java
- LLCell.java
- LLCellEnumeration.java
- LLMap.java
- LLPair.java
- LLPairEnumeration.java
- LinkedBuffer.java
- LinkedList.java
- Map.java
- MappingEnumeration.java
- Pair.java
- Predicate.java
- Procedure.java
- RBCell.java
- RBCellEnumeration.java
- RBMap.java
- RBPair.java
- RBPairEnumeration.java
- RBTree.java
- Seq.java
- Set.java
- SortableCollection.java
- UpdatableBag.java
- UpdatableBagImpl.java
- UpdatableCollection.java
- UpdatableImpl.java
- UpdatableMap.java
- UpdatableMapImpl.java
- UpdatableSeq.java
- UpdatableSeqImpl.java
- UpdatableSet.java
- UpdatableSetImpl.java

Also, SimpleTest.java contains some very simple tests of most classes.

## To Do List

- Write example applications.
- Put together a decent set of applications to wrap in Checked and to serve as a test suite.
- Add to this list.

## History

- V0.91 Wed 11Oct95. Made public release.
- V0.92 Thu 12Oct95. Fixed some documentation; Disabled questionable optimization in IncrImpl.
- V0.93 Fri 13Oct95. Cleaned up Checked classes. Re-implemented copy-avoidance scheme for enumerations in Incr classes. Refactored to avoid PureCollection; allowing concept of Immutability to be applied to other classes as well. Made ImplementationCheckable extend Assertable. Fixed some protection problems. Made some interface/class diagrams.
- V0.94 Sun 22Oct95. Added more support and utilities for enumerations. Fixed version-checking in Checked classes. Fixed removeAt error. Expanded documentation.
- V0.95 Thu 14Dec95. Adjusted to new java `clone` conventions: Declared base classes to be Cloneable; added public callable `duplicate` method.
- V0.95b Wed 10Jan96. Fixed error in Dynarray constructor.
- V0.95c Tue 16Apr96. Fixed error in IncrMap.removingAt
- V0.96 Wed 9Apr97. Added Serialization support. Added bounds check in LinkedList.firstIndexOf. Made helper `Impl' classes public to enable extension. Added sample SimpleTest.java.
- V0.96b Thu 17Apr. Fixed RBMap.comparator, RBTree.comparator

Last modified: Thu Apr 17 07:13:19 EDT 1997