Copyright (c) 1994 Carnegie Mellon University All rights reserved.The various modules in this library contain a few new types and operations which are compatible with the collection types specified in the Dylan Interim Reference Manual, but which are not part of that specification.
Users of Mindy 1.1 should be aware that the string-searching functions of the string-search module have been moved to the String-extensions library. The collection-extensions module "string-search" has for that reason been renamed "vector-search". The semantics of the moved functions have been changed, so string-search users are advised to read the String-extensions documentation.
It is to be expected that more collection types will appear in time, and they will likely be added to this library. This may also result in reorganizations which could force incompatible changes to the existing modules. We hope to minimize such imcompatibilities and, when forced to them, will include sufficient information to facilitate conversion of existing code.
The particular modules provided at present are:
define class <heap-item> (<object>); slot priority; slot data; end class <heap-item>;with appropriate methods defined for < and =. The user could, however, have simply a sorted list of integers, or have some item where the priority is an integral part of the item itself.
make on heaps supports the less-than: keyword, which supply the heap's comparison and defaults to <.
Heaps support all the usual sequence operations. The most useful ones:
push(heap, item) => updated-heap pop(heap) => smallest-element first(heap) => smallest-element second(heap) => second-smallest-element add!(heap, item) => updated-heap sort, sort! => sorted-sequenceThese are all "efficient" operations (defined below). As with <deque>, push is another name for add!, and does exactly the same thing except that push doesn't accept any keywords. sort and sort! return a sequence that's not a heap. Not necessarily efficient but useful anyhow:
add-new!(heap, item, #key test:, efficient:) => updated-heap remove!(heap, item, #key test:, efficient:) => updated-heap member?(heap, item, #key test:, efficient:) => <boolean>The efficient: keyword defaults to #f. If #t, it uses the random-iteration-protocol (which is considerably more efficient, but isn't really standard behavior, so it had to be optional). Conceivably most sequence methods could support such a keyword, but they don't yet.
The user can use element-setter or the iteration protocol to change an item in the heap, but changing the priority of an item is an error and Bad Things(tm) will happen. No error will be signaled. Both of these operations are very inefficient.
Heaps are not <stretchy-collection>s, although add! and pop can magically change the size of the heap.
Efficiency: Approximate running times of different operations are given below: (N is the size of the heap)
first, first-setter O(1) second (but not second-setter) O(1) size O(1) add! O(lg N) push O(lg N) pop(heap) O(lg N) sort, sort! O(N * lg N) forward-iteration-protocol setup: O(N) next-state: O(lg N) current-element: O(1) current-element-setter: O(N) backwards-iteration-protocol setup: O(N * lg N) next-state: O(1) current-element: O(1) current-element-setter: O(N) random-iteration-protocol setup: O(1) next-state: O(1) current-element: O(1) current-element-setter: O(1) element(heap, M) O(M*lg N + N) element-setter(value, heap, M) O(N + M*lg N + M)element, element-setter on arbitrary keys use the forward-iteration-protocol (via the inherited methods), and have accordingly bad performance.
Because they have a very low overhead, self-organizing lists may provide better peformance than hash tables in cases where references have a high degree of temporal locality. They may also be useful in situations where it is difficult to create a proper hash function.
Define new self-organizing-lists with
make(<self-organizing-list>, test: test)Test is expected to be an equality function. In particular, it is expected to satisfy the identity and transitivity requirements described in chapter 5. If not specified, test defaults to \==.
subsequence(sequence, start: 0, end: 3)where start: and end: are optional keywords which default to the beginning and end, respectively, of the source sequence. No other new operations are defined for subsequences, since all necessary operations are inherited from <sequence>.
Because subsequences are aliased references into other sequences, several properties must be remembered:
Efficiency notes:
subsequence(subsequence(source, start: 1), start: 2)would produce a subsequence identical to the one produced by
subsequence(source, start: 3)
The following functions are supplied: