lib/standard/queue.nit

   1 # This file is part of NIT ( http://www.nitlanguage.org ).
   2 #
   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
   9 # another product.
  10
  11 # Queuing data structures and wrappers
  12 # Provides a queue abstraction for LIFO, FIFO (stack) and heaps.
  13 #
  14 # Topics:
  15 # * `Queue`
  16 # * `Sequence::as_lifo`
  17 # * `Sequence::as_fifo`
  18 # * `SimpleCollection::as_random`
  19 # * `MinHeap`
  20 module queue
  21
  22 import collection::array
  23 import collection::sorter
  24 import math
  25
  26 # Queues are collection that controls how elements are retrieved.
  27 #
  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.
  30 #
  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.
  36 #
  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.
  39 interface Queue[E]
  40         super SimpleCollection[E]
  41
  42         # Take the next element (according to the specific queue)
  43         # ~~~
  44         # var a = (new Array[Int]).as_lifo
  45         # a.add 1
  46         # a.add 2
  47         # assert a.take == 2
  48         # assert a.take == 1
  49         #
  50         # var h = new MinHeapCmp[Int]
  51         # h.add 2
  52         # h.add 1
  53         # h.add 10
  54         # assert h.take == 1
  55         # assert h.take == 2
  56         # assert h.take == 10
  57         # ~~~
  58         # ensure `result == peek`
  59         fun take: E is abstract
  60
  61         # Look at the next element but does not remove it
  62         #
  63         # ~~~
  64         # var a = (new Array[Int]).as_lifo
  65         # a.add 1
  66         # assert a.peek == 1
  67         # a.add 2
  68         # assert a.peek == 2
  69         # assert a.take == 2
  70         # assert a.peek == 1
  71         # ~~~
  72         fun peek: E is abstract
  73
  74         # `first` is made an alias of `peek` to avoid bad surprises
  75         redef fun first do return peek
  76
  77         # Take and return all elements until the queue is empty
  78         # ensure `is_empty`
  79         # ensure `result.length == old(length)`
  80         # ensure `not old(is_empty) implies result.first == old(peek)`
  81         # ~~~
  82         # var a = (new Array[Int]).as_lifo
  83         # a.add 1
  84         # a.add 2
  85         # a.add 3
  86         # assert a.take_all == [3, 2, 1]
  87         # assert a.is_empty
  88         # ~~~
  89         fun take_all: Array[E]
  90         do
  91                 var res = new Array[E]
  92                 while not is_empty do res.add take
  93                 return res
  94         end
  95 end
  96
  97 redef class Sequence[E]
  98         # Return a LIFO proxy queue (stack) where `result.take` is `pop`.
  99         #
 100         # The point of such a proxy is to let the user choose the underling data structure
 101         # behind the LIFO.
 102         #
 103         # ~~~
 104         # var a = [1, 2, 3]
 105         # var q = a.as_lifo
 106         # assert q.take == 3
 107         # assert q.take == 2
 108         # q.add(4)
 109         # q.add(5)
 110         # assert q.take == 5
 111         # assert a == [1, 4]
 112         # ~~~
 113         fun as_lifo: Queue[E] do return new LifoQueue[E](self)
 114
 115         # Return a FIFO proxy queue where `result.take` is `shift`.
 116         #
 117         # The point of such a proxy is to let the user choose the underling data structure
 118         # behind the FIFO.
 119         #
 120         # Note that some `Sequence`, like `Array`, have an inefficient `shift` implementation,
 121         # thus are not the best candidates to serve as a FIFO.
 122         #
 123         # ~~~
 124         # var a = new List[Int].from([1,2,3])
 125         # var q = a.as_fifo
 126         # assert q.take == 1
 127         # q.add(4)
 128         # q.add(5)
 129         # assert q.take == 2
 130         # assert a == [3, 4, 5]
 131         # ~~~
 132         fun as_fifo: Queue[E] do return new FifoQueue[E](self)
 133 end
 134
 135 # Factorize common proxy implementation
 136 private abstract class ProxyQueue[E]
 137         super Queue[E]
 138         var seq: Sequence[E]
 139
 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)
 145 end
 146
 147
 148 private class LifoQueue[E]
 149         super ProxyQueue[E]
 150         redef fun take do return seq.pop
 151         redef fun peek do return seq.last
 152 end
 153
 154 private class FifoQueue[E]
 155         super ProxyQueue[E]
 156         redef fun take do return seq.shift
 157         redef fun peek do return seq.first
 158 end
 159
 160
 161 redef class SimpleCollection[E]
 162         # Return a random proxy queue where `result.take` is random.
 163         #
 164         # The point of such a proxy is to provide a randomized removal.
 165         #
 166         # ~~~
 167         # var a = [1,2,3]
 168         # var b = a.as_random.take
 169         # assert b == 1 or b == 2 or b == 3 # Eh, it is random!
 170         # ~~~
 171         fun as_random: Queue[E] do return new RandQueue[E](self)
 172 end
 173
 174 private class RandQueue[E]
 175         super Queue[E]
 176         var seq: SimpleCollection[E]
 177         redef fun add(e)
 178         do
 179                 seq.add(e)
 180                 # Reset the cache to give the new element a chance!
 181                 peek_cached = false
 182         end
 183         redef fun take
 184         do
 185                 var res = peek
 186                 peek_cached = false
 187                 seq.remove(res)
 188                 return res
 189         end
 190         redef fun peek do
 191                 if peek_cached then return peek_cache
 192                 var res = seq.rand
 193                 peek_cache = res
 194                 peek_cached = true
 195                 return res
 196         end
 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)
 203 end
 204
 205
 206 # A min-heap implemented over an array
 207 #
 208 # The order is given by the `comparator`.
 209 # If `E` is Comparable, then the subclass `MinHeapCmp` can be used instead.
 210 #
 211 # ~~~
 212 # var a = [3,4,1,2]
 213 # var h = new MinHeap[Int](new DefaultComparator[Int])
 214 # h.add_all(a)
 215 # assert h.peek == 1
 216 # var b = h.take_all
 217 # assert b == [1, 2, 3, 4]
 218 # ~~~
 219 class MinHeap[E: Object]
 220         super Queue[E]
 221
 222         private var items = new Array[E]
 223         var comparator: Comparator[E]
 224
 225         redef fun is_empty do return items.is_empty
 226         redef fun length do return items.length
 227         redef fun iterator do return items.iterator
 228
 229         redef fun peek do return items.first
 230         redef fun add(e)
 231         do
 232                 #assert assert_best else print "try to add {e}"
 233                 #var ol = length
 234                 var ei = items.length + 1
 235                 while ei > 1 do
 236                         var pi = ei/2
 237                         var p = items[pi-1]
 238                         if comparator.compare(p, e) <= 0 then break
 239
 240                         # bubble-up
 241                         items[ei-1] = p
 242
 243                         # next
 244                         ei = pi
 245                 end
 246                 items[ei-1] = e
 247                 #assert length == ol + 1
 248                 #assert assert_best else print "added {e}"
 249         end
 250
 251         redef fun take do
 252                 #assert assert_best else print "tri to take"
 253                 #var ol = length
 254                 if length < 2 then return items.pop
 255
 256                 var res = items.first
 257                 var ei = 1
 258                 var e = items.pop
 259
 260                 var last = items.length
 261                 loop
 262                         # Check first child
 263                         var ci = ei*2
 264                         if ci > last then break # no children
 265                         var c = items[ci-1]
 266                         var upc = comparator.compare(e, c) > 0
 267
 268                         # Check second child
 269                         var c2i = ci + 1
 270                         if c2i <= last then do
 271                                 var c2 = items[c2i-1]
 272                                 # possibility to bubble-down to c2, or not?
 273                                 if comparator.compare(e, c2) <= 0 then break label
 274                                 # c2 is a better path, or not?
 275                                 if upc and comparator.compare(c2, c) > 0 then break label
 276                                 # goes to c2 path
 277                                 upc = true
 278                                 c = c2
 279                                 ci = c2i
 280                         end label
 281
 282                         # bubble-down?
 283                         if not upc then break
 284
 285                         items[ei-1] = c
 286                         ei = ci
 287                 end
 288                 items[ei-1] = e
 289                 #assert length == ol - 1 else print "is {length}, expected {ol - 1}"
 290                 #assert assert_best else print "dequed {res}"
 291                 return res
 292         end
 293
 294         # Used internally do debug the Heap.
 295         # Not removed because this can still be useful.
 296         private fun assert_best: Bool
 297         do
 298                 if is_empty then return true
 299                 var b = peek
 300                 for i in self do if comparator.compare(b, i) > 0 then
 301                         #print "  peek is {b} but better found {i}"
 302                         for j in self do
 303                                 #print "   {j}"
 304                         end
 305                         return false
 306                 end
 307                 return true
 308         end
 309 end
 310
 311 # A `MinHeap` for `Comparable` that does not need a specific `Comparator`
 312 #
 313 # ~~~
 314 # var a = [3,4,1,2]
 315 # var h = new MinHeapCmp[Int]
 316 # h.add_all(a)
 317 # assert h.peek == 1
 318 # var b = h.take_all
 319 # assert b == [1, 2, 3, 4]
 320 # ~~~
 321 class MinHeapCmp[E: Comparable]
 322         super MinHeap[E]
 323         init is old_style_init do super(new DefaultComparator[E])
 324 end