Class OpenList

java.lang.Object
  |
  +--OpenList

All Implemented Interfaces:

java.lang.Cloneable

class OpenList

extends java.lang.Object

implements java.lang.Cloneable

OpenList is a type of uni-directional linked list that permits sharing of list tails. It implements the list abstraction used in many languages, such as rex, Lisp, etc.

Field Summary

static java.lang.String	defaultLeftParen the default left paren used when a list is printed.
static java.lang.String	defaultRightParen the default right paren used when a list is printed
static java.lang.String	defaultSpacer the default space used when a list is printed
private java.lang.Object	First the Object in the first cell of a non-empty list
static java.lang.String	firstException exception message for first of empty list
static OpenList	nil the one and only empty OpenList.
static java.lang.String	nthException exception message for nth of a list
private OpenList	Rest the rest of a list, defined to be an OpenList of all but the first cell
static java.lang.String	restException exception message for rest of empty list
static java.lang.String	secondException exception message for second of a list
static java.lang.String	thirdException exception message for third of a list
static java.lang.String	wherePart part of exception message for nth of a list

Constructor Summary

private

OpenList(java.lang.Object _First, OpenList _Rest) Construct an OpenList from its first and rest.

Method Summary

OpenList	append(OpenList L2) Create a new list formed by elements of this list followed by those of the argument list.
static OpenList	append(OpenList L1, OpenList L2) Create a new list formed by elements of the first argument followed by those of the second.
static OpenList	assoc(java.lang.Object X, OpenList L) Find out whether the first argument occurs as the first element of any pair in the second argument, an association list.
java.lang.Object	clone() Return a clone of this OpenList.
OpenList	cons(java.lang.Object _First) Return a new OpenList constructed from this list and a first.
static OpenList	cons(java.lang.Object _First, OpenList _Rest) Return a new OpenList constructed from its first and rest.
java.util.Enumeration	elements() Return an Enumeration of the elements of this OpenList.
boolean	equals(java.lang.Object Ob) Return true if this list is equal to the argument list.
static boolean	equals(OpenList L1, OpenList L2) Return true if the two OpenLists are equal, in the sense of having the equal elements in both listss.
static OpenList	explode(java.lang.String s) Explode the argument String into a list of Characters wrapping the characters of the String.
java.lang.Object	first() Return the first of this non-empty OpenList.
static java.lang.Object	first(OpenList List) Return the first of the argument, a non-empty OpenList.
static OpenList	fromArray(java.lang.Object[] a) Create an OpenList from an array of Objects.
java.lang.String	implode() Implode this OpenList into a single String.
static java.lang.String	implode(OpenList L) Implode the contents of an OpenList into a single String.
boolean	isEmpty() Return true if this list is empty, false otherwise.
static boolean	isEmpty(OpenList List) Return true if the argument list is empty, false otherwise.
(package private) static java.lang.String	lconcat(OpenList L, java.lang.String S) lconcat concatenates the elements of an OpenList, interspersing a designated String between elements.
(package private) java.lang.String	lconcat(java.lang.String S) lconcat concatenates the elements of this OpenList, interspersing a designated String between elements.
int	length() Return the number of elements of this list.
static int	length(OpenList L) Return the number of elements of the argument list.
static OpenList	list() Return the list consisting of the argument objects, in this case the empty list.
static OpenList	list(java.lang.Object First) Return the list consisting of the argument objects.
static OpenList	list(java.lang.Object First, java.lang.Object Second) Return the list consisting of the argument objects.
static OpenList	list(java.lang.Object First, java.lang.Object Second, java.lang.Object Third) Return the list consisting of the argument objects.
static OpenList	list(java.lang.Object First, java.lang.Object Second, java.lang.Object Third, java.lang.Object Fourth) Return the list consisting of the argument objects.
static OpenList	list(java.lang.Object First, java.lang.Object Second, java.lang.Object Third, java.lang.Object Fourth, java.lang.Object Fifth) Return the list consisting of the argument objects.
static OpenList	list(java.lang.Object First, java.lang.Object Second, java.lang.Object Third, java.lang.Object Fourth, java.lang.Object Fifth, java.lang.Object Sixth) Return the list consisting of the argument objects.
static OpenList	list(java.lang.Object First, java.lang.Object Second, java.lang.Object Third, java.lang.Object Fourth, java.lang.Object Fifth, java.lang.Object Sixth, java.lang.Object Seventh) Return the list consisting of the argument objects.
static void	main(java.lang.String[] arg) test program: exercises a variety of the defined methods, printing out results
OpenList	map(Function1 f) Map a Function1 f over this OpenList.
static OpenList	map(Function1 f, OpenList L) Map a Function1 function object f over an OpenList L.
static OpenList	mappend(Function1 f, OpenList L) Map a Function1 function object f over an OpenList L, where the function is expected to produce a list for each object, then append the results together to get an overall list.
boolean	member(java.lang.Object Ob) Return true if the first argument is a member (in the sense of being equals) of this OpenList
static boolean	member(java.lang.Object Ob, OpenList L) Return true if the first argument is a member (in the sense of being equals) of the second argument list
boolean	nonEmpty() Return true if this list is non-empty, false otherwise.
static boolean	nonEmpty(OpenList List) Return true if the argument list is non-empty, false otherwise.
java.lang.Object	nth(int n) Return the nth element of this list, starting with n = 0, 1, 2, ...
static java.lang.Object	nth(int n, OpenList L) Return the nth element of the second argument list, starting with n = 0, 1, 2, ...
OpenList	prefix(int n) Returns the first n elements of this OpenList.
static OpenList	prefix(int n, OpenList L) Returns the first n elements of an OpenList.
static OpenList	readLines(java.io.BufferedReader reader) Read lines from a BufferedReader, each as a separate String.
java.lang.Object	reduce(Function2 b, java.lang.Object u) Reduce this OpenList using Function2 b and unit u.
static java.lang.Object	reduce(Function2 b, java.lang.Object u, OpenList L) Reduce an OpenList using Function2 b and unit u.
OpenList	rest() Return the rest, i.e. all a list of all but the first of this non-empty OpenList.
static OpenList	rest(OpenList List) Return the rest, i.e. all a list of all but the first of the argument non-empty OpenList.
OpenList	reverse() Return a new list containing the elements of the argument this list in reverse order.
static OpenList	reverse(OpenList L1) Return a new list containing the elements of the argument list in reverse order.
java.lang.Object	second() Return the second element of this OpenList, assuming it has one.
static java.lang.Object	second(OpenList L) Return the second element of the argument OpenList, assuming it has one.
static OpenList	solidify(java.util.Enumeration E) Create an OpenList of the elements from an Enumeration.
OpenList	sort(java.util.Comparator comparator) Return a sorted version of this list, as determined by the Comparator, using the Quicksort algorithm
java.lang.Object	third() Return the third element of this OpenList, assuming it has one.
static java.lang.Object	third(OpenList L) Return the third element of the argument OpenList, assuming it has one.
java.lang.Object[]	toArray() Return an array of the Objects in this OpenList.
static java.lang.Object[]	toArray(OpenList L) Return an array of the Objects in the argument OpenList.
java.lang.String	toString() Convert this OpenList to a String, using default punctuation.
java.lang.String	toString(java.lang.String leftParen, java.lang.String spacer, java.lang.String rightParen) Convert this OpenList to a String, using the arguments as punctuation.

Methods inherited from class java.lang.Object

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

Field Detail

nil

public static final OpenList nil

the one and only empty OpenList. Do not create any others. This list is represented by a unique cell allocated for the purpose. The first and rest are not intended to be used. We do not use null for this list, so that we can call methods on it. We do not create other empty lists so that our implementation of isEmpty() works by comparing references.

defaultLeftParen

public static java.lang.String defaultLeftParen

the default left paren used when a list is printed. Defaults are used when the toString() method is called, i.e. whenever an OpenList is automatically cast to a String, as in printing. To use different punctuation, or no punctuation, use the three-argument toString, and supply the punctuation you want.

defaultRightParen

public static java.lang.String defaultRightParen

the default right paren used when a list is printed

defaultSpacer

public static java.lang.String defaultSpacer

the default space used when a list is printed

firstException

public static java.lang.String firstException

exception message for first of empty list

restException

public static java.lang.String restException

exception message for rest of empty list

nthException

public static java.lang.String nthException

exception message for nth of a list

wherePart

public static java.lang.String wherePart

part of exception message for nth of a list

secondException

public static java.lang.String secondException

exception message for second of a list

thirdException

public static java.lang.String thirdException

exception message for third of a list

First

private java.lang.Object First

the Object in the first cell of a non-empty list

Rest

private OpenList Rest

the rest of a list, defined to be an OpenList of all but the first cell

Constructor Detail

OpenList

private OpenList(java.lang.Object _First,
                 OpenList _Rest)

Construct an OpenList from its first and rest. This constructor is private because it is intended that the pseudo-constructor (or "factory") cons be used outside.

Parameters:

_First - the first Object in the list

_Rest - list of the rest of the objects in the list

Method Detail

cons

public static OpenList cons(java.lang.Object _First,
                            OpenList _Rest)

Return a new OpenList constructed from its first and rest.

Parameters:

_First - the first Object in the list

_Rest - list of the rest of the objects in the list

Returns:

new OpenList from first and rest

cons

public OpenList cons(java.lang.Object _First)

Return a new OpenList constructed from this list and a first.

Parameters:

_First - the first Object in the list

Returns:

new OpenList from first and rest

first

public java.lang.Object first()
                       throws OpenListException

Return the first of this non-empty OpenList.

Returns:

first of this list

Throws:

OpenListException - if this list happens to be empty

first

public static java.lang.Object first(OpenList List)
                              throws OpenListException

Return the first of the argument, a non-empty OpenList.

Parameters:

List - the list the rest of which is to be returned

Returns:

first of the argument list

Throws:

OpenListException - if the argument happens to be empty

rest

public OpenList rest()
              throws OpenListException

Return the rest, i.e. all a list of all but the first of this non-empty OpenList.

Returns:

rest of this list

Throws:

OpenListException - if this list happens to be empty

rest

public static OpenList rest(OpenList List)
                     throws OpenListException

Return the rest, i.e. all a list of all but the first of the argument non-empty OpenList.

Parameters:

List - the list the rest of which is to be returned

Returns:

rest of the argument list

Throws:

OpenListException - if the argument happens to be empty

isEmpty

public boolean isEmpty()

Return true if this list is empty, false otherwise. Note: Done by comparing this list to nil, which should be the only way to determine whether the list is empty.

Returns:

true if this list is empty, false otherwise

nonEmpty

public boolean nonEmpty()

Return true if this list is non-empty, false otherwise.

Returns:

true if this list is non-empty, false otherwise

isEmpty

public static boolean isEmpty(OpenList List)

Return true if the argument list is empty, false otherwise. Note: Done by comparing this list to nil, which should be the only way to determine whether the list is empty.

Parameters:

List - the OpenList for which emptiness is to be determined

Returns:

true if the argument list is empty, false otherwise

nonEmpty

public static boolean nonEmpty(OpenList List)

Return true if the argument list is non-empty, false otherwise.

Parameters:

List - the OpenList for which non-emptiness is to be determined

Returns:

true if the argument list is non-empty, false otherwise

append

public static OpenList append(OpenList L1,
                              OpenList L2)

Create a new list formed by elements of the first argument followed by those of the second.

Parameters:

L1 - the list providing the initial elements of the result

L2 - the list providing the final elements of the result

Returns:

the list containing the elements of the first list followed by those of the second

append

public OpenList append(OpenList L2)

Create a new list formed by elements of this list followed by those of the argument list.

Returns:

the list containing the elements of this list followed by those of the second

member

public static boolean member(java.lang.Object Ob,
                             OpenList L)

Return true if the first argument is a member (in the sense of being equals) of the second argument list

Parameters:

Ob - the object being tested for membership

L - the list in which membership is to be tested

Returns:

true if the first argument is a member of the second, false otherwise

member

public boolean member(java.lang.Object Ob)

Return true if the first argument is a member (in the sense of being equals) of this OpenList

Parameters:

Ob - the object being tested for membership

Returns:

true if the first argument is a member of this list, false otherwise

reverse

public static OpenList reverse(OpenList L1)

Return a new list containing the elements of the argument list in reverse order.

Parameters:

L1 - the list providing the elements

Returns:

the reverse of the argument list

reverse

public OpenList reverse()

Return a new list containing the elements of the argument this list in reverse order.

Returns:

the reverse of this list

length

public static int length(OpenList L)

Return the number of elements of the argument list.

Parameters:

L - the list, the length of which is to be determined

Returns:

the number of elements of the argument list

length

public int length()

Return the number of elements of this list.

Returns:

the number of elements of this list

nth

public static java.lang.Object nth(int n,
                                   OpenList L)
                            throws OpenListException

Return the nth element of the second argument list, starting with n = 0, 1, 2, ... If there is no nth element, throws an OpenListException so indicating.

Parameters:

n - the index (0, 1, 2, ...) of the desired element.

L - the list from which the indexed item is selected

Returns:

the nth element of this list

Throws:

OpenListException - if there is no nth element

nth

public java.lang.Object nth(int n)
                     throws OpenListException

Return the nth element of this list, starting with n = 0, 1, 2, ... If there is no nth element, throws an EmptyList exception so indicating.

Parameters:

n - the index (0, 1, 2, ...) of the desired element.

Returns:

the nth element of this list

Throws:

OpenListException - if there is no nth element

prefix

public OpenList prefix(int n)

Returns the first n elements of this OpenList. If there aren't n elements in the list, returns the entire list. If n <= 0, returns nil.

Parameters:

n - the length of the desired prefix of this list.

Returns:

the prefix of this list of the desired length, or the entire list itself if the list is not as long as desired.

prefix

public static OpenList prefix(int n,
                              OpenList L)

Returns the first n elements of an OpenList. If there aren't n elements in the list, returns the entire list. If n <= 0, returns nil.

Parameters:

n - the length of the desired prefix of this list.

L - the list, the prefix of which is to be extracted

Returns:

the prefix of this list of the desired length, or the entire list itself if the list is not as long as desired.

second

public java.lang.Object second()
                        throws OpenListException

Return the second element of this OpenList, assuming it has one.

Returns:

the second element of this OpenList

Throws:

OpenListException - if there is no second element

third

public java.lang.Object third()
                       throws OpenListException

Return the third element of this OpenList, assuming it has one.

Returns:

the third element of this OpenList

Throws:

OpenListException - if there is no third element

second

public static java.lang.Object second(OpenList L)
                               throws OpenListException

Return the second element of the argument OpenList, assuming it has one.

Parameters:

L - an OpenList, the second element of which is to be extracted

Returns:

the second element L

Throws:

OpenListException - if there is no second element

third

public static java.lang.Object third(OpenList L)
                              throws OpenListException

Return the third element of the argument OpenList, assuming it has one.

Parameters:

L - an OpenList, the third element of which is to be extracted

Returns:

the second element L

Throws:

OpenListException - if there is no third element

list

public static OpenList list()

Return the list consisting of the argument objects, in this case the empty list.

Returns:

the list consisting of the argument objects

list

public static OpenList list(java.lang.Object First)

Return the list consisting of the argument objects.

Parameters:

First - the first element in the resulting list

Returns:

the list consisting of the argument objects

list

public static OpenList list(java.lang.Object First,
                            java.lang.Object Second)

Return the list consisting of the argument objects.

Parameters:

First - the first element in the resulting list

Second - the second element in the resulting list

Returns:

the list consisting of the argument objects

list

public static OpenList list(java.lang.Object First,
                            java.lang.Object Second,
                            java.lang.Object Third)

Return the list consisting of the argument objects.

Parameters:

First - the first element in the resulting list

Second - the second element in the resulting list

Third - the third element in the resulting list

Returns:

the list consisting of the argument objects

list

public static OpenList list(java.lang.Object First,
                            java.lang.Object Second,
                            java.lang.Object Third,
                            java.lang.Object Fourth)

Return the list consisting of the argument objects.

Parameters:

First - the first element in the resulting list

Second - the second element in the resulting list

Third - the third element in the resulting list

Fourth - the fourth element in the resulting list

Returns:

the list consisting of the argument objects

list

public static OpenList list(java.lang.Object First,
                            java.lang.Object Second,
                            java.lang.Object Third,
                            java.lang.Object Fourth,
                            java.lang.Object Fifth)

Return the list consisting of the argument objects.

Parameters:

First - the first element in the resulting list

Second - the second element in the resulting list

Third - the third element in the resulting list

Fourth - the fourth element in the resulting list

Fifth - the fifth element in the resulting list

Returns:

the list consisting of the argument objects

list

public static OpenList list(java.lang.Object First,
                            java.lang.Object Second,
                            java.lang.Object Third,
                            java.lang.Object Fourth,
                            java.lang.Object Fifth,
                            java.lang.Object Sixth)

Return the list consisting of the argument objects.

Parameters:

First - the first element in the resulting list

Second - the second element in the resulting list

Third - the third element in the resulting list

Fourth - the fourth element in the resulting list

Fifth - the fifth element in the resulting list

Sixth - the sixth element in the resulting list

Returns:

the list consisting of the argument objects

list

public static OpenList list(java.lang.Object First,
                            java.lang.Object Second,
                            java.lang.Object Third,
                            java.lang.Object Fourth,
                            java.lang.Object Fifth,
                            java.lang.Object Sixth,
                            java.lang.Object Seventh)

Return the list consisting of the argument objects.

Parameters:

First - the first element in the resulting list

Second - the second element in the resulting list

Third - the third element in the resulting list

Fourth - the fourth element in the resulting list

Fifth - the fifth element in the resulting list

Sixth - the sixth element in the resulting list

Seventh - the seventh element in the resulting list

Returns:

the list consisting of the argument objects

equals

public static boolean equals(OpenList L1,
                             OpenList L2)

Return true if the two OpenLists are equal, in the sense of having the equal elements in both listss.

Parameters:

L1 - one of two OpenLists to be compared for equality

L2 - the other of two OpenLists to be compared for equality

Returns:

true if the arguments are equal, false otherwise

equals

public boolean equals(java.lang.Object Ob)

Return true if this list is equal to the argument list.

Overrides:

equals in class java.lang.Object

Parameters:

Ob - the Object to be compared with this for equality

Returns:

true if the argument is an OpenList equal to this one.

clone

public java.lang.Object clone()

Return a clone of this OpenList. Any Cloneable Objects in the list will be cloned in the result. Non-Cloneable Objects will be included as is.

Overrides:

clone in class java.lang.Object

Returns:

Object which is really an OpenList (for conformance to the Cloneable interface)

map

public static OpenList map(Function1 f,
                           OpenList L)

Map a Function1 function object f over an OpenList L.

Parameters:

f - a member of a class that implements the Function1 interface, i.e. that provides a method Object apply(Object).

L - a list, the elements of which will be arguments of f

Returns:

A list resulting from applying f to each element of L

map

public OpenList map(Function1 f)

Map a Function1 f over this OpenList.

Parameters:

f - a member of a class that implements the Function1 interface, i.e. that provides a method Object apply(Object).

Returns:

A list resulting from applying f to each element of L

mappend

public static OpenList mappend(Function1 f,
                               OpenList L)

Map a Function1 function object f over an OpenList L, where the function is expected to produce a list for each object, then append the results together to get an overall list.

Parameters:

f - a member of a class that implements the Function1 interface, i.e. that provides a method Object apply(Object).

L - a list, the elements of which will be arguments of f

Returns:

A list resulting from applying f to each element of L then appending the results together.

reduce

public static java.lang.Object reduce(Function2 b,
                                      java.lang.Object u,
                                      OpenList L)

Reduce an OpenList using Function2 b and unit u.

Parameters:

b - a member of a class that implements the Function2 interface, i.e. that provides a method Object apply(Object, Object).

u - the unit for the function b. This will be the value returned if L is the empty list.

L - the list to be reduced by the function b.

Returns:

A list resulting from applying f to each element of L

reduce

public java.lang.Object reduce(Function2 b,
                               java.lang.Object u)

Reduce this OpenList using Function2 b and unit u.

Parameters:

b - a member of a class that implements the Function2 interface, i.e. that provides a method Object apply(Object, Object).

u - the unit for the function b. This will be the value returned

Returns:

A list resulting from applying f to each element of this.

assoc

public static OpenList assoc(java.lang.Object X,
                             OpenList L)

Find out whether the first argument occurs as the first element of any pair in the second argument, an association list. If it does, return the entire pair. If not, return the empty list.

 assoc(S, []) => [];
 
 assoc(S, [[S, T] | L]) => [S, T];

 assoc(S, [_ | L]) => assoc(S, L);

toString

public java.lang.String toString()

Convert this OpenList to a String, using default punctuation.

Overrides:

toString in class java.lang.Object

Returns:

String representing this OpenList

toString

public java.lang.String toString(java.lang.String leftParen,
                                 java.lang.String spacer,
                                 java.lang.String rightParen)

Convert this OpenList to a String, using the arguments as punctuation.

Parameters:

leftParen - String that is output before the list elements

spacer - String that is output between list elements

rightParen - String that is output after the list elements

Returns:

String representing OpenList

explode

public static OpenList explode(java.lang.String s)

Explode the argument String into a list of Characters wrapping the characters of the String.

Returns:

OpenList containing the characters of the String

implode

public static java.lang.String implode(OpenList L)

Implode the contents of an OpenList into a single String. The list can contain any Objects, not just Characters. The toString method is used to get the character representation of the object. No parentheses or spacing is added around or between the elements of the outer list. If these are wanted, use the toString method rather than implode.

Parameters:

L - the list to be imploded

Returns:

String representing the imploded list.

implode

public java.lang.String implode()

Implode this OpenList into a single String. The list can contain any Objects, not just Characters. The toString method is used to get the character representation of the object. No parentheses or spacing is added around or between the elements of the outer list.

Returns:

String representing the imploded list.

toArray

public static java.lang.Object[] toArray(OpenList L)

Return an array of the Objects in the argument OpenList.

Parameters:

L - the list of objects to be used as elements of the array

Returns:

an array of the Objects in the argument OpenList

toArray

public java.lang.Object[] toArray()

Return an array of the Objects in this OpenList.

Returns:

an array of the Objects in this OpenList

fromArray

public static OpenList fromArray(java.lang.Object[] a)

Create an OpenList from an array of Objects.

Returns:

an OpenList containing the Objects in the argument array

sort

public OpenList sort(java.util.Comparator comparator)

Return a sorted version of this list, as determined by the Comparator, using the Quicksort algorithm

Parameters:

comparator - used to determine whether one element is less than another

Returns:

the list consisting of the Objects in the original list in order as determined by the comparator

readLines

public static OpenList readLines(java.io.BufferedReader reader)
                          throws java.io.IOException

Read lines from a BufferedReader, each as a separate String. The lines read are returned as an OpenList of Strings.

Parameters:

reader - reads the lines that are compiled into a list

Returns:

list of Strings read, one String per line

java.io.IOException

elements

public java.util.Enumeration elements()

Return an Enumeration of the elements of this OpenList.

Returns:

an Enumeration of the elements of this OpenList

solidify

public static OpenList solidify(java.util.Enumeration E)

Create an OpenList of the elements from an Enumeration.

Parameters:

E - an Enumeration that provides the elements for a new OpenList

Returns:

an OpenList of the elements from an Enumeration

lconcat

java.lang.String lconcat(java.lang.String S)

lconcat concatenates the elements of this OpenList, interspersing a designated String between elements.

Parameters:

S - a String to be interspersed between the items of this list

Returns:

a String consisting of the items in this list with S interspersed between each.

lconcat

static java.lang.String lconcat(OpenList L,
                                java.lang.String S)

lconcat concatenates the elements of an OpenList, interspersing a designated String between elements.

Parameters:

L - an OpenList, the elements of which are to be concatenated.

S - a String to be interspersed between the items of L.

Returns:

a String consisting of the items in L with S interspersed between each.

main

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

test program: exercises a variety of the defined methods, printing out results