Lesson 13 of 25 · Data and types

Vector and HashMap

An array has a fixed size. A Vector is a list that grows and shrinks, and a HashMap connects every key to a value. Between the two you can hold most of the data a program works with, and the collections package adds a Set, a Stack and a Queue for the jobs they fit better.

In this lesson

Vector
Inserting and removing
A Vector of structs
Sorting
HashMap
Counting with a HashMap
Set, Stack and Queue
Sharing and copying
Rules of thumb

Vector

Build one with Vector {} as Vector<type>. push adds an element at the end, get and set read and replace one by its position, pop takes the last one off and returns it, and len gives the count. each walks the elements in order.

vector.salam

func main:
    mut numbers := Vector {} as Vector<int>
    defer numbers.free()
    numbers.push(10)
    numbers.push(20)
    numbers.push(30)
    numbers.set(1, 25)
    println numbers.len(), numbers.get(1)
    last := numbers.pop()
    println last, numbers.len()
    each n in numbers:
        println n
    end
end

Output3 25 30 2 10 25

A Vector and a HashMap both allocate memory. Write defer name.free() on the line after creating one, so the memory is released when the function ends, however it ends.

Inserting and removing

A Vector is not limited to its end. insert(i, x) puts a value at position i and moves the rest along, and remove_at(i) takes one out and gives it back. first() and last() read the two ends, clear() empties the Vector and is_empty() tells you whether anything is left. Square brackets work as they do on an array: v[i] reads and v[i] = x writes.

vector-edit.salam

func main:
    mut playlist := Vector {} as Vector<str>
    defer playlist.free()
    playlist.push("Blue in Green")
    playlist.push("So What")
    playlist.push("Naima")
    playlist.insert(0, "Intro")
    println playlist
    removed := playlist.remove_at(2)
    println "removed:", removed
    println "first:", playlist.first(), "last:", playlist.last()
    playlist[1] = playlist[1] + " (live)"
    println playlist[1], playlist.len()
    playlist.clear()
    println playlist.is_empty()
end

Output["Intro", "Blue in Green", "So What", "Naima"] removed: So What first: Intro last: Naima Blue in Green (live) 3 true

Positions start at 0 and end at len() - 1. Reading past the end is not quietly ignored: the program stops with Vector.get: index out of bounds. Inserting or removing near the front moves every element after it, so on a very long Vector, work at the end when you can.

A Vector of structs

The element type can be anything, and most real programs keep a list of records: tasks, orders, players. each i, t in tasks gives you the position and the element together.

vector-structs.salam

struct Task:
    pub title: str = ""
    pub minutes: int = 0
    pub done: bool = false
end

func main:
    mut tasks := Vector {} as Vector<Task>
    defer tasks.free()
    tasks.push(Task { title = "standup", minutes = 15 })
    tasks.push(Task { title = "write report", minutes = 90 })
    tasks.push(Task { title = "review code", minutes = 40 })

    first := tasks.ref(0)
    first.done = true

    mut left := 0
    each i, t in tasks:
        mark := t.done ? "x" : " "
        println i + 1, "[" + mark + "]", t.title
        if not t.done:
            left += t.minutes
        end
    end
    println "minutes left:", left
end

Output1 [x] standup 2 [ ] write report 3 [ ] review code minutes left: 130

The loop variable t is a copy of the element. Changing t.done inside the loop would change only the copy and leave the Vector as it was. To change an element in place, take a pointer to it with ref(i) and write through that, as the example does with the first task. The other way is to read the element, change it and put it back with set(i, x).

The next lesson covers structs themselves.

Sorting

The sort package sorts a Vector in place. sort.Sort puts numbers and strings in ascending order and sort.SortDesc in descending order. For structs, or for any order of your own, sort.SortBy takes a function that answers one question: should a come before b?

vector-sort.salam

import sort

struct Player:
    pub name: str = ""
    pub score: int = 0
end

func main:
    mut times := Vector {} as Vector<int>
    defer times.free()
    times.push(42)
    times.push(7)
    times.push(19)
    sort.Sort(times)
    println times
    sort.SortDesc(times)
    println times

    mut board := Vector {} as Vector<Player>
    defer board.free()
    board.push(Player { name = "Sara", score = 31 })
    board.push(Player { name = "Omid", score = 48 })
    board.push(Player { name = "Lena", score = 27 })
    sort.SortBy(board, (a: Player, b: Player): ret a.score > b.score end)
    each i, p in board:
        println i + 1, p.name, p.score
    end
end

Output[7, 19, 42] [42, 19, 7] 1 Omid 48 2 Sara 31 3 Lena 27

The comparison here is a.score > b.score, so higher scores come first. sort.SortBy does not promise to keep equal elements in their original order. When that matters, for example when a list already sorted by name is sorted again by score, use sort.StableSortBy, which takes the same arguments. The package also has sort.Sorted (a sorted copy), sort.BinarySearch, sort.Min and sort.Max; see the sort reference.

HashMap

A HashMap connects keys to values: put stores a pair (and replaces the value if the key is already there), get returns the value for a key, has tests whether a key is there, remove takes it out and size gives the number of pairs. each key, value in map walks all of them.

hashmap.salam

func main:
    mut capitals := HashMap {} as HashMap<str, str>
    defer capitals.free()
    capitals.put("Iran", "Tehran")
    capitals.put("Japan", "Tokyo")
    println capitals.get("Iran")
    println capitals.has("France"), capitals.size()
    capitals.remove("Japan")
    each country, city in capitals:
        println country, "->", city
    end
end

OutputTehran false 2 Iran -> Tehran

get on a missing key does not fail; it returns the zero value of the value type, such as 0 or an empty string. When 0 could be a real value, check with has first, or use get_or(key, fallback) to choose what comes back for a missing key.

Counting with a HashMap

Counting how often something occurs is the job a HashMap is made for. Here every word of a sentence is a key and its count is the value. get_or(w, 0) + 1 covers both the first time a word is seen and every time after that.

hashmap-count.salam

import sort
import str

func main:
    text := "the cat saw the dog and the dog saw the cat run"
    words := str.Split(text, " ")
    defer words.free()

    mut counts := HashMap {} as HashMap<str, int>
    defer counts.free()
    each w in words:
        counts.put(w, counts.get_or(w, 0) + 1)
    end
    println words.len(), "words,", counts.size(), "different"

    mut keys := Vector {} as Vector<str>
    defer keys.free()
    each word, _ in counts:
        keys.push(word)
    end
    sort.Sort(keys)
    each word in keys:
        println word, counts.get(word)
    end
end

Output12 words, 6 different and 1 cat 2 dog 2 run 1 saw 2 the 4

A HashMap does not remember the order in which keys were added, and walking it gives them in an order that has nothing to do with your data. When the output needs an order, collect the keys into a Vector, sort it, and look each key up, as the example does.

Set, Stack and Queue

The collections package (import collections) has a few more containers, each for a narrower job:

Type	Use it for	Main methods
`Set<T>`	Remembering which values you have seen, without duplicates	`add has remove size is_empty`
`Stack<T>`	Last in, first out: undo history, nested brackets	`push pop peek size is_empty`
`Queue<T>`	First in, first out: jobs and requests in arrival order	`enqueue dequeue peek size is_empty`
`Deque<T>`	Adding and removing at both ends	`push_front push_back pop_front pop_back`
`PriorityQueue<T>`	Always taking the smallest element next	`push pop peek`

A Stack is the natural way to check that brackets are balanced: every opening bracket is pushed, and every closing one must match the bracket on top.

coll-stack.salam

import collections
import str

func balanced(code: str): bool:
    mut open := collections.Stack {} as collections.Stack<str>
    defer open.free()
    chars := str.Chars(code)
    defer chars.free()
    each c in chars:
        if c == "(" or c == "[":
            open.push(c)
        else c == ")" or c == "]":
            if open.is_empty():
                ret false
            end
            top := open.pop()
            if (c == ")" and top != "(") or (c == "]" and top != "["):
                ret false
            end
        end
    end
    ret open.is_empty()
end

func main:
    println balanced("total(a[1], b[2])")
    println balanced("f(x]")
    println balanced("((x)")
end

Outputtrue false false

A Queue serves things in the order they arrived. In this example a Set sits next to it, so a customer who is already waiting is not added a second time:

coll-queue.salam

import collections

func main:
    mut queue := collections.Queue {} as collections.Queue<str>
    defer queue.free()
    mut waiting := collections.Set {} as collections.Set<str>
    defer waiting.free()

    each customer in ["sara", "omid", "sara", "lena", "omid"]:
        if waiting.has(customer):
            println customer, "is already in the queue"
            continue
        end
        waiting.add(customer)
        queue.enqueue(customer)
    end

    println queue.size(), "waiting, next is", queue.peek()
    until not queue.is_empty():
        customer := queue.dequeue()
        waiting.remove(customer)
        println "helping", customer
    end
    println waiting.is_empty()
end

Outputsara is already in the queue omid is already in the queue 3 waiting, next is sara helping sara helping omid helping lena true

Like a Vector, all of these allocate and need free(). Their full method lists are in the collections reference.

Sharing and copying

Assigning a Vector to another variable does not copy its elements. same := prices gives a second name for the same storage, so a change made through one name shows through the other. When you need an independent copy, for example a snapshot to compare with later, call copy(). The copy has its own memory, so it needs its own free().

vector-copy.salam

func add_fee(prices &: Vector<int>, fee: int):
    prices.push(fee)
end

func main:
    mut prices := Vector {} as Vector<int>
    defer prices.free()
    prices.push(100)
    prices.push(250)

    same := prices
    saved := prices.copy()
    defer saved.free()

    prices.set(0, 90)
    println same.get(0), saved.get(0)

    add_fee(prices, 5)
    println prices
    println saved
end

Output90 100 [90, 250, 5] [100, 250]

The same goes for parameters. A function that only reads a Vector can take it by value, but a function that adds to the caller's Vector must take it with &:, as add_fee does; elements pushed onto a by-value parameter never reach the caller. A HashMap behaves the same way and has a copy() too.

Free each piece of storage exactly once. In the example, same and prices are the same storage, so only prices is freed; saved is separate and is freed on its own.

Rules of thumb

Use an array when the size is fixed, a Vector when it grows, and a HashMap when you look things up by a key.
Write defer x.free() on the line after every Vector, HashMap or collection you create, including the ones returned by functions such as str.Split.
The loop variable of each is a copy. Change elements with ref(i), set(i, x) or v[i] = x.
Do not rely on the order of a HashMap. Sort the keys when the order matters.
b := a shares a Vector and a.copy() makes a new one. A function that pushes to the caller's Vector takes it with &:.