Interface

empty

empty(x)
x.empty()

Returns true if the list x is empty, false otherwise.

Default Constructor

slist<T>()

Is an empty list to which can be added elements of type T.

singleton

slist(v)

Returns a unique list of one element v.

slist from initializer list

slist({1,2,3,4})

Precondition: All the elements in the list must have the same type.

slist_from_container

slist_from_container (C)

Requires C be an STL container with a begin() method returning an input iterator and an end() method returning an end iterator. Returns a list of all the elements in the container in the sequence found from the iterator.

slist_from_iterators

slist_from_iterators<T> (begin,end)

Requires begin, end be valid iterators for a sequence. Returns all the values in the range of the begin iterator up to but excluding the end iterator. T::value_type must specify the container value type.

size

size(x)
x.size()

Returns the length of the list x.

uniq

uniq(x)
x.uniq()

Returns true if x s empty or is the only reference to the underlying list and all tails thereof. Implies the reference counts of all nodes of the underlying list are 1.

cons

cons (h,t)
t.cons(h)

returns list t with value h added to front. Unique if and only if t is unique.

tail

tail (x)
x.tail()

Precondition non-empty list. Returns list with first value removed. Unique if x is unique, may be unique even if x is not.

join

join (x,y)
x + y

Returns the list which is the concatenation of lists x and y. Unique if y is unique.

rev

rev (x)

Returns the list reversed. always unique.

copy

copy (x)

Makes a copy of the list. Always unique.

make_unique

TODO. Returns the list if it is unique, or a copy otherwise. Result is always unique.

map

map<U> (f,x)
x.map(f)

Returns a list with elements of type U, the result of applying f to each element of x. Always unique. Cost N allocations.

filter

filter (f,x)
x.filter(f)

Returns a sublist of elements of x satifying predicate f(v). Always unique.

fold_left

fold_left (f,init,x)

TODO. Uses f to fold each value of x starting at the front into init. Returns final result. f must accept two arguments, the first of type U, the type of init, and the second of type T, the type of the elements of x.

zip

zip(x,y)

TODO. Precondition, x and y have the same length. Returns a list of std::pair of corresponding element from x and y.

unzip

unzip(x)

TODO. Splits a list of pairs into a pair of lists. Precondition, the value type of x must be a std::pair.

begin

x.begin()

Returns forward list iterator starting at head of list. This iterator uses a strong pointer to the head of the list but scans the list using a weak pointer, avoiding the overhead of managing the reference count at the expense of retaining the whole list during the scan.

end

x.end()

Returns terminal fast list iterator.

begin_input

x.begin_input()

Returns input list iterator starting at the head of the list. This iterator uses a strong pointer to scan the list. Reference counts are adjusted during the scan. If the list is unique, then a scan will consume the list, freeing memory during the scan.

end_input

x.end_input()

Returns terminal input list iterator.

get_back_inserter

x.get_back_inserter()

Fetches an output iterator for the list x. The list should be unique. If not, the handle x detaches its current list and is set to a copy, making it unique. A prefix of the previous list may be lost because the head node’s refcount is decremented. Note the whole list cannot be lost because it would have to be unique for that to happen, there must be at least one other reference to some non-empty suffix of the list.

Writes to the output iterator append elements to the end of the list. The pre-increment and post-increment operators have no effect. The dereference operator returns a proxy which accepts an assignment from the list value type, which causes a new node to be appended to the end of the list and the output iterator then advances.

Note, the iterator returned by this method is faster than

std::back_inserter(x)

however at present it is not fully safe. If the iterator is retained and the list shared, subsequent insertions will also be shared.

push_front

x.push_front(v);

Sematically equivalent to

x = x.cons(v);

Returns a reference to x.

push_back

x.push_back(v);

Sematically equivalent to

x = x + v;

Returns a reference to x.