collections
Data structures: vector and map, stack, queue, deque, set, linked list, priority queue and counter.
import collections
This package holds Salam's data structures. Vector and HashMap, which turn up in every program, are defined here but built in: you can use them without an import. The rest (Stack, Queue, Deque, Set, Counter, PriorityQueue, OrderedMap, LinkedList, CircularList, Pair) and the vector helpers such as clone and IndexOf need import collections. To sort or search a vector use sort; to share a structure between threads, guard it with sync, because none of these types locks.
All of them are generic: you set the element type with <...>, as in collections.Stack<str>, and build an empty one with collections.Stack {} as collections.Stack<str>. All of them allocate, so write defer x.Free() right after creating one. Free releases the structure itself, not heap strings or other objects stored in it.
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; for "always give me the smallest", PriorityQueue; and for string settings that must keep their order, OrderedMap. Most of them are thin layers over Vector: a stack is one vector, a queue and a deque are two.
What people get wrong:
- Copying with
=.b := acopies only the vector's header, so both names see the same elements:b.Set(0, x)changesatoo, and apushon one can move the memory under the other. Take a real copy with the built-inv.copy()or withcollections.clone(v). The same goes for aHashMap(m.copy()) and for any struct holding one. - Changing a struct you got from a map.
m.Get(k)returns a copy; change it andPutit back. - Reading from an empty structure.
pop,peek,dequeue,first,lastand an index past the end stop the program with a message such asVector.pop: empty. Checkis_empty()first. A--releasebuild leaves the check out, and the same mistake then reads garbage. - Printing a map in its own order.
each key, value in mvisits the slots in hash order, which changes as the map grows. Collect and sort the keys when the order shows.
Vector: insert, remove, copy
push and pop work at the end in constant time. Insert and remove_at shift every later element, so they are fine for short lists and slow inside a loop over a long one. IndexOf and contains scan from the front. The example also shows the copy trap from the list above: alias writes straight into line, while the clone keeps its own elements.
import collections
func main:
mut line := Vector {} as Vector<str>
defer line.Free()
each name in ["Ali", "Sara", "Reza"]:
line.Push(name)
end
line.Insert(1, "Mina")
println "after insert:", line
served := line.RemoveAt(0)
println "served", served, "->", line
println "Reza is at", collections.IndexOf(line, "Reza"), "and Omid at", collections.IndexOf(line, "Omid")
backup := collections.Clone(line)
defer backup.Free()
alias := line
alias.Set(0, "Neda")
println "alias wrote into line:", line.Get(0)
println "the clone kept: ", backup.Get(0)
front := collections.Slice(line, 0, 2)
defer front.Free()
println "first two:", front, "last:", line.Last()
endslice returns a new vector and clamps a range that runs past the end, so it never fails. Printing a vector with println shows its elements, which is handy while debugging.
HashMap: stock by product code
A HashMap finds a value by its key in constant time. Get on a missing key returns the zero value of the type (0, empty text, a struct of zeros) and never fails, so ask Has first when a missing key is an error, or use GetOr when a default is right. Struct values come back as copies: change the copy and Put it again.
import sort
struct Stock:
pub name: str = ""
pub qty: int = 0
end
func main:
mut stock := HashMap {} as HashMap<str, Stock>
defer stock.Free()
stock.Put("TEA-01", Stock { name = "Green tea", qty = 40 })
stock.Put("COF-02", Stock { name = "Coffee beans", qty = 12 })
stock.Put("MUG-07", Stock { name = "Mug", qty = 2 })
each sku in ["COF-02", "MUG-07", "TEA-01", "MUG-07", "BAG-99"]:
if not stock.Has(sku):
println "unknown product", sku
continue
end
mut item := stock.Get(sku)
item.qty--
stock.Put(sku, item)
end
println "a missing key gives a zero value:", stock.Get("BAG-99").qty
mut reorder_at := HashMap {} as HashMap<str, int>
defer reorder_at.Free()
reorder_at.Put("TEA-01", 10)
mut skus := Vector {} as Vector<str>
defer skus.Free()
each sku, item in stock:
if item.qty > 0:
skus.Push(sku)
else:
println item.name, "is sold out"
end
end
sort.Sort(skus)
each sku in skus:
item := stock.Get(sku)
low := item.qty <= reorder_at.GetOr(sku, 5)
println sku, item.name, item.qty, "reorder:", low
end
endDo not Put or Remove while an each loop walks the same map: a Put can grow the table and move every entry. Collect the keys first, as the example does, then change the map.
Stack: matching brackets
A stack is the tool when the most recent thing must be dealt with first. Checking brackets is the classic case: push every opening bracket, and on a closing bracket the top of the stack must be its partner. peek looks at the top without removing it, and whatever is left at the end was never closed.
import collections
import str
func opener(c: char): char:
if c == ')': ret '(' end
if c == ']': ret '[' end
ret '{'
end
func check(s: str): str:
mut open := collections.Stack {} as collections.Stack<char>
defer open.Free()
repeat str.Len(s) in i:
c := s[i]
if c == '(' or c == '[' or c == '{':
open.Push(c)
else c == ')' or c == ']' or c == '}':
if open.IsEmpty() or open.Peek() != opener(c):
ret "mismatch at " + str.FromInt(i)
end
open.Pop()
end
end
if not open.IsEmpty():
ret str.FromInt(open.Size()) + " left open"
end
ret "balanced"
end
func main:
each s in ["f(a[1], {b: 2})", "(1 + 2]", "{[()]}", "((x)", "x)"]:
println s, "->", check(s)
end
endQueue: shortest path in a grid
A queue hands items out in the order they arrived, which is exactly what a breadth first search needs: every cell at distance 1 is handled before any cell at distance 2, so the first time the search reaches the exit, it has found a shortest path. enqueue adds at the back and dequeue takes from the front.
import collections
func main:
maze := ["S.#.....", ".##.###.", "....#...", ".##...#E"]
rows := maze.Len()
cols := 8
dr := [-1, 1, 0, 0]
dc := [0, 0, -1, 1]
mut dist := Vector {} as Vector<int>
defer dist.Free()
repeat rows * cols:
dist.Push(-1)
end
mut todo := collections.Queue {} as collections.Queue<int>
defer todo.Free()
todo.enqueue(0)
dist.Set(0, 0)
mut goal := -1
until not todo.IsEmpty():
cell := todo.dequeue()
r := cell / cols
c := cell % cols
if maze[r][c] == 'E':
goal = cell
break
end
repeat 4 in k:
nr := r + dr[k]
nc := c + dc[k]
if nr >= 0 and nr < rows and nc >= 0 and nc < cols:
next := nr * cols + nc
if maze[nr][nc] != '#' and dist.Get(next) == -1:
dist.Set(next, dist.Get(cell) + 1)
todo.enqueue(next)
end
end
end
end
println "shortest path to E:", dist.Get(goal), "steps"
mut seen := 0
each d in dist:
if d >= 0: seen++ end
end
println "cells reached:", seen, "of", rows * cols
endDeque and Stack together: undo with a limit
An undo history adds at one end and, once it is full, drops the oldest step at the other end, so it needs a Deque. Undone steps go onto a Stack for redo, and any new edit clears that stack, as editors do.
import collections
func main:
limit := 3
mut undo := collections.Deque {} as collections.Deque<str>
defer undo.Free()
mut redo := collections.Stack {} as collections.Stack<str>
defer redo.Free()
mut doc := ""
each word in ["Salam", " is", " a", " small", " language"]:
undo.PushBack(doc)
if undo.Size() > limit:
undo.PopFront()
end
redo.Clear()
doc += word
println "typed: [" + doc + "]"
end
until not undo.IsEmpty():
redo.Push(doc)
doc = undo.PopBack()
println "undo: [" + doc + "]"
end
println "the history keeps only", limit, "steps, so the rest are gone"
doc = redo.Pop()
println "redo: [" + doc + "]", redo.Size(), "more redo steps"
endCounter and Set: counting words
Counter keeps a count for each value it has seen; count answers 0 for a value it never saw, so no check is needed first. A Set answers "have I seen this?" quickly and here keeps the words in order of first use. A stable sort by count then keeps that order among words with the same count.
import collections
import sort
import str
func main:
text := "to be or not to be that is the question to ask"
mut counts := collections.Counter {} as collections.Counter<str>
defer counts.Free()
mut seen := collections.Set {} as collections.Set<str>
defer seen.Free()
mut order := Vector {} as Vector<str>
defer order.Free()
each w in str.Fields(text):
counts.Add(w)
if not seen.Has(w):
seen.Add(w)
order.Push(w)
end
end
println counts.distinct(), "different words, in order of first use:"
println order
sort.StableSortBy(order, (a: str, b: str): ret counts.count(a) > counts.count(b) end)
println "most frequent:"
repeat 3 in i:
w := order.Get(i)
println " " + w, counts.count(w)
end
endPriorityQueue: the most urgent job first
PriorityQueue is a binary min-heap: push and pop take log n steps, and pop always returns the smallest element. It compares elements with <, so it holds numbers or strings, not structs. To queue records, pack the priority and a position into one number, here urgency * 1000 + index, and keep the records in a vector. The position also breaks ties in arrival order, which a heap would not do by itself. For the largest first, push negative numbers.
import collections
func main:
jobs := ["nightly backup", "send invoices", "resize images", "page the on-call", "rebuild index"]
urgency := [3, 2, 3, 1, 2]
mut queue := collections.PriorityQueue {} as collections.PriorityQueue<i64>
defer queue.Free()
repeat jobs.Len() in i:
queue.Push((urgency[i] as i64) * 1000 + (i as i64))
end
until not queue.IsEmpty():
key := queue.Pop()
println "urgency", key / 1000, jobs[(key % 1000) as int]
end
mut largest := collections.PriorityQueue {} as collections.PriorityQueue<int>
defer largest.Free()
each kb in [120, 4800, 35, 990]:
largest.Push(0 - kb)
end
println "largest upload first:", 0 - largest.Pop(), "KB, then", 0 - largest.Peek(), "KB"
endOrderedMap: settings that keep their order
A HashMap gives its keys back in no particular order, which is a nuisance when you write a configuration file back to disk. OrderedMap keeps keys in the order they were first set; changing a value keeps its position, and Set returns that position. GetOr supplies a default for a missing key.
import collections
import str
func main:
mut conf := collections.OrderedMap {}
defer conf.Free()
conf.Set("host", "127.0.0.1")
conf.Set("port", "8080")
conf.Set("workers", "4")
conf.Set("log", "info")
overrides := ["port=9000", "log=debug", "tls=on", "broken"]
each line in overrides:
cut := str.IndexOf(line, "=")
if cut < 0:
println "skipping", line
continue
end
key := line.Substr(0, cut)
value := line.Substr(cut + 1, str.Len(line) - cut - 1)
known := conf.Has(key)
pos := conf.Set(key, value)
if known:
println "changed", key, "at position", pos
else:
println "added", key, "at position", pos
end
end
conf.Remove("workers")
repeat conf.Len() in i:
println conf.KeyAt(i) + " = " + conf.ValAt(i)
end
println "timeout:", conf.GetOr("timeout", "30")
end| You need | Use | Main methods |
|---|---|---|
| Last in, first out | Stack | push, pop, peek |
| First in, first out | Queue | enqueue, dequeue |
| Both ends | Deque | push_back, pop_front, pop_back |
| How often each value appears | Counter | add, count, distinct |
| Each value once | Set | add, Has |
| A list by position | Vector | push, Get, Insert, remove_at |
| A value by key | HashMap | Put, Has, GetOr, Remove |
| The smallest first | PriorityQueue | push, pop, peek |
| Taking turns in a circle | CircularList | current, advance |
| String settings in a fixed order | OrderedMap | Set, GetOr, KeyAt, ValAt |
Every one of these types allocates. Put defer x.Free() on the line after you create it, as the examples do, and the memory is released when the function returns. Set and Counter have no way to list their contents; when you need that, walk their inner map with each value, _ in s.m, or keep a vector beside them as the word count example does.
Types
Deque
struct Deque<T>pop_front and pop_back copies all its elements each time.| 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.PushBack(2)
d.PushBack(3)
d.PushFront(1)
println d.FrontVal(), d.BackVal(), d.Get(1), d.Size()
println d.PopFront(), d.PopBack(), d.Size(), d.IsEmpty()
endPushFront
func PushFront(x: T)push_front
func push_front(x: T)The example for this item is shown with the ones above: collections-Deque.salam
PushBack
func PushBack(x: T)push_back
func push_back(x: T)The example for this item is shown with the ones above: collections-Deque.salam
PopFront
func PopFront(): Tpop_front
func pop_front(): TThe example for this item is shown with the ones above: collections-Deque.salam
PopBack
func PopBack(): Tpop_back
func pop_back(): TThe example for this item is shown with the ones above: collections-Deque.salam
Front
func Front(): Tfront_val
func front_val(): TThe example for this item is shown with the ones above: collections-Deque.salam
FrontVal
func FrontVal(): TBack
func Back(): Tback_val
func back_val(): TThe example for this item is shown with the ones above: collections-Deque.salam
BackVal
func BackVal(): TSize
func Size(): intThe example for this item is shown with the ones above: collections-Deque.salam
size
func size(): intIsEmpty
func IsEmpty(): boolThe example for this item is shown with the ones above: collections-Deque.salam
is_empty
func is_empty(): boolGet
func Get(i: int): Ti counted from the front.The example for this item is shown with the ones above: collections-Deque.salam
get
func get(i: int): TFree
func Free()The example for this item is shown with the ones above: collections-Deque.salam
free
func free()HashMap
struct HashMap<K, V>OrderedMap. Built in, no import needed.| Name | Type | Description |
|---|---|---|
keys | K* | The address of the array of keys. |
vals | V* | The address of the array of values. |
state | i8* | 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.IsEmpty()
m.Put("apple", 3)
m.Insert("pear", 5)
m.Put("apple", 4)
println m.Size(), m.Has("apple"), m.Get("apple"), m.GetOr("banana", 0)
println m.Remove("pear"), m.Remove("pear"), m.Size()
mut it := m.Iter()
until it.HasNext():
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
put
func put(k: K, v: V)Insert
func Insert(k: K, v: V)Put.The example for this item is shown with the ones above: collections-HashMap.salam
insert
func insert(k: K, v: V)Has
func Has(k: K): boolThe example for this item is shown with the ones above: collections-HashMap.salam
has
func has(k: K): boolGet
func Get(k: K): VHas first or use GetOr. A struct value is a copy; Put it back after changing it.The example for this item is shown with the ones above: collections-HashMap.salam
get
func get(k: K): VGetOr
func GetOr(k: K, def: V): VThe example for this item is shown with the ones above: collections-HashMap.salam
get_or
func get_or(k: K, def: V): VRemove
func Remove(k: K): boolThe example for this item is shown with the ones above: collections-HashMap.salam
remove
func remove(k: K): boolSize
func Size(): intThe example for this item is shown with the ones above: collections-HashMap.salam
size
func size(): intIsEmpty
func IsEmpty(): boolThe example for this item is shown with the ones above: collections-HashMap.salam
is_empty
func is_empty(): boolIter
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
iter
func iter(): MapIter<K, V>Free
func Free()The example for this item is shown with the ones above: collections-HashMap.salam
free
func free()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 | i8* | 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
HasNext
func HasNext(): boolThe example for this item is shown with the ones above: collections-HashMap.salam
has_next
func has_next(): boolKey
func Key(): Kkey
func key(): KThe example for this item is shown with the ones above: collections-HashMap.salam
Value
func Value(): Vvalue
func value(): VThe example for this item is shown with the ones above: collections-HashMap.salam
Next
func Next()next
func next()The example for this item is shown with the ones above: collections-HashMap.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. |
offset | int = 0 |
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.ToVector(), c.Get(0), c.Size(), c.IsEmpty()
endAdd
func Add(x: T)add
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
size
func size(): intIsEmpty
func IsEmpty(): boolThe example for this item is shown with the ones above: collections-CircularList.salam
is_empty
func is_empty(): boolGet
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
get
func get(i: int): TRotate
func Rotate(k: int)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(): Tcurrent
func current(): TThe example for this item is shown with the ones above: collections-CircularList.salam
Advance
func Advance()advance
func advance()The example for this item is shown with the ones above: collections-CircularList.salam
ToVector
func ToVector(): Vector<T>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
free
func free()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.IsEmpty()
endPush
func Push(x: T)push
func push(x: T)The example for this item is shown with the ones above: collections-Stack.salam
Pop
func Pop(): Tpop
func pop(): TThe example for this item is shown with the ones above: collections-Stack.salam
Peek
func Peek(): Tpeek
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
size
func size(): intIsEmpty
func IsEmpty(): boolThe example for this item is shown with the ones above: collections-Stack.salam
is_empty
func is_empty(): boolClear
func Clear()clear
func clear()The example for this item is shown with the ones above: collections-Stack.salam
Iter
func Iter(): StackIter<T>each ... in on items does the same.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")
mut it := s.Iter()
until it.HasNext():
println it.Value()
it.Next()
end
enditer
func iter(): StackIter<T>Free
func Free()The example for this item is shown with the ones above: collections-Stack.salam
free
func free()StackIter
struct StackIter<T>HasNext, value and next.| Name | Type | Description |
|---|---|---|
items | Vector | The stack's elements, bottom first. |
pos | int = 0 | The current position. |
The example for this item is shown with the ones above: collections-StackIter.salam
HasNext
func HasNext(): boolThe example for this item is shown with the ones above: collections-StackIter.salam
has_next
func has_next(): boolValue
func Value(): Tvalue
func value(): TThe example for this item is shown with the ones above: collections-StackIter.salam
Next
func Next()next
func next()The example for this item is shown with the ones above: collections-StackIter.salam
Set
struct Set<T>HashMap to bool underneath and has no iterator of its own; walk s.m to list the elements.| 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.IsEmpty()
endAdd
func Add(x: T)add
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
has
func has(x: T): boolRemove
func Remove(x: T): boolThe example for this item is shown with the ones above: collections-Set.salam
remove
func remove(x: T): boolSize
func Size(): intThe example for this item is shown with the ones above: collections-Set.salam
size
func size(): intIsEmpty
func IsEmpty(): boolThe example for this item is shown with the ones above: collections-Set.salam
is_empty
func is_empty(): boolIter
func Iter(): SetIter<T>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
mut seen := 0
mut it := s.Iter()
until it.HasNext():
if s.Has(it.Value()):
seen++
end
it.Next()
end
println seen, s.Size()
enditer
func iter(): SetIter<T>Free
func Free()The example for this item is shown with the ones above: collections-Set.salam
free
func free()SetIter
struct SetIter<T>HasNext, value and next.| Name | Type | Description |
|---|---|---|
inner | MapIter | The map iterator underneath. |
The example for this item is shown with the ones above: collections-SetIter.salam
HasNext
func HasNext(): boolThe example for this item is shown with the ones above: collections-SetIter.salam
has_next
func has_next(): boolValue
func Value(): Tvalue
func value(): TThe example for this item is shown with the ones above: collections-SetIter.salam
Next
func Next()next
func next()The example for this item is shown with the ones above: collections-SetIter.salam
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.PushBack("b")
l.PushBack("c")
l.PushFront("a")
println l.ToVector(), l.Size()
println l.FrontVal(), l.BackVal(), l.Get(1)
println l.PopFront(), l.PopBack(), l.Size(), l.IsEmpty()
endpush_back
func push_back(v: T)The example for this item is shown with the ones above: collections-LinkedList.salam
PushBack
func PushBack(v: T)push_front
func push_front(v: T)The example for this item is shown with the ones above: collections-LinkedList.salam
PushFront
func PushFront(v: T)pop_front
func pop_front(): TThe example for this item is shown with the ones above: collections-LinkedList.salam
PopFront
func PopFront(): Tpop_back
func pop_back(): TThe example for this item is shown with the ones above: collections-LinkedList.salam
PopBack
func PopBack(): TFrontVal
func FrontVal(): Tfront_val
func front_val(): TThe example for this item is shown with the ones above: collections-LinkedList.salam
BackVal
func BackVal(): Tback_val
func back_val(): TThe example for this item is shown with the ones above: collections-LinkedList.salam
size
func size(): intSize
func Size(): intThe example for this item is shown with the ones above: collections-LinkedList.salam
is_empty
func is_empty(): boolIsEmpty
func IsEmpty(): boolThe example for this item is shown with the ones above: collections-LinkedList.salam
get
func get(i: int): TGet
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
ToVector
func ToVector(): Vector<T>free
func free()Free
func Free()The example for this item is shown with the ones above: collections-LinkedList.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.GetOr("licence", "-")
println m.IndexOf("language"), m.KeyAt(0), m.ValAt(0)
m.SetAt(0, "Salam")
println m.Remove("version"), m.Len()
keys := m.CloneKeys()
println keys
endIndexOf
func IndexOf(k: str): intThe example for this item is shown with the ones above: collections-OrderedMap.salam
index_of
func index_of(k: str): intLen
func Len(): intThe example for this item is shown with the ones above: collections-OrderedMap.salam
len
func len(): intHas
func Has(k: str): boolThe example for this item is shown with the ones above: collections-OrderedMap.salam
has
func has(k: str): boolGet
func Get(k: str): strThe example for this item is shown with the ones above: collections-OrderedMap.salam
get
func get(k: str): strGetOr
func GetOr(k: str, def: str): strThe example for this item is shown with the ones above: collections-OrderedMap.salam
get_or
func get_or(k: str, def: str): strSet
func Set(k: str, v: str): intThe example for this item is shown with the ones above: collections-OrderedMap.salam
set
func set(k: str, v: str): intKeyAt
func KeyAt(i: int): stri, or empty text when i is out of range.The example for this item is shown with the ones above: collections-OrderedMap.salam
key_at
func key_at(i: int): strValAt
func ValAt(i: int): stri, or empty text when i is out of range.The example for this item is shown with the ones above: collections-OrderedMap.salam
val_at
func val_at(i: int): strSetAt
func SetAt(i: int, v: str)set_at
func set_at(i: int, v: str)Remove
func Remove(k: str): intThe example for this item is shown with the ones above: collections-OrderedMap.salam
remove
func remove(k: str): intCloneKeys
func CloneKeys(): Vector<str>clone_keys
func clone_keys(): Vector<str>The example for this item is shown with the ones above: collections-OrderedMap.salam
Iter
func Iter(): OrderedMapIterimport collections
func main:
mut m := collections.OrderedMap {}
defer m.Free()
m.Set("name", "Salam")
m.Set("version", "0.5.0")
m.Set("language", "english")
mut it := m.Iter()
until it.HasNext():
println it.Key(), it.Value()
it.Next()
end
enditer
func iter(): OrderedMapIterFree
func Free()The example for this item is shown with the ones above: collections-OrderedMap.salam
free
func free()OrderedMapIter
struct OrderedMapIterHasNext, key, value and next.| Name | Type | Description |
|---|---|---|
keys | Vector | The keys in order. |
vals | Vector | The values in order. |
pos | int = 0 | The current position. |
The example for this item is shown with the ones above: collections-OrderedMapIter.salam
HasNext
func HasNext(): boolThe example for this item is shown with the ones above: collections-OrderedMapIter.salam
has_next
func has_next(): boolKey
func Key(): strkey
func key(): strThe example for this item is shown with the ones above: collections-OrderedMapIter.salam
Value
func Value(): strvalue
func value(): strThe example for this item is shown with the ones above: collections-OrderedMapIter.salam
Next
func Next()next
func next()The example for this item is shown with the ones above: collections-OrderedMapIter.salam
PriorityQueue
struct PriorityQueue<T><, so the elements must be numbers or strings; push negative numbers for the largest first. For scheduling work and for shortest path algorithms.| 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.IsEmpty():
print q.Pop(), ""
end
println ""
endPush
func Push(x: T)push
func push(x: T)The example for this item is shown with the ones above: collections-PriorityQueue.salam
Peek
func Peek(): Tpeek
func peek(): TThe example for this item is shown with the ones above: collections-PriorityQueue.salam
Pop
func Pop(): Tpop
func pop(): 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
size
func size(): intIsEmpty
func IsEmpty(): boolThe example for this item is shown with the ones above: collections-PriorityQueue.salam
is_empty
func is_empty(): boolFree
func Free()The example for this item is shown with the ones above: collections-PriorityQueue.salam
free
func free()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.IsEmpty()
endEnqueue
func Enqueue(x: T)enqueue
func enqueue(x: T)The example for this item is shown with the ones above: collections-Queue.salam
Dequeue
func Dequeue(): Tdequeue
func dequeue(): TThe example for this item is shown with the ones above: collections-Queue.salam
Peek
func Peek(): Tpeek
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
size
func size(): intIsEmpty
func IsEmpty(): boolThe example for this item is shown with the ones above: collections-Queue.salam
is_empty
func is_empty(): boolIter
func Iter(): QueueIter<T>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.dequeue()
q.enqueue("customer 4")
mut it := q.Iter()
until it.HasNext():
println it.Value()
it.Next()
end
enditer
func iter(): QueueIter<T>Free
func Free()The example for this item is shown with the ones above: collections-Queue.salam
free
func free()QueueIter
struct QueueIter<T>HasNext, value and next.| Name | Type | Description |
|---|---|---|
outbox | Vector | The front part of the queue, as the iterator saw it. |
inbox | Vector | The back part of the queue, as the iterator saw it. |
pos | int = 0 | The current position. |
The example for this item is shown with the ones above: collections-QueueIter.salam
HasNext
func HasNext(): boolThe example for this item is shown with the ones above: collections-QueueIter.salam
has_next
func has_next(): boolValue
func Value(): Tvalue
func value(): TThe example for this item is shown with the ones above: collections-QueueIter.salam
Next
func Next()next
func next()The example for this item is shown with the ones above: collections-QueueIter.salam
Counter
struct Counter<K>c.m.| 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)add
func add(k: K)k.The example for this item is shown with the ones above: collections-Counter.salam
Count
func Count(k: K): intcount
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
Total
func Total(): inttotal
func total(): intDistinct
func Distinct(): intdistinct
func distinct(): intThe example for this item is shown with the ones above: collections-Counter.salam
Iter
func Iter(): CounterIter<K>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 the"):
c.Add(word)
end
mut total := 0
mut it := c.Iter()
until it.HasNext():
if it.Key() == "the":
println it.Key(), it.Value()
end
total += it.Value()
it.Next()
end
println total, c.distinct()
enditer
func iter(): CounterIter<K>Free
func Free()The example for this item is shown with the ones above: collections-Counter.salam
free
func free()CounterIter
struct CounterIter<K>HasNext, key, value and next.| Name | Type | Description |
|---|---|---|
inner | MapIter | The map iterator underneath. |
The example for this item is shown with the ones above: collections-CounterIter.salam
HasNext
func HasNext(): boolThe example for this item is shown with the ones above: collections-CounterIter.salam
has_next
func has_next(): boolKey
func Key(): Kkey
func key(): KThe example for this item is shown with the ones above: collections-CounterIter.salam
Value
func Value(): intvalue
func value(): intThe example for this item is shown with the ones above: collections-CounterIter.salam
Next
func Next()next
func next()The example for this item is shown with the ones above: collections-CounterIter.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.IsEmpty()
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.RemoveAt(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): Tref
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)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; anything already in the vector is dropped.The example for this item is shown with the ones above: collections-Vector.salam
alloc
func alloc(n: int)n uninitialised elements, dropping what was there; fill them before reading.The example for this item is shown with the ones above: collections-Vector.salam
len
func len(): intcap
func cap(): intThe example for this item is shown with the ones above: collections-Vector.salam
is_empty
func is_empty(): boolfirst
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)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>free
func free()Reserve
func Reserve(need: int)Push
func Push(x: T)Pop
func Pop(): TGet
func Get(i: int): Ti. An index outside 0 to len()-1 stops the program (the check is left out of --release builds).The example for this item is shown with the ones above: collections-Vector.salam
Ref
func Ref(i: int): T*Set
func Set(i: int, x: T)i, which must already exist; use push to add.The example for this item is shown with the ones above: collections-Vector.salam
ResizeSet
func ResizeSet(i: int, x: T)Zeros
func Zeros(n: int)Alloc
func Alloc(n: int)Len
func Len(): intThe example for this item is shown with the ones above: collections-Vector.salam
Cap
func Cap(): intIsEmpty
func IsEmpty(): boolThe example for this item is shown with the ones above: collections-Vector.salam
First
func First(): TLast
func Last(): TClear
func Clear()Insert
func Insert(i: int, x: T)i (0 to len()) and shifts the rest forward, so it takes longer the more elements follow.The example for this item is shown with the ones above: collections-Vector.salam
RemoveAt
func RemoveAt(i: int): TIter
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.HasNext():
println it.Value()
it.Next()
end
endFree
func Free()str functions, are not freed.The example for this item is shown with the ones above: collections-Vector.salam
VectorIter
struct VectorIter<T>HasNext, value and next.| Name | Type | Description |
|---|---|---|
data | T* | The address of the vector's elements. |
len | int = 0 | |
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(): boolvalue
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
HasNext
func HasNext(): boolThe example for this item is shown with the ones above: collections-VectorIter.salam
Value
func Value(): TNext
func Next()Functions
Contains
func Contains<T>(v: Vector<T>, x: T): boolcontains
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.IndexOf(a, 2), collections.LastIndexOf(a, 2), collections.CountOf(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()
endIndexOf
func IndexOf<T>(v: Vector<T>, x: T): intx, or minus one.The example for this item is shown with the ones above: collections-Funcs.salam
index_of
func index_of<T>(v: Vector<T>, x: T): intReverse
func Reverse<T>(v: Vector<T>): Vector<T>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>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>slice
func slice<T>(v: Vector<T>, start: int, count: int): Vector<T>count elements starting at start; a range past the end is cut short instead of failing.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)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
CountOf
func CountOf<T>(v: Vector<T>, x: T): intcount_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
LastIndexOf
func LastIndexOf<T>(v: Vector<T>, x: T): intlast_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>)extend
func extend<T>(dst &: Vector<T>, src: Vector<T>)src to the end of dst; dst is passed by reference.The example for this item is shown with the ones above: collections-Funcs.salam