Treap<T> extension type

A persistent treap implementation using immutable nodes.

Provides efficient insertion, deletion, and lookup operations (O(log N)).

on
Implemented types

Constructors

Treap()
Creates an empty Treap.
Treap.of(Iterable<T> items)
Creates a Treap containing the items.

Properties

base → TreapBase<T, ImmutableNode<T>>
final
compare → Comparator<T>
The Comparator used to determine element order.
finalinherited
first → T
The first item in the sorted sequence.
no setterinherited
firstOrDefault → T?
The first item in the sorted sequence, or null if this treap is empty.
no setterinherited
hashCode → int
The hash code for this object.
no setterinherited
isEmpty → bool
Whether this treap is empty.
no setterinherited
last → T
The last item in the sorted sequence.
no setterinherited
lastOrDefault → T?
The last item in the sorted sequence, or null if this treap is empty.
no setterinherited
runtimeType → Type
A representation of the runtime type of the object.
no setterinherited
size → int
The number of items in this treap.
no setterinherited
values → Iterable<T>
An Iterable of the items in this treap in ascending order according to compare.
no setterinherited

Methods

add(T item) → Treap<T>
Adds an item to this treap.
override
addAll(Iterable<T> items) → Treap<T>
Adds all items to this treap.
override
addOrUpdate(T item) → Treap<T>
Adds or updates an item in this treap.
override
copy() → Treap<T>
Returns a copy of this treap.
override
difference(Treap<T> other) → Treap<T>
Returns the difference of this treap minus other.
override
find(T item) → T?
Finds the item in this treap equal to item.
inherited
has(T item) → bool
Whether this treap contains an item equal to item.
inherited
intersection(Treap<T> other) → Treap<T>
Returns the intersection of this treap and other.
override
next(T item) → T
Returns the item succeeding item in the sorted sequence.
inherited
noSuchMethod(Invocation invocation) → dynamic
Invoked when a nonexistent method or property is accessed.
inherited
prev(T item) → T
Returns the item preceding item in the sorted sequence.
inherited
rank(T item) → int
Returns the rank of item in the sorted sequence of items.
inherited
remove(T item) → Treap<T>
Removes an item from this treap.
override
select(int index) → T
Returns the item at the given index in the sorted sequence.
inherited
skip(int count) → Treap<T>
Returns a new treap skipping the first count items.
override
take(int count) → Treap<T>
Returns a new treap containing the first count items.
override
toString() → String
A string representation of this object.
inherited
union(Treap<T> other) → Treap<T>
Returns the union of this treap and other.
override

Operators

operator &(TreapBase<T, ImmutableNode<T>> other) → TreapBase<T, ImmutableNode<T>>
Operator overload for the intersection of two treaps.
inherited
operator +(T item) → TreapBase<T, ImmutableNode<T>>
Operator overload for adding an item to the treap.
inherited
operator -(TreapBase<T, ImmutableNode<T>> other) → TreapBase<T, ImmutableNode<T>>
Operator overload for the difference of two treaps.
inherited
operator ==(Object other) → bool
The equality operator.
inherited
operator [](int index) → T
Operator overload for selecting an item in the treap by its index.
inherited
operator |(TreapBase<T, ImmutableNode<T>> other) → TreapBase<T, ImmutableNode<T>>
Operator overload for the union of two treaps.
inherited