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         # 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 #
 210 # ~~~
 211 # var a = [3,4,1,2]
 212 # var h = new MinHeap[Int].default
 213 # h.add_all(a)
 214 # assert h.peek == 1
 215 # var b = h.take_all
 216 # assert b == [1, 2, 3, 4]
 217 # ~~~
 218 class MinHeap[E: Object]
 219         super Queue[E]
 220
 221         private var items = new Array[E]
 222
 223         # The comparator used to order the Heap
 224         var comparator: Comparator
 225
 226         # Use the `default_comparator` on Comparable elements
 227         #
 228         # Require self isa MinHeap[Comparable]
 229         init default
 230         do
 231                 assert self isa MinHeap[Comparable]
 232                 init(default_comparator)
 233         end
 234
 235         redef fun is_empty do return items.is_empty
 236         redef fun length do return items.length
 237         redef fun iterator do return items.iterator
 238
 239         redef fun peek do return items.first
 240         redef fun add(e)
 241         do
 242                 #assert assert_best else print "try to add {e}"
 243                 #var ol = length
 244                 var ei = items.length + 1
 245                 while ei > 1 do
 246                         var pi = ei/2
 247                         var p = items[pi-1]
 248                         if comparator.compare(p, e) <= 0 then break
 249
 250                         # bubble-up
 251                         items[ei-1] = p
 252
 253                         # next
 254                         ei = pi
 255                 end
 256                 items[ei-1] = e
 257                 #assert length == ol + 1
 258                 #assert assert_best else print "added {e}"
 259         end
 260
 261         redef fun take do
 262                 #assert assert_best else print "tri to take"
 263                 #var ol = length
 264                 if length < 2 then return items.pop
 265
 266                 var res = items.first
 267                 var ei = 1
 268                 var e = items.pop
 269
 270                 var last = items.length
 271                 loop
 272                         # Check first child
 273                         var ci = ei*2
 274                         if ci > last then break # no children
 275                         var c = items[ci-1]
 276                         var upc = comparator.compare(e, c) > 0
 277
 278                         # Check second child
 279                         var c2i = ci + 1
 280                         if c2i <= last then do
 281                                 var c2 = items[c2i-1]
 282                                 # possibility to bubble-down to c2, or not?
 283                                 if comparator.compare(e, c2) <= 0 then break label
 284                                 # c2 is a better path, or not?
 285                                 if upc and comparator.compare(c2, c) > 0 then break label
 286                                 # goes to c2 path
 287                                 upc = true
 288                                 c = c2
 289                                 ci = c2i
 290                         end label
 291
 292                         # bubble-down?
 293                         if not upc then break
 294
 295                         items[ei-1] = c
 296                         ei = ci
 297                 end
 298                 items[ei-1] = e
 299                 #assert length == ol - 1 else print "is {length}, expected {ol - 1}"
 300                 #assert assert_best else print "dequed {res}"
 301                 return res
 302         end
 303
 304         # Used internally do debug the Heap.
 305         # Not removed because this can still be useful.
 306         private fun assert_best: Bool
 307         do
 308                 if is_empty then return true
 309                 var b = peek
 310                 for i in self do if comparator.compare(b, i) > 0 then
 311                         #print "  peek is {b} but better found {i}"
 312                         for j in self do
 313                                 #print "   {j}"
 314                         end
 315                         return false
 316                 end
 317                 return true
 318         end
 319 end