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.
81 # * `result.length == old(length)`
82 # * `not old(is_empty) implies result.first == old(peek)`
85 # var a = (new Array[Int]).as_lifo
89 # assert a.take_all == [3, 2, 1]
92 fun take_all
: Array[E
]
94 var res
= new Array[E
]
95 while not is_empty
do res
.add take
100 redef class Sequence[E
]
101 # Return a LIFO proxy queue (stack) where `result.take` is `pop`.
103 # The point of such a proxy is to let the user choose the underling data structure
116 fun as_lifo
: Queue[E
] do return new LifoQueue[E
](self)
118 # Return a FIFO proxy queue where `result.take` is `shift`.
120 # The point of such a proxy is to let the user choose the underling data structure
123 # Note that some `Sequence`, like `Array`, have an inefficient `shift` implementation,
124 # thus are not the best candidates to serve as a FIFO.
127 # var a = new List[Int].from([1,2,3])
133 # assert a == [3, 4, 5]
135 fun as_fifo
: Queue[E
] do return new FifoQueue[E
](self)
138 # Factorize common proxy implementation
139 private abstract class ProxyQueue[E
]
143 redef fun add
(e
) do seq
.add
(e
)
144 redef fun length
do return seq
.length
145 redef fun is_empty
do return seq
.is_empty
146 redef fun iterator
do return seq
.iterator
147 redef fun remove
(e
) do seq
.remove
(e
)
151 private class LifoQueue[E
]
153 redef fun take
do return seq
.pop
154 redef fun peek
do return seq
.last
157 private class FifoQueue[E
]
159 redef fun take
do return seq
.shift
160 redef fun peek
do return seq
.first
164 redef class SimpleCollection[E
]
165 # Return a random proxy queue where `result.take` is random.
167 # The point of such a proxy is to provide a randomized removal.
171 # var b = a.as_random.take
172 # assert b == 1 or b == 2 or b == 3 # Eh, it is random!
174 fun as_random
: Queue[E
] do return new RandQueue[E
](self)
177 private class RandQueue[E
]
179 var seq
: SimpleCollection[E
]
183 # Reset the cache to give the new element a chance!
194 if peek_cached
then return peek_cache
200 var peek_cached
= false
201 var peek_cache
: E
is noinit
202 redef fun length
do return seq
.length
203 redef fun is_empty
do return seq
.is_empty
204 redef fun iterator
do return seq
.iterator
205 redef fun remove
(e
) do seq
.remove
(e
)
209 # A min-heap implemented over an array
211 # The order is given by the `comparator`.
215 # var h = new MinHeap[Int].default
219 # assert b == [1, 2, 3, 4]
221 class MinHeap[E
: Object]
224 private var items
= new Array[E
]
226 # The comparator used to order the Heap
227 var comparator
: Comparator
229 # Use the `default_comparator` on Comparable elements
231 # Require self isa MinHeap[Comparable]
234 assert self isa MinHeap[Comparable]
235 init(default_comparator
)
238 redef fun is_empty
do return items
.is_empty
239 redef fun length
do return items
.length
240 redef fun iterator
do return items
.iterator
242 redef fun peek
do return items
.first
245 #assert assert_best else print "try to add {e}"
247 var ei
= items
.length
+ 1
251 if comparator
.compare
(p
, e
) <= 0 then break
260 #assert length == ol + 1
261 #assert assert_best else print "added {e}"
265 #assert assert_best else print "tri to take"
267 if length
< 2 then return items
.pop
269 var res
= items
.first
273 var last
= items
.length
277 if ci
> last
then break # no children
279 var upc
= comparator
.compare
(e
, c
) > 0
283 if c2i
<= last
then do
284 var c2
= items
[c2i-1
]
285 # possibility to bubble-down to c2, or not?
286 if comparator
.compare
(e
, c2
) <= 0 then break label
287 # c2 is a better path, or not?
288 if upc
and comparator
.compare
(c2
, c
) > 0 then break label
296 if not upc
then break
302 #assert length == ol - 1 else print "is {length}, expected {ol - 1}"
303 #assert assert_best else print "dequed {res}"
307 # Used internally do debug the Heap.
308 # Not removed because this can still be useful.
309 private fun assert_best
: Bool
311 if is_empty
then return true
313 for i
in self do if comparator
.compare
(b
, i
) > 0 then
314 #print " peek is {b} but better found {i}"