diff options
Diffstat (limited to 'lib')
| -rw-r--r-- | lib/pure/collections/heapqueue.nim | 17 |
1 files changed, 13 insertions, 4 deletions
diff --git a/lib/pure/collections/heapqueue.nim b/lib/pure/collections/heapqueue.nim index f958a5b0a..b0789593a 100644 --- a/lib/pure/collections/heapqueue.nim +++ b/lib/pure/collections/heapqueue.nim @@ -50,6 +50,7 @@ assert jobs[0].priority == 1 ]## +import std/private/since type HeapQueue*[T] = object ## A heap queue, commonly known as a priority queue. @@ -125,6 +126,12 @@ proc pop*[T](heap: var HeapQueue[T]): T = else: result = lastelt +proc find*[T](heap: HeapQueue[T], x: T): int {.since: (1, 3).} = + ## Linear scan to find index of item ``x`` or -1 if not found. + result = -1 + for i in 0 ..< heap.len: + if heap[i] == x: return i + proc del*[T](heap: var HeapQueue[T], index: Natural) = ## Removes the element at `index` from `heap`, maintaining the heap invariant. swap(heap.data[^1], heap.data[index]) @@ -207,18 +214,20 @@ when isMainModule: heap.del(0) doAssert(heap[0] == 1) - heap.del(heap.data.find(7)) + heap.del(heap.find(7)) doAssert(heap.toSortedSeq == @[1, 2, 3, 4, 5, 6, 8, 9]) - heap.del(heap.data.find(5)) + heap.del(heap.find(5)) doAssert(heap.toSortedSeq == @[1, 2, 3, 4, 6, 8, 9]) - heap.del(heap.data.find(6)) + heap.del(heap.find(6)) doAssert(heap.toSortedSeq == @[1, 2, 3, 4, 8, 9]) - heap.del(heap.data.find(2)) + heap.del(heap.find(2)) doAssert(heap.toSortedSeq == @[1, 3, 4, 8, 9]) + doAssert(heap.find(2) == -1) + block: # Test del last var heap = initHeapQueue[int]() let data = [1, 2, 3] |