edu.rice.cs.plt.collect
Class ConsList<T>

java.lang.Object
  edu.rice.cs.plt.iter.AbstractIterable<T>
      edu.rice.cs.plt.collect.ConsList<T>

All Implemented Interfaces:

SizedIterable<T>, Composite, java.io.Serializable, java.lang.Iterable<T>

Direct Known Subclasses:

ConsList.Empty, ConsList.Nonempty

public abstract class ConsList<T>
extends AbstractIterable<T>
implements SizedIterable<T>, Composite, java.io.Serializable

A Lisp- or Scheme-style immutable list. A ConsList is either an ConsList.Empty or a ConsList.Nonempty; operations may be defined on the lists by implementing ConsVisitor. While ComposedIterable provides similar facilities for creating lists, ConsLists provide a more efficient means of decomposing lists -- because there is no rest operation on Iterables in general, the only way to produce an Iterable sublist of an Iterable is to make a copy. With a well-designed ConsList, on the other hand, producing a sublist is trivial.

This class also defines a few static convenience methods to simplify client code. A static import (import static edu.rice.cs.plt.collect.ConsList.*) will eliminate the need for explicit name qualifiers when using these methods.

See Also:

Serialized Form

Nested Class Summary

static class	ConsList.Empty<T> The empty variant of a ConsList.
static class	ConsList.Nonempty<T> The nonempty variant of a ConsList.

Constructor Summary

ConsList()

Method Summary

static <T> ConsList<? extends T>	append(ConsList<? extends T> l1, ConsList<? extends T> l2) Append l2 to the end of l1
abstract <Ret> Ret	apply(ConsVisitor<? super T,? extends Ret> visitor)
int	compositeHeight() Get the maximum path length from this node to a leaf.
int	compositeSize() Get the number of nodes in the tree rooted at this node.
static <T> ConsList.Nonempty<T>	cons(T first, ConsList<? extends T> rest) Create a nonempty list (via ConsList())
static <T> ConsList.Empty<T>	empty() Create an empty list (via ConsList.Empty.make())
static <T> ConsList<? extends T>	filter(ConsList<? extends T> list, Predicate<? super T> pred) Filter the given list according to a predicate
static <T> T	first(ConsList<? extends T> list) Attempt to access the first of the given list (throws an exception in the empty case).
boolean	hasFixedSize() Return true: cons lists have a fixed size.
abstract boolean	isEmpty() Whether this is an empty ConsList.
boolean	isInfinite() Return false: cons lists are not infinite.
boolean	isStatic() Return true: cons lists are immutable.
abstract java.util.Iterator<T>	iterator()
static <S,T> ConsList<? extends T>	map(ConsList<? extends S> list, Lambda<? super S,? extends T> lambda) Map the given list according to a lambda
static <T> ConsList<? extends T>	rest(ConsList<? extends T> list) Attempt to access the rest of the given list (throws an exception in the empty case).
static <T> ConsList<? extends T>	reverse(ConsList<? extends T> list) Reverse the given list
static <T> ConsList.Nonempty<T>	singleton(T value) Create a singleton nonempty list (via ConsList())
abstract int	size() Compute the size of the list.
abstract int	size(int bound) Compute the size of the list, up to a given bound.

Methods inherited from class edu.rice.cs.plt.iter.AbstractIterable

equals, hashCode, toString

Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, wait, wait, wait

Constructor Detail

ConsList

public ConsList()

Method Detail

apply

public abstract <Ret> Ret apply(ConsVisitor<? super T,? extends Ret> visitor)

iterator

public abstract java.util.Iterator<T> iterator()

Specified by:

iterator in interface java.lang.Iterable<T>

isEmpty

public abstract boolean isEmpty()

Whether this is an empty ConsList.

Specified by:

isEmpty in interface SizedIterable<T>

size

public abstract int size()

Compute the size of the list. Note that this is a linear — not constant-time — operation.

Specified by:

size in interface SizedIterable<T>

size

public abstract int size(int bound)

Compute the size of the list, up to a given bound. Note that this is a linear — not constant-time — operation.

Specified by:

size in interface SizedIterable<T>

Parameters:

bound - Maximum result. Assumed to be nonnegative.

isInfinite

public boolean isInfinite()

Return false: cons lists are not infinite.

Specified by:

isInfinite in interface SizedIterable<T>

hasFixedSize

public boolean hasFixedSize()

Return true: cons lists have a fixed size.

Specified by:

hasFixedSize in interface SizedIterable<T>

isStatic

public boolean isStatic()

Return true: cons lists are immutable.

Specified by:

isStatic in interface SizedIterable<T>

compositeHeight

public int compositeHeight()

Description copied from interface: Composite

Get the maximum path length from this node to a leaf.

Specified by:

compositeHeight in interface Composite

compositeSize

public int compositeSize()

Description copied from interface: Composite

Get the number of nodes in the tree rooted at this node. Always 1 or greater.

Specified by:

compositeSize in interface Composite

empty

public static <T> ConsList.Empty<T> empty()

Create an empty list (via ConsList.Empty.make())

cons

public static <T> ConsList.Nonempty<T> cons(T first,
                                            ConsList<? extends T> rest)

Create a nonempty list (via ConsList())

singleton

public static <T> ConsList.Nonempty<T> singleton(T value)

Create a singleton nonempty list (via ConsList())

first

public static <T> T first(ConsList<? extends T> list)

Attempt to access the first of the given list (throws an exception in the empty case).

rest

public static <T> ConsList<? extends T> rest(ConsList<? extends T> list)

Attempt to access the rest of the given list (throws an exception in the empty case).

reverse

public static <T> ConsList<? extends T> reverse(ConsList<? extends T> list)

Reverse the given list

append

public static <T> ConsList<? extends T> append(ConsList<? extends T> l1,
                                               ConsList<? extends T> l2)

Append l2 to the end of l1

filter

public static <T> ConsList<? extends T> filter(ConsList<? extends T> list,
                                               Predicate<? super T> pred)

Filter the given list according to a predicate

map

public static <S,T> ConsList<? extends T> map(ConsList<? extends S> list,
                                              Lambda<? super S,? extends T> lambda)

Map the given list according to a lambda