randoop.util
Class SimpleList<T>

Object
  extended by SimpleList<T>
Direct Known Subclasses:
ArrayListSimpleList, ListOfLists, OneMoreElementList

public abstract class SimpleList<T>
extends Object

List implementation used by Randoop to store the sequence of Statements making up a Sequence.

IMPLEMENTATION NOTE

Randoop's main generator (ForwardGenerator creates new sequences by concatenation existing sequences and appending a statement at the end. A naive implementation of concatenation copies the elements of the concatenated sub-sequences into a new list. The first implementation of Sequence concatenation took this approach.

When profiling Randoop, we observed that naive concatenation took up a large portion of the tool's running time, and the component set (i.e. the set of stored sequences used to create more sequences) quickly exhausted the memory available.

To improve memory and time efficiency, we now do concatenation differently. We store the list of statements in a Sequence in a SimpleList, an abstract class that has three subclasses:

When concantenating N Sequences to create a new sequence, we store the concatenated sequence statements in a ListofLists, which takes space (and creation time) proportional to N, not to the length of the new sequence.

When extending a Sequence with a new statement, we store the old sequence's statements plus the new statement in a OneMoreElementList, which takes up only 2 references in memory (and constant creation time).


Constructor Summary
Constructor and Description
SimpleList()
           
 
Method Summary
Modifier and Type Method and Description
abstract  T get(int index)
           
 boolean isEmpty()
           
abstract  int size()
           
abstract  List<T> toJDKList()
          Returns a java.util.List version of this list.
 
Methods inherited from class Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

SimpleList

public SimpleList()
Method Detail

size

public abstract int size()

get

public abstract T get(int index)

isEmpty

public final boolean isEmpty()

toJDKList

public abstract List<T> toJDKList()
Returns a java.util.List version of this list.