1 # This file is part of NIT ( http://www.nitlanguage.org ).
3 # This file is free software, which comes along with NIT. This software is
4 # distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
5 # without even the implied warranty of MERCHANTABILITY or FITNESS FOR A
6 # PARTICULAR PURPOSE. You can modify it is you want, provided this header
7 # is kept unaltered, and a notification of the changes is added.
8 # You are allowed to redistribute it and sell it, alone or is a part of
11 # Queuing data structures and wrappers
12 # Provides a queue abstraction for LIFO, FIFO (stack) and heaps.
16 # * `Sequence::as_lifo`
17 # * `Sequence::as_fifo`
18 # * `SimpleCollection::as_random`
22 import collection
::array
23 import collection
::sorter
26 # Queues are collection that controls how elements are retrieved.
28 # This interface is used for data structures and algorithms that need
29 # some queuing but that let their users control how the queuing is done.
31 # Most concrete queues have an efficient implementation of the basic methods
32 # `is_empty`, `length`, `add`, `peek`, and `take`.
33 # However, the `remove` method is possibly inefficient.
34 # To workaround an inefficient implementation, one can instead mark the removed
35 # elements (with a flag or in a set), and ignore then when `take` returns one.
37 # Unless stated otherwise, the `iterator` method is unrelated with the queue
38 # logic and may visit the elements in a order dependent on implementation.
40 super SimpleCollection[E
]
42 # Take the next element (according to the specific queue)
44 # var a = (new Array[Int]).as_lifo
50 # var h = new MinHeap[Int].default
58 # ensure `result == peek`
59 fun take
: E
is abstract
61 # Look at the next element but does not remove it
64 # var a = (new Array[Int]).as_lifo
72 fun peek
: E
is abstract
74 # `first` is made an alias of `peek` to avoid bad surprises
75 redef fun first
do return peek
77 # Take and return all elements until the queue is empty
79 # ensure `result.length == old(length)`
80 # ensure `not old(is_empty) implies result.first == old(peek)`
82 # var a = (new Array[Int]).as_lifo
86 # assert a.take_all == [3, 2, 1]
89 fun take_all
: Array[E
]
91 var res
= new Array[E
]
92 while not is_empty
do res
.add take
97 redef class Sequence[E
]
98 # Return a LIFO proxy queue (stack) where `result.take` is `pop`.
100 # The point of such a proxy is to let the user choose the underling data structure
113 fun as_lifo
: Queue[E
] do return new LifoQueue[E
](self)
115 # Return a FIFO proxy queue where `result.take` is `shift`.
117 # The point of such a proxy is to let the user choose the underling data structure
120 # Note that some `Sequence`, like `Array`, have an inefficient `shift` implementation,
121 # thus are not the best candidates to serve as a FIFO.
124 # var a = new List[Int].from([1,2,3])
130 # assert a == [3, 4, 5]
132 fun as_fifo
: Queue[E
] do return new FifoQueue[E
](self)
135 # Factorize common proxy implementation
136 private abstract class ProxyQueue[E
]
140 redef fun add
(e
) do seq
.add
(e
)
141 redef fun length
do return seq
.length
142 redef fun is_empty
do return seq
.is_empty
143 redef fun iterator
do return seq
.iterator
144 redef fun remove
(e
) do seq
.remove
(e
)
148 private class LifoQueue[E
]
150 redef fun take
do return seq
.pop
151 redef fun peek
do return seq
.last
154 private class FifoQueue[E
]
156 redef fun take
do return seq
.shift
157 redef fun peek
do return seq
.first
161 redef class SimpleCollection[E
]
162 # Return a random proxy queue where `result.take` is random.
164 # The point of such a proxy is to provide a randomized removal.
168 # var b = a.as_random.take
169 # assert b == 1 or b == 2 or b == 3 # Eh, it is random!
171 fun as_random
: Queue[E
] do return new RandQueue[E
](self)
174 private class RandQueue[E
]
176 var seq
: SimpleCollection[E
]
180 # Reset the cache to give the new element a chance!
191 if peek_cached
then return peek_cache
197 var peek_cached
= false
198 var peek_cache
: E
is noinit
199 redef fun length
do return seq
.length
200 redef fun is_empty
do return seq
.is_empty
201 redef fun iterator
do return seq
.iterator
202 redef fun remove
(e
) do seq
.remove
(e
)
206 # A min-heap implemented over an array
208 # The order is given by the `comparator`.
212 # var h = new MinHeap[Int].default
216 # assert b == [1, 2, 3, 4]
218 class MinHeap[E
: Object]
221 private var items
= new Array[E
]
223 # The comparator used to order the Heap
224 var comparator
: Comparator
226 # Use the `default_comparator` on Comparable elements
228 # Require self isa MinHeap[Comparable]
231 assert self isa MinHeap[Comparable]
232 init(default_comparator
)
235 init(comparator
: Comparator) do self.comparator
= comparator
237 redef fun is_empty
do return items
.is_empty
238 redef fun length
do return items
.length
239 redef fun iterator
do return items
.iterator
241 redef fun peek
do return items
.first
244 #assert assert_best else print "try to add {e}"
246 var ei
= items
.length
+ 1
250 if comparator
.compare
(p
, e
) <= 0 then break
259 #assert length == ol + 1
260 #assert assert_best else print "added {e}"
264 #assert assert_best else print "tri to take"
266 if length
< 2 then return items
.pop
268 var res
= items
.first
272 var last
= items
.length
276 if ci
> last
then break # no children
278 var upc
= comparator
.compare
(e
, c
) > 0
282 if c2i
<= last
then do
283 var c2
= items
[c2i-1
]
284 # possibility to bubble-down to c2, or not?
285 if comparator
.compare
(e
, c2
) <= 0 then break label
286 # c2 is a better path, or not?
287 if upc
and comparator
.compare
(c2
, c
) > 0 then break label
295 if not upc
then break
301 #assert length == ol - 1 else print "is {length}, expected {ol - 1}"
302 #assert assert_best else print "dequed {res}"
306 # Used internally do debug the Heap.
307 # Not removed because this can still be useful.
308 private fun assert_best
: Bool
310 if is_empty
then return true
312 for i
in self do if comparator
.compare
(b
, i
) > 0 then
313 #print " peek is {b} but better found {i}"