std.container.rbtree

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

auto rbt = redBlackTree(3, 1, 4, 2, 5);
assert(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]));

// Запрос ограничивается в пределах O(log(n))
assert(rbt.lowerBound(3).equal([1, 2]));
assert(rbt.equalRange(3).equal([3]));
assert(rbt.upperBound(3).equal([4, 5]));

// Красно-черное дерево с наибольшим элементом спереди:
import std.range : iota;
auto maxTree = redBlackTree!"a > b"(iota(5));
assert(equal(maxTree[], [4, 3, 2, 1, 0]));

// добавление дубликатов не добавит их, но возвращается 0
auto rbt2 = redBlackTree(1, 3);
assert(rbt2.insert(1) == 0);
assert(equal(rbt2[], [1, 3]));
assert(rbt2.insert(2) == 1);

// тем не менее, вы можете разрешить дубликаты
auto ubt = redBlackTree!true([0, 1, 0, 1]);
assert(equal(ubt[], [0, 0, 1, 1]));

Переместиться к: back · clear · ConstRange · dup · Elem · empty · equalRange · front · ImmutableRange · insert · length · lowerBound · opBinaryRight · opEquals · opSlice · Range · remove · removeAny · removeBack · removeFront · removeKey · stableInsert · this · toString · upperBound

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

@property bool empty();

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

const @property size_t length();

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

Сложность: Ο(1).

@property RedBlackTree dup();

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

Сложность: Ο(n)

Range opSlice();

const ConstRange opSlice();

immutable ImmutableRange opSlice();

Извлекает диапазон, который охватывает все элементы в контейнере.

Сложность: Ο(1)

Elem front();

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

Сложность: Ο(1)

Elem back();

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

Сложность: Ο(log(n))

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

Оператор in. Проверяет, присутствует ли данный элемент в контейнере.

Сложность: Ο(log(n))

bool opEquals(Object rhs);

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

Сложность: Ο(n)

void clear();

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

Сложность: Ο(1)

Переместиться к: 2

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

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

Возвращает:

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

Сложность: Ο(log(n))

size_t stableInsert(Stuff)(Stuff stuff)
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))

Переместиться к: 2

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)
if (allSatisfy!(isImplicitlyConvertibleToElem, U));

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

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

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

Возвращает:

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

Сложность: Ο(m log(n)) (где m – это количество элементов для удаления)

Example:

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, FormatSpec!char fmt);

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

Переместиться к: 2 · 3

this(Elem[] elems...);

Конструктор. Ему должен передаваться массив элементов или отдельные элементы, чтобы инициализировать с ними дерево.

this(Stuff)(Stuff stuff)
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...)
if (is(typeof(binaryFun!less(E.init, E.init))));

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

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

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

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

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

Удобная функция для создания RedBlackTree!E из списка величин.

Parameters:

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);

// также работает с диапазонами 
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));