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
241 redef fun clear
do items
.clear
243 redef fun peek
do return items
.first
246 #assert assert_best else print "try to add {e}"
248 var ei
= items
.length
+ 1
252 if comparator
.compare
(p
, e
) <= 0 then break
261 #assert length == ol + 1
262 #assert assert_best else print "added {e}"
266 #assert assert_best else print "tri to take"
268 if length
< 2 then return items
.pop
270 var res
= items
.first
274 var last
= items
.length
278 if ci
> last
then break # no children
280 var upc
= comparator
.compare
(e
, c
) > 0
284 if c2i
<= last
then do
285 var c2
= items
[c2i-1
]
286 # possibility to bubble-down to c2, or not?
287 if comparator
.compare
(e
, c2
) <= 0 then break label
288 # c2 is a better path, or not?
289 if upc
and comparator
.compare
(c2
, c
) > 0 then break label
297 if not upc
then break
303 #assert length == ol - 1 else print "is {length}, expected {ol - 1}"
304 #assert assert_best else print "dequed {res}"
308 # Used internally do debug the Heap.
309 # Not removed because this can still be useful.
310 private fun assert_best
: Bool
312 if is_empty
then return true
314 for i
in self do if comparator
.compare
(b
, i
) > 0 then
315 #print " peek is {b} but better found {i}"