16 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 Chapter 11, 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 Chapter 17, The Airport Application, for more details.