std.container.rbtree

В этом модуле реализован контейнер красно-чёрного дерева.

Этот модуль является подмодулем std.container.

Исходный код

std/container/rbtree.d

Лицензия:

Распространяется по лицензии Boost Software License, версия 1.0. (См. прилагаемый файл LICENSE_1_0.txt или копию на boost.org/LICENSE_1_0.txt).

Авторы:

Steven Schveighoffer, Andrei Alexandrescu

Примеры:

import std.algorithm.comparison : equal;
import std.container.rbtree;

auto rbt = redBlackTree(3, 1, 4, 2, 5);
writeln(rbt.front); // 1
assert(equal(rbt[], [1, 2, 3, 4, 5]));

rbt.removeKey(1, 4);
assert(equal(rbt[], [2, 3, 5]));

rbt.removeFront();
assert(equal(rbt[], [3, 5]));

rbt.insert([1, 2, 4]);
assert(equal(rbt[], [1, 2, 3, 4, 5]));

// Query bounds in O(log(n))
assert(rbt.lowerBound(3).equal([1, 2]));
assert(rbt.equalRange(3).equal([3]));
assert(rbt.upperBound(3).equal([4, 5]));

// A Red Black tree with the highest element at front:
import std.range : iota;
auto maxTree = redBlackTree!"a > b"(iota(5));
assert(equal(maxTree[], [4, 3, 2, 1, 0]));

// adding duplicates will not add them, but return 0
auto rbt2 = redBlackTree(1, 3);
writeln(rbt2.insert(1)); // 0
assert(equal(rbt2[], [1, 3]));
writeln(rbt2.insert(2)); // 1

// however you can allow duplicates
auto ubt = redBlackTree!true([0, 1, 0, 1]);
assert(equal(ubt[], [0, 0, 1, 1]));

class RedBlackTree(T, alias less = "a < b", bool allowDuplicates = false) if (is(typeof(binaryFun!less(T.init, T.init))));

Реализация контейнера красно-чёрного дерева.

Все операции вставки, удаления, поиска и любые функции в целом имеют сложность Ο(lg(n)).

Чтобы использовать сравнение отличное от "a < b", передайте другую строку оператора, которая может быть использована std.functional.binaryFun, или передайте функцию, делегат, функтор или любой тип, где less(a, b) приводит к значению bool.

Обратите внимание, что less должно обеспечивать строгое упорядочение. То есть, для двух неравных элементов a и b, less(a, b) == !less(b, a). less(a, a) всегда должно быть равно false.

Если allowDuplicates установлено в значение true, то вставка одного и того же элемента более одного раза продолжает добавлять больше элементов. Если это false, дубликаты элементов игнорируются при вставке. Если дубликаты разрешены, то новые элементы вставляются после всех существующих дубликатов.

alias Elem = T;

Тип элемента для дерева

alias Range = RBRange!(RBNode*);

alias ConstRange = RBRange!(const(RBNode)*);

alias ImmutableRange = RBRange!(immutable(RBNode)*);

Типы диапазонов для RedBlackTree

const @property bool empty();

Проверка, существуют ли какие-либо элементы в контейнере. Возвращает false если хотя бы один элемент существует.

const @property size_t length();

Возвращает количество элементов в контейнере.

Сложность

Ο(1).

@property RedBlackTree dup();

Создать копию этого контейнера. Результирующий контейнер содержит поверхностную копию элементов.

Сложность

Ο(n)

Range opSlice();

const ConstRange opSlice();

immutable ImmutableRange opSlice();

Получение диапазона, охватывающего все элементы в контейнере.

Сложность

Ο(1)

inout inout(Elem) front();

Первый элемент в контейнере

Сложность

Ο(1)

inout inout(Elem) back();

Последний элемент в контейнере

Сложность

Ο(log(n))

const bool opBinaryRight(string op)(Elem e)
Constraints: if (op == "in");

Оператор in. Проверка наличия заданного элемента в контейнере.

Сложность

Ο(log(n))

bool opEquals(Object rhs);

Сравнение двух деревьев на равенство.

Сложность

Ο(n)

nothrow @safe size_t toHash();

Генерирует хеш для дерева. Обратите внимание, что с пользовательской функцией сравнения может не выполняться условие, что если два rbtree равны, то хеши деревьев будут равны.

void clear();

Удаляет все элементы из контейнера.

Сложность

Ο(1)

size_t stableInsert(Stuff)(Stuff stuff)
Constraints: if (isImplicitlyConvertible!(Stuff, Elem));

Вставка одного элемента в контейнер. Обратите внимание, что это не делает недействительными любые текущие итерации контейнера.

Возвращает:

Количество добавленных элементов.

Сложность

Ο(log(n))

size_t stableInsert(Stuff)(scope Stuff stuff)
Constraints: if (isInputRange!Stuff && isImplicitlyConvertible!(ElementType!Stuff, Elem));

alias insert = stableInsert;

Вставка диапазона элементов в контейнер. Обратите внимание, что это не делает недействительными любые текущие итерации контейнера.

Возвращает:

Количество добавленных элементов.

Сложность

Ο(m * log(n))

Elem removeAny();

Удаление элемента из контейнера и возврат его значения.

Сложность

Ο(log(n))

void removeFront();

Удаление первого элемента из контейнера.

Сложность

Ο(log(n))

void removeBack();

Удаление последнего элемента из контейнера.

Сложность

Ο(log(n))

Range remove(Range r);

Удаление заданного диапазона из контейнера.

Возвращает:

Диапазон, содержащий все элементы, которые были после данного диапазона.

Сложность

Ο(m * log(n)) (где m - количество элементов в диапазоне)

Range remove(Take!Range r);

Удаление заданного Take!Range из контейнера

Возвращает:

Диапазон, содержащий все элементы, которые были после данного диапазона.

Сложность

Ο(m * log(n)) (где m - количество элементов в диапазоне)

size_t removeKey(U...)(U elems)
Constraints: if (allSatisfy!(isImplicitlyConvertibleToElem, U));

size_t removeKey(U)(scope U[] elems)
Constraints: if (isImplicitlyConvertible!(U, Elem));

size_t removeKey(Stuff)(Stuff stuff)
Constraints: if (isInputRange!Stuff && isImplicitlyConvertible!(ElementType!Stuff, Elem) && !isDynamicArray!Stuff);

Удаляет элементы из контейнера, равные заданным значениям согласно компаратору less. Один элемент удаляется для каждого заданного значения, которое присутствует в контейнере. Если allowDuplicates истинно, дубликаты удаляются только если даны дубликаты значений.

Возвращает:

Количество удаленных элементов.

Сложность

Ο(m log(n)) (где m - количество элементов для удаления)

Пример

auto rbt = redBlackTree!true(0, 1, 1, 1, 4, 5, 7);
rbt.removeKey(1, 4, 7);
assert(equal(rbt[], [0, 1, 1, 5]));
rbt.removeKey(1, 1, 0);
assert(equal(rbt[], [5]));

Range upperBound(Elem e);

const ConstRange upperBound(Elem e);

immutable ImmutableRange upperBound(Elem e);

Получить диапазон из контейнера со всеми элементами, которые > e согласно компаратору less

Сложность

Ο(log(n))

Range lowerBound(Elem e);

const ConstRange lowerBound(Elem e);

immutable ImmutableRange lowerBound(Elem e);

Получить диапазон из контейнера со всеми элементами, которые < e согласно компаратору less

Сложность

Ο(log(n))

auto equalRange(this This)(Elem e);

Получить диапазон из контейнера со всеми элементами, которые == e согласно компаратору less

Сложность

Ο(log(n))

const void toString(scope void delegate(const(char)[]) sink, ref scope const FormatSpec!char fmt);

Форматирует RedBlackTree в функцию-приёмник. Для получения более подробной информации см. std.format.formatValue. Обратите внимание, что это доступно только когда тип элемента может быть отформатирован. В противном случае используется стандартный toString из Object.

this(Elem[] elems...);

Конструктор. Передайте массив элементов или отдельные элементы для инициализации дерева.

this(Stuff)(Stuff stuff)
Constraints: if (isInputRange!Stuff && isImplicitlyConvertible!(ElementType!Stuff, Elem));

Конструктор. Передайте диапазон элементов для инициализации дерева.

this();

auto redBlackTree(E)(E[] elems...);

auto redBlackTree(bool allowDuplicates, E)(E[] elems...);

auto redBlackTree(alias less, E)(E[] elems...)
Constraints: if (is(typeof(binaryFun!less(E.init, E.init))));

auto redBlackTree(alias less, bool allowDuplicates, E)(E[] elems...)
Constraints: if (is(typeof(binaryFun!less(E.init, E.init))));

auto redBlackTree(Stuff)(Stuff range)
Constraints: if (isInputRange!Stuff && !isArray!Stuff);

auto redBlackTree(bool allowDuplicates, Stuff)(Stuff range)
Constraints: if (isInputRange!Stuff && !isArray!Stuff);

auto redBlackTree(alias less, Stuff)(Stuff range)
Constraints: if (is(typeof(binaryFun!less((ElementType!Stuff).init, (ElementType!Stuff).init))) && isInputRange!Stuff && !isArray!Stuff);

auto redBlackTree(alias less, bool allowDuplicates, Stuff)(Stuff range)
Constraints: if (is(typeof(binaryFun!less((ElementType!Stuff).init, (ElementType!Stuff).init))) && isInputRange!Stuff && !isArray!Stuff);

Функция для создания RedBlackTree!E из списка значений.

Параметры:

allowDuplicates	Разрешить дубликаты (необязательно, по умолчанию: false)
less	предикат для сортировки (необязательно)
E[] elems	элементы для вставки в rbtree (переменное число аргументов)
Stuff range	диапазон элементов для вставки в rbtree (альтернатива elems)

Примеры:

import std.range : iota;

auto rbt1 = redBlackTree(0, 1, 5, 7);
auto rbt2 = redBlackTree!string("hello", "world");
auto rbt3 = redBlackTree!true(0, 1, 5, 7, 5);
auto rbt4 = redBlackTree!"a > b"(0, 1, 5, 7);
auto rbt5 = redBlackTree!("a > b", true)(0.1, 1.3, 5.9, 7.2, 5.9);

// also works with ranges
auto rbt6 = redBlackTree(iota(3));
auto rbt7 = redBlackTree!true(iota(3));
auto rbt8 = redBlackTree!"a > b"(iota(3));
auto rbt9 = redBlackTree!("a > b", true)(iota(3));