Skip to content
FutureBlitz

    Install

    Import std.collections.sorted

    std.collections.sorted

    A map and a set that keep their keys in order, in a B-tree.

    SortedMap<K, V> and SortedSet<T>: keys in order, in a B-tree. Each node holds from Order - 1 to 2 * Order - 1 keys in order, but the root, which can hold fewer, and a node that isn't a leaf has a child before, between, and after its keys, which hold the keys between them. Finding, adding, and removing a key looks at about log(Count) nodes.

    std/collections/sorted.fb

    Types

    SortedMap class 

    @DebugEntries Public Class SortedMap<K: Comparable, V> Implements Iterable<(K, V)>, Cloneable, Defaultable

    A Map that keeps its keys in order, smallest first, for ranges and the nearest key to another.

    Examples

    Local grades = SortedMap<Int, String>()
grades.Add(90, "A")
grades.Add(70, "C")
grades.Add(80, "B")
Expect(grades.Keys() == [70, 80, 90])
Expect(grades.Floor(85) == (80, "B"))
Expect(grades.Ceiling(85) == (90, "A"))
Expect(grades.Range(70, 90) == [(70, "C"), (80, "B")])

    std/collections/sorted.fb, line 58

    • Public New() constructor #

      A new, empty SortedMap.

    • Public Property Count: Int property #

      How many entries it holds.

    • @PanicsAtCaller Public Method Add(key: K, value: V) method #

      Adds an entry, or gives an existing key its new value, which leaves the tree as it is. A key that isn't equal to itself, like NaN, panics.

    • Public Method Get(key: K): V? method #

      The key's value, or Null when it isn't there.

    • Public Method Get(key: K, fallback: V): V method #

      The key's value, or fallback when it isn't there.

    • @PanicsAtCaller Operator [](key: K): V operator #

      The key's value. A key that isn't there panics.

    • @PanicsAtCaller Operator []=(key: K, value: V) operator #

      Gives the key a value, adding it when it isn't there.

    • Public Method Contains(key: K): Bool method #

      Whether key has an entry.

    • Public Method Remove(key: K): Bool method #

      Removes the key's entry, and tells whether there was one. A key that isn't there leaves the tree as it is.

    • Public Method Clear() method #

      Takes every entry out.

    • Public Method First(): (K, V)? method #

      The smallest key and its value, or Null when there's none.

    • Public Method Last(): (K, V)? method #

      The largest key and its value, or Null when there's none.

    • Public Method Floor(key: K): (K, V)? method #

      The largest key that isn't above key, and its value, or Null when there's none, as for a key that isn't equal to itself.

    • Public Method Ceiling(key: K): (K, V)? method #

      The smallest key that isn't below key, and its value, or Null when there's none, as for a key that isn't equal to itself.

    • Public Method Range(low: K, high: K): (K, V)[] method #

      The entries from low up to high, without high itself, in order, in a new array. An end that isn't equal to itself finds none.

    • Public Method Keys(): K[] method #

      The keys, in order.

    • Public Method Values(): V[] method #

      The values, in their keys' order.

    • Public Static Method DefaultValue(): SortedMap<K, V> static method #

      A new, empty SortedMap.

    • Public Method Clone(): SortedMap<K, V> method #

      A new SortedMap with the same entries.

    • Public Method Iterate(): SortedMapIterator<K, V> method #

      Each key and its value, in order, for 'For key, value In map'. Giving a key a new value while going over them is fine, but adding or removing one panics.

    SortedMapIterator struct 

    Public Struct SortedMapIterator<K: Comparable, V> Implements Iterator<(K, V)>

    The entries of a SortedMap, in key order, which a For loop goes over.

    std/collections/sorted.fb, line 474

    • @PanicsAtCaller Public ByRef Method Next(): (K, V)? method #

      The next key and its value, in order, or Null after the largest. Panics when the SortedMap changed since the loop began.

    SortedSet class 

    @DebugElements Public Class SortedSet<T: Comparable> Implements Iterable<T>, Cloneable, Defaultable, Equatable

    Values without repeats, in order, which a SortedMap holds as its keys.

    Examples

    Local words = SortedSet<String>()
For word In ["pear", "apple", "fig", "apple"]
    words.Add(word)
End For

Expect(words.ToArray() == ["apple", "fig", "pear"])
Expect(words.First() == "apple" && words.Ceiling("b") == "fig")

    std/collections/sorted.fb, line 569

    • Public New() constructor #

      A new, empty SortedSet.

    • Public Property Count: Int property #

      How many values it holds.

    • @PanicsAtCaller Public Method Add(value: T): Bool method #

      Adds the value, and tells whether it's new. A value that isn't equal to itself, like NaN, panics.

    • Public Method Remove(value: T): Bool method #

      Removes the value, and tells whether it was there.

    • Public Method Contains(value: T): Bool method #

      Whether it holds value.

    • Public Method Clear() method #

      Takes every value out.

    • Public Method First(): T? method #

      The smallest value, or Null when there's none.

    • Public Method Last(): T? method #

      The largest value, or Null when there's none.

    • Public Method Floor(value: T): T? method #

      The largest value that isn't above value, or Null when there's none.

    • Public Method Ceiling(value: T): T? method #

      The smallest value that isn't below value, or Null when there's none.

    • Public Method Range(low: T, high: T): T[] method #

      The values from low up to high, without high itself, in order, in a new array.

    • Public Method ToArray(): T[] method #

      The values, in order, in a new array.

    • Public Static Method DefaultValue(): SortedSet<T> static method #

      A new, empty SortedSet.

    • Public Method Clone(): SortedSet<T> method #

      A new SortedSet with the same values.

    • Operator ==(a: SortedSet<T>, b: SortedSet<T>): Bool operator #

      Two SortedSets are equal when they have the same values.

    • Public Method Iterate(): SortedSetIterator<T> method #

      The values, in order. Adding or removing one while going over them panics.

    SortedSetIterator struct 

    Public Struct SortedSetIterator<T: Comparable> Implements Iterator<T>

    The values of a SortedSet, smallest first, which a For loop goes over.

    std/collections/sorted.fb, line 649

    • @PanicsAtCaller Public ByRef Method Next(): T? method #

      The next value, in order, or Null after the largest. Panics when the SortedSet changed since the loop began.

    Extends

    SortedMap extend 

    Extend SortedMap<K, V> Implements Equatable

    Compares SortedMaps with == and !=, where their values can be compared.

    std/collections/sorted.fb, line 525

    • Operator ==(a: SortedMap<K, V>, b: SortedMap<K, V>): Bool operator #

      Whether the two have the same keys, each with an equal value.

    SortedMap extend 

    Extend SortedMap<K, V> Implements Printable

    Shows a SortedMap in a string, as its ToString writes it.

    std/collections/sorted.fb, line 542

    • Public Method ToString(): String method #

      Its entries, in order, as "{a: 1, b: 2}".

    SortedSet extend 

    Extend SortedSet<T> Implements Printable

    Shows a SortedSet in a string, as its ToString writes it.

    std/collections/sorted.fb, line 664

    • Public Method ToString(): String method #

      Its values, in order, as "{1, 2, 3}".

    Report an issue with this page or with FutureBlitz on GitHub.