std.container.rbtree

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

// 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);
writeln(rbt2.insert(1)); // 0
assert(equal(rbt2[], [1, 3]));
writeln(rbt2.insert(2)); // 1

// しかしながら、重複を許可することもできる
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 は厳密な順序付けを行うべきである。つまり、2つの異なる要素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();

コンテナ内に要素が存在するかどうかを確認します。少なくとも1つの要素が存在する場合はfalse を返します。

const @property size_t length();

コンテナ内の要素数を返す。

複雑度 Ο(1)。

@property RedBlackTree dup();

このコンテナを複製する。結果として得られるコンテナには、要素の浅い コピーが含まれる。

Complexity Ο(n)

Range opSlice();

const ConstRange opSlice();

immutable ImmutableRange opSlice();

コンテナ内のすべての要素にまたがる範囲を取得する。

複雑性 Ο(1)

inout inout(Elem) front();

コンテナの最前面の要素

Complexity Ο(1)

inout inout(Elem) back();

コンテナ内の最後の要素

Complexity Ο(log(n))

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

in 演算子。指定された要素がコンテナ内に存在するかどうかを確認する。

Complexity Ο(log(n))

bool opEquals(Object rhs);

2つのツリーが等しいかどうかを比較する。

複雑性 Ο(n)

nothrow @safe size_t toHash();

ツリーに対するハッシュを生成する。カスタム比較関数を使用する場合、 2つのrbtreeが等しい場合でも、ツリーのハッシュが 等しくなるとは限らないことに注意すること。

void clear();

コンテナからすべての要素を削除する。

複雑度 Ο(1)

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

コンテナに単一の要素を挿入する。 現在コンテナを反復している範囲は無効にならないことに注意すること。

Returns:

挿入された要素の数。

複雑性 Ο(log(n))

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

alias insert = stableInsert;

コンテナ内の要素の範囲を挿入する。 コンテナを現在反復している範囲が無効になることはないことに注意。

Returns:

挿入された要素の数。

複雑性 Ο(m * log(n))

Elem removeAny();

コンテナから要素を削除し、その値を返す。

複雑性 Ο(log(n))

void removeFront();

コンテナから先頭の要素を削除する。

複雑性 Ο(log(n))

void removeBack();

コンテナから背面の要素を取り外す。

複雑さ Ο(log(n))

Range remove(Range r);

コンテナから指定された範囲を削除する。

Returns:

指定された範囲より後にあるすべての要素を含む範囲。

複雑性 Ο(m * log(n)) (ここで、m は範囲内の要素の数である )

Range remove(Take!Range r);

与えられたTake!Range をコンテナから削除する

Returns:

指定された範囲の後に続くすべての要素を含む範囲 。

Complexity Ο(m * log(n)) (ここでmは範囲内の要素数)

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

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

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

コンテナから、与えられた値と等しい要素を削除する。 less比較演算子に従う。コンテナ内の値の数だけ要素が削除される。allowDuplicates がtrueの場合、 重複値が与えられている場合のみ重複要素が削除される。

Returns:

削除される要素の数。

複雑さ Ο(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 である範囲を取得する。

複雑度 Ο(log(n))

Range lowerBound(Elem e);

const ConstRange lowerBound(Elem e);

immutable ImmutableRange lowerBound(Elem e);

コンテナから、less比較演算子に従ってeより小さいすべての要素を含む範囲を取得する

Ο(log(n))

auto equalRange(this This)(Elem e);

コンテナから、less比較演算子に従ってeと等しいすべての要素を含む範囲を取得する

複雑性 Ο(log(n))

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

RedBlackTreeをシンク関数にフォーマットする。詳細は std.format.formatValue を参照のこと。これは要素型がフォーマット可能である場合のみ利用できることに注意すること。 それ以外の場合、ObjectのデフォルトのtoStringが使用される。

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の代替)

rangerange

Examples:

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