lib/standard/collection/collection.nit

   1 # This file is part of NIT ( http://www.nitlanguage.org ).
   2 #
   3 # Copyright 2009 Jean Privat <jean@pryen.org>
   4 #
   5 # This file is free software, which comes along with NIT.  This software is
   6 # distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
   7 # without  even  the implied warranty of  MERCHANTABILITY or  FITNESS FOR A
   8 # PARTICULAR PURPOSE.  You can modify it is you want,  provided this header
   9 # is kept unaltered, and a notification of the changes is added.
  10 # You  are  allowed  to  redistribute it and sell it, alone or is a part of
  11 # another product.
  12
  13 # This module define several collection classes.
  14 module collection
  15
  16 import abstract_collection
  17 import range
  18 import list
  19 import array
  20 import sorter
  21 import hash_collection
  22 import union_find
  23
  24 redef class Sequence[E]
  25         fun subarray(start, len: Int): Array[E]
  26         do
  27                 var a = new Array[E].with_capacity(len)
  28                 for i in [start .. start+len[ do a.add(self[i])
  29                 return a
  30         end
  31 end
  32
  33 # A queue is a FIFO data structure
  34 #
  35 # It's particular kind of collection in which the entities in the collection are kept in order.
  36 # and the principal operations on the collection are:
  37 #  * the addition of entities to the rear terminal position, known as `enqueue`
  38 #  * the removal of entities from the front terminal position, known as `dequeue`
  39 # This makes the queue a First-In-First-Out (FIFO) data structure.
  40 # In a FIFO data structure, the first element added to the queue will be the first one to be removed.
  41 # This is equivalent to the requirement that once a new element is added,
  42 # all elements that were added before have to be removed before the new element can be removed.
  43 interface Queue[E]
  44         super Collection[E]
  45
  46         # Add an item in the queue
  47         fun enqueue(item: E) is abstract
  48
  49         # Dequeue the next item
  50         fun dequeue: E is abstract
  51
  52         # Show the next item on the queue but do not remove it
  53         fun top: E is abstract
  54 end
  55
  56 # Circular queue based on an array.
  57 # A data structure that uses a single, fixed-size queue as if it were connected end-to-end.
  58 class CircularQueue[E]
  59         super Queue[E]
  60
  61         private var items: Array[nullable E]
  62         private var head = 0
  63         private var tail = 0
  64         private var icount = 0
  65         private var size: Int
  66
  67         init(size: Int) do
  68                 self.size = size
  69                 items = new Array[nullable E].filled_with(null, size)
  70         end
  71
  72         #     var queue = new CircularQueue[Int](5)
  73         #     queue.enqueue 10
  74         #     queue.enqueue 20
  75         #     queue.enqueue 30
  76         #     assert queue.length == 3
  77         redef fun enqueue(item) do
  78                 assert is_full: not is_full
  79                 items[tail] = item
  80                 if tail == size - 1 then
  81                         tail = 0
  82                 else
  83                         tail += 1
  84                 end
  85                 icount += 1
  86         end
  87
  88         #     var queue = new CircularQueue[Int](5)
  89         #     queue.enqueue 10
  90         #     queue.enqueue 20
  91         #     assert queue.dequeue == 10
  92         #     assert queue.dequeue == 20
  93         #     assert queue.is_empty
  94         redef fun dequeue do
  95                 assert is_empty: not is_empty
  96                 var e = items[head]
  97                 items[head] = null
  98                 if head == size - 1 then
  99                         head = 0
 100                 else
 101                         head += 1
 102                 end
 103                 icount -= 1
 104                 return e.as(not null)
 105         end
 106
 107         #     var queue = new CircularQueue[Int](5)
 108         #     queue.enqueue 1
 109         #     queue.enqueue 2
 110         #     assert queue.top == 1
 111         #     queue.dequeue
 112         #     assert queue.top == 2
 113         redef fun top do
 114                 assert is_empty: not is_empty
 115                 return items[head]
 116         end
 117
 118         #     var queue = new CircularQueue[Int](5)
 119         #     queue.enqueue 10
 120         #     assert queue.length == 1
 121         #     queue.enqueue 20
 122         #     assert queue.length == 2
 123         #     queue.dequeue
 124         #     assert queue.length == 1
 125         #     queue.dequeue
 126         #     assert queue.length == 0
 127         redef fun length do return icount
 128
 129         #     var queue = new CircularQueue[Int](5)
 130         #     assert queue.is_empty
 131         #     queue.enqueue 1
 132         #     assert not queue.is_empty
 133         #     queue.dequeue
 134         #     assert queue.is_empty
 135         redef fun is_empty do return icount == 0
 136
 137         # Is the queue full?
 138         #
 139         #     var queue = new CircularQueue[Int](3)
 140         #     assert not queue.is_full
 141         #     queue.enqueue 10
 142         #     queue.enqueue 20
 143         #     queue.enqueue 30
 144         #     assert queue.is_full
 145         #     queue.dequeue
 146         #     assert not queue.is_full
 147         fun is_full: Bool do return icount == size
 148
 149         #     var queue = new CircularQueue[Int](3)
 150         #     queue.enqueue 10
 151         #     queue.enqueue 20
 152         #     queue.enqueue 30
 153         #     var res = new Array[Int]
 154         #     for e in queue do res.add(e)
 155         #     assert res == [10, 20, 30]
 156         redef fun iterator do return new CircularQueueIterator[E](self)
 157 end
 158
 159 private class CircularQueueIterator[E]
 160         super Iterator[E]
 161
 162         var queue: CircularQueue[E]
 163         var current: Int
 164         var iterations: Int
 165
 166         init(queue: CircularQueue[E]) do
 167                 self.queue = queue
 168                 self.current = queue.head
 169                 self.iterations = 0
 170         end
 171
 172         redef fun is_ok do return iterations < queue.length
 173
 174         redef fun next do
 175                 if current == queue.size - 1 then
 176                         current = 0
 177                 else
 178                         current += 1
 179                 end
 180                 iterations += 1
 181         end
 182
 183         redef fun item do return queue.items[current]
 184 end
 185
 186 # Stack implemented with an array
 187 # A stack is a particular kind of collection
 188 # in which the principal operations are:
 189 #  * the addition of an entity to the collection, known as `push`
 190 #  * the removal of an entity, known as `pop`
 191 # This makes the queue a Last-In-First-Out (LIFO) data structure.
 192 # In a LIFO data structure, the last element added to the structure must be the first one
 193 # to be removed.
 194 # This is equivalent to the requirement that, considered as a linear collection,
 195 # the push and pop operations occur only at one end of the structure,
 196 # referred to as the top of the stack.
 197 #
 198 # Example:
 199 #
 200 #     var stack = new Stack[Int]
 201 #     stack.push 1
 202 #     stack.push 2
 203 #     assert stack.pop == 2
 204 #     assert stack.pop == 1
 205 class Stack[E]
 206         super Collection[E]
 207
 208         private var items = new List[E]
 209         private var itop = 0
 210
 211         # Is the stack empty?
 212         #
 213         #     var stack = new Stack[Int]
 214         #     assert stack.is_empty
 215         #     stack.push 1
 216         #     assert not stack.is_empty
 217         #     stack.pop
 218         #     assert stack.is_empty
 219         redef fun is_empty do return itop == 0
 220
 221         # Add an item on top of the stack
 222         #
 223         #     var stack = new Stack[Int]
 224         #     stack.push 1
 225         #     stack.push 2
 226         #     assert stack.length == 2
 227         fun push(item: E) do
 228                 itop += 1
 229                 items.add item
 230         end
 231
 232         # Pop the item on the top of the stack
 233         #
 234         #     var stack = new Stack[Int]
 235         #     stack.push 1
 236         #     stack.push 2
 237         #     assert stack.pop == 2
 238         #     assert stack.pop == 1
 239         #     assert stack.is_empty
 240         fun pop: E do
 241                 assert empty: not is_empty
 242                 itop -= 1
 243                 return items[itop]
 244         end
 245
 246         # Show the item on the top of the stack but do not remove it
 247         #
 248         #     var stack = new Stack[Int]
 249         #     stack.push 1
 250         #     stack.push 2
 251         #     assert stack.top == 2
 252         #     stack.pop
 253         #     assert stack.top == 1
 254         fun top: E do
 255                 assert empty: not is_empty
 256                 return items[itop - 1]
 257         end
 258
 259         # Number of items contained in the stack
 260         #
 261         #     var stack = new Stack[Int]
 262         #     assert stack.length == 0
 263         #     stack.push 1
 264         #     assert stack.length == 1
 265         #     stack.push 2
 266         #     assert stack.length == 2
 267         #     assert stack.pop == 2
 268         #     assert stack.length == 1
 269         #     assert stack.pop == 1
 270         #     assert stack.length == 0
 271         redef fun length do return itop
 272
 273         # Get an iterator over the stack
 274         #
 275         #     var stack = new Stack[Int]
 276         #     stack.push 1
 277         #     stack.push 2
 278         #     var sum = 0
 279         #     for item in stack do sum += item
 280         #     assert sum == 3
 281         redef fun iterator do return items.iterator
 282 end
 283
 284 # A heap is a data structure that satisfies the heap property:
 285 # If A is a parent node of B then the key of node A is ordered with respect
 286 # to the key of node B with the same ordering applying across the heap.
 287 # Either the keys of parent nodes are always greater than or equal to those of the children
 288 # and the highest key is in the root node (this kind of heap is called max heap)
 289 # or the keys of parent nodes are less than or equal to those of the children
 290 # and the lowest key is in the root node (min heap).
 291 #
 292 # Heaps are crucial in several efficient graph algorithms such as Dijkstra's algorithm,
 293 # and in the sorting algorithm heapsort.
 294 interface Heap[E]
 295         super Collection[E]
 296
 297         # Get the minimum element of the heap
 298         fun min: E is abstract
 299
 300         # Remove and return the minimum
 301         fun pop: E is abstract
 302
 303         # Add an element in the heap
 304         fun add(e: E) is abstract
 305
 306         # Update the heap structure
 307         fun build_heap is abstract
 308 end
 309
 310 # Heap implemented over an array
 311 class ArrayHeap[E]
 312         super Heap[E]
 313
 314         private var items: Array[E]
 315         private var size: Int = -1
 316         private var comparator: Comparator[E]
 317
 318         init(comparator: Comparator[E]) do
 319                 self.comparator = comparator
 320                 items = new Array[E]
 321         end
 322
 323         # Init the heap using an existing array
 324         init from(comparator: Comparator[E], array: Array[E]) do
 325                 self.comparator = comparator
 326                 size = array.length - 1
 327                 items = array
 328                 build_heap
 329         end
 330
 331         redef fun build_heap do
 332                 var i = size / 2
 333                 while i >= 0 do
 334                         heapify(i)
 335                         i -= 1
 336                 end
 337         end
 338
 339         private fun heapify(from: Int) do
 340                 var l = from * 2 + 1
 341                 var r = l + 1
 342                 var largest = from
 343                 if l <= size and comparator.compare(items[l], items[largest]) > 0 then
 344                         largest = l
 345                 else
 346                         largest = from
 347                 end
 348                 if r <= size and comparator.compare(items[r], items[largest]) > 0 then
 349                         largest = r
 350                 end
 351                 if largest != from then
 352                         items.swap_at(from, largest)
 353                         heapify(largest)
 354                 end
 355         end
 356
 357         private fun swap_at(a, b: Int) do
 358                 var tmp = items[a]
 359                 items[a] = items[b]
 360                 items[b] = tmp
 361         end
 362
 363         redef fun length do return size + 1
 364         redef fun is_empty do return length == 0
 365         redef fun iterator do return items.iterator
 366
 367         redef fun min do
 368                 assert not_empty: not is_empty
 369                 return items.first
 370         end
 371
 372         redef fun pop do
 373                 assert not_empty: not is_empty
 374                 var e = min
 375                 swap_at(0, size)
 376                 size -= 1
 377                 build_heap
 378                 return e
 379         end
 380
 381         redef fun add(e) do
 382                 size += 1
 383                 items[size] = e
 384                 build_heap
 385         end
 386
 387         redef fun to_a do
 388                 var res = new Array[E]
 389                 for i in [0..size] do res.add items[i]
 390                 return res
 391         end
 392 end
 393
 394 # Priority Queue implemented over an ArrayHeap
 395 # A priority queue is an abstract data type which is like a regular queue,
 396 # but where additionally each element has a "priority" associated with it.
 397 # In a priority queue, an element with high priority is served before an element with low priority.
 398 # If two elements have the same priority, they are served according to their order in the queue.
 399 #
 400 # Example:
 401 #
 402 #     var comparator = new DefaultComparator[Int]
 403 #     var queue = new PriorityQueue[Int](comparator)
 404 #     queue.enqueue 11
 405 #     queue.enqueue 9
 406 #     queue.enqueue 30
 407 #     assert not queue.is_empty
 408 #     assert queue.dequeue == 30
 409 #     assert queue.dequeue == 11
 410 #     assert queue.dequeue == 9
 411 #
 412 # Init priority queue from array:
 413 #
 414 #     var queue2 = new PriorityQueue[Int].from(comparator, [2, 4, 1, 5, 3, 12, 0])
 415 #     assert queue2.length == 7
 416 #     assert queue2.top == 12
 417 class PriorityQueue[E]
 418         super Queue[E]
 419
 420         var heap: Heap[E]
 421
 422         init(comparator: Comparator[E]) do
 423                 heap = new ArrayHeap[E](comparator)
 424         end
 425
 426         init from(comparator: Comparator[E], items: Collection[E]) do
 427                 heap = new ArrayHeap[E].from(comparator, items.to_a)
 428         end
 429
 430         #     var comparator = new DefaultComparator[Int]
 431         #     var queue = new PriorityQueue[Int].from(comparator, [2, 4, 1, 5, 3, 12, 0])
 432         #     assert queue.dequeue == 12
 433         #     assert queue.dequeue == 5
 434         #     assert queue.dequeue == 4
 435         #     assert queue.length == 4
 436         redef fun dequeue do return heap.pop
 437
 438         #     var comparator = new DefaultComparator[Int]
 439         #     var queue = new PriorityQueue[Int](comparator)
 440         #     queue.enqueue 18
 441         #     queue.enqueue 12
 442         #     queue.enqueue 32
 443         #     assert queue.dequeue == 32
 444         #     assert queue.dequeue == 18
 445         #     assert queue.dequeue == 12
 446         redef fun enqueue(e) do heap.add e
 447
 448         #     var comparator = new DefaultComparator[Int]
 449         #     var queue = new PriorityQueue[Int].from(comparator, [2, 4, 1, 5, 3, 12, 0])
 450         #     assert queue.top == 12
 451         #     queue.dequeue
 452         #     assert queue.top == 5
 453         redef fun top do return heap.min
 454
 455         redef fun length do return heap.length
 456         redef fun iterator do return heap.iterator
 457 end
 458