return a
end
end
-
-# A queue is a FIFO data structure
-#
-# It's particular kind of collection in which the entities in the collection are kept in order.
-# and the principal operations on the collection are:
-# * the addition of entities to the rear terminal position, known as `enqueue`
-# * the removal of entities from the front terminal position, known as `dequeue`
-# This makes the queue a First-In-First-Out (FIFO) data structure.
-# In a FIFO data structure, the first element added to the queue will be the first one to be removed.
-# This is equivalent to the requirement that once a new element is added,
-# all elements that were added before have to be removed before the new element can be removed.
-interface Queue[E]
- super Collection[E]
-
- # Add an item in the queue
- fun enqueue(item: E) is abstract
-
- # Dequeue the next item
- fun dequeue: E is abstract
-
- # Show the next item on the queue but do not remove it
- fun top: E is abstract
-end
-
-# Circular queue based on an array.
-# A data structure that uses a single, fixed-size queue as if it were connected end-to-end.
-class CircularQueue[E]
- super Queue[E]
-
- private var items: Array[nullable E]
- private var head = 0
- private var tail = 0
- private var icount = 0
- private var size: Int
-
- init(size: Int) do
- self.size = size
- items = new Array[nullable E].filled_with(null, size)
- end
-
- # var queue = new CircularQueue[Int](5)
- # queue.enqueue 10
- # queue.enqueue 20
- # queue.enqueue 30
- # assert queue.length == 3
- redef fun enqueue(item) do
- assert is_full: not is_full
- items[tail] = item
- if tail == size - 1 then
- tail = 0
- else
- tail += 1
- end
- icount += 1
- end
-
- # var queue = new CircularQueue[Int](5)
- # queue.enqueue 10
- # queue.enqueue 20
- # assert queue.dequeue == 10
- # assert queue.dequeue == 20
- # assert queue.is_empty
- redef fun dequeue do
- assert is_empty: not is_empty
- var e = items[head]
- items[head] = null
- if head == size - 1 then
- head = 0
- else
- head += 1
- end
- icount -= 1
- return e.as(not null)
- end
-
- # var queue = new CircularQueue[Int](5)
- # queue.enqueue 1
- # queue.enqueue 2
- # assert queue.top == 1
- # queue.dequeue
- # assert queue.top == 2
- redef fun top do
- assert is_empty: not is_empty
- return items[head]
- end
-
- # var queue = new CircularQueue[Int](5)
- # queue.enqueue 10
- # assert queue.length == 1
- # queue.enqueue 20
- # assert queue.length == 2
- # queue.dequeue
- # assert queue.length == 1
- # queue.dequeue
- # assert queue.length == 0
- redef fun length do return icount
-
- # var queue = new CircularQueue[Int](5)
- # assert queue.is_empty
- # queue.enqueue 1
- # assert not queue.is_empty
- # queue.dequeue
- # assert queue.is_empty
- redef fun is_empty do return icount == 0
-
- # Is the queue full?
- #
- # var queue = new CircularQueue[Int](3)
- # assert not queue.is_full
- # queue.enqueue 10
- # queue.enqueue 20
- # queue.enqueue 30
- # assert queue.is_full
- # queue.dequeue
- # assert not queue.is_full
- fun is_full: Bool do return icount == size
-
- # var queue = new CircularQueue[Int](3)
- # queue.enqueue 10
- # queue.enqueue 20
- # queue.enqueue 30
- # var res = new Array[Int]
- # for e in queue do res.add(e)
- # assert res == [10, 20, 30]
- redef fun iterator do return new CircularQueueIterator[E](self)
-end
-
-private class CircularQueueIterator[E]
- super Iterator[E]
-
- var queue: CircularQueue[E]
- var current: Int
- var iterations: Int
-
- init(queue: CircularQueue[E]) do
- self.queue = queue
- self.current = queue.head
- self.iterations = 0
- end
-
- redef fun is_ok do return iterations < queue.length
-
- redef fun next do
- if current == queue.size - 1 then
- current = 0
- else
- current += 1
- end
- iterations += 1
- end
-
- redef fun item do return queue.items[current]
-end
-
-# Stack implemented with an array
-# A stack is a particular kind of collection
-# in which the principal operations are:
-# * the addition of an entity to the collection, known as `push`
-# * the removal of an entity, known as `pop`
-# This makes the queue a Last-In-First-Out (LIFO) data structure.
-# In a LIFO data structure, the last element added to the structure must be the first one
-# to be removed.
-# This is equivalent to the requirement that, considered as a linear collection,
-# the push and pop operations occur only at one end of the structure,
-# referred to as the top of the stack.
-#
-# Example:
-#
-# var stack = new Stack[Int]
-# stack.push 1
-# stack.push 2
-# assert stack.pop == 2
-# assert stack.pop == 1
-class Stack[E]
- super Collection[E]
-
- private var items = new List[E]
- private var itop = 0
-
- # Is the stack empty?
- #
- # var stack = new Stack[Int]
- # assert stack.is_empty
- # stack.push 1
- # assert not stack.is_empty
- # stack.pop
- # assert stack.is_empty
- redef fun is_empty do return itop == 0
-
- # Add an item on top of the stack
- #
- # var stack = new Stack[Int]
- # stack.push 1
- # stack.push 2
- # assert stack.length == 2
- fun push(item: E) do
- itop += 1
- items.add item
- end
-
- # Pop the item on the top of the stack
- #
- # var stack = new Stack[Int]
- # stack.push 1
- # stack.push 2
- # assert stack.pop == 2
- # assert stack.pop == 1
- # assert stack.is_empty
- fun pop: E do
- assert empty: not is_empty
- itop -= 1
- return items[itop]
- end
-
- # Show the item on the top of the stack but do not remove it
- #
- # var stack = new Stack[Int]
- # stack.push 1
- # stack.push 2
- # assert stack.top == 2
- # stack.pop
- # assert stack.top == 1
- fun top: E do
- assert empty: not is_empty
- return items[itop - 1]
- end
-
- # Number of items contained in the stack
- #
- # var stack = new Stack[Int]
- # assert stack.length == 0
- # stack.push 1
- # assert stack.length == 1
- # stack.push 2
- # assert stack.length == 2
- # assert stack.pop == 2
- # assert stack.length == 1
- # assert stack.pop == 1
- # assert stack.length == 0
- redef fun length do return itop
-
- # Get an iterator over the stack
- #
- # var stack = new Stack[Int]
- # stack.push 1
- # stack.push 2
- # var sum = 0
- # for item in stack do sum += item
- # assert sum == 3
- redef fun iterator do return items.iterator
-end
-
-# A heap is a data structure that satisfies the heap property:
-# If A is a parent node of B then the key of node A is ordered with respect
-# to the key of node B with the same ordering applying across the heap.
-# Either the keys of parent nodes are always greater than or equal to those of the children
-# and the highest key is in the root node (this kind of heap is called max heap)
-# or the keys of parent nodes are less than or equal to those of the children
-# and the lowest key is in the root node (min heap).
-#
-# Heaps are crucial in several efficient graph algorithms such as Dijkstra's algorithm,
-# and in the sorting algorithm heapsort.
-interface Heap[E]
- super Collection[E]
-
- # Get the minimum element of the heap
- fun min: E is abstract
-
- # Remove and return the minimum
- fun pop: E is abstract
-
- # Add an element in the heap
- fun add(e: E) is abstract
-
- # Update the heap structure
- fun build_heap is abstract
-end
-
-# Heap implemented over an array
-class ArrayHeap[E]
- super Heap[E]
-
- private var items: Array[E]
- private var size: Int = -1
- private var comparator: Comparator[E]
-
- init(comparator: Comparator[E]) do
- self.comparator = comparator
- items = new Array[E]
- end
-
- # Init the heap using an existing array
- init from(comparator: Comparator[E], array: Array[E]) do
- self.comparator = comparator
- size = array.length - 1
- items = array
- build_heap
- end
-
- redef fun build_heap do
- var i = size / 2
- while i >= 0 do
- heapify(i)
- i -= 1
- end
- end
-
- private fun heapify(from: Int) do
- var l = from * 2 + 1
- var r = l + 1
- var largest = from
- if l <= size and comparator.compare(items[l], items[largest]) > 0 then
- largest = l
- else
- largest = from
- end
- if r <= size and comparator.compare(items[r], items[largest]) > 0 then
- largest = r
- end
- if largest != from then
- items.swap_at(from, largest)
- heapify(largest)
- end
- end
-
- private fun swap_at(a, b: Int) do
- var tmp = items[a]
- items[a] = items[b]
- items[b] = tmp
- end
-
- redef fun length do return size + 1
- redef fun is_empty do return length == 0
- redef fun iterator do return items.iterator
-
- redef fun min do
- assert not_empty: not is_empty
- return items.first
- end
-
- redef fun pop do
- assert not_empty: not is_empty
- var e = min
- swap_at(0, size)
- size -= 1
- build_heap
- return e
- end
-
- redef fun add(e) do
- size += 1
- items[size] = e
- build_heap
- end
-
- redef fun to_a do
- var res = new Array[E]
- for i in [0..size] do res.add items[i]
- return res
- end
-end
-
-# Priority Queue implemented over an ArrayHeap
-# A priority queue is an abstract data type which is like a regular queue,
-# but where additionally each element has a "priority" associated with it.
-# In a priority queue, an element with high priority is served before an element with low priority.
-# If two elements have the same priority, they are served according to their order in the queue.
-#
-# Example:
-#
-# var comparator = new DefaultComparator[Int]
-# var queue = new PriorityQueue[Int](comparator)
-# queue.enqueue 11
-# queue.enqueue 9
-# queue.enqueue 30
-# assert not queue.is_empty
-# assert queue.dequeue == 30
-# assert queue.dequeue == 11
-# assert queue.dequeue == 9
-#
-# Init priority queue from array:
-#
-# var queue2 = new PriorityQueue[Int].from(comparator, [2, 4, 1, 5, 3, 12, 0])
-# assert queue2.length == 7
-# assert queue2.top == 12
-class PriorityQueue[E]
- super Queue[E]
-
- var heap: Heap[E]
-
- init(comparator: Comparator[E]) do
- heap = new ArrayHeap[E](comparator)
- end
-
- init from(comparator: Comparator[E], items: Collection[E]) do
- heap = new ArrayHeap[E].from(comparator, items.to_a)
- end
-
- # var comparator = new DefaultComparator[Int]
- # var queue = new PriorityQueue[Int].from(comparator, [2, 4, 1, 5, 3, 12, 0])
- # assert queue.dequeue == 12
- # assert queue.dequeue == 5
- # assert queue.dequeue == 4
- # assert queue.length == 4
- redef fun dequeue do return heap.pop
-
- # var comparator = new DefaultComparator[Int]
- # var queue = new PriorityQueue[Int](comparator)
- # queue.enqueue 18
- # queue.enqueue 12
- # queue.enqueue 32
- # assert queue.dequeue == 32
- # assert queue.dequeue == 18
- # assert queue.dequeue == 12
- redef fun enqueue(e) do heap.add e
-
- # var comparator = new DefaultComparator[Int]
- # var queue = new PriorityQueue[Int].from(comparator, [2, 4, 1, 5, 3, 12, 0])
- # assert queue.top == 12
- # queue.dequeue
- # assert queue.top == 5
- redef fun top do return heap.min
-
- redef fun length do return heap.length
- redef fun iterator do return heap.iterator
-end
-
--- /dev/null
+# This file is part of NIT ( http://www.nitlanguage.org ).
+#
+# This file is free software, which comes along with NIT. This software is
+# distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
+# without even the implied warranty of MERCHANTABILITY or FITNESS FOR A
+# PARTICULAR PURPOSE. You can modify it is you want, provided this header
+# is kept unaltered, and a notification of the changes is added.
+# You are allowed to redistribute it and sell it, alone or is a part of
+# another product.
+
+# Queuing data structures and wrappers
+# Provides a queue abstraction for LIFO, FIFO (stack) and heaps.
+#
+# Topics:
+# * `Queue`
+# * `Sequence::as_lifo`
+# * `Sequence::as_fifo`
+# * `SimpleCollection::as_random`
+# * `MinHeap`
+module queue
+
+import collection::array
+import collection::sorter
+import math
+
+# Queues are collection that controls how elements are retrieved.
+#
+# This interface is used for data structures and algorithms that need
+# some queuing but that let their users control how the queuing is done.
+#
+# Most concrete queues have an efficient implementation of the basic methods
+# `is_empty`, `length`, `add`, `peek`, and `take`.
+# However, the `remove` method is possibly inefficient.
+# To workaround an inefficient implementation, one can instead mark the removed
+# elements (with a flag or in a set), and ignore then when `take` returns one.
+#
+# Unless stated otherwise, the `iterator` method is unrelated with the queue
+# logic and may visit the elements in a order dependent on implementation.
+interface Queue[E]
+ super SimpleCollection[E]
+
+ # Take the next element (according to the specific queue)
+ # ~~~
+ # var a = (new Array[Int]).as_lifo
+ # a.add 1
+ # a.add 2
+ # assert a.take == 2
+ # assert a.take == 1
+ #
+ # var h = new MinHeapCmp[Int]
+ # h.add 2
+ # h.add 1
+ # h.add 10
+ # assert h.take == 1
+ # assert h.take == 2
+ # assert h.take == 10
+ # ~~~
+ # ensure `result == peek`
+ fun take: E is abstract
+
+ # Look at the next element but does not remove it
+ #
+ # ~~~
+ # var a = (new Array[Int]).as_lifo
+ # a.add 1
+ # assert a.peek == 1
+ # a.add 2
+ # assert a.peek == 2
+ # assert a.take == 2
+ # assert a.peek == 1
+ # ~~~
+ fun peek: E is abstract
+
+ # `first` is made an alias of `peek` to avoid bad surprises
+ redef fun first do return peek
+
+ # Take and return all elements until the queue is empty
+ # ensure `is_empty`
+ # ensure `result.length == old(length)`
+ # ensure `not old(is_empty) implies result.first == old(peek)`
+ # ~~~
+ # var a = (new Array[Int]).as_lifo
+ # a.add 1
+ # a.add 2
+ # a.add 3
+ # assert a.take_all == [3, 2, 1]
+ # assert a.is_empty
+ # ~~~
+ fun take_all: Array[E]
+ do
+ var res = new Array[E]
+ while not is_empty do res.add take
+ return res
+ end
+end
+
+redef class Sequence[E]
+ # Return a LIFO proxy queue (stack) where `result.take` is `pop`.
+ #
+ # The point of such a proxy is to let the user choose the underling data structure
+ # behind the LIFO.
+ #
+ # ~~~
+ # var a = [1, 2, 3]
+ # var q = a.as_lifo
+ # assert q.take == 3
+ # assert q.take == 2
+ # q.add(4)
+ # q.add(5)
+ # assert q.take == 5
+ # assert a == [1, 4]
+ # ~~~
+ fun as_lifo: Queue[E] do return new LifoQueue[E](self)
+
+ # Return a FIFO proxy queue where `result.take` is `shift`.
+ #
+ # The point of such a proxy is to let the user choose the underling data structure
+ # behind the FIFO.
+ #
+ # Note that some `Sequence`, like `Array`, have an inefficient `shift` implementation,
+ # thus are not the best candidates to serve as a FIFO.
+ #
+ # ~~~
+ # var a = new List[Int].from([1,2,3])
+ # var q = a.as_fifo
+ # assert q.take == 1
+ # q.add(4)
+ # q.add(5)
+ # assert q.take == 2
+ # assert a == [3, 4, 5]
+ # ~~~
+ fun as_fifo: Queue[E] do return new FifoQueue[E](self)
+end
+
+# Factorize common proxy implementation
+private abstract class ProxyQueue[E]
+ super Queue[E]
+ var seq: Sequence[E]
+
+ redef fun add(e) do seq.add(e)
+ redef fun length do return seq.length
+ redef fun is_empty do return seq.is_empty
+ redef fun iterator do return seq.iterator
+ redef fun remove(e) do seq.remove(e)
+end
+
+
+private class LifoQueue[E]
+ super ProxyQueue[E]
+ redef fun take do return seq.pop
+ redef fun peek do return seq.last
+end
+
+private class FifoQueue[E]
+ super ProxyQueue[E]
+ redef fun take do return seq.shift
+ redef fun peek do return seq.first
+end
+
+
+redef class SimpleCollection[E]
+ # Return a random proxy queue where `result.take` is random.
+ #
+ # The point of such a proxy is to provide a randomized removal.
+ #
+ # ~~~
+ # var a = [1,2,3]
+ # var b = a.as_random.take
+ # assert b == 1 or b == 2 or b == 3 # Eh, it is random!
+ # ~~~
+ fun as_random: Queue[E] do return new RandQueue[E](self)
+end
+
+private class RandQueue[E]
+ super Queue[E]
+ var seq: SimpleCollection[E]
+ redef fun add(e)
+ do
+ seq.add(e)
+ # Reset the cache to give the new element a chance!
+ peek_cached = false
+ end
+ redef fun take
+ do
+ var res = peek
+ peek_cached = false
+ seq.remove(res)
+ return res
+ end
+ redef fun peek do
+ if peek_cached then return peek_cache
+ var res = seq.rand
+ peek_cache = res
+ peek_cached = true
+ return res
+ end
+ var peek_cached = false
+ var peek_cache: E is noinit
+ redef fun length do return seq.length
+ redef fun is_empty do return seq.is_empty
+ redef fun iterator do return seq.iterator
+ redef fun remove(e) do seq.remove(e)
+end
+
+
+# A min-heap implemented over an array
+#
+# The order is given by the `comparator`.
+# If `E` is Comparable, then the subclass `MinHeapCmp` can be used instead.
+#
+# ~~~
+# var a = [3,4,1,2]
+# var h = new MinHeap[Int](new DefaultComparator[Int])
+# h.add_all(a)
+# assert h.peek == 1
+# var b = h.take_all
+# assert b == [1, 2, 3, 4]
+# ~~~
+class MinHeap[E: Object]
+ super Queue[E]
+
+ private var items = new Array[E]
+ var comparator: Comparator[E]
+
+ redef fun is_empty do return items.is_empty
+ redef fun length do return items.length
+ redef fun iterator do return items.iterator
+
+ redef fun peek do return items.first
+ redef fun add(e)
+ do
+ #assert assert_best else print "try to add {e}"
+ #var ol = length
+ var ei = items.length + 1
+ while ei > 1 do
+ var pi = ei/2
+ var p = items[pi-1]
+ if comparator.compare(p, e) <= 0 then break
+
+ # bubble-up
+ items[ei-1] = p
+
+ # next
+ ei = pi
+ end
+ items[ei-1] = e
+ #assert length == ol + 1
+ #assert assert_best else print "added {e}"
+ end
+
+ redef fun take do
+ #assert assert_best else print "tri to take"
+ #var ol = length
+ if length < 2 then return items.pop
+
+ var res = items.first
+ var ei = 1
+ var e = items.pop
+
+ var last = items.length
+ loop
+ # Check first child
+ var ci = ei*2
+ if ci > last then break # no children
+ var c = items[ci-1]
+ var upc = comparator.compare(e, c) > 0
+
+ # Check second child
+ var c2i = ci + 1
+ if c2i <= last then do
+ var c2 = items[c2i-1]
+ # possibility to bubble-down to c2, or not?
+ if comparator.compare(e, c2) <= 0 then break label
+ # c2 is a better path, or not?
+ if upc and comparator.compare(c2, c) > 0 then break label
+ # goes to c2 path
+ upc = true
+ c = c2
+ ci = c2i
+ end label
+
+ # bubble-down?
+ if not upc then break
+
+ items[ei-1] = c
+ ei = ci
+ end
+ items[ei-1] = e
+ #assert length == ol - 1 else print "is {length}, expected {ol - 1}"
+ #assert assert_best else print "dequed {res}"
+ return res
+ end
+
+ # Used internally do debug the Heap.
+ # Not removed because this can still be useful.
+ private fun assert_best: Bool
+ do
+ if is_empty then return true
+ var b = peek
+ for i in self do if comparator.compare(b, i) > 0 then
+ #print " peek is {b} but better found {i}"
+ for j in self do
+ #print " {j}"
+ end
+ return false
+ end
+ return true
+ end
+end
+
+# A `MinHeap` for `Comparable` that does not need a specific `Comparator`
+#
+# ~~~
+# var a = [3,4,1,2]
+# var h = new MinHeapCmp[Int]
+# h.add_all(a)
+# assert h.peek == 1
+# var b = h.take_all
+# assert b == [1, 2, 3, 4]
+# ~~~
+class MinHeapCmp[E: Comparable]
+ super MinHeap[E]
+ init do super(new DefaultComparator[E])
+end
nitlanguage / nit.git / commitdiff