org.key_project.util.collection

Class ImmutableSLList<T>

java.lang.Object

org.key_project.util.collection.ImmutableSLList<T>

All Implemented Interfaces:

java.io.Serializable, java.lang.Iterable<T>, ImmutableList<T>

Direct Known Subclasses:

ImmutableSLList.Cons, ImmutableSLList.NIL

public abstract class ImmutableSLList<T>
extends java.lang.Object
implements ImmutableList<T>

Simple implementation of a non-destructive (unmodifiable) list. The list implementation allows list sharing of sublists. The costs of the different operations are O(1) for prepending one element, O(m) for prepending a list with m elements, O(n) for appending an element to this list(size n) O(n) for appending a list with m elements to this list (size n) head() has O(1) tail has O(1) size has O(1) ATTENTION appending and prepending and element can be realized with O(1) costs (see Osaka) then having tail and head with amortized O(1). This will be done later (if necessary).

See Also:

Serialized Form

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
private static class	ImmutableSLList.Cons<S>
private static class	ImmutableSLList.NIL<S>
private static class	ImmutableSLList.SLListIterator<T> iterates through a none destructive list

Field Summary

Fields

Modifier and Type	Field and Description
private static long	serialVersionUID generated serial id

Constructor Summary

Constructors

Constructor and Description
ImmutableSLList()

Method Summary

Modifier and Type	Method and Description
ImmutableList<T>	append(java.lang.Iterable<T> collection) appends an iterable collection
static <T> ImmutableSLList<T>	nil() the empty list
ImmutableList<T>	prepend(T... array) prepends array (O(n))
protected ImmutableList<T>	prepend(T[] array, int n) prepends the first n elements of an array (O(n))
ImmutableList<T>	prependReverse(java.lang.Iterable<T> collection) prepends an iterable collection in reverse order, i.e., [4,5,6].prepend([1,2,3]) will be [3,2,1,4,5,6]
ImmutableList<T>	reverse() Reverses this list (O(N))
ImmutableList<T>	take(int n) first n elements of the list are truncated
<S> S[]	toArray(java.lang.Class<S> type) Convert the list to a Java array (O(n))
<S> S[]	toArray(S[] array) Convert the list to a Java array (O(n))

Methods inherited from class java.lang.Object

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

Methods inherited from interface org.key_project.util.collection.ImmutableList

append, append, append, contains, exists, head, isEmpty, iterator, prepend, prepend, prependReverse, removeAll, removeFirst, size, stream, tail

Methods inherited from interface java.lang.Iterable

forEach, spliterator

Field Detail

serialVersionUID

private static final long serialVersionUID

generated serial id

See Also:

Constant Field Values

Constructor Detail

ImmutableSLList

public ImmutableSLList()

Method Detail

nil

public static <T> ImmutableSLList<T> nil()

the empty list

reverse

public ImmutableList<T> reverse()

Reverses this list (O(N))

Specified by:

reverse in interface ImmutableList<T>

toArray

public <S> S[] toArray(S[] array)

Convert the list to a Java array (O(n))

Specified by:

toArray in interface ImmutableList<T>

toArray

public <S> S[] toArray(java.lang.Class<S> type)

Convert the list to a Java array (O(n))

Specified by:

toArray in interface ImmutableList<T>

prepend

public ImmutableList<T> prepend(T... array)

prepends array (O(n))

Specified by:

prepend in interface ImmutableList<T>

Parameters:

array - the array of the elements to be prepended

Returns:

IList the new list

prepend

protected ImmutableList<T> prepend(T[] array,
                                   int n)

prepends the first n elements of an array (O(n))

Parameters:

array - the array of the elements to be prepended

n - an int specifying the number of elements to be prepended

Returns:

IList the new list

append

public ImmutableList<T> append(java.lang.Iterable<T> collection)

Description copied from interface: ImmutableList

appends an iterable collection

Specified by:

append in interface ImmutableList<T>

prependReverse

public ImmutableList<T> prependReverse(java.lang.Iterable<T> collection)

Description copied from interface: ImmutableList

prepends an iterable collection in reverse order, i.e., [4,5,6].prepend([1,2,3]) will be [3,2,1,4,5,6]

Specified by:

prependReverse in interface ImmutableList<T>

Returns:

reverse(collection)++this

take

public ImmutableList<T> take(int n)

first n elements of the list are truncated

Specified by:

take in interface ImmutableList<T>

Parameters:

n - an int specifying the number of elements to be truncated

Returns:

IList this list without the first n elements