Treap<T> class final

A fully persistent (immutable) implementation of a Treap.

A treap is a type of binary search tree where each node is assigned a uniformly distributed priority, either randomly or by a strong hash.

Nodes in the tree are kept heap-ordered with respect to their priority. This ensures that the shape of the tree is a random variable with the same probability distribution as a random binary tree. Hence the name treap, which is a portmanteau of tree and heap.

In particular (with high probability), given a treap with N keys, the height is O(log(N)), so that find, add, remove, etc. also take O(log(N)) time to perform.

This particular implementation is made persistent by means of path copying.

Both add and remove have a space complexity of O(log(N)) due to path copying, but erased nodes can later be reclaimed by the garbage collector if the old treaps containing them become eligible for collection.

Annotations
  • @immutable

Constructors

Treap.new([Comparator<T>? compare])
Creates an empty Treap with an optional compare function.
Treap.of(Iterable<T> items, [Comparator<T>? compare])
Builds a treap containing the items.
factory

Properties

compare → Comparator<T>
The Comparator used to determine element order.
no setter
first → T
Returns the first item in this treap.
no setter
firstOrDefault → T?
Returns the first item in this treap, or null if it is empty.
no setter
hashCode → int
The hash code for this object.
no setterinherited
isEmpty → bool
Checks whether this treap is empty.
no setter
last → T
Returns the last item in this treap.
no setter
lastOrDefault → T?
Returns the last item in this treap, or null if it is empty.
no setter
runtimeType → Type
A representation of the runtime type of the object.
no setterinherited
size → int
Returns the size of this treap.
no setter
values → Iterable<T>
Returns the values in this treap ordered by the compare.
no setter

Methods

add(T item) → Treap<T>
Adds an item to the treap.
addAll(Iterable<T> items) → Treap<T>
Adds a range of items to the treap.
addOrUpdate(T item) → Treap<T>
Adds or updates an item in the treap.
copy() → Treap<T>
Creates a copy of this treap.
difference(Treap<T> other) → Treap<T>
Returns a new treap that is the difference of this treap minus the other treap.
find(T item) → T?
Finds the item in this treap.
has(T item) → bool
Checks whether an item exists in this treap.
intersection(Treap<T> other) → Treap<T>
Returns a new treap that is the intersection of this treap and the other treap.
next(T item) → T
Returns the next item in the treap for a given item.
noSuchMethod(Invocation invocation) → dynamic
Invoked when a nonexistent method or property is accessed.
inherited
prev(T item) → T
Returns the item preceding a given item in this treap.
rank(T item) → int
Returns the rank of an item.
remove(T item) → Treap<T>
Removes an item from the treap, if it exists.
select(int index) → T
Selects an item in this treap by its index.
skip(int n) → Treap<T>
Skips the first n items and returns a new treap with the remaining items.
take(int n) → Treap<T>
Returns a new treap with the first n items.
toString() → String
A string representation of this object.
inherited
union(Treap<T> other) → Treap<T>
Returns a new treap that is the union of this treap and the other treap.

Operators

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