15.5 Sorted sequences

Part of what process-aircraft will do in our example is to generate a collection of possible transition steps for aircraft in or around the airport. For example, if an aircraft is on the runway, then one possible transition step would be to move the aircraft to the taxiway. If there are many aircraft in the airport, there are many possible transitions that might take place at various time. The process-aircraft method needs to consider these transitions in order. That is, if an aircraft is ready to land on a runway in 5 minutes, but another one is ready to take off in 2 minutes, process-aircraft should attempt to complete the take-off transition before completing the landing transition. To keep these transitions in time order, we use a collection called a sorted sequence.

Dylan does not provide a sorted sequence class in its built-in collection library. However, Dylan does provide an extensible collection framework that permits us to define sorted sequences ourselves. In fact, Dylan already provides all the generic functions that we need to interact with sorted sequences: size, shallow-copy, element, add!, pop, remove!, and forward-iteration-protocol. We just need to provide methods for each of these generic functions that implement these operations for sorted sequences. By defining a method for forward-iteration-protocol, we allow sorted sequences to work with the standard Dylan collection iterators discussed in Chapter 11, Collections and Control Flow. Because sorted sequences are generally useful, we define them in their own library, in the same manner as we did the time and angle components.