Reference

std/collections/set

std/collections/src/set.trb

A collection without duplicates: Set, its default implementation TrieSet, and the flat HashSet.

There is no literal of its own - a list literal builds one wherever a Set is expected - and no index: the only way to see an item is to remove it or to iterate the whole set.

Related

trait Set

trait Set<Item> with Iterate<Item>, Length

Collection without duplicates. insert of a value that is already present does nothing.

Verbs change the set in place (insert, remove, insertAll, removeAll, retainAll). The set operations are nouns of the type and never change either operand: Set.union(first, second), Set.intersection(first, second) and Set.difference(first, second) take both sets as arguments, because neither is the one the operation belongs to.

Every implementation iterates in insertion order, and removing a value does not reorder the rest. The order reaches the output through Show, so it is a rule of the language and not of the implementation.

Examples

var unique: Set<Int> = [1, 2, 2, 3]
unique.insert 2
print unique

The set operations never change either operand:

const primes = Set.of 2, 3, 5, 7
const evenPrimes = Set.intersection primes, Set.of(2, 4, 6)
print evenPrimes

Related

  • Map - the same idea keyed by more than presence.
  • Iterate - the pipeline vocabulary (map, filter, fold, ...) every set has.

fn of

static fn of(...items: Item): Self where Self: From<Iterate<Item>>, Item: Hash

Builds a set from its arguments: Set.of(2, 3, 5, 7), needs Item: Hash. Answers Self.

fn contains

fn contains(value: Item): Bool

Whether the value is present. Required: a set that has to search is not a set.

fn count

fn count(): Int

How many values there are. A set knows its size, so counting it does not walk it.

fn insert

var fn insert(value: Item)

Inserts value, in place; does nothing if it is already present.

fn insertAll

var fn insertAll(values: Iterate<Item>)

Inserts every value of values, in place.

fn remove

var fn remove(value: Item): Bool

Removes the value, in place, and answers whether it was present.

fn removeAll

var fn removeAll(values: Iterate<Item>)

Removes every value of values, in place.

fn retainAll

var fn retainAll(values: Set<Item>)

Keeps only the values also in values, in place; drops the rest.

fn clear

var fn clear()

Removes every value, in place.

fn inserted

fn inserted(value: Item): Self

The participle of Set.insert: a changed copy with value in it, for a const binding.

fn insertedAll

fn insertedAll(values: Iterate<Item>): Self

The participle of Set.insertAll: a changed copy with every value of values in it.

fn removed

fn removed(value: Item): Self

The participle of Set.remove: a changed copy with the value gone.

fn union

static fn union(first: Self, second: Self): Self

The values of either set: those of first in their order, then the new ones of second.

A function of the type and not a member of one operand, because the operation is symmetric: Set.union(a, b) says that neither set is the one that changes. Set.insertedAll is the same step read as filling one set from anything that iterates, and that one is a member.

Examples

const both = Set.union Set.of(1, 2), Set.of(2, 3)
print both

fn intersection

static fn intersection(first: Self, second: Self): Self

The values common to both sets, in the order of first.

Examples

const common = Set.intersection Set.of(1, 2, 3), Set.of(2, 3, 4)
print common

fn difference

static fn difference(first: Self, second: Self): Self

The values of first that are not in second, in the order of first.

Examples

const left = Set.difference Set.of(1, 2, 3), Set.of(2)
print left

extend Set<Item> with From<Iterate<Item>>

extend<Item: Hash> Set<Item> with From<Iterate<Item>>

The factory picks the default implementation. This is what makes toSet(), to<Set<Item>>() and a list literal adapted to Set<Item> work.

fn from

static fn from(items: Iterate<Item>): Set<Item>

extend Set<Item> with Show

extend<Item: Show> Set<Item> with Show

{a, b} - braces, so a set is never mistaken for a list. Empty is {}.

fn show

fn show(): String

extend Set<Item> with Equals

extend<Item: Equals> Set<Item> with Equals

Equal when they hold the same items, regardless of insertion order.

fn equals

fn equals(other: Self): Bool

extend Set<Item> with Hash

extend<Item: Hash> Set<Item> with Hash

Order-independent, unlike List.hash: entries are combined with bitwiseExclusiveOr, so insertion order never changes the hash of equal sets.

Hash requires Equals, and the Equals implementation above satisfies that: Item: Hash implies Item: Equals.

fn hash

fn hash(): Int

type TrieSet

native type TrieSet<Item: Hash> with Set<Item>, From<Iterate<Item>>

Hash array mapped trie - the default. Cheap to keep in many versions. Iterates in insertion order.

Until the trie exists, this name is a documented alias of HashSet. Only performance differs: iteration order and Show are the same either way.

fn from

static fn from(items: Iterate<Item>): TrieSet<Item>

Builds the set from items: TorbScript, because items is a trait-typed value of the program: see TrieMap.from.

fn withCapacity

native static fn withCapacity(capacity: Int): TrieSet<Item>

The empty set, with room for capacity items before it has to grow again.

fn length

native fn length(): Int

How many items there are.

fn contains

native fn contains(value: Item): Bool

Whether value is present.

fn iterate

fn iterate(): Iterator<Item>

Ordinary TorbScript over itemAfter: see SetIterator.

fn itemAfter

native fn itemAfter(var cursor: Int): Item?

The item at or after cursor in insertion order, with cursor left one past it: see TrieMap.entryAfter.

fn insert

native var fn insert(value: Item)

Inserts value, in place; does nothing if it is already present.

fn remove

native var fn remove(value: Item): Bool

Removes value and answers whether it was present, in place.

fn clear

native var fn clear()

Removes every item, in place.

type HashSet

native type HashSet<Item: Hash> with Set<Item>, From<Iterate<Item>>

Flat hash table: the fastest lookups and writes, but a write to a shared table copies all of it. Iterates in insertion order.

fn from

static fn from(items: Iterate<Item>): HashSet<Item>

Same as TrieSet.from.

fn withCapacity

native static fn withCapacity(capacity: Int): HashSet<Item>

Same as TrieSet.withCapacity.

fn length

native fn length(): Int

Same as TrieSet.length.

fn contains

native fn contains(value: Item): Bool

Same as TrieSet.contains.

fn iterate

fn iterate(): Iterator<Item>

A cursor over the items, in insertion order; see HashSetIterator.

fn itemAfter

native fn itemAfter(var cursor: Int): Item?

Same as TrieSet.itemAfter.

fn insert

native var fn insert(value: Item)

Same as TrieSet.insert.

fn remove

native var fn remove(value: Item): Bool

Same as TrieSet.remove.

fn clear

native var fn clear()

Same as TrieSet.clear.