Side of Software

 Dated Collections Tutorial

Table of Contents

Introduction

Dates

Date Ranges

Date Range Arithmetic

Dated Objects

Dated Values

Dated Collections

Algorithms

Adapters

Example

Introduction

The Dated Collections Library offers data structures that depend on time. The library is purposely modeled after the widely used Collections Library in the package java.util. As a result, in this library you’ll find familiar-looking sets, maps, lists, algorithms, and more. This library is not meant to replace the Collections Library but to accompany it where dates and time are needed in the application.

Compare these questions:

1. How many members are there?
2. How many members are there at 1:30 pm on February 1, 2001?

Question A implies a time—the present time. If the question is asked at 1:30 pm on February 1, 2001, it is equivalent to Question B, which explicitly specifies the date and time. Question A corresponds to an invocation in the Collections Library, while question B corresponds to the Dated Collections Library. Since time is not built into the Collections Library, you can only ask questions for the present; you cannot query the past or future without additional information. On the other hand, all of the dated data structures in the Dated Collections Library require the explicit use of time, making it easy to look up past or future values.

To update a dated data structure, the programmer must specify a date range for which the update applies. To query the data structure, the programmer must specify either a date or a date range, depending on the type of the query.

Dates

The initial version of the library required all dates to be implemented as instances of java.util.Date. Since version 2.0, however, dates are merely an abstraction and can be implemented using an arbitrary "date" class. Examples include java.util.Date, Joda Time, java.lang.Integer, java.lang.String, or your own class. The only requirement is that instances of the "date" class be comparable by implementing java.lang.Comparable. Throughout the API and this tutorial we use the letter D to represent the generic "date" class. In some concrete examples, we use the specific java.util.Date class.

Date Ranges

A date range, or time interval, is not a class of its own but rather the coupling of a beginning date and an ending date. A date range should be interpreted as being closed at the beginning and open at the end. For example, the date range [t0,t1) signifies the time interval starting at t0 and continuing up to (but not including) t1. Also, the ending date must always be greater than the beginning date.

Date Range Arithmetic

The library’s Dates interface allows programmers to perform date range arithmetic. After briefly reviewing date range arithmetic, we will show how the interface Dates accomplishes it. In all of the examples in this tutorial, t represents a value in time, ti < tj if and only if i < j, and r represents a range.

Consider the case of addition. If r1 = [t0,t4) and r2 = [t2,t6), then r1 + r2 = [t0,t6). The result contains all dates in either r1 or r2. Pictorially, we can illustrate this as

  r1:     [       )

  r2:  +      [         )

  ------------------------

          [             )

If r1 = [t0,t4) and r2 = [t5,t6), then r1 + r2 = [t0,t4),[t5,t6):

  r1:     [       )

  r2:  +             [  )

  ------------------------

          [       )  [  )

The sum does not include range [t4,t5) because neither r1 nor r2 includes this range. A pictorial example of adding several date ranges is:

       [    ) [ )   [    )   [  )

    +       [         )     [ ) [   )

  -----------------------------------

       [                 )  [       )

A Dates object encapsulates a group of non-overlapping date ranges, or one line in the above diagrams. To add a range to a Dates object, you invoke the method

  Dates<D> addRange( D from, D to )

To add ranges in bulk, use

  Dates<D> addAll( Dates<D> dates )

The receiver object holds the result of the addition, and at any time, you can iterate through the ranges with the dateIterator method. The returned value indicates what changes are made due to the addition.

Consider the case of subtraction. If r1 = [t0,t4) and r2 = [t2,t3), then r1 – r2 = [t0,t2),[t3,t4). The result contains all dates in r1 but not in r2. Pictorially, we have

  r1:     [       )

  r2:  -     [  )

  ------------------------

          [  )  [ )

Additionally, r2 – r1 is an empty range:

  r2:        [  )

  r1:  -  [       )

  ------------------------

A pictorial example of subtracting multiple ranges is:

       [    ) [ )   [    )   [  )

    -       [         )     [ ) [   )

  -----------------------------------

       [    )         [  )    [ )

You can use the following methods to achieve subtraction:

  Dates<D> removeRange( D from, D to )

  Dates<D> removeAll( Dates<D> dates )

  Dates<D> retainAll( Dates<D> dates )

Last, use the complement method to invert date ranges:

    ~       [     )     [   )

  -----------------------------------

      [     )     [     )   [       )

The library provides one implementation of Dates: TreeDates. This implementation uses a balanced tree to efficiently maintain date ranges; all operations are logarithmic in complexity.

Dated Objects

At the top of the library’s interface hierarchy, you’ll find DatedObject. This interface depicts any object whose state depends on time. It extends java.lang.Object by adding the following date-specific methods:

  String toString( D date )

  int hashCode( D date )

  bool equals( D date, DatedObject<D> datedObj, D objDate )

  DateIterator<D> dateIterator()

By invoking the dateIterator method, you can iterate over the dates for which the object’s state changes, as in:

  DateIterator<D> dateIter = datedObj.dateIterator();

  while( dateIter.hasNext() ) {

    D from = dateIter.nextFrom();

    D to = dateIter.nextTo();

    dateIter.next();

    // use variables “from” and “to”

  }

Dated Values

The library’s DatedValue interface provides a way to capture simple values over time. Think of a DatedValue as a reference field requiring explicit dates. To assign a value, invoke set, passing the new value and the date range, as in:

  datedValue.set( Integer.valueOf( 6 ), t1, t3 );

After this call, DatedValue has the value 6 from t1 to t3. Note that, like reference fields, primitive values must first be wrapped in the appropriate class. To acquire the value, you must invoke get and specify a date:

  Integer length = datedValue.get( t2 );

A dated value will return null if the value is not defined at the specified time. The library provides one implementation of DatedValue: ValueByDate. This implementation uses a balanced tree to map date ranges to values.

Dated Collections

Perhaps most importantly, the library provides collections that are based on dates. Namely, it provides lists, sets, sorted sets, maps, and sorted maps.

Suppose a company has a set of customers who come and go over time. To generate accurate reports from the past, you should use a dated set to maintain the history of customers. First, you create the dated data structure:

  DatedSet<Person,Date> customers = new TreeSetByElement<Person,Date>();

Then on April 17, 2002, suppose your program executes:

  Date now = new Date();

  Date endofTime = new Date( Long.MAX_VALUE );

  // person F is a customer starting now to the end of time

  customers.add( personF, now, endOfTime );

  // person B is not a customer starting now to the end of time

  customers.remove( personB, now, endOfTime );

On October 7, 2002, suppose it executes:

  Date now = new Date();

  // person C is a customer starting now to the end of time

  customers.add( personC, now, endOfTime );

If on a later date you wish to know who your customers were on September 30, 2002, iterate through the elements on the desired date:

  Date sept30 = ...

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

  while( iter.hasNext() ) {

    ...

  }

The history of elements is stored in the dated set. You do not have to write your own data structures to track the changes, and thus you avoid the tedious and error-prone task of designing and implementing efficient storage containers. Simply pick an implementation that is appropriate for you use.

The library provides at least two implementations for each type of dated collection.

1.      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 date retrieval needs to be fast.

2.      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 Collection Library’s implementation choices.

The best choice of implementation depends on the properties of your dated collection. If none of these implementations satisfy your requirements, you can write your own implementation. If you take this route, extending the appropriate AbstractDatedCollection class will simplify your task.

After perusing the library’s API, you’ll notice that the names and interfaces of dated collections closely resemble their non-dated cousins. The main differences are:

• Interface names include the word Dated
• Query methods require a date
• Update methods require a date range
• Instead of returning boolean, update methods return a Dates object, signaling when the changes occurred
• Bulk operations take a dated collection rather than a non-dated collection
• Some new query methods (indicated by the word Throughout) operate over a date range
• The iterator method returns an sos.dated.util.Iterator object, not a java.util.Iterator object

Algorithms

Basic algorithms, such as binary search and sort, accompany the dated collections. The algorithms are static methods of the DatedCollections class. Algorithms that query a dated collection take a date parameter:

  static int binarySearch( DatedList datedList, Object key, D date )

  static int indexOfSubList( DatedList datedList, List target, D date )

  static int lastIndexOfSubList( DatedList datedList, List target, D date )

  static Object max( DatedCollection datedCollection, D date )

  static Object min( DatedCollection datedCollection, D date )

The date signals when to perform the query on the dated collection. For example, to find the minimum value in a dated set, pass the date in question to the min method:

  Object minValue = DatedCollections.min( datedSet, date );

Algorithms that update a dated collection require a date range. These methods include

  static void copy( DatedList datedList, List source, D from, D to )

  static void fill( DatedList datedList, Object obj, D from, D to )

  static Dates replaceAll( DatedList datedList, Object oldVal, Object newVal, 

    D from, D to )

  static void reverse( DatedList datedList, D from, D to )

  static void rotate( DatedList datedList, int distance, D from, D to )

  static void shuffle( DatedList datedList, D from, D to )

  static void sort( DatedList datedList, D from, D to )

  static void swap( DatedList datedList, int i, int j, D from, D to )

If none of these static update methods achieve your goal, you can manually update your dated collection with the help of the method

  static void applyAtDates( DatedCollection datedCollection, D from, 

    D to, DatedCollection.Action action )

Here, action is an object that operates on the dated collection at periods when the collection does not change. As an example, suppose you wish to exchange the first and last elements of a dated list between t0 and t8. Since the number of elements in the dated list may change, you cannot use the provided swap method. However, you can create an anonymous action that performs the appropriate swap during static date ranges, as follows:

  DatedCollections.applyAtDates( datedList, t0, t8, 

                                 new DatedCollection.Action() {

    public void perform( DatedObject datedObject, Date from, Date to ) {

      DatedList sameDatedList = (DatedList)datedObject;

      int size = sameDatedList.size( from );

      if( size < 2 ) return;

      Object first = sameDatedList.get( 0, from );

      Object last = sameDatedList.get( size - 1, from );

      sameDatedList.set( 0, last, from, to );

      sameDatedList.set( size - 1, first, from, to );

    }

  } );

Similarly, you can pass an action to queryAtDates to perform a query throughout constant date ranges.

Adapters

Oftentimes you’ll want to treat a dated collection as non-dated or a non-dated collection as dated. Perhaps an existing interface requires one form or the other; it usually does not make sense to rewrite the functionality for the other type of collection. The static methods in Adapters allow you to map between the dated and non-dated worlds.

By specifying an anchor date, you can disguise a dated collection as a read-only non-dated collection at the anchor date. The returned non-dated collection is a wrapper that forwards all queries to the underlying dated collection, passing in the anchor date. Updates throw an UnsupportedOperationException. The names of these methods have the form asXXX, where XXX is the type of collection:

  static Collection asCollection( DatedCollection datedCollection, D date )

  static List asList( DatedList datedList, D date )

  static Map asMap( DatedMap datedMap, D date )

  static Set asSet( DatedSet datedSet, D date )

  static SortedMap asSortedMap( DatedSortedMap datedSortedMap, D date )

  static SortedSet asSortedSet( DatedSortedSet datedSortedSet, D date )

If the dated collection is constant within a date range, then you can treat it as a modifiable non-dated collection. These methods take two date parameters, and an update on the returned non-dated collection gets applied throughout the specified dates.

Furthermore, you can disguise a non-dated collection as a read-only dated collection by providing a date range. These methods have the name asDatedXXX, where XXX is the type of the collection:

  static DatedCollection asDatedCollection( Collection collection, 

    D from, D to )

  static DatedList asDatedList( List list, D from, D to )

  static DatedMap asDatedMap( Map map, D from, D to )

  static DatedSet asDatedSet( Set set, D from, D to )

  static DatedSortedMap asDatedSortedMap( SortedMap sortedMap, 

    D from, D to )

  static DatedSortedSet asDatedSortedSet( SortedSet sortedSet, 

    D from, D to )

For example, to treat a map as a never-changing dated map valid for all of time, you could say:

  DatedMap datedMap = Adapters.asDatedMap( map, new Date( Long.MIN_VALUE ), 

    new Date( Long.MAX_VALUE ));

Example

The simplified example StockExample demonstrates the use of several dated objects and techniques. (It has been simplified to fit into a single class. The real-world version would utilize a number of interfaces and classes to encapsulate its domain objects.)

We represent the stock market as a mapping from company names to stock values. Since the companies belonging to the stock market change dynamically, it would make sense to use a dated map to represent the stock market. For simplicity, however, we treat the market as constant and use a non-dated map:

    stockMarket = new HashMap<String,DatedValue<Double,Date>>();

Since a company’s stock value changes over time, we use a DatedValue to maintain a history of values. It is important to maintain the history because users typically want to know how a company is performing relative to the past. Without a history, it would be impossible to, say, graph the company’s progress. The following lines instantiate this data structure, add it to the market, and set the stock prices randomly:

    // stock prices vary over time, so use a dated value

    DatedValue<Double,Date> values = new ValueByDate<Double,Date>();

    // add the stock to the stock market

    stockMarket.put( stock, values );

    // set the stock prices

    double value = initialValue;

    for( int i = 0; i < d.length - 1; i++ )

    {

      values.set( Double.valueOf( value ), d[i], d[i+1] );

      double change = r.nextDouble();

      value += change < 0.6? -change : change;

      if( value < 0.0 )

        value = 0.0;

    }

Since a person’s portfolio is quite dynamic, we use a dated map to associate company names with the number of shares owned. We choose a sorted dated map so that the companies are automatically listed in alphabetical order:

    DatedMap<String,Integer,Date> portfolio = new TreeMapByKey<String,Integer,Date>();

When we buy or sell shares, we update the portfolio with a call to buyStock:

  /**

   * Increments the number of stock shares in the specified portfolio.

   */

  private void buyStock( DatedMap<String,Integer,Date> portfolio, String stock, 

    int numShares, Date date )

  {

    // get the current number of shares owned

    Integer currentShares = portfolio.get( stock, date );

    // if none owned, add an entry to the dated map

    if( currentShares == null )

    {

      portfolio.put( stock, Integer.valueOf( numShares ), date, 

        END_OF_TIME );

      return;

    }

    // add to the current number of shares

    int totalShares = currentShares.intValue() + numShares;

    // update the dated map

    portfolio.put( stock, Integer.valueOf( totalShares ), date, 

      END_OF_TIME );

  }

Periodically, this example calculates the value of the portfolio at certain dates. The value depends on the number of shares owned and on the value of the stock at some date. The method getPortfolioValue, which can be called at any date, does the calculation:

  /**

   * Calculates and returns the value of the specified portfolio at the

   * specified date.

   */

  private double getPortfolioValue( DatedMap<String,Integer,Date> portfolio, Date date )

  {

    double total = 0.0;

    // for each entry in the dated map

    DatedSet<DatedMap.Entry<String,Integer,Date>,Date> entrySet = portfolio.entrySet();

    Iterator<DatedMap.Entry<String,Integer,Date>,Date> iter = entrySet.iterator( date );

    while( iter.hasNext() )

    {

      DatedMap.Entry<String,Integer,Date> entry = iter.next();

      // what stock is it?

      String stock = entry.getKey();

      // for how many shares?

      Integer shares = entry.getValue();

      // look up the value

      double price = lookupStockPrice( stock, date );

      double value = price * shares.intValue();

      // keep a running total

      total += value;

    }

    return total;

  }

The method lookupStockPrice, referenced in the code above, retrieves the dated value for the company name and returns the value at the specified date:

  /**

   * Returns the value of the specified stock at the specified date.

   */

  private double lookupStockPrice( String stock, Date date )

  {

    DatedValue<Double,Date> values = stockMarket.get( stock );

    if( values == null )

      throw new NoSuchElementException();

    Double value = values.get( date );

    assert value != null;

    return value.doubleValue();

  }

This example, although simplified, demonstrates a use of dated maps and dated values. It also demonstrates that you can maintain histories of values without much additional effort. Simply construct and pass the appropriate dates to your underlying data structures.

Home  |  Contact Us  |  Privacy Policy

Copyright © 2016 Side of Software, a branch of Natavision. All rights reserved.