README#Immutable Priority Queue
A priority queue is a data structure capable of maintaining maximum/minimum values at the front of the queue, which may have other names in other programming languages (C++ std::priority_queue / Rust BinaryHeap). The priority queue here is implemented as an immutable binary heap using a complete binary tree representation.
#Usage
#Create
You can use PriorityQueue([]) or of() to create an immutable priority queue.
///|
test {
let _queue1 : @priority_queue.PriorityQueue[Int] = PriorityQueue([])
let _queue2 = @priority_queue.from_array([1, 2, 3])
}Note, however, that the default immutable priority queue created is greater-first; if you need to create a less-first queue, you can write a struct belongs to Compare trait to implement it.
#Length & Empty
You can use the length to get the length of the immutable priority queue.
///|
test {
let pq = @priority_queue.PriorityQueue([])
@test.assert_eq(pq.length(), 0)
@test.assert_eq(pq.push(1).length(), 1)
}You can use the is_empty to determine whether the immutable priority queue is empty.
///|
test {
let pq : @priority_queue.PriorityQueue[Int] = PriorityQueue([])
@test.assert_eq(pq.is_empty(), true)
}#Peek & Push & Pop
You can use peek() to look at the head element of a queue, which must be either the maximum or minimum value of an element in the queue, depending on the nature of the specification. The return value of peek() is an Option, which means that the result will be None when the queue is empty.
///|
test {
let pq = @priority_queue.from_array([1, 2, 3, 4, 5])
@test.assert_eq(pq.peek(), Some(5))
// @json.json_inspect(pq)
// we have to add `@json` package in test-import
// it's reported unused package currently
}You can use push() to add elements to the immutable priority queue and get a new queue.
///|
test {
let pq : @priority_queue.PriorityQueue[Int] = PriorityQueue([])
@test.assert_eq(pq.push(1).peek(), Some(1))
}You can use pop() to remove the element at the front of the priority queue and get a new immutable priority queue wrapped with Option. If the immutable priority queue is empty, then it will return None.
///|
test {
let pq = @priority_queue.from_array([5, 4, 3, 2, 1])
let val = match pq.pop() {
Some(q) => q.peek()
None => None
}
@test.assert_eq(val, Some(4))
}#PriorityQueue
type PriorityQueue[A]impl Compare for PriorityQueue[A]
Compare two priority queues based on shortlex order by comparing their sorted contents.
Parameters:
- self : The first list to compare.
- other : The second list to compare.
Returns an integer that indicates the relative order:
- A negative value if self is less than other
- Zero if self equals other
- A positive value if self is greater than other
Example:
test {
let pq1 = @priority_queue.from_array([1, 2, 3])
let pq2 = @priority_queue.from_array([1, 2, 4])
let pq3 = @priority_queue.from_array([1, 2])
inspect(pq1.compare(pq2), content="-1") // pq1 < pq2
inspect(pq1.compare(pq3), content="1") // pq1 > pq3 (longer)
inspect(pq3.compare(pq1), content="-1") // pq3 < pq1 (shorter)
inspect(pq1.compare(pq1), content="0") // pq1 = pq1
}impl Eq for PriorityQueue[A]impl Hash for PriorityQueue[A]impl Show for PriorityQueue[A]impl ToJson for PriorityQueue[A]impl Debug for PriorityQueue[A]#PriorityQueue::PriorityQueue
#as_free_fn(of, deprecated="Use from_array instead")
#alias(of, deprecated="Use from_array instead")
#as_free_fn(from_array)
#alias(from_array)
fn[A : Compare + Eq] PriorityQueue::PriorityQueue(array : ArrayView[A]) -> PriorityQueue[A]Creates a new immutable priority queue from an array.
Runs in O(n): the elements are copied once and turned into a heap in place,
which is asymptotically faster than inserting them one by one with push
(O(n log n)).
Example
test {
let queue = @priority_queue.PriorityQueue([1, 2, 3, 4, 5])
inspect(queue.length(), content="5")
}#PriorityQueue::compare
fn[A : Compare + Eq] PriorityQueue::compare(self : PriorityQueue[A], other : PriorityQueue[A]) -> Int#PriorityQueue::equal
fn[A : Compare + Eq] PriorityQueue::equal(self : PriorityQueue[A], other : PriorityQueue[A]) -> Bool#PriorityQueue::from_iter
#as_free_fn(from_iterator, deprecated="Use PriorityQueue::from_iter instead.")
#alias(from_iterator, deprecated="`from_iterator` is deprecated, use `from_iter` instead")
#as_free_fn
fn[A : Compare + Eq] PriorityQueue::from_iter(iter : Iter[A]) -> PriorityQueue[A]Creates a priority queue from an iterator of values.
#PriorityQueue::hash
#PriorityQueue::is_empty
Checks if the immutable priority queue is empty.
Example
test {
let queue = @priority_queue.PriorityQueue([])
inspect(queue.is_empty(), content="true")
@test.assert_eq(queue.push(1).is_empty(), false)
}#PriorityQueue::iter
#alias(iterator, deprecated="`iterator` is deprecated, use `iter` instead")
fn[A : Compare + Eq] PriorityQueue::iter(self : PriorityQueue[A]) -> Iter[A]Returns an iterator over elements in descending priority order.
#PriorityQueue::length
Return the length of the immutable priority queue.
Example
test {
let queue = @priority_queue.PriorityQueue([])
inspect(queue.length(), content="0")
@test.assert_eq(queue.push(1).length(), 1)
}#PriorityQueue::new
#as_free_fn(deprecated="Use `PriorityQueue([])` instead")
#deprecated("Use `PriorityQueue([])` instead")
fn[A] PriorityQueue::new() -> PriorityQueue[A]Creates a new empty immutable priority queue.
Deprecated: use PriorityQueue([]) instead.
#PriorityQueue::peek
Peeks at the first value in the immutable priority queue, which returns None if the immutable priority queue is empty.
Example
test {
let queue = @priority_queue.from_array([1, 2, 3, 4])
@test.assert_eq(queue.peek(), Some(4))
}#PriorityQueue::pop
Pops the first value from the immutable priority queue, which returns None if the queue is empty.
Example
test {
let queue = @priority_queue.from_array([1, 2, 3, 4])
let first = queue.pop()
@test.assert_eq(first, Some(@priority_queue.from_array([1, 2, 3])))
}#PriorityQueue::push
Adds a value to the immutable priority queue.
Example
test {
let queue = @priority_queue.PriorityQueue([])
@test.assert_eq(queue.push(1).length(), 1)
}#PriorityQueue::to_array
Returns an array of all elements in descending priority order.
Install
Installed by default
corestandard library
0.1.20260811+bc794d341
Apache-2.0
Updated 5 days ago