Sorted

A sorted collection holds records in order by one or more fields you choose as the sort criteria (called "key fields"). You can look up a record by those fields instantly and iterate all records in that order. The collection stays sorted as you add new elements — no manual sorting needed. Name the key fields in square brackets after the record type, as in sorted<Elm[-key]>: field sorts A→Z / 0→9 (ascending), -field sorts Z→A / 9→0 (descending).

struct Elm {
  key: text,
  value: integer
}
struct Db {
  map: sorted < Elm[-key] >
}
fn main() {

Adding Elements

You initialise a sorted collection the same way as a vector. The elements are automatically placed in the right position as you add them.

  db = Db {map: [
  Elm {key: "One", value: 1 },
  Elm {key: "Two", value: 2 },
  Elm {key: "Three", value: 3 },
  Elm {key: "Four", value: 4 }
  ] };

Looking Up by Key

Use square brackets with the key value to find a record instantly. If the key is not present the result is null — you can check it with !.

  assert(db.map["Two"].value == 2, "Key lookup: Two");
  assert(db.map["Three"].value == 3, "Key lookup: Three");
  assert(!db.map["Five"], "Missing key returns null");
  assert(!db.map[null], "Null key returns null");

Append new elements with +=; they are placed in the correct sorted position.

  db.map +=[Elm {key: "Zero", value: 0 }];
  assert(db.map["Zero"].value == 0, "Newly added element");

Iterating in Order

A for loop over a sorted collection visits elements in key order. Here the key is -key (descending text), so the order is: Zero, Two, Three, One, Four.

  sum = 0;
  for v in db.map {
    sum = sum * 10 + v.value;
  }

Zero(0), Two(2), Three(3), One(1), Four(4) → 0*10+2=2, *10+3=23, *10+1=231, *10+4=2314

  assert(sum == 2314, "Sorted iteration total: {sum}");

Iterating in Reverse

Wrap the collection in rev() to visit elements from last to first key order. Here the collection is sorted by -key (descending text), so the stored order is Zero, Two, Three, One, Four. rev() visits them in the opposite order.

  rev_sum = 0;
  for v in rev(db.map) {
    rev_sum = rev_sum * 10 + v.value;
  }

Four(4), One(1), Three(3), Two(2), Zero(0) → 4*10+1=41, *10+3=413, *10+2=4132, *10+0=41320

  assert(rev_sum == 41320, "Reverse iteration total: {rev_sum}");

Loop Helpers: #first, #count, #index, and #remove

v#first is true for the very first element visited. v#count is a running index starting at 0. v#index is a sequential counter over the visited elements, also starting at 0 — on a sorted collection it advances in step with #count. v#remove removes the current element while iterating.

  first_key = "";
  labels = "";
  index_sum = 0;
  for v in db.map {
    if v#first {
      first_key = v.key
    }
    if !v#first {
      labels += ","
    }

#index matches #count here: both run 0,1,2,3,4 over the five elements.

    assert(v#index == v#count, "index tracks count: {v#index} vs {v#count}");
    index_sum += v#index;
    labels += "{v#count}:{v.key}"
  }
  assert(first_key == "Zero", "First element: {first_key}");
  assert(labels == "0:Zero,1:Two,2:Three,3:One,4:Four", "Labels: {labels}");
  assert(index_sum == 10, "0+1+2+3+4 = {index_sum}");

Remove elements with value > 2 while iterating.

  for v in db.map if v.value > 2 {
    v#remove
  }
  sum2 = 0;
  for v in db.map {
    sum2 += v.value
  }

Remaining: Zero(0), Two(2), One(1) → sum = 3

  assert(sum2 == 3, "Sum after remove: {sum2}");

Removing by Key

Assigning null to a sorted subscript removes the element with that key. Removing a key that is not present is a safe no-op.

  db2 = Db {map: [
  Elm {key: "A", value: 10 },
  Elm {key: "B", value: 20 },
  Elm {key: "C", value: 30 }
  ] };
  db2.map["B"] = null;
  assert(!db2.map["B"], "B was removed");
  assert(db2.map["A"].value == 10, "A still present");
  assert(db2.map["C"].value == 30, "C still present");
  db2.map["missing"] = null;

no-op; does not panic

  sum3 = 0;
  for v in db2.map {
    sum3 += v.value
  }
  assert(sum3 == 40, "Sum after key removal: {sum3}");

Note: #index works on a sorted collection — it is a sequential counter that advances one per visited element (see the loop above). It is only index<T> collections that reject #index — use #count there instead (see the Index page).

Iterating a Key Range

The range examples live in main_ranges below; run them here, because a file with a main runs only its main.

  main_ranges();
}
struct Word {
  name: text,
  score: integer
}
struct Dict {
  words: sorted<Word[name]>
}
fn main_ranges() {

Iterating a Key Range

Give the collection a RANGE in square brackets and the loop starts and stops at the right places, without looking at the records outside it. This is the operation a sorted collection exists for. c[lo..hi] from lo up to but NOT including hi c[lo..=hi] from lo up to AND including hi c[lo..] from lo to the end c[..hi] from the start up to but not including hi Mind the two spellings: .. leaves the last key out, ..= keeps it. That is the same rule as a vector slice.

  d = Dict { words: [
    Word { name: "apple",      score: 5 },
    Word { name: "banana",     score: 3 },
    Word { name: "cherry",     score: 8 },
    Word { name: "date",       score: 2 },
    Word { name: "elderberry", score: 1 }
  ] };
  slice_total = 0;
  for w in d.words["banana"..="date"] {
    slice_total += w.score
  }
  assert(slice_total == 13, "banana(3)+cherry(8)+date(2) = {slice_total}");
  half_open = 0;
  for w in d.words["banana".."date"] {
    half_open += w.score
  }
  assert(half_open == 11, "'..' leaves date out: {half_open}");
  head_total = 0;
  for w in d.words[.."cherry"] {
    head_total += w.score
  }
  assert(head_total == 8, "apple(5)+banana(3) = {head_total}");

Filtering on something that is NOT the key

An if guard inside the loop still works, and it is what you want when the condition is not about the key: the guard sees every element and the body runs only for the matching ones. Use a range when you are selecting BY key, and a guard when you are selecting by anything else.

  cheap = 0;
  for w in d.words if w.score < 4 {
    cheap += w.score
  }
  assert(cheap == 6, "banana(3)+date(2)+elderberry(1) = {cheap}");

Open-ended Range (tail)

All records from "cherry" onward to the end of the sorted order.

  tail_count = 0;
  for w in d.words if w.name >= "cherry" {
    tail_count += 1
  }
  assert(tail_count == 3, "cherry, date, elderberry = {tail_count}");

Open-ended Range (head)

All records up to and including "banana".

  head_names = "";
  for w in d.words if w.name <= "banana" {
    head_names += w.name + " "
  }
  assert(head_names == "apple banana ", "apple and banana: '{head_names}'");

Range outside the for (building a result vector)

Collect matching records into a vector for later use.

  subset = [for w in d.words if w.name >= "banana" && w.name <= "cherry" { w.score }];
  assert(subset[0] == 3, "first in range: {subset[0]}");
  assert(subset[1] == 8, "second in range: {subset[1]}");
}

filling and finding values