Definition of a New Collection#
In this chapter, we implement a data structure called a sorted sequence. A sorted sequence is a sequence that automatically keeps the elements of the sequence in a particular order, based on some value computed from each element. Elements are added and removed from sorted sequences; however, the sorted sequence determines the key associated with the element. Thus, it does not make sense to store an element in a sorted sequence at a specific key, because the sorted sequence will determine the correct key to satisfy the automatic-ordering constraint.
We use Dylan’s forward-iteration-protocol to implement the connection
between our new collection class and Dylan’s standard collection generic
functions. Dylan’s forward-iteration protocol is a well-defined
interface that collection implementors and collection-iterator
implementors can use to enable iterators to operate over new
collections, and to enable collections to work with new iterators. Once
the forward iteration protocol is defined on <sorted-sequence>, many
of the standard Dylan collection generic functions that we covered in
Collections and Control Flow, will work with instances of the new sequence.
The airport application uses a sorted sequence to keep track of aircraft transition in time order. See The Airport Application, for more details.
The sorted-sequence.dylan file#
The sorted-sequence.dylan file contains the module constants, classes,
and methods that build on Dylan’s collection framework to define the
structure and behavior of the new <sorted-sequence> collection.
A new collection class#
The sorted-sequence.dylan file.
module: sorted-sequence
define class <sorted-sequence> (<sequence>)
// The vector that stores the elements of the sorted sequence, in order
slot data :: <stretchy-vector> = make(<stretchy-vector>, size: 0);
// The function used to extract the comparison value from an element
constant slot value-function :: <function> = identity,
init-keyword: value-function:;
// The function used to determine whether one comparison value is
// smaller than another comparison value
constant slot comparison-function :: <function> = \<,
init-keyword: comparison-function:;
end class <sorted-sequence>;
Because is there is a well-defined ordering of the elements of sorted
sequences, we choose <sequence> to be the superclass of
<sorted-sequence>. We use the built-in collection class called
<stretchy-vector> to store the elements of our sorted sequence,
because we want to be able to have the sorted sequence grow to any size
in a convenient way.
The slots comparison-function and value-function are constant slots,
because we intend to have clients specify these functions only when they
create the sorted sequence. If we had decided to let clients change the
value of these slots, we would have made the slots virtual, so that we
could reorder the data vector after either function had changed.
Now that we have covered the structure and initialization of the sorted sequence data structure, we can define basic collection methods.
Basic collection methods#
The sorted-sequence.dylan file. (continued)
define method size (sorted-sequence :: <sorted-sequence>)
=> (sorted-sequence-size :: <integer>)
sorted-sequence.data.size;
end method size;
define method shallow-copy (sorted-sequence :: <sorted-sequence>)
=> (copy :: <sorted-sequence>)
let copy
= make(<sorted-sequence>,
value-function: sorted-sequence.value-function,
comparison-function: sorted-sequence.comparison-function);
// The map-into function replaces the elements of the copy’s data array
// to be the identical elements of the data array of sorted sequence
copy.data.size := sorted-sequence.data.size;
map-into(copy.data, identity, sorted-sequence.data);
copy;
end method shallow-copy;
define constant $unsupplied = list(#f);
define method element
(sorted-sequence :: <sorted-sequence>, key :: <integer>,
#key default = $unsupplied)
=> (element :: <object>);
if (key < sorted-sequence.data.size)
sorted-sequence.data[key];
elseif (default = $unsupplied)
error("Attempt to access key %= which is outside of %=.", key,
sorted-sequence);
else default;
end if;
end method element;
In the preceding code, we define methods for determining the number of
elements in the sorted sequence, for copying the sorted sequence (but
not the elements stored in the sorted sequence), and for accessing a
particular item in the sorted sequence. Once we have defined the
element method for sorted sequences, we can use the subscripting
syntax to access particular items in the sorted sequence. Our element
method implements the standard Dylan protocol, which allows the caller
to specify a default value if the key is not contained within the
collection. If the key is not part of the collection, and no default
value is specified, then an error is signaled. Since we do not export
$unsupplied from our library, we can be certain that no one can supply
that value as the default keyword parameter for our element method.
Note that the element-setter method is not defined, because it does
not make sense to store an element at a particular position within the
sorted sequence. The sorted sequence itself determines the correct key
for each item added to the sorted sequence, based on the item being
added and on the value and comparison functions.
Next, we show methods for adding and removing elements from sorted sequences.
Adding and removing elements#
The sorted-sequence.dylan file. (continued)
// Add an element to the sorted sequence
define method add!
(sorted-sequence :: <sorted-sequence>, new-element :: <object>)
=> (sorted-sequence :: <sorted-sequence>)
let element-value = sorted-sequence.value-function;
let compare = sorted-sequence.comparison-function;
add!(sorted-sequence.data, new-element);
sorted-sequence.data
:= sort!(sorted-sequence.data,
test: method (e1, e2)
compare(element-value(e1), element-value(e2))
end);
sorted-sequence;
end method add!;
// Remove the item at the top of the sorted sequence
define method pop (sorted-sequence :: <sorted-sequence>)
=> (top-of-sorted-sequence :: <object>)
let data-vector = sorted-sequence.data;
let top-of-sorted-sequence = data-vector[0];
let sorted-sequence-size = data-vector.size;
if (empty?(sorted-sequence))
error("Trying to pop empty sorted-sequence %=.", sorted-sequence);
else
// Shuffle up existing data, removing the top element from the
// sorted sequence
for (i from 0 below sorted-sequence-size - 1)
data-vector[i] := data-vector[i + 1];
end for;
// Decrease the size of the data vector, and return the top element
data-vector.size := sorted-sequence-size - 1;
top-of-sorted-sequence;
end if;
end method pop;
// Remove a particular element from the sorted sequence
define method remove!
(sorted-sequence :: <sorted-sequence>, value :: <object>,
#key test = \==, count = #f)
=> (sorted-sequence :: <sorted-sequence>)
let data-vector = sorted-sequence.data;
let sorted-sequence-size = data-vector.size;
for (deletion-point from 0,
// If we have reached the end of the sequence, or we have reached
// the user-specified limit, we are done
// Note that specifying a bound in the preceding clause for
// deletion-point does not work, because bounds are computed only
// once, and we change sorted-sequence-size in the body
until: (deletion-point >= sorted-sequence-size)
| (count & count = 0))
// Otherwise, if we found a matching element, remove it from the
// sorted sequence.
if (test(data-vector[deletion-point], value))
for (i from deletion-point below sorted-sequence-size - 1)
data-vector[i] := data-vector[i + 1]
end for;
sorted-sequence-size
:= (data-vector.size := sorted-sequence-size - 1);
if (count) count := count - 1 end;
end if;
end for;
sorted-sequence;
end method remove!;
The remove! method uses a form of the for loop that includes an
until: clause, much like the my-copy-sequence method defined in
Lists and efficiency. Note that all termination checks are tested
prior to the execution of the body.
Although the pop method is not used in the airport application, it is
included for completeness. We could make the pop method faster by
storing the data elements in reverse order; however, that would lead to
either odd behavior or odd implementation of the element function on
sorted sequences.
The forward-iteration protocol#
Dylan’s forward-iteration protocol allows us to connect the usual
collection iteration functions to our new collection class. Connecting
to the forward-iteration protocol is as simple as defining an
appropriate method for the forward-iteration-protocol generic
function. This method must return two objects and six functions.
The sorted-sequence.dylan file. (continued)
// This method enables many standard and user-defined collection operations
define method forward-iteration-protocol
(sorted-sequence :: <sorted-sequence>)
=> (initial-state :: <integer>, limit :: <integer>,
next-state :: <function>, finished-state? :: <function>,
current-key :: <function>, current-element :: <function>,
current-element-setter :: <function>, copy-state :: <function>)
values(
// Initial state
0,
// Limit
sorted-sequence.size,
// Next state
method (collection :: <sorted-sequence>, state :: <integer>)
state + 1
end,
// Finished state?
method (collection :: <sorted-sequence>, state :: <integer>,
limit :: <integer>)
state = limit;
end,
// Current key
method (collection :: <sorted-sequence>, state :: <integer>)
state
end,
// Current element
element,
// Current element setter
method (value :: <object>, collection :: <sorted-sequence>,
state :: <integer>)
error("Setting an element of a sorted sequence is not allowed.");
end,
// Copy state
identity);
end method forward-iteration-protocol;
If we are to iterate over any collection, we must maintain some state to
help the iterator remember the current point of iteration. For the
forward-iteration protocol, we maintain this state using any object
suitable for a given collection. In this case, an integer is sufficient
to maintain where we are in the iteration process. The first object
returned by forward-iteration-protocol is a state object that is
suitable for the start of an iteration. The second object returned is a
state object that represents the ending state of the iteration. Since,
in this case, the state object is just the current key of the sorted
sequence, the integer 0 is the correct initial state, and the integer
that represents the size of the collection is the correct ending state.
The third value returned is a function that takes the collection and the current iteration state, and returns a state that is the next step in the iteration. In this case, we can determine the next state simply by adding 1 to the current state.
The fourth value returned is a function that receives the collection, the current state, and the ending state, and that determines whether the iteration is complete. In this case, we need only to check whether the current state is equal to the ending state.
The fifth value returned is a function that generates the current key into the collection, given a collection and a state. In this case, the key is the state object.
The sixth value returned is a function that receives a collection and a
state, and returns the current element of the collection. In this case,
the element function is the obvious choice, since our state is just
the key.
The seventh value returned is a function that receives a new value, a
collection, and a state, and changes the current element to be the new
value. In this case, such an operation is illegal, since the only
rational way to add elements to sorted sequences is with add!.
Because this operation is illegal, an error is signaled.
The eighth and final value returned is a function that receives a collection and a state, and returns a copy of the state. In this case, we just return the state, because it is an integer and thus has no slots that are modified during the iteration process. If we represented the state with an object that had one or more slots that did change during iteration, we would have to make a new state instance and to copy the significant information from the old state instance to the new state instance.
Once we have defined a forward-iteration-protocol method for sorted
sequences, we can iterate over them using for loops, mapping
functions, and other collections iterators described in Collections and Control Flow.
Also, if someone defines a new iterator that uses the forward-iteration
protocol, then this new iterator will work with sorted sequences.
Dylan has several other related protocols for backward iteration and for tables. See the The Dylan Reference Manual for details.
The sorted-sequence-library.dylan file#
The definitions for the sorted sequence library and module are simple.
The only module variable that we need to export is for the sorted
sequence class itself. All the generic functions that we want clients to
use on sorted sequences are exported by the dylan module.
The sorted-sequence-library.dylan file.
module: dylan-user
define library sorted-sequence
export sorted-sequence;
use dylan;
use definitions;
end library sorted-sequence;
define module sorted-sequence
export <sorted-sequence>;
use dylan;
use definitions;
end module sorted-sequence;
The definitions library and module are defined in The Airport Application.
The sorted-sequence.lid file#
The LID file for sorted sequences is also straightforward. The entire
library is contained within two files (in addition to the LID file
itself). The library and module definitions are in the file
sorted-sequence-library.dylan. The definitions of module constants,
classes, and methods are in the implementation file,
sorted-sequence.dylan.
The sorted-sequence.lid file.
library: sorted-sequence
files: sorted-sequence-library
sorted-sequence
Summary#
In this chapter, we covered the following:
We explored how to define our own collection class.
We showed how to integrate that class into Dylan’s collection framework.
We used several variations of the control structures presented in Collections and Control Flow.