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.

Definition of a New Collection¶

The sorted-sequence.dylan file¶

A new collection class¶

Basic collection methods¶

Adding and removing elements¶

The forward-iteration protocol¶

The sorted-sequence-library.dylan file¶

The sorted-sequence.lid file¶

Summary¶

The `sorted-sequence.dylan` file¶

The `sorted-sequence-library.dylan` file¶

The `sorted-sequence.lid` file¶