Tree set

A hash set answers "is it here?" and nothing about order. A TreeSet<T> answers the same question and also keeps its elements sorted, the way a tree map keeps its keys.

That makes it the set to reach for when the members should come out in order — a word list in alphabetical order, free seat numbers lowest first — or when the question is "which member comes next after this one?".

Making a tree set

Like a tree map, it is told how to order two elements:

var tags = TreeSet<char8[..]>(allocator, CompareSlice);

CompareSlice orders text by its bytes. For lowercase English words that is alphabetical order; the Common mistakes below show where it is not.

Membership, as in a hash set

Insert reports whether the element was new, and a duplicate is not added a second time:

let incoming: char8[..][7] = ["rust", "memory", "arena", "rux", "memory", "pool", "arena"];
for tag in incoming {
    let isNew = tags.Insert(tag)?;
    if !isNew {
        PrintLine("duplicate  {}", tag);
    }
}

Seven tags go in; memory and arena arrive twice, so five are kept. Contains asks without changing anything, just as on a hash set.

Walking in order

A for loop walks the set in order, whatever order the elements arrived in:

for tag in tags {
    Print(" {}", tag);
}

They arrived as rust memory arena rux pool; they come out as arena memory pool rust rux.

Ordered questions

The same questions a tree map answers about its keys, a tree set answers about its elements. Each returns an optional, because the answer may not exist — so the program supplies a stand-in with ??:

PrintLine("first      {}", tags.First() ?? "(none)");
PrintLine("last       {}", tags.Last() ?? "(none)");
PrintLine("from n on  {}", tags.Ceiling("n") ?? "(none)");
PrintLine("from z on  {}", tags.Ceiling("z") ?? "(none)");

Ceiling is the smallest element at or above the one asked for. "n" is not a tag, so Ceiling("n") finds the first tag from n on: pool. Nothing comes at or after "z", so that one prints (none).

flowchart LR
    a["`arena`"] --> m["`memory`"] --> p["`pool`"] --> r["`rust`"] --> x["`rux`"]
    n(["`Ceiling` of `n`"]) -. "smallest element<br/>at or above `n`" .-> p
    f(["`Floor` of `n`"]) -. "largest element<br/>at or below `n`" .-> m

A range of elements

Range(start, end) walks the elements from start up to, but not including, end:

for tag in tags.Range("r", "s") {
    Print(" {}", tag);
}

Every word that starts with r sorts at or after "r" and before "s", so this prints rust rux — a prefix search in one call.

The program

The whole lesson is one package in the Examples repository. Its comments explain every step.

// A hash set answers "is it here?" and nothing about order. A `TreeSet<T>` answers the same
// question and also keeps its elements sorted, the way a tree map keeps its keys.
//
// That makes it the set to reach for when the members should come out in order — a word list
// in alphabetical order, a list of free seat numbers lowest first — or when the question is
// "which member comes next after this one?".
import Allocator::{ Allocator, SystemAllocator };
import Collections::{ CollectionError, CompareSlice, TreeSet };
import Io::{ Print, PrintLine };

func Main() -> ! CollectionError {
    var system = SystemAllocator();
    let allocator: Allocator = system;

    // Like a tree map, it is told how to order two elements. `CompareSlice` orders text by its
    // bytes, which is alphabetical for lowercase English words.
    var tags = TreeSet<char8[..]>(allocator, CompareSlice);

    // Membership works as in a hash set: `Insert` reports whether the element was new, and a
    // duplicate is not added a second time.
    let incoming: char8[..][7] = ["rust", "memory", "arena", "rux", "memory", "pool", "arena"];
    for tag in incoming {
        let isNew = tags.Insert(tag)?;
        if !isNew {
            PrintLine("duplicate  {}", tag);
        }
    }
    PrintLine("{} tags in, {} kept", incoming.length, tags.Length());
    PrintLine("has pool?  {}", tags.Contains("pool"));

    // A `for` loop walks the set in order, whatever order the elements arrived in.
    Print("in order  ");
    for tag in tags {
        Print(" {}", tag);
    }
    PrintLine();

    // Ordered questions return optionals, because the answer may not exist. `Ceiling` is the
    // smallest element at or above the one asked for, so it finds the first tag from "n" on.
    PrintLine("first      {}", tags.First() ?? "(none)");
    PrintLine("last       {}", tags.Last() ?? "(none)");
    PrintLine("from n on  {}", tags.Ceiling("n") ?? "(none)");
    PrintLine("from z on  {}", tags.Ceiling("z") ?? "(none)");

    // `Range(start, end)` walks the elements from `start` up to, but not including, `end`.
    Print("r to s    ");
    for tag in tags.Range("r", "s") {
        Print(" {}", tag);
    }
    PrintLine();
}

Besides Io, its Rux.toml lists Allocator and Collections under [Dependencies].

Run it

cd Examples/Collections/TreeSet
rux run

duplicate  memory
duplicate  arena
7 tags in, 5 kept
has pool?  true
in order   arena memory pool rust rux
first      arena
last       rux
from n on  pool
from z on  (none)
r to s     rust rux

Common mistakes

Try it yourself

1. Print tags.Floor("n"), the largest tag at or below "n". Then Floor("a") — what does it give, and why?
2. Insert "Zebra" and see where it lands in the walk. Then insert it as "zebra".
3. Keep free seat numbers in a TreeSet<int32> made with CompareInt32. Take the lowest free seat with First(), and remove it so it is no longer free.
4. Print every tag from "a" up to, but not including, "n" with Range.

Learn more

• Hash set — the unordered set, and the methods both share
• Tree map — the same ordered questions, for keys with values
• Coalesce — the ?? that supplies (none)
• Sort — sorting a slice once, when the values do not change afterwards