Differences

This shows you the differences between two versions of the page.

--- at:tutorial:appendix [2008/07/08 11:47] – *edited tvcutsem
+++ at:tutorial:appendix [2008/07/10 14:51] – added tvcutsem
@@ Line 1: / Line 1: @@
 ====== Appendix ======
-In the appendix, we explain useful libraries available to the AmbientTalk/2 programmer.
+In the appendix, we explain useful libraries available to the AmbientTalk/2 programmer. These libraries provide abstractions ranging from traditional, established "collections" up to newly researched language constructs, such as "ambient references".
 ===== Unit Testing Framework =====
@@ Line 95: / Line 95: @@
 The ''TestSuite'' object groups the given unit test objects. You can execute all tests in batch by sending the test suite object the ''runTest'' message, just like for running a single unit test. It is possible to nest multiple test suites within each other.
+===== Basic Collections =====
+The modules ''/.at.collections.vector'' and ''/.at.collections.list'' define a Vector and List datastructure respectively.
+==== Vector ====
+A vector is a dynamically resizable AmbientTalk table (aka array). Indexed reading from and writing to a vector is fast (O(1)). Adding elements to a vector is mostly fast, but sometimes requires a resize of the vector. Vectors support the traditional stack operations ''push'' and ''pop'' and may be turned into sets by invoking their ''uniq'' method (note that a ''uniq''-ed vector is not permanently a Set: subsequent duplicates added to the vector will not be filtered).
+Vectors may be created as follows:
+<code>
+import /.at.collections.vector;
+def v := Vector.new(10); // a vector with starting length 10
+</code>
+The constructor optionally takes a comparator as a second argument. A comparator is a binary function returning a boolean whose job is to compare elements of the Vector. This comparator is used among others when sorting the vector. The Vector's interface is as follows:
+<code>
+// returns the number of elements in the vector (not its capacity!)
+length()
+// returns whether the vector contains elements or not
+isEmpty()
+// is the vector at max. capacity?
+atMaxCapacity()
+// return idx'th element or raise an IndexOutOfBounds exception
+at(idx)
+// write idx'th element or raise IndexOutOfBounds exception
+atPut(idx, val)
+// iterate over the vector
+each: iterator, returns nil
+// map a unary function over the vector, returns a new vector
+map: fun
+// accumulate a function with a given starting value
+inject: init into: accum;
+// returns a new vector whose elements satisfy "cond"
+filter: cond;
+// implode a vector of character strings into one text string
+implode()
+// join a vector of character strings together with the given string
+join(txt)
+// returns a range [start,stop[ as a table
+select(start, stop)
+// appends an element to the back of the vector. Returns the vector itself
+add(element)
+// alias for add(element)
+<<(element)
+// insert an element at a given position, causing subsequent elements to shift one pos to the right. Returns this vector
+insert(atPos, element)
+// delete the element at the given position, shifts all following elements one pos to the left. Returns the value of the element at the deleted position.
+delete(atPos)
+// adds elements to the back of the vector
+push(element)
+// deletes elements from the back of the vector
+pop()
+// return the index of the first element matching the unary predicate or nil if none is found
+find: filter
+// remove the given element from the vector, return true if the element was actually found and deleted, false otherwise
+remove(elt, cmp := defaultComparator)
+// remove all objects for which filter(elt) returns true
+removeAll: filter
+// destructively appends otherVector to self. Returns this vector
+addAll(otherVector)
+// empties the vector
+clear()
+// Return a new vector whose elements form the set-union of all elements in self U otherVector
+union(otherVector, cmp := defaultComparator)
+// Return a new vector whose elements form the set-intersection of all elements in self ^ otherVector
+intersection(otherVector, cmp := defaultComparator)
+// Return a new vector whose elements form the set-difference of self \ otherVector
+difference(otherVector, cmp := defaultComparator)
+// Quicksort the vector in-place. The comparator defines the ordering among elements.
+sort(cmp := { |e1,e2| e1 < e2 })
+// Turn the vector into a set without duplicates in O(nlogn + n)
+// The vector's ordering is lost (it becomes sorted)
+uniq(cmp := defaultComparator, ordercmp := {|e1,e2| e1 < e2 })
+// return an element drawn randomly using a uniform distribution from the array or raise an EmptyVector exception.
+random()
+// return a table containing all elements of the vector
+asTable()
+</code>
+The file ''at/collections/vector.at'' contains a unit tests that further helps to illustrate the usage of this Vector abstraction.
+==== List ====
+The module ''/.at.collections.list'' implements Scheme-like list datastructures. The module exports the prototype ''NIL'', which is bound to the empty list. Non-empty lists are defined as a chain of cons-cells.
+The list module defines two styles to manipulate cons-cells: an object-oriented and a functional style. The object-oriented style represents cons-cells as ''Cons'' prototypes. Given a cons-cell ''c'', a new one can be constructed by invoking ''c.new(car, cdr)''. The car and cdr part of the cons-cell can be extracted by means of ''c.car'' and ''c.cdr''.
+The functional style allows one to manipulate lists by means of the following functions:
+<code>
+cons(car,cdr) -> a new cons-cell
+car(conscell) -> the car
+cdr(conscell) -> the cdr
+list(@items) -> a cons-cell representing the head of a list
+</code>
+Lists (cons-cells or the empty list) support the following operations:
+<code>
+// accessors for car and cdr
+car()
+cdr()
+// the length of the list
+length()
+// whether the list is empty or not
+isEmpty()
+// returns the nth element of the list
+nth(n)
+// apply a unary function to each element of the list
+each: fun
+// apply a function to each element and its index in the list
+// i.e. list.eachWithIndex: { |elt, idx| ... }
+eachWithIndex: fun
+// map a unary function over the list, returning a new list
+ map: fun
+// accumulate a value over a list
+inject: init into: accum
+// return a new list whose elements satisfy the unary predicate
+filter: cond
+// does the list contain the element?
+contains(elt, cmp := DEFAULTCOMPARATOR)
+// implode or join a list of text strings
+implode()
+join(txt)
+// return a range [start,stop] represented as a list
+select(start, stop)
+// prepend an element to the list
+add(elt)
+// insert an element in the list (functionally)
+insert(atPos, element)
+// return a new list where the element atPos is deleted
+delete(atPos)
+// functional append
+append(aList)
+// return the index of the first matching element, or nil if none is found
+find: filter
+// return the index in the list of the element or nil of not found
+indexOf(elt, cmp := DEFAULTCOMPARATOR)
+// return a list where the given element is removed
+remove(elt, cmp := DEFAULTCOMPARATOR)
+// return a new list where all objects for which filter(elt) is true are removed
+removeAll: filter
+// convert the list into a table
+asTable()
+</code>
+The file ''at/collections/list.at'' contains a unit test that further illustrates the usage of the list datastructure.