3.6 Collections

Slate's collection hierarchy makes use of multiple delegation to provide a collection system that can be reasoned about with greater certainty, and that can be extended more easily than other object-oriented languages' collection types.

Figure 1 shows the overview of the collection types, and how their delegation is patterned.

Figure 1: Core Collections Inheritance

All collections support a minimal set of methods, including support for basic internal iteration and testing. The following are representative core methods, and are by no means the limit of collection features:

3.6.0.1 Testing Methods

isEmpty

answers whether or not the collection has any elements in it.

includes:

answers whether the collection contains the object.

3.6.0.2 Properties

size

returns the number of elements in it. This is often calculated dynamically for extensible collections, so it's often useful to cache it in a calling method.

capacity

returns the size that the collection's implementation is currently ready for.

3.6.0.3 Making new collections

newSize:

returns a new collection of the same type that is sized to the argument.

newEmpty

returns a new collection of the same type that is sized to some small default value.

as:

alias newWithAll: has extensive support in the collection types to produce copies of the first collection with the type of the second.

3.6.0.4 Iterating

do:

executes a block with :each (the idiomatic input slot for iterating) of the collection's elements in turn. It returns the original collection.

collect:

also takes a block, but returns a collection with all the results of those block-applications put into a new collection of the appropriate type.

select:

takes a block that returns a Boolean and returns a new collection of the elements that the block filters (returns True).

3.6.1 Extensible Collections

Collections delegating to ExtensibleCollection respond to add:, remove:, and other protocol messages based upon them, such as the batch operations addAll: and removeAll:.

3.6.2 Sequences

Sequences are Mappings from a range of natural numbers to some objects, sometimes restricted to a given type. Slate sequences are all addressed from a base of 0.

To access and modify sequences, the basic methods seq at: index and
seq at: index put: object are provided.

3.6.2.1 Arrays

Arrays are fixed-length sequences and are supported primitively. Various parameter types of Array are supported primitively, such as WordArray, ByteArray, and String.

3.6.2.2 Vectors

Vectors and Tuples are fixed-length sequences constructed for geometrical purposes. Points happen to be Tuples. The constructor message for these types is ``,''.

3.6.2.3 Subsequences / Slices

Subsequences allow one to treat a segment of a sequence as a separate sequence with its own addressing scheme; however, modifying the subsequence will cause the original to be modified.

3.6.2.4 Cords

Cords are a non-copying representation of a concatenation of Sequences. Normal concatenation of Sequences is performed with the ; method, and results in copying both of the arguments into a new Sequence of the appropriate type; the ;; method will construct a Cord instead. They efficiently implement accessing via at: and iteration via do:, and Cord as: Sequence will ``flatten'' the Cord into a Sequence.

3.6.2.5 Extensible and Sorted Sequences

An ExtensibleSequence is an extensible Sequence with some special methods to treat both ends as queues. Adding to an ExtensibleSequence will add at the last index, at the ``end''.

A SortedSequence behaves similarly except that it will arrange for its members to remain sorted according to a block closure that compares two individual elements. A Heap is a SortedSequence designed for collecting elements in arbitrary order, and removing the first elements.

3.6.2.6 Stacks

A Stack is an ExtensibleSequence augmented with methods to honor the stack abstraction: push:, pop, top, etc.

3.6.2.7 Ranges

A Range is a Sequence of Numbers between two values, that is ordered consecutively and has some stepping value.

3.6.2.8 Buffers

A Buffer is a special ExtensibleSequence that takes extra care to only use one underlying array object, and also stores its elements in a ``wrap-around'' fashion, to make for an efficient queue for Streams (see BufferReadStream and BufferWriteStream (des:BufferReadStream)). One consequence of this is that a Buffer has a limited upper bound in size which the client must handle, although the capacity can be grown explicitly.

3.6.3 Strings and Characters

Strings in Slate are Arrays of Characters. Strings and characters have a special literal syntax, and methods specific to dealing with text.

3.6.4 Collections without Duplicates

NoDuplicatesCollection forms a special protocol that allows for extension in a well-mannered way. Instead of an add: protocol for extension, these collections provide include:, which ensures that at least one element of the collection is the target object, but doesn't do anything otherwise. Using include: will never add an object if it is already present. These collection types still respond to add: and its variants, but they will behave in terms of the include: semantics.

The default implementation of this protocol is Set, which stores its elements in a (somewhat sparse) hashed array.

3.6.5 Mappings and Dictionaries

Mappings provide a general protocol for associating the elements of a set of keys each to a value object. A Dictionary is essentially a Set of these Associations, but they are generally used with symbols as keys.

Mapping defines the general protocol at: and at:put: that Sequences use, which also happen to be Mappings. Mappings also support iteration protocols such as keysDo:, valuesDo:, and keysAndValuesDo:.

3.6.6 Linked Collections

A LinkedCollection provides a type of collection where the elements themselves are central to defining what is in the collection and what is not.

3.6.6.1 Linked Lists

The usual LinkedList type, comprised of individual Links with forward and backward directional access, is provided as a flexible but basic data structure.

3.6.6.2 Trees

Slate includes libraries for binary trees, red-black trees, trees with ordered elements, and tries.

3.6.6.3 Graphs

A directed graph, or Digraph (directed graph) type, is provided with associated Node and Edge types. A KeyedDigraph provides the same behavior with a keyed access, similar to that in a Mapping, although there is an allowance for various kinds of non-determinism, which makes this useful for creating Non-deterministic Finite Automata.

3.6.7 Vectors and Matrices

Slate includes the beginnings of a mathematical vector and matrix library. See the 'src/matrix.slate' file for an overview.