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 MinHeap[Int].default
  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         #
  79         # Ensure:
  80         # * `is_empty`
  81         # * `result.length == old(length)`
  82         # * `not old(is_empty) implies result.first == old(peek)`
  83         #
  84         # ~~~
  85         # var a = (new Array[Int]).as_lifo
  86         # a.add 1
  87         # a.add 2
  88         # a.add 3
  89         # assert a.take_all == [3, 2, 1]
  90         # assert a.is_empty
  91         # ~~~
  92         fun take_all: Array[E]
  93         do
  94                 var res = new Array[E]
  95                 while not is_empty do res.add take
  96                 return res
  97         end
  98 end
  99
 100 redef class Sequence[E]
 101         # Return a LIFO proxy queue (stack) where `result.take` is `pop`.
 102         #
 103         # The point of such a proxy is to let the user choose the underling data structure
 104         # behind the LIFO.
 105         #
 106         # ~~~
 107         # var a = [1, 2, 3]
 108         # var q = a.as_lifo
 109         # assert q.take == 3
 110         # assert q.take == 2
 111         # q.add(4)
 112         # q.add(5)
 113         # assert q.take == 5
 114         # assert a == [1, 4]
 115         # ~~~
 116         fun as_lifo: Queue[E] do return new LifoQueue[E](self)
 117
 118         # Return a FIFO proxy queue where `result.take` is `shift`.
 119         #
 120         # The point of such a proxy is to let the user choose the underling data structure
 121         # behind the FIFO.
 122         #
 123         # Note that some `Sequence`, like `Array`, have an inefficient `shift` implementation,
 124         # thus are not the best candidates to serve as a FIFO.
 125         #
 126         # ~~~
 127         # var a = new List[Int].from([1,2,3])
 128         # var q = a.as_fifo
 129         # assert q.take == 1
 130         # q.add(4)
 131         # q.add(5)
 132         # assert q.take == 2
 133         # assert a == [3, 4, 5]
 134         # ~~~
 135         fun as_fifo: Queue[E] do return new FifoQueue[E](self)
 136 end
 137
 138 # Factorize common proxy implementation
 139 private abstract class ProxyQueue[E]
 140         super Queue[E]
 141         var seq: Sequence[E]
 142
 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)
 148 end
 149
 150
 151 private class LifoQueue[E]
 152         super ProxyQueue[E]
 153         redef fun take do return seq.pop
 154         redef fun peek do return seq.last
 155 end
 156
 157 private class FifoQueue[E]
 158         super ProxyQueue[E]
 159         redef fun take do return seq.shift
 160         redef fun peek do return seq.first
 161 end
 162
 163
 164 redef class SimpleCollection[E]
 165         # Return a random proxy queue where `result.take` is random.
 166         #
 167         # The point of such a proxy is to provide a randomized removal.
 168         #
 169         # ~~~
 170         # var a = [1,2,3]
 171         # var b = a.as_random.take
 172         # assert b == 1 or b == 2 or b == 3 # Eh, it is random!
 173         # ~~~
 174         fun as_random: Queue[E] do return new RandQueue[E](self)
 175 end
 176
 177 private class RandQueue[E]
 178         super Queue[E]
 179         var seq: SimpleCollection[E]
 180         redef fun add(e)
 181         do
 182                 seq.add(e)
 183                 # Reset the cache to give the new element a chance!
 184                 peek_cached = false
 185         end
 186         redef fun take
 187         do
 188                 var res = peek
 189                 peek_cached = false
 190                 seq.remove(res)
 191                 return res
 192         end
 193         redef fun peek do
 194                 if peek_cached then return peek_cache
 195                 var res = seq.rand
 196                 peek_cache = res
 197                 peek_cached = true
 198                 return res
 199         end
 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)
 206 end
 207
 208
 209 # A min-heap implemented over an array
 210 #
 211 # The order is given by the `comparator`.
 212 #
 213 # ~~~
 214 # var a = [3,4,1,2]
 215 # var h = new MinHeap[Int].default
 216 # h.add_all(a)
 217 # assert h.peek == 1
 218 # var b = h.take_all
 219 # assert b == [1, 2, 3, 4]
 220 # ~~~
 221 class MinHeap[E: Object]
 222         super Queue[E]
 223
 224         private var items = new Array[E]
 225
 226         # The comparator used to order the Heap
 227         var comparator: Comparator
 228
 229         # Use the `default_comparator` on Comparable elements
 230         #
 231         # Require self isa MinHeap[Comparable]
 232         init default
 233         do
 234                 assert self isa MinHeap[Comparable]
 235                 init(default_comparator)
 236         end
 237
 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
 242         redef fun peek do return items.first
 243         redef fun add(e)
 244         do
 245                 #assert assert_best else print "try to add {e}"
 246                 #var ol = length
 247                 var ei = items.length + 1
 248                 while ei > 1 do
 249                         var pi = ei/2
 250                         var p = items[pi-1]
 251                         if comparator.compare(p, e) <= 0 then break
 252
 253                         # bubble-up
 254                         items[ei-1] = p
 255
 256                         # next
 257                         ei = pi
 258                 end
 259                 items[ei-1] = e
 260                 #assert length == ol + 1
 261                 #assert assert_best else print "added {e}"
 262         end
 263
 264         redef fun take do
 265                 #assert assert_best else print "tri to take"
 266                 #var ol = length
 267                 if length < 2 then return items.pop
 268
 269                 var res = items.first
 270                 var ei = 1
 271                 var e = items.pop
 272
 273                 var last = items.length
 274                 loop
 275                         # Check first child
 276                         var ci = ei*2
 277                         if ci > last then break # no children
 278                         var c = items[ci-1]
 279                         var upc = comparator.compare(e, c) > 0
 280
 281                         # Check second child
 282                         var c2i = ci + 1
 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
 289                                 # goes to c2 path
 290                                 upc = true
 291                                 c = c2
 292                                 ci = c2i
 293                         end label
 294
 295                         # bubble-down?
 296                         if not upc then break
 297
 298                         items[ei-1] = c
 299                         ei = ci
 300                 end
 301                 items[ei-1] = e
 302                 #assert length == ol - 1 else print "is {length}, expected {ol - 1}"
 303                 #assert assert_best else print "dequed {res}"
 304                 return res
 305         end
 306
 307         # Used internally do debug the Heap.
 308         # Not removed because this can still be useful.
 309         private fun assert_best: Bool
 310         do
 311                 if is_empty then return true
 312                 var b = peek
 313                 for i in self do if comparator.compare(b, i) > 0 then
 314                         #print "  peek is {b} but better found {i}"
 315                         for j in self do
 316                                 #print "   {j}"
 317                         end
 318                         return false
 319                 end
 320                 return true
 321         end
 322 end