collections
Data structures: vector and map, stack, queue, deque, set, linked list, priority queue and counter.
import collections
Vector and HashMap, which turn up in every program, are defined in this package, but you do not have to import it to use them. The rest, such as the stack and the queue, become available with import collections.
All of these are generic: you set the element type with <...>, as in collections.Stack<str>. All of them allocate, so write defer ....free() right after creating one.
Which should you pick? For an ordinary list, Vector; for "last in, first out", Stack; for "first in, first out", Queue; for adding and removing at both ends, Deque; for fast lookup by a key, HashMap; for removing duplicates, Set; and for "always give me the smallest", PriorityQueue.
Types
LinkedList
struct LinkedList<T>| Name | Type | Description |
|---|---|---|
vals | Vector | The values of the nodes. |
nxt | Vector | The index of each node's next node. |
prv | Vector | The index of each node's previous node. |
head | int | The index of the first node. |
tail | int | The index of the last node. |
freed | int | The index of the first freed node, kept for reuse. |
count | int = 0 | The number of elements. |
import collections
func main:
mut l := collections.LinkedList {} as collections.LinkedList<str>
defer l.free()
l.push_back("b")
l.push_back("c")
l.push_front("a")
println l.to_vector(), l.size()
println l.front_val(), l.back_val(), l.get(1)
println l.pop_front(), l.pop_back(), l.size(), l.is_empty()
endpush_back
func push_back(v: T)The example for this item is shown with the ones above: collections-LinkedList.salam
push_front
func push_front(v: T)The example for this item is shown with the ones above: collections-LinkedList.salam
pop_front
func pop_front(): TThe example for this item is shown with the ones above: collections-LinkedList.salam
pop_back
func pop_back(): TThe example for this item is shown with the ones above: collections-LinkedList.salam
front_val
func front_val(): TThe example for this item is shown with the ones above: collections-LinkedList.salam
back_val
func back_val(): TThe example for this item is shown with the ones above: collections-LinkedList.salam
size
func size(): intThe example for this item is shown with the ones above: collections-LinkedList.salam
is_empty
func is_empty(): boolThe example for this item is shown with the ones above: collections-LinkedList.salam
get
func get(i: int): Ti from the front. Reaching it means walking from the front, so for repeated access by index a vector is better.The example for this item is shown with the ones above: collections-LinkedList.salam
to_vector
func to_vector(): Vector<T>The example for this item is shown with the ones above: collections-LinkedList.salam
free
func free()The example for this item is shown with the ones above: collections-LinkedList.salam
Counter
struct Counter<K>| Name | Type | Description |
|---|---|---|
m | HashMap | A map from each thing to its count. |
import collections
import str
func main:
mut c := collections.Counter {} as collections.Counter<str>
defer c.free()
each word in str.Fields("in the name of the friend"):
c.add(word)
end
c.add_n("friend", 2)
println c.count("the"), c.count("friend"), c.count("missing"), c.distinct()
endadd
func add(k: K)k.The example for this item is shown with the ones above: collections-Counter.salam
add_n
func add_n(k: K, n: int)n to the count of k.The example for this item is shown with the ones above: collections-Counter.salam
count
func count(k: K): intk has been seen, or zero if never.The example for this item is shown with the ones above: collections-Counter.salam
distinct
func distinct(): intThe example for this item is shown with the ones above: collections-Counter.salam
free
func free()The example for this item is shown with the ones above: collections-Counter.salam
PriorityQueue
struct PriorityQueue<T>| Name | Type | Description |
|---|---|---|
h | Vector | The elements as a binary heap. |
import collections
func main:
mut q := collections.PriorityQueue {} as collections.PriorityQueue<int>
defer q.free()
each n in [5, 1, 4, 2, 3]:
q.push(n)
end
println q.peek(), q.size()
until not q.is_empty():
print q.pop(), ""
end
println ""
endpush
func push(x: T)The example for this item is shown with the ones above: collections-PriorityQueue.salam
peek
func peek(): TThe example for this item is shown with the ones above: collections-PriorityQueue.salam
size
func size(): intThe example for this item is shown with the ones above: collections-PriorityQueue.salam
is_empty
func is_empty(): boolThe example for this item is shown with the ones above: collections-PriorityQueue.salam
pop
func pop(): TThe example for this item is shown with the ones above: collections-PriorityQueue.salam
free
func free()The example for this item is shown with the ones above: collections-PriorityQueue.salam
Set
struct Set<T>| Name | Type | Description |
|---|---|---|
m | HashMap | The map that holds the elements as keys. |
import collections
func main:
mut s := collections.Set {} as collections.Set<str>
defer s.free()
each word in ["hello", "world", "hello"]:
s.add(word)
end
println s.size(), s.has("hello"), s.has("goodbye")
println s.remove("world"), s.size(), s.is_empty()
endadd
func add(x: T)The example for this item is shown with the ones above: collections-Set.salam
has
func has(x: T): boolThe example for this item is shown with the ones above: collections-Set.salam
remove
func remove(x: T): boolThe example for this item is shown with the ones above: collections-Set.salam
size
func size(): intThe example for this item is shown with the ones above: collections-Set.salam
is_empty
func is_empty(): boolThe example for this item is shown with the ones above: collections-Set.salam
free
func free()The example for this item is shown with the ones above: collections-Set.salam
OrderedMap
struct OrderedMap| Name | Type | Description |
|---|---|---|
keys | Vector | The keys in insertion order. |
vals | Vector | The values in the same order. |
idx | HashMap | A map from key to its position, for fast lookup. |
import collections
func main:
mut m := collections.OrderedMap {}
defer m.free()
m.set("name", "Salam")
m.set("version", "0.5.0")
m.set("language", "english")
println m.len(), m.has("version"), m.get("name"), m.get_or("licence", "-")
println m.index_of("language"), m.key_at(0), m.val_at(0)
m.set_at(0, "Salam")
println m.remove("version"), m.len()
keys := m.clone_keys()
println keys
endindex_of
func index_of(k: str): intThe example for this item is shown with the ones above: collections-OrderedMap.salam
len
func len(): intThe example for this item is shown with the ones above: collections-OrderedMap.salam
has
func has(k: str): boolThe example for this item is shown with the ones above: collections-OrderedMap.salam
get
func get(k: str): strThe example for this item is shown with the ones above: collections-OrderedMap.salam
get_or
func get_or(k: str, def: str): strThe example for this item is shown with the ones above: collections-OrderedMap.salam
set
func set(k: str, v: str): intThe example for this item is shown with the ones above: collections-OrderedMap.salam
key_at
func key_at(i: int): stri.The example for this item is shown with the ones above: collections-OrderedMap.salam
val_at
func val_at(i: int): stri.The example for this item is shown with the ones above: collections-OrderedMap.salam
set_at
func set_at(i: int, v: str)i.The example for this item is shown with the ones above: collections-OrderedMap.salam
remove
func remove(k: str): intThe example for this item is shown with the ones above: collections-OrderedMap.salam
clone_keys
func clone_keys(): Vector<str>The example for this item is shown with the ones above: collections-OrderedMap.salam
free
func free()The example for this item is shown with the ones above: collections-OrderedMap.salam
Deque
struct Deque<T>| Name | Type | Description |
|---|---|---|
front | Vector | The elements at the front end. |
back | Vector | The elements at the back end. |
import collections
func main:
mut d := collections.Deque {} as collections.Deque<int>
defer d.free()
d.push_back(2)
d.push_back(3)
d.push_front(1)
println d.front_val(), d.back_val(), d.get(1), d.size()
println d.pop_front(), d.pop_back(), d.size(), d.is_empty()
endpush_front
func push_front(x: T)The example for this item is shown with the ones above: collections-Deque.salam
push_back
func push_back(x: T)The example for this item is shown with the ones above: collections-Deque.salam
pop_front
func pop_front(): TThe example for this item is shown with the ones above: collections-Deque.salam
pop_back
func pop_back(): TThe example for this item is shown with the ones above: collections-Deque.salam
front_val
func front_val(): TThe example for this item is shown with the ones above: collections-Deque.salam
back_val
func back_val(): TThe example for this item is shown with the ones above: collections-Deque.salam
size
func size(): intThe example for this item is shown with the ones above: collections-Deque.salam
is_empty
func is_empty(): boolThe example for this item is shown with the ones above: collections-Deque.salam
get
func get(i: int): Ti counted from the front.The example for this item is shown with the ones above: collections-Deque.salam
free
func free()The example for this item is shown with the ones above: collections-Deque.salam
Vector
struct Vector<T>[i].| Name | Type | Description |
|---|---|---|
data | T* | The address of the elements in memory. |
func main:
mut v := Vector {} as Vector<int>
defer v.free()
v.reserve(8)
println v.len(), v.cap() >= 8, v.is_empty()
v.push(10)
v.push(20)
v.push(30)
println v, v.first(), v.last(), v.get(1), v[2]
v.set(0, 11)
v[1] = 22
v.insert(1, 15)
println v
println v.remove_at(1), v.pop(), v
r := v.ref(0)
r[0] = 99
println v
v.resize_set(v.len(), 7)
println v
v.clear()
println v.len()
mut z := Vector {} as Vector<int>
defer z.free()
z.zeros(3)
println z
mut a := Vector {} as Vector<int>
defer a.free()
a.alloc(4)
println a.len()
endreserve
func reserve(need: int)need elements in advance, so that later additions do not move the memory again.The example for this item is shown with the ones above: collections-Vector.salam
push
func push(x: T)The example for this item is shown with the ones above: collections-Vector.salam
pop
func pop(): TThe example for this item is shown with the ones above: collections-Vector.salam
get
func get(i: int): Ti.The example for this item is shown with the ones above: collections-Vector.salam
ref
func ref(i: int): T*i, so you can change it in place without a copy.The example for this item is shown with the ones above: collections-Vector.salam
set
func set(i: int, x: T)i.The example for this item is shown with the ones above: collections-Vector.salam
resize_set
func resize_set(i: int, x: T)set, but grows the vector when i is past the end. The slots between the old length and i have no defined value, so either fill them in order or start with zeros.The example for this item is shown with the ones above: collections-Vector.salam
zeros
func zeros(n: int)n zero elements.The example for this item is shown with the ones above: collections-Vector.salam
alloc
func alloc(n: int)n without initialising it; fill the elements before reading them.The example for this item is shown with the ones above: collections-Vector.salam
len
func len(): intThe example for this item is shown with the ones above: collections-Vector.salam
cap
func cap(): intThe example for this item is shown with the ones above: collections-Vector.salam
is_empty
func is_empty(): boolThe example for this item is shown with the ones above: collections-Vector.salam
first
func first(): TThe example for this item is shown with the ones above: collections-Vector.salam
last
func last(): TThe example for this item is shown with the ones above: collections-Vector.salam
clear
func clear()The example for this item is shown with the ones above: collections-Vector.salam
insert
func insert(i: int, x: T)i and shifts the rest forward.The example for this item is shown with the ones above: collections-Vector.salam
remove_at
func remove_at(i: int): Ti and shifts the rest back.The example for this item is shown with the ones above: collections-Vector.salam
operator_index
func operator_index(i: int): Tv[i].The example for this item is shown with the ones above: collections-Vector.salam
operator_index_set
func operator_index_set(i: int, x: T)v[i] = x.The example for this item is shown with the ones above: collections-Vector.salam
iter
func iter(): VectorIter<T>each ... in is simpler.func main:
mut v := Vector {} as Vector<str>
defer v.free()
v.push("spring")
v.push("summer")
mut it := v.iter()
until it.has_next():
println it.value()
it.next()
end
endfree
func free()The example for this item is shown with the ones above: collections-Vector.salam
VectorIter
struct VectorIter<T>has_next, value and next.| Name | Type | Description |
|---|---|---|
data | T* | The address of the vector's elements. |
len | int = 0 | The number of elements. |
pos | int = 0 | The current position. |
The example for this item is shown with the ones above: collections-VectorIter.salam
has_next
func has_next(): boolThe example for this item is shown with the ones above: collections-VectorIter.salam
value
func value(): TThe example for this item is shown with the ones above: collections-VectorIter.salam
next
func next()The example for this item is shown with the ones above: collections-VectorIter.salam
Queue
struct Queue<T>| Name | Type | Description |
|---|---|---|
inbox | Vector | The newly arrived elements. |
outbox | Vector | The elements ready to leave; whenever it empties it is refilled from inbox. |
import collections
func main:
mut q := collections.Queue {} as collections.Queue<str>
defer q.free()
q.enqueue("customer 1")
q.enqueue("customer 2")
q.enqueue("customer 3")
println q.peek(), q.size()
println q.dequeue(), q.dequeue(), q.is_empty()
endenqueue
func enqueue(x: T)The example for this item is shown with the ones above: collections-Queue.salam
dequeue
func dequeue(): TThe example for this item is shown with the ones above: collections-Queue.salam
peek
func peek(): TThe example for this item is shown with the ones above: collections-Queue.salam
size
func size(): intThe example for this item is shown with the ones above: collections-Queue.salam
is_empty
func is_empty(): boolThe example for this item is shown with the ones above: collections-Queue.salam
free
func free()The example for this item is shown with the ones above: collections-Queue.salam
Stack
struct Stack<T>| Name | Type | Description |
|---|---|---|
items | Vector | The elements of the stack; the last one is the top. |
import collections
func main:
mut s := collections.Stack {} as collections.Stack<str>
defer s.free()
s.push("book 1")
s.push("book 2")
s.push("book 3")
println s.peek(), s.size()
println s.pop(), s.pop(), s.size()
s.clear()
println s.is_empty()
endpush
func push(x: T)The example for this item is shown with the ones above: collections-Stack.salam
pop
func pop(): TThe example for this item is shown with the ones above: collections-Stack.salam
peek
func peek(): TThe example for this item is shown with the ones above: collections-Stack.salam
size
func size(): intThe example for this item is shown with the ones above: collections-Stack.salam
is_empty
func is_empty(): boolThe example for this item is shown with the ones above: collections-Stack.salam
clear
func clear()The example for this item is shown with the ones above: collections-Stack.salam
free
func free()The example for this item is shown with the ones above: collections-Stack.salam
Pair
struct Pair<A, B>| Name | Type | Description |
|---|---|---|
first | A | The first value. |
second | B | The second value. |
import collections
func main:
p := collections.Pair { first = "Tehran", second = 8700000 } as collections.Pair<str, int>
println p.first, p.second
endCircularList
struct CircularList<T>| Name | Type | Description |
|---|---|---|
items | Vector | The elements in the order they were added. |
head | int = 0 | The index of the current element. |
import collections
func main:
mut c := collections.CircularList {} as collections.CircularList<str>
defer c.free()
each name in ["Ali", "Sara", "Reza"]:
c.add(name)
end
repeat 4:
print c.current(), ""
c.advance()
end
println ""
c.rotate(1)
println c.to_vector(), c.get(0), c.size(), c.is_empty()
endadd
func add(x: T)The example for this item is shown with the ones above: collections-CircularList.salam
size
func size(): intThe example for this item is shown with the ones above: collections-CircularList.salam
is_empty
func is_empty(): boolThe example for this item is shown with the ones above: collections-CircularList.salam
get
func get(i: int): Ti places on from the current one; a negative number is accepted.The example for this item is shown with the ones above: collections-CircularList.salam
rotate
func rotate(k: int)k places, or back with a negative number.The example for this item is shown with the ones above: collections-CircularList.salam
current
func current(): TThe example for this item is shown with the ones above: collections-CircularList.salam
advance
func advance()The example for this item is shown with the ones above: collections-CircularList.salam
to_vector
func to_vector(): Vector<T>The example for this item is shown with the ones above: collections-CircularList.salam
free
func free()The example for this item is shown with the ones above: collections-CircularList.salam
HashMap
struct HashMap<K, V>OrderedMap.| Name | Type | Description |
|---|---|---|
keys | K* | The address of the array of keys. |
vals | V* | The address of the array of values. |
state | int* | The state of each slot: empty, filled or removed. |
cap | int = 0 | The number of slots. |
count | int = 0 | The number of keys present. |
used | int = 0 | The number of slots in use, removed ones included. |
func main:
mut m := HashMap {} as HashMap<str, int>
defer m.free()
println m.is_empty()
m.put("apple", 3)
m.insert("pear", 5)
m.put("apple", 4)
println m.size(), m.has("apple"), m.get("apple"), m.get_or("banana", 0)
println m.remove("pear"), m.remove("pear"), m.size()
mut it := m.iter()
until it.has_next():
println it.key(), it.value()
it.next()
end
endput
func put(k: K, v: V)The example for this item is shown with the ones above: collections-HashMap.salam
insert
func insert(k: K, v: V)put.The example for this item is shown with the ones above: collections-HashMap.salam
has
func has(k: K): boolThe example for this item is shown with the ones above: collections-HashMap.salam
get
func get(k: K): Vhas first or use get_or.The example for this item is shown with the ones above: collections-HashMap.salam
get_or
func get_or(k: K, def: V): VThe example for this item is shown with the ones above: collections-HashMap.salam
remove
func remove(k: K): boolThe example for this item is shown with the ones above: collections-HashMap.salam
size
func size(): intThe example for this item is shown with the ones above: collections-HashMap.salam
is_empty
func is_empty(): boolThe example for this item is shown with the ones above: collections-HashMap.salam
iter
func iter(): MapIter<K, V>each key, value in is simpler.The example for this item is shown with the ones above: collections-HashMap.salam
free
func free()The example for this item is shown with the ones above: collections-HashMap.salam
MapIter
struct MapIter<K, V>| Name | Type | Description |
|---|---|---|
keys | K* | The address of the array of keys. |
vals | V* | The address of the array of values. |
state | int* | The state of the slots. |
cap | int = 0 | The number of slots. |
pos | int = 0 | The current position. |
The example for this item is shown with the ones above: collections-HashMap.salam
has_next
func has_next(): boolThe example for this item is shown with the ones above: collections-HashMap.salam
key
func key(): KThe example for this item is shown with the ones above: collections-HashMap.salam
value
func value(): VThe example for this item is shown with the ones above: collections-HashMap.salam
next
func next()The example for this item is shown with the ones above: collections-HashMap.salam
Functions
contains
func contains<T>(v: Vector<T>, x: T): boolx is in the vector.import collections
func main:
mut a := Vector {} as Vector<int>
defer a.free()
each n in [1, 2, 3, 2, 5]:
a.push(n)
end
println collections.contains(a, 3), collections.index_of(a, 2), collections.last_index_of(a, 2), collections.count_of(a, 2)
println collections.reverse(a), collections.slice(a, 1, 3)
b := collections.clone(a)
collections.swap(a, 0, 4)
println a, b
mut c := Vector {} as Vector<int>
defer c.free()
collections.extend(c, b)
collections.extend(c, b)
println c.len()
endindex_of
func index_of<T>(v: Vector<T>, x: T): intx, or minus one.The example for this item is shown with the ones above: collections-Funcs.salam
reverse
func reverse<T>(v: Vector<T>): Vector<T>The example for this item is shown with the ones above: collections-Funcs.salam
clone
func clone<T>(v: Vector<T>): Vector<T>The example for this item is shown with the ones above: collections-Funcs.salam
slice
func slice<T>(v: Vector<T>, start: int, count: int): Vector<T>count elements starting at start.The example for this item is shown with the ones above: collections-Funcs.salam
swap
func swap<T>(v: Vector<T>, i: int, j: int)The example for this item is shown with the ones above: collections-Funcs.salam
count_of
func count_of<T>(v: Vector<T>, x: T): intx occurs in the vector.The example for this item is shown with the ones above: collections-Funcs.salam
last_index_of
func last_index_of<T>(v: Vector<T>, x: T): intx, or minus one.The example for this item is shown with the ones above: collections-Funcs.salam
extend
func extend<T>(dst &: Vector<T>, src: Vector<T>)src to the end of dst.The example for this item is shown with the ones above: collections-Funcs.salam