Tuesday, March 31, 2009

Examples of Lazy Lists and Factories

In this post, I'm going to examine Lazy Lists and the Apache Factory.

In accordance with most of the Apache Commons Collection utilities, a LazyList is simply a decorator (and at this point that shouldn't be a surprise). It decorates another List creating a sort-of "list on demand" list. Calling the method get(int index) when the index is greater than the size of the list will grow the list with objects from the given factory. Using the get(int index) method to get an object that the factory did not fill in will result in an IndexOutOfBoundsException.

For all of the examples, lets use the following simple factory.
The Code:

package com.blogspot.apachecommonstipsandtricks.lazymapexamples;
import java.util.*;
import org.apache.commons.collections.*;
public class LazyListFactory implements Factory
{
private static int i = 0;
private List<String> strings = new ArrayList();
public LazyListFactory(List<String> strings)
{
this.strings.addAll(strings);
}
public Object create()
{
return this.strings.get(i++);
}
}

In this example Java code we have implemented the Factory interface, which defines a Object create(), but more importantly the constructor takes as an argument a List of Strings. These strings are effectively the "feed" that the create method will use. A more practical solution would be some form of a data source, but that would result in a lot of code, and this is simple. So with this factory, let us create some lazy data!

Our first java example of a lazy list.
The Code:

package com.blogspot.apachecommonstipsandtricks.lazymapexamples;
import java.util.*;
import org.apache.commons.collections.list.*;
public class ListManager
{
public static void main(String[] args)
{
// First lets create a simple list "A" through "C"
List<String> backingList = new ArrayList<String>( Arrays.asList("A","B","C") );
// Now we create a Decorated List with homegrown class called LazyListFactory which implements Factory
List<String> list = LazyList.decorate( GrowthList.decorate( backingList ), new LazyListFactory( Arrays.asList("D","E","F","G") ) );
System.out.println("The size method on list thinks there are " + list.size() + " elements in the array list. but Im going to get 7!");
// as the more and more elements are requested, the factory creates more..
for (int i = 0; i < 7; i++)
{
Object o = list.get(i);
System.out.println( " Element [" + i + "] = " + o );
}
}
}


Results in

The size method on list thinks there are 3 elements in the array list. but Im going to get 7!
Element [0] = A
Element [1] = B
Element [2] = C
Element [3] = D
Element [4] = E
Element [5] = F
Element [6] = G


In this example, we first created a list, with Strings "A","B", and "C" than we decorated it, and attached a factory constructed with four more additional strings "D" through "G". I knew there was seven items in the list, so I forced it to loop to seven. Did you notice, the list thought the size was only 3. You might be thinking, which I am too, that’s not very helpful. How can I tell how much to loop through? Let’s look at this same example, but with some minor modifications.

The Code:

package com.blogspot.apachecommonstipsandtricks.lazymapexamples;
import java.util.*;
import org.apache.commons.collections.list.*;
public class ListManager
{
public static void main(String[] args)
{
// First lets create a simple list "A" through "C"
List<String> backingList = new ArrayList<String>( Arrays.asList("A","B","C") );
// Now we create a Decorated List with homegrown class called LazyListFactory which implements Factory
List<String> list = LazyList.decorate( GrowthList.decorate( backingList ), new LazyListFactory( Arrays.asList("D","E","F","G") ) );

// Now puit "Z" in position 15
list.set( 15, "Z" );

System.out.println("After putting \"Z\" in position 15, the size is equal to " + list.size());

System.out.println("Which allows us to us a standard for-loop with a IndexOutOfBoundsException try-catch block.");
for (int i = 0; i < list.size(); i++)
{
try
{
Object o = list.get(i);
System.out.println( " Element [" + i + "] = " + o );
} catch (IndexOutOfBoundsException e) {}
}

}
}


You might have immediately noticed I put another String, "Z" at position 15, and now, the size is 15. I find it likely that this might be a solution to the "unknown size problem". The problem statement might go something like this, create a LazyList and set the last element to a known end state. Therefore, the user could pick what they wanted to consume out of the list while knowing the end is near at 15.

The results of the program above would look like this.

After putting "Z" in position 15, the size is equal to 16
Which allows us to us a standard for-loop with a IndexOutOfBoundsException try-catch block.
Element [0] = A
Element [1] = B
Element [2] = C
Element [3] = D
Element [4] = E
Element [5] = F
Element [6] = G
Element [15] = Z

If you are hung up on swallowing the IndexOutOfBoundsException exception or simply don’t like the idea of having to put in the last element this next solution may suite you. It uses the Java 1.5 for-loop.

The Code:

package com.blogspot.apachecommonstipsandtricks.lazymapexamples;
import java.util.*;
import org.apache.commons.collections.list.*;
public class ListManager
{
public static void main(String[] args)
{
// First lets create a simple list "A" through "C"
List<String> backingList = new ArrayList<String>( Arrays.asList("A","B","C") );
// Now we create a Decorated List with homegrown class called LazyListFactory which implements Factory
List<String> list = LazyList.decorate( GrowthList.decorate( backingList ), new LazyListFactory( Arrays.asList("D","E","F","G") ) );

// Now puit "Z" in position 15
list.set( 15, "Z" );

System.out.println("With a Java 1.5 for-loop the results look like this." );
int i = 0;
for (String s : list)
{
System.out.println( " Element [" + i++ + "] = " + s );
}
}
}


Like every solution, there is a draw back to this method, when an element does not exist, the result is null. In this example, I print every element, including the nulls. Let's examine the output.

With a Java 1.5 for-loop the results look like this.
Element [0] = A
Element [1] = B
Element [2] = C
Element [3] = null
Element [4] = null
Element [5] = null
Element [6] = null
Element [7] = null
Element [8] = null
Element [9] = null
Element [10] = null
Element [11] = null
Element [12] = null
Element [13] = null
Element [14] = null
Element [15] = Z


Each solution I have covered has some form of a draw back. I hope you can find one suitable for you. I will be examining the LazyMap in my next installment; it is well suited for hierarchical data.


Thanks for reading this article, I look forward to any questions or feedback. Please drop me a line if you want me to cover something in particular or would like to point something useful out.
Author: Philip A Senger

2 comments:

  1. The assignment from LazyList.decorate to List<String> is not typesafe. The compiler balks at it because of the unchecked casts.

    ReplyDelete
  2. That is correct, this is not type safe. The entire library pre-dates Java 1.5 and does not support generics. Refer to http://larvalabs.com/collections/download.html for a generics version of the library. Regarding your comment “The compiler balks…..", I think you are trying to say it produces warnings, as it should. Regardless of the warnings, it does compile in Java 1.6, and runs.

    ReplyDelete