TreeSet<T> structv0.1.0

pub struct TreeSet<T> {
    // private fields
}

Move-only: it owns every node and every element in them.

Type parameters

Constructors

TreeSet

pub func TreeSet(
    allocator: Allocator,
    compare: func(T, T) -> Ordering
) -> TreeSet<T>

An empty set ordered by compare, which has allocated nothing. allocator is borrowed for the call and kept for the set's life. compare must impose the same order every call; a set whose comparison changes under it loses elements it still holds. Cannot fail. Runs in constant time and allocates nothing.

Returns: an empty collection that has taken no storage yet

Source

Methods

Length

pub func Length(self: &TreeSet<T>) -> uint

How many elements the set holds.

Returns: how many elements it holds

Source

IsEmpty

pub func IsEmpty(self: &TreeSet<T>) -> bool

Whether the set holds no elements.

Returns: whether it holds nothing

Source

Contains

pub func Contains(self: &TreeSet<T>, value: T) -> bool

Whether value is in the set. Runs in time proportional to the height, which is at most twice the logarithm of the length.

Returns: whether the value is present

Source

Insert

pub func Insert(
    self: &var TreeSet<T>,
    value: T
) -> bool ! CollectionError

Puts value into the set, and reports whether it was not already there. Takes ownership. An element equal to one already present is destroyed rather than stored, since the one in the set is equal to it and is what everything is already ordered against — so a set never grows past the number of distinct elements put into it. Reports OutOfMemory when the node cannot be allocated, having changed nothing.

Returns: whether the value was new rather than already present

Source

Remove

pub func Remove(self: &var TreeSet<T>, value: T) -> bool

Takes value out of the set, reporting whether it was there. Cannot fail. Runs in time proportional to the height and allocates nothing.

Returns: whether the value was there to remove

Source

Clear

pub func Clear(self: &var TreeSet<T>)

Destroys every element, leaving an empty set that is still usable.

Source

First

pub func First(self: &TreeSet<T>) -> T?

The smallest element, or none for an empty set. Runs in time proportional to the height and allocates nothing.

Returns: the smallest element, or none when empty

Source

Last

pub func Last(self: &TreeSet<T>) -> T?

The largest element, or none for an empty set.

Returns: the largest element, or none when empty

Source

Floor

pub func Floor(self: &TreeSet<T>, value: T) -> T?

The largest element at or below value, or none when every element is above it.

Returns: the largest element at or below value, or none

Source

Ceiling

pub func Ceiling(self: &TreeSet<T>, value: T) -> T?

The smallest element at or above value, or none when every element is below it.

Returns: the smallest element at or above value, or none

Source

Iterate

pub func Iterate(self: &TreeSet<T>) -> TreeSetIterator<T>

A walk over this set, smallest element first, leaving it untouched. self is borrowed and must outlive the walk, which must not run across an insertion or a removal.

Returns: a cursor over the elements in order

Source

Range

pub func Range(
    self: &TreeSet<T>,
    start: T,
    end: T
) -> TreeSetRangeIterator<T>

A walk over the elements at or above start and below end. Half-open, so Range(a, b) and Range(b, c) together give exactly Range(a, c) with nothing repeated and nothing missed. A range whose end is not above its start hands back nothing.

Returns: a cursor over the elements that fall in [start, end)

Source

IntoIterator

pub func IntoIterator(self: TreeSet<T>) -> TreeSetIntoIterator<T>

A walk that consumes this set, smallest element first. Takes ownership; the set is gone afterwards.

Returns: a cursor that consumes the set as it goes, in order

Source

IsSubsetOf

pub func IsSubsetOf(
    self: &TreeSet<T>,
    other: &TreeSet<T>
) -> bool

Whether every element of this set is in other. The empty set is a subset of everything, including itself. Allocates nothing and cannot fail. Runs in time proportional to this set's length times the logarithm of other's.

Returns: whether every element of this set is in other

Source

IsSupersetOf

pub func IsSupersetOf(
    self: &TreeSet<T>,
    other: &TreeSet<T>
) -> bool

Whether every element of other is in this set.

Returns: whether every element of other is in this set

Source

IsDisjointFrom

pub func IsDisjointFrom(
    self: &TreeSet<T>,
    other: &TreeSet<T>
) -> bool

Whether the two sets share no element. The empty set is disjoint from everything, including itself. The smaller set is the one walked, since either walk gives the same answer and one of them is shorter.

Returns: whether the two share no element

Source

Equals

pub func Equals(
    self: &TreeSet<T>,
    other: &TreeSet<T>
) -> bool

Whether the two sets hold exactly the same elements. Order is not part of the question — two sets are equal when each contains the other — but having an order makes the lengths enough to reject most pairs before looking at an element.

Returns: whether both hold exactly the same elements

Source

UnionWith

pub func UnionWith(
    self: &var TreeSet<T>,
    other: &TreeSet<T>
) -> ! CollectionError

Adds every element of other that is not already here. Reports OutOfMemory if a node cannot be allocated, having added what it managed to before that — unlike the hash set's, which reserves the worst case first and is all-or-nothing. A tree has no capacity to reserve: every element is a separate allocation, so there is no point at which the whole operation can be paid for in advance. What it gives back instead is that a partial union is still a set with every invariant intact, and running the same call again finishes it.

Returns: nothing when the operation succeeded, or why it did not

Source

IntersectWith

pub func IntersectWith(
    self: &var TreeSet<T>,
    other: &TreeSet<T>
)

Keeps only the elements that are also in other. Allocates nothing and cannot fail: a set only ever gets smaller here. The walk asks for the next element by key rather than by following a pointer, because removing relinks the nodes around what was removed — including, when it has two children, the very node a pointer walk would have been about to visit. A key survives that; a pointer does not. The price is a descent per element rather than an edge.

Source

Subtract

pub func Subtract(self: &var TreeSet<T>, other: &TreeSet<T>)

Removes every element that is also in other. Allocates nothing and cannot fail, and walks the same way IntersectWith does and for the same reason.

Source

SymmetricDifferenceWith

pub func SymmetricDifferenceWith(
    self: &var TreeSet<T>,
    other: &TreeSet<T>
) -> ! CollectionError

Keeps the elements that are in exactly one of the two sets. Reports OutOfMemory if a node cannot be allocated, having done what it managed to first. The removals and the additions cannot be interleaved: an element removed from this set would then look absent when other's copy of it arrived, and be added straight back. So what is shared is taken out first, and only then is what is left of other put in.

Returns: nothing when the operation succeeded, or why it did not

Source

Clone

pub func Clone(self: &TreeSet<T>) -> TreeSet<T> ! CollectionError

A set holding what this one holds, ordered the same way and allocating from the same allocator. A failed clone hands back nothing rather than half of a set.

Returns: an independent copy

Source

Related

WriteTreeSetDebug<T>

pub func WriteTreeSetDebug<T: Debug>(
    writer: &var TextWriter,
    value: &TreeSet<T>,
    spec: FormatSpec
) -> ! FormatError

Writes a borrowed ordered set as {first, second, third}, in order. An empty set is {}. The order is the set's own, so the rendering is stable between sets holding the same elements and between runs, unlike a hash set's. Every element is shown through a borrow of the node holding it, and spec is handed to each unchanged. Reports whatever the writer or an element's implementation reported, stopping at the first refusal.

Source

Type parameters

Parameters

Returns: success when the whole rendering was accepted

TreeSetIterator<T>

pub struct TreeSetIterator<T> {
    // private fields
}

A walk over a borrowed set, smallest element first.

Source

Type parameters

Implements Iterator

TreeSetIterator<T> conforms to Iterator.

Next

pub func Next(self: &var TreeSetIterator<T>) -> T?

The next element in order, or none when there are no more. Runs in constant amortized time: a whole walk crosses every edge of the tree exactly twice.

Returns: the next element in order, or none at the end

Source

TreeSetRangeIterator<T>

pub struct TreeSetRangeIterator<T> {
    // private fields
}

A walk over a borrowed set that stops at a bound.

Source

Type parameters

Implements Iterator

TreeSetRangeIterator<T> conforms to Iterator.

Next

pub func Next(self: &var TreeSetRangeIterator<T>) -> T?

The next element below the bound, or none once the walk reaches it.

Returns: the next element in order, or none at the end

Source

TreeSetIntoIterator<T>

pub struct TreeSetIntoIterator<T> {
    // private fields
}

A walk that consumes the set, smallest element first. Owns the nodes, and destroys whatever is left in them when it dies — so a walk stopped part-way destroys the rest exactly once, and nothing already handed out is destroyed twice.

Source

Type parameters

Implements Iterator

TreeSetIntoIterator<T> conforms to Iterator.

Next

pub func Next(self: &var TreeSetIntoIterator<T>) -> T?

The next element in order, or none when there are no more. Takes the smallest element out of the tree rather than reading past it, which is what makes it the caller's.

Returns: the next element in order, or none at the end

Source