org.uacalc.util

Class SimpleList

java.lang.Object

org.uacalc.util.SimpleList

All Implemented Interfaces:

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

public class SimpleList
extends java.lang.Object
implements java.lang.Cloneable, 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

Fields

Modifier and Type	Field and Description
static org.uacalc.util.SimpleList.EmptyList	EMPTY_LIST The empty list is a class constant
static org.uacalc.util.SimpleList.EmptyList	emptyList
protected java.lang.Object	first
protected SimpleList	rest

Constructor Summary

Constructors

Constructor and Description
SimpleList(java.util.Collection c)
SimpleList(java.lang.Object obj, SimpleList list) Constructs a list with obj followed by list.

Method Summary

Modifier and Type	Method and Description
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.
java.lang.Object	clone()
SimpleList	cons(java.lang.Object obj)
boolean	contains(java.lang.Object o)
boolean	containsAll(java.util.Collection c)
SimpleList	copyList()
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)
java.util.Iterator	getIterator()
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 i)
boolean	removeAll(java.util.Collection i)
SimpleList	rest()
boolean	retainAll(java.util.Collection i)
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

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

Methods inherited from interface java.util.List

equals, hashCode, replaceAll, sort, spliterator

Methods inherited from interface java.util.Collection

parallelStream, removeIf, stream

Methods inherited from interface java.lang.Iterable

forEach

Field Detail

first

protected transient java.lang.Object first

rest

protected transient SimpleList rest

EMPTY_LIST

public static org.uacalc.util.SimpleList.EmptyList EMPTY_LIST

The empty list is a class constant

emptyList

public static org.uacalc.util.SimpleList.EmptyList emptyList

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.

getIterator

public java.util.Iterator getIterator()

copyList

public SimpleList copyList()

clone

public java.lang.Object clone()

Overrides:

clone in class java.lang.Object

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 i)
               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 i)
                  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 i)
                  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)