|
|||||||||
| PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
| SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD | ||||||||
ObjectSimpleList<T>
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:
ArrayListSimpleList: a typical list is stored as an array list.
ListOfLists: a list that only stores pointers to its constituent
sub-lists.
OneMoreElementList: stores a SimpleList plus one additional final
element.
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 and Description |
|---|
SimpleList()
|
| 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 |
|---|
public SimpleList()
| Method Detail |
|---|
public abstract int size()
public abstract T get(int index)
public final boolean isEmpty()
public abstract List<T> toJDKList()
|
|||||||||
| PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
| SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD | ||||||||