sos.dated.util (Side of Software - Dated Collections Library)

Package

Class

Use

Tree

Deprecated

Index

Help

Side of Software
Dated Collections Library 2.0

PREV PACKAGE NEXT PACKAGE

FRAMES NO FRAMES

Package sos.dated.util

Provides collection classes and interfaces that are based on dates.

See:
Description

Interface Summary
DatedCollection<E,D>	A collection of elements over time.
DatedCollections.Action<D>	Action to perform on a dated object at a period when it does not change.
DatedList<E,D>	A list of elements over time.
DatedMap<K,V,D>	A mapping of elements over time.
DatedMap.Entry<K,V,D>	An entry in a dated map.
DatedObject<D>	An object that maintains its state explicitly over time.
DatedSet<E,D>	A set of elements over time.
DatedSortedMap<K,V,D>	A dated map whose keys are ordered.
DatedSortedSet<E,D>	A dated set whose elements are ordered.
DatedValue<E,D>	A value over time.
DateIterator<D>	An iterator of ordered, non-overlapping date ranges.
Dates<D>	An ordered list of non-overlapping date ranges.
Iterator<E,D>	A mechanism to step through and (possibly) alter a dated collection at a given date.
ListIterator<E,D>	A forward and reverse mechanism to step through and (possibly) alter a dated list.

Class Summary
AbstractDatedCollection<E,D>	A partial implementation of a dated collection.
AbstractDatedList<E,D>	A partial implementation of a dated list.
AbstractDatedMap<K,V,D>	A partial implementation of a dated map.
AbstractDatedObject<D>	A partial implementation of a dated object.
AbstractDatedSet<E,D>	A partial implementation of a dated set.
AbstractDatedValue<E,D>	A partial implementation of a dated value.
AbstractDates<D>	A partial implementation of a series of date ranges.
AbstractMapByDate<K,V,D>	A partial implementation of `DatedMap` that maintains a complete, non-dated map at each date where a change occurs.
AbstractSequentialDatedList<E,D>	A partial implementation of a dated list that does not provide random access to its elements at a given date.
Adapters	A bridge between dated and non-dated collections.
ArrayListByDate<E,D>	An implementation of `DatedList` that can efficiently iterate through the list of elements at a given date by maintaining a `java.util.ArrayList` at each date.
ArrayListByElement<E,D>	An implementation of `DatedList` that uses a single `java.util.ArrayList` to efficiently add and set values.
DatedCollections	Views and algorithms that act on dated collections.
HashMapByDate<K,V,D>	An implementation of `DatedMap` that maintains a `java.util.HashMap` at each date where a change occurs, yielding fast date iterations and fast retrievals.
HashMapByKey<K,V,D>	An implementation of `DatedMap` that indexes its keys with a `java.util.HashMap`, yielding fast insertions and removals.
HashSetByDate<E,D>	An implementation of `DatedSet` that uses a `HashMapByDate` as its underlying data structure.
HashSetByElement<E,D>	An implementation of `DatedSet` that uses a `HashMapByKey` as its underlying data structure.
IdentityHashMapByDate<K,V,D>	A special-purpose, non-conforming implementation of `DatedMap` that uses identity equality and identity hash code by maintaining a `java.util.IdentityHashMap` at each date.
IdentityHashMapByKey<K,V,D>	A special-purpose, non-conforming implementation of `DatedMap` that uses identity equality and identity hash code.
LinkedHashMapByDate<K,V,D>	An implementation of `DatedMap` that maintains a `java.util.LinkedHashMap` at each date where a change occurs, yielding fast date iterations, fast retrievals, and predictable entry iterations.
LinkedHashSetByDate<E,D>	An implementation of `DatedSet` that uses a `LinkedHashMapByDate` as its underlying data structure.
TreeDates<D>	An implementation of `Dates` that uses a Red-Black tree to achieve logarithmic insertions and deletions.
TreeMapByDate<K,V,D>	An implementation of `DatedSortedMap` that maintains a `java.util.TreeMap` at each date where a change occurs, yielding fast date iterations and logarithmic retrievals.
TreeMapByKey<K,V,D>	An implementation of `DatedSortedMap` that uses an underlying `TreeMap` to keep all keys in sorted order and to achieve fast access to all keys.
TreeSetByDate<E,D>	An implementation of `DatedSet` that uses a `TreeMapByDate` as its underlying data structure.
TreeSetByElement<E,D>	An implementation of `DatedSet` that uses a `TreeMapByKey` as its underlying data structure to keep its elements in sorted order and to provide fast indexing to elements.
ValueByDate<E,D>	An implementation of `DatedValue` that can efficiently produce the value at a given date.

Exception Summary
DateOutOfRangeException	Indication that a date unexpectedly falls outside a range.

Package sos.dated.util Description

Provides collection classes and interfaces that are based on dates. The intent of this package is to add dates to the interface of the collection classes in java.util.

Dates allow the programmer to maintain the history (or future) of a value. In real life, most values are dependent on time. Consider the price of a share of stock. At 10:00 am the price may be $4.00, but at 2:00 pm it may be $4.50. Simply having the assignment price = 4.5 loses the fact that it was 4.0 at 10 am. This package introduces DatedValue, which maintains a value over time.

The Collections Library of java.util does not deal with dates. Suppose a company has a set of customers. The members of this set change over time. Simply using a java.util.Set object to maintain the customer base ignores when people are customers, making it impossible without additional information to know the customers of, say, last year. For example, consider a program that initially executes

  Set<Person> customers = new TreeSet<Person>();
  ...

On April 17, 2002, the program executes:

  customers.add( personF );     // person F is now a customer
  customers.remove( personB );  // person B is no longer a customer

On October 7, 2002, it executes:

  customers.add( personC );     // person C is now a customer

Generating a report that lists the customers on September 30, 2002, is not possible unless the program has maintained the changes in its own data structures. The Set customers contains person C, who was not a customer on September 30 and hence should not be included in the report. Similarly, a report for February 3, 2002, should include person B but not person C.

With the Dated Collections package, it is easy to maintain the history of values and collections because the dates are maintained in the data structures. This example becomes:

  DatedSet<Person,Date> customers = new TreeSetByElement<Person,Date>();
  Date endOfTime = new Date( Long.MAX_VALUE );
  ...

On April 17, 2002, the program executes:

  Date now = new Date();
  customers.add( personF, now, endOfTime );    // person F is a customer starting now to the end of time
  customers.remove( personB, now, endOfTime ); // person B is not a customer starting now to the end of time

On October 7, 2002, it executes:

  Date now = new Date();
  customers.add( personC, now, endOfTime );  // person C is a customer starting now to the end of time

The interface to the dated collections in this package requires dates that indicate when the operation should be applied. Thus, adding and removing a customer requires a start date and an end date. Determining who is a customer on September 30 is as simple as passing the date to the query operation:

  Date sept30 = ...
  Iterator<Person,Date> iter = customers.iterator( sept30 );

Building dates into the core data structures not only relieves the client from having to maintain a history of values but also allows the data structures to use efficient storage and implementation.

Similarities Between This Package and java.util

This package is intentionally designed to mirror java.util. Programmers who are familiar with the Collections Library can easily learn and use this Dated Collections Library. They do not have to learn an entirely new API. Some of the similarities are outlined here.

Class names are similar
The interface hierarchy is identical
Method names are identical
Method behavior, including returned values and thrown exceptions, are nearly identical
Iterators are fail-fast to assist in identifying programming errors
The same types of algorithms and wrappers are available
The use of skeleton implementations is identical

The following table shows the similarities between class names.

Collections (java.util)	Dated Collections (sos.dated.util)
AbstractCollection	AbstractDatedCollection
AbstractList	AbstractDatedList
AbstractMap	AbstractDatedMap
AbstractSequentialList	AbstractSequentialDatedList
AbstractSet	AbstractDatedSet
Collection	DatedCollection
Collections	DatedCollections
List	DatedList
Map	DatedMap
Set	DatedSet
SortedMap	DatedSortedMap
SortedSet	DatedSortedSet

Differences Between This Package and java.util

Because of the addition of time, there are some fundamental differences between Collections and Dated Collections:

All query methods take an extra date parameter. For example,
```
  Object get( int index )
```
in java.util.List<E> becomes
```
  Object get( int index, D date )
```
in DatedList<E,D>.

All update methods take two extra date parameters. For example,
```
  void add( int index, E e )
```
in java.util.List<E> becomes
```
  void add( int index, E e, D from, D to )
```
in DatedList<E,D>.

Return values have been extended to cover dates where appropriate. For example,
```
  V put( K key, V value )
```
in java.util.Map<K,V> becomes
```
  DatedValue<V,D> put( K key, V value, D from, D to )
```
in DatedMap<K,V,D>.

Iterators are fail-fast only if assertions are enabled.

There are no dated equivalents to LinkedList.

Implementation Choices

This package provides two implementation choices for most data structures.

Indexed by Date. With this implementation the entire collection is maintained at each date that a change occurs. A class that uses this implementation has a name that ends with “ByDate.”

Advantage: Easy to determine when a collection changes because a distinct non-dated collection is maintained at each date

Disadvantage: Potentially uses a lot of space

When to use: If nearly the entire collection changes at the same time or if the size is small and knowing the dates needs to be fast.

Indexed by Content. With this implementation the content is mapped to dates, indicating when it appears in the collection. A class that follows this implementation has a name that ends with “ByElement” if it is a set or list or “ByKey” if it is a map.

Advantage: Potentially much lower space usage than above.

Disadvantage: Usually difficult to determine change dates.

When to use: If the collection is large and changes frequently.

The following table shows the implementation choices and how they match up with the Collections implementation choices.

Collections (java.util)	Dated Collections (sos.dated.util)
Collections (java.util)	By Date	By Content
ArrayList	ArrayListByDate	ArrayListByElement
HashMap	HashMapByDate	HashMapByKey
HashSet	HashSetByDate	HashSetByElement
IdentityHashMap	IdentityHashMapByDate	IdentityHashMapByKey
LinkedHashMap	LinkedHashMapByDate	None
LinkedHashSet	LinkedHashSetByDate	None
LinkedList	None	None
TreeMap	TreeMapByDate	TreeMapByKey
TreeSet	TreeSetByDate	TreeSetByElement