org.latdraw.util
Class SimpleList

java.lang.Object
  org.latdraw.util.SimpleList

All Implemented Interfaces:

java.io.Serializable, java.lang.Iterable, java.util.Collection, java.util.List

public class SimpleList
extends java.lang.Object
implements java.util.List, java.io.Serializable

Simple Linked lists. Java's collection framework has LinkedList's but I need to guarentee that there is a great deal of sharing to save space (memory). For example, the space required to hold all subsets of an n element set requires space proportional to (n/2) 2ⁿ using vectors, but only 2ⁿ with linked lists.

This version just has an element and a pointer to the rest, which is another LinkedList. This means push and pop not are supported but rest does not have to make a new object.

The rest of the empty list is itself.

This class implements java.util.List.

Efficiency. size() takes time proportional to the size and get(int i) takes time proportional to i. Moral: do not use for loops to iterator over the elements; use the iterator. The former uses time proportional to n² while the latter uses only n.

See Also:

Serialized Form

Field Summary

static org.latdraw.util.SimpleList.EmptyList	EMPTY_LIST The empty list is a class constant
protected java.lang.Object	first
protected SimpleList	rest

Constructor Summary

SimpleList(java.util.Collection c)

SimpleList(java.lang.Object obj, SimpleList list)
Constructs a list with obj followed by list.

Method Summary

void	add(int index, java.lang.Object elt) This just throws an UnsupportedOperationException.
boolean	add(java.lang.Object elt) This just throws an UnsupportedOperationException.
boolean	addAll(java.util.Collection c)
boolean	addAll(int index, java.util.Collection c) This just throws an UnsupportedOperationException.
SimpleList	append(SimpleList lst) This corresponds to (APPEND this lst) in lisp.
void	clear() This just throws an UnsupportedOperationException.
SimpleList	cons(java.lang.Object obj)
boolean	contains(java.lang.Object o)
boolean	containsAll(java.util.Collection c)
java.util.Enumeration	elements()
java.lang.Object	first()
java.util.Iterator	frontIterator(SimpleList tail) This Iterator will iterate through the list until it reaches tail or to the end if tail is not found.
java.lang.Object	get(int i)
int	indexOf(java.lang.Object o)
boolean	isEmpty()
java.util.Iterator	iterator()
int	lastIndexOf(java.lang.Object o)
java.util.ListIterator	listIterator()
java.util.ListIterator	listIterator(int i)
static void	main(java.lang.String[] args)
static SimpleList	makeList()
static SimpleList	makeList(java.lang.Object obj)
java.lang.Object	remove(int i)
boolean	remove(java.lang.Object obj)
boolean	removeAll(java.util.Collection c)
SimpleList	rest()
boolean	retainAll(java.util.Collection c)
SimpleList	reverse()
SimpleList	reverse(SimpleList lst) This is revappend in Common Lisp.
java.lang.Object	set(int i, java.lang.Object o)
int	size() The size of the list.
java.util.List	subList(int i, int j)
java.lang.Object[]	toArray()
java.lang.Object[]	toArray(java.lang.Object[] a)
java.lang.String	toString()

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Methods inherited from interface java.util.List

equals, hashCode

Field Detail

first

protected java.lang.Object first

rest

protected transient SimpleList rest

EMPTY_LIST

public static final org.latdraw.util.SimpleList.EmptyList EMPTY_LIST

The empty list is a class constant

Constructor Detail

SimpleList

public SimpleList(java.lang.Object obj,
                  SimpleList list)

Constructs a list with obj followed by list. The same as cons in Lisp.

Parameters:

obj - The Object to be first.

list - The List to be the rest.

SimpleList

public SimpleList(java.util.Collection c)

Method Detail

makeList

public static SimpleList makeList()

makeList

public static SimpleList makeList(java.lang.Object obj)

isEmpty

public boolean isEmpty()

Specified by:

isEmpty in interface java.util.Collection

Specified by:

isEmpty in interface java.util.List

size

public int size()

The size of the list. It is inefficient since it takes time proportional to the size.

Specified by:

size in interface java.util.Collection

Specified by:

size in interface java.util.List

first

public java.lang.Object first()

rest

public SimpleList rest()

cons

public SimpleList cons(java.lang.Object obj)

elements

public java.util.Enumeration elements()

iterator

public java.util.Iterator iterator()

Specified by:

iterator in interface java.lang.Iterable

Specified by:

iterator in interface java.util.Collection

Specified by:

iterator in interface java.util.List

frontIterator

public java.util.Iterator frontIterator(SimpleList tail)

This Iterator will iterate through the list until it reaches tail or to the end if tail is not found. Note tail must be == to a tail of the list.

Parameters:

tail - a list == to a tail of the list.

append

public SimpleList append(SimpleList lst)

This corresponds to (APPEND this lst) in lisp.

reverse

public SimpleList reverse()

reverse

public SimpleList reverse(SimpleList lst)

This is revappend in Common Lisp. It produces (APPEND (REVERSE this) lst)

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object

add

public void add(int index,
                java.lang.Object elt)
         throws java.lang.UnsupportedOperationException,
                java.lang.ClassCastException,
                java.lang.IllegalArgumentException,
                java.lang.IndexOutOfBoundsException

This just throws an UnsupportedOperationException.

Specified by:

add in interface java.util.List

Throws:

java.lang.UnsupportedOperationException

java.lang.ClassCastException

java.lang.IllegalArgumentException

java.lang.IndexOutOfBoundsException

add

public boolean add(java.lang.Object elt)
            throws java.lang.UnsupportedOperationException,
                   java.lang.ClassCastException,
                   java.lang.IllegalArgumentException

This just throws an UnsupportedOperationException.

Specified by:

add in interface java.util.Collection

Specified by:

add in interface java.util.List

Throws:

java.lang.UnsupportedOperationException

java.lang.ClassCastException

java.lang.IllegalArgumentException

addAll

public boolean addAll(int index,
                      java.util.Collection c)
               throws java.lang.UnsupportedOperationException,
                      java.lang.ClassCastException,
                      java.lang.IllegalArgumentException,
                      java.lang.IndexOutOfBoundsException

This just throws an UnsupportedOperationException.

Specified by:

addAll in interface java.util.List

Throws:

java.lang.UnsupportedOperationException

java.lang.ClassCastException

java.lang.IllegalArgumentException

java.lang.IndexOutOfBoundsException

addAll

public boolean addAll(java.util.Collection c)
               throws java.lang.UnsupportedOperationException,
                      java.lang.ClassCastException,
                      java.lang.IllegalArgumentException

Specified by:

addAll in interface java.util.Collection

Specified by:

addAll in interface java.util.List

Throws:

java.lang.UnsupportedOperationException

java.lang.ClassCastException

java.lang.IllegalArgumentException

clear

public void clear()
           throws java.lang.UnsupportedOperationException

This just throws an UnsupportedOperationException.

Specified by:

clear in interface java.util.Collection

Specified by:

clear in interface java.util.List

Throws:

java.lang.UnsupportedOperationException

contains

public boolean contains(java.lang.Object o)

Specified by:

contains in interface java.util.Collection

Specified by:

contains in interface java.util.List

containsAll

public boolean containsAll(java.util.Collection c)

Specified by:

containsAll in interface java.util.Collection

Specified by:

containsAll in interface java.util.List

get

public java.lang.Object get(int i)
                     throws java.lang.IndexOutOfBoundsException

Specified by:

get in interface java.util.List

Throws:

java.lang.IndexOutOfBoundsException

indexOf

public int indexOf(java.lang.Object o)

Specified by:

indexOf in interface java.util.List

lastIndexOf

public int lastIndexOf(java.lang.Object o)

Specified by:

lastIndexOf in interface java.util.List

remove

public java.lang.Object remove(int i)
                        throws java.lang.UnsupportedOperationException

Specified by:

remove in interface java.util.List

Throws:

java.lang.UnsupportedOperationException

remove

public boolean remove(java.lang.Object obj)
               throws java.lang.UnsupportedOperationException

Specified by:

remove in interface java.util.Collection

Specified by:

remove in interface java.util.List

Throws:

java.lang.UnsupportedOperationException

removeAll

public boolean removeAll(java.util.Collection c)
                  throws java.lang.UnsupportedOperationException

Specified by:

removeAll in interface java.util.Collection

Specified by:

removeAll in interface java.util.List

Throws:

java.lang.UnsupportedOperationException

retainAll

public boolean retainAll(java.util.Collection c)
                  throws java.lang.UnsupportedOperationException

Specified by:

retainAll in interface java.util.Collection

Specified by:

retainAll in interface java.util.List

Throws:

java.lang.UnsupportedOperationException

set

public java.lang.Object set(int i,
                            java.lang.Object o)
                     throws java.lang.UnsupportedOperationException

Specified by:

set in interface java.util.List

Throws:

java.lang.UnsupportedOperationException

toArray

public java.lang.Object[] toArray(java.lang.Object[] a)

Specified by:

toArray in interface java.util.Collection

Specified by:

toArray in interface java.util.List

toArray

public java.lang.Object[] toArray()

Specified by:

toArray in interface java.util.Collection

Specified by:

toArray in interface java.util.List

subList

public java.util.List subList(int i,
                              int j)

Specified by:

subList in interface java.util.List

listIterator

public java.util.ListIterator listIterator(int i)

Specified by:

listIterator in interface java.util.List

listIterator

public java.util.ListIterator listIterator()

Specified by:

listIterator in interface java.util.List

main

public static void main(java.lang.String[] args)