lib/core/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         redef fun clear do items.clear
 242
 243         redef fun peek do return items.first
 244         redef fun add(e)
 245         do
 246                 #assert assert_best else print "try to add {e}"
 247                 #var ol = length
 248                 var ei = items.length + 1
 249                 while ei > 1 do
 250                         var pi = ei/2
 251                         var p = items[pi-1]
 252                         if comparator.compare(p, e) <= 0 then break
 253
 254                         # bubble-up
 255                         items[ei-1] = p
 256
 257                         # next
 258                         ei = pi
 259                 end
 260                 items[ei-1] = e
 261                 #assert length == ol + 1
 262                 #assert assert_best else print "added {e}"
 263         end
 264
 265         redef fun take do
 266                 #assert assert_best else print "tri to take"
 267                 #var ol = length
 268                 if length < 2 then return items.pop
 269
 270                 var res = items.first
 271                 var ei = 1
 272                 var e = items.pop
 273
 274                 var last = items.length
 275                 loop
 276                         # Check first child
 277                         var ci = ei*2
 278                         if ci > last then break # no children
 279                         var c = items[ci-1]
 280                         var upc = comparator.compare(e, c) > 0
 281
 282                         # Check second child
 283                         var c2i = ci + 1
 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
 290                                 # goes to c2 path
 291                                 upc = true
 292                                 c = c2
 293                                 ci = c2i
 294                         end label
 295
 296                         # bubble-down?
 297                         if not upc then break
 298
 299                         items[ei-1] = c
 300                         ei = ci
 301                 end
 302                 items[ei-1] = e
 303                 #assert length == ol - 1 else print "is {length}, expected {ol - 1}"
 304                 #assert assert_best else print "dequed {res}"
 305                 return res
 306         end
 307
 308         # Used internally do debug the Heap.
 309         # Not removed because this can still be useful.
 310         private fun assert_best: Bool
 311         do
 312                 if is_empty then return true
 313                 var b = peek
 314                 for i in self do if comparator.compare(b, i) > 0 then
 315                         #print "  peek is {b} but better found {i}"
 316                         for j in self do
 317                                 #print "   {j}"
 318                         end
 319                         return false
 320                 end
 321                 return true
 322         end
 323 end