3.8 Collections

Slate's collection hierarchy makes use of composing multiple behaviors (via inheritance) 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. Primarily Slate collections are mutable, which means that basic modifications occur destructively on the collection object.

Figure 2 shows the overview of the collection types, and how their inheritance is patterned.

Figure 2: 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.8.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.8.0.2 Properties

size

answers 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

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

3.8.0.3 Making new collections

new &capacity:

answers a new (empty) collection of the same type that is sized to the optional argument or a sensible default per type.

newSizeOf:

answers a new collection of the same type that is sized to same size that the argument has.

as: via newWithAll:

has extensive support in the collection types to produce collections of the type of the second with the contents of the first collection (vice versa for newWithAll: arguments).

3.8.0.4 Iterating

do:

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

collect:

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

select:

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

reject:

performs the logical opposite of select:, answering elements for which the block answers False.

inject: init into: accumulator

takes a two-argument accumulation block and applies it across the collection's elements. The initial value given becomes the first argument, and is replaced through the iterations with the result of the block.

reduce:

takes a two-argument block and performs the same action as inject:into: only using one of the collection's elements as an initial value.

project:

takes a block, answering a Dictionary or Mapping in general with each argument (member of the original collection) mapped to the result of applying the block to it.

3.8.1 Extensible Collections

Collections derived from ExtensibleCollection can be modified by adding or removing elements in various ways. The core protocol is:

add:

inserts the given object into the collection.

remove:

removes an object equal to the given one from the collection.

addAll:

inserts all elements from the first collection contained in the second.

removeAll:

removes all elements from the first collection contained in the second.

clear

removes all the elements from the collection.

3.8.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.

at:

answers the element at the index given.

at:put:

replaces the element at the index given with the object that is the last argument.

doWithIndex:

operates as do:, but applying the block with both the element as first argument and the index of the element in the Sequence as the second argument.

3.8.2.1 Arrays

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

3.8.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.8.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.8.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.8.2.5 Extensible and Sorted Sequences

An ExtensibleSequence is an extensible Sequence with some special methods to treat both ends as queues. It provides the following additional protocol:

addFirst:

inserts the given object at the beginning of the sequence.

addLast:

inserts the given object at the end of the sequence.

add:

inserts the given object at the end of the sequence (it's addLast:).

first:

answers a sequence of the first N elements.

last:

answers a sequence of the final N elements.

removeFirst

removes the first element from the sequence.

removeLast

removes the final element from the sequence.

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; as a result, it should not be manipulated except via add: and remove: since it maintains its own ordering. A Heap is a SortedSequence designed for collecting elements in arbitrary order, and removing the first elements.

3.8.2.6 Stacks

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

3.8.2.7 Ranges

A Range is a Sequence of Numbers between two values, that is ordered consecutively and has some stepping value; they include the start value and also the end value unless the stepping doesn't lead to the end value exactly, in which case the last value is the greatest value in the sequence that is still before the end marker value. Creating ranges is identical to the numeric iteration protocol in 3.5.4, without the final do: keyword, and sending the do: message to a Range performs the identical function.

3.8.2.8 Buffers

A RingBuffer 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 ReadBufferStream and WriteBufferStream (des:ReadBufferStream)). One consequence of this is that a RingBuffer has a limited upper bound in size which the client must handle, although the capacity can be grown explicitly.

3.8.3 Strings and Characters

Strings in Slate are non-extensible, mutable Sequences of Characters (although ExtensibleSequences can easily be made for them via, say, as:). Strings and Characters have a special literal syntax, and methods specific to dealing with text; most of the useful generic methods for strings are lifted to the Sequence type. Strings provide the following specific protocol:

lexicographicallyCompare:

performs an in-order comparison of the codes of the constituent Characters of the String arguments, returning the sign of comparison, +1 if the first argument is greater, 0 if equal, and -1 if lesser.

capitalize

uppercases in-place the first Character in the String.

toUppercase

uppercases in-place all Characters in the String.

toLowercase

lowercases in-place all Characters in the String.

toSwapCase

toggles in-place the case of all Characters in the String.

toCamelCase &separators:

splits the String up according to the given separators (defaulting to whitespace), joining capitalize'd versions of each element.

fromCamelCase &separator:

splits the String up according to capitalization transition boundaries and joins the elements together with the given separator.

escaped

answers a new String based on adding slash-escapes for literal printing so it can be read in as the same value.

unescaped

answers a new String based on removing slash-escapes, the same way that parsing is done.

readFrom:

takes a String or a Stream with compatible contents and parses the first available data as a String with the relevant escape interpretation.

plural

uses English rules to answer a new regular plural form of the argument String.

asAn

uses English rules to answer a new String with 'a ' or 'an ' prepended.

3.8.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.8.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.8.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.8.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. This type does require that its elements follow the Link protocol, however, so it does require some advanced preparation to use it.

3.8.6.2 Trees

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

3.8.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.8.7 Vectors and Matrices

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