Sets, deques & heaps

Unique values, queues, and priority queues.

On this page

Besides arrays and maps, the core library has HashSet for unique values, Deque for queues, Heap for priority queues and FlatMap for small ordered maps. All of them are available without a use.

Unique values#

Valk

fn main() {
    let seen = HashSet[String]{ "a", "b" }
    seen.add("c")
    println(seen.insert("a"))   // false: already there
    println(seen.has("b"))      // true
    println(seen.remove("b"))   // true: it was there
    println(seen.length)        // 2
    each seen as value : print(value + " ")
    println("")
}

add ignores a value that is already present; insert does the same but returns whether the value was new. Values are compared like map keys.

Set operations#

Valk

fn main() {
    let a = HashSet[int]{ 1, 2, 3 }
    let b = HashSet[int]{ 2, 3, 4 }
    println((a + b).length)                // 4: union
    println(a.intersection(b).length)      // 2
    println(a.difference(b).items().join(",")) // 1
    println(a.is_subset_of(b))             // false
    println(a.is_disjoint(HashSet[int]{ 9 })) // true
}

Method	Result
`union(other)`, `a + b`	Values in either set
`intersection(other)`	Values in both
`difference(other)`	Values not in `other`
`is_subset_of(other)`, `is_disjoint(other)`, `equals(other)`	`bool`
`items()`	The values as an `Array`
`add_all(array)`	Add many values
`remove_where(fn)`, `retain(fn)`	Remove or keep values the function accepts

Queues at both ends#

A Deque adds and removes quickly at the front and the back:

Valk

fn main() {
    let queue = Deque[String]{ "b", "c" }
    queue.push_front("a")
    queue.push_back("d")
    println(queue.pop_front() !? "")  // a
    println(queue.pop_back() !? "")   // d
    println(queue.peek_front() !? "") // b
    println(queue[1] ?? "")           // c: null when out of range
    queue[0] = "B" !!                 // throws when out of range
    each queue as item : print(item)  // Bc
    println("")
}

pop_* and peek_* throw LookupError on an empty deque. to_array() copies the items front to back.

Priority queues#

A Heap always pops the smallest item first:

Valk

fn main() {
    let heap = Heap[int]{ 5, 1, 4 }
    heap.push(3)
    println(heap.pop() !? 0)   // 1
    println(heap.peek() !? 0)  // 3
    println(heap.drain().join(",")) // 3,4,5: pops everything in order

    let tasks = Heap[(int, String)]{}
    tasks.push((2, "write"))
    tasks.push((1, "plan"))
    let next = tasks.pop() !? (0, "")
    println(next[1])           // plan: tuples order by their first member
}

For another order, pass a function to new that returns true when a should come out before b:

Valk

fn main() {
    let longest_first = Heap[String].new(fn(a: String, b: String) bool { return a.length > b.length })
    longest_first.push("hi")
    longest_first.push("hello")
    println(longest_first.pop() !? "")  // hello
}

Small ordered maps#

A FlatMap[K, V] keeps its entries in insertion order, also after removals. It finds keys by comparing each one, so it suits maps of a few dozen entries:

Valk

fn main() {
    let headers = FlatMap[String, String]{ "Host" => "example.com" }
    headers.set("Accept", "*/*")
    headers["Host"] = "valk-lang.dev"
    each headers as value, name : println("%name: %value")
    println(headers.get("Accept") !? "") // */*
}

It has the same methods as HashMap, and its keys only need ==.

View page source ↗