Usage

Firstly, add using directive for WBTrees namespace.

using System;
using System.Collections.Generic;
using System.Linq;
using WBTrees;

WBList<T>

The basic operations of the WBList<T> class are similar to that of the System.Collections.Generic.List<T> class.

var list = new WBList<int>();

// Clears and constructs a tree with data.
list.Initialize(Enumerable.Range(0, 100));

list.Prepend(123);
list.Add(-234);
list.Insert(3, 345);
list.RemoveAt(5);

var item = list[7];
list[9] = 456;

// In a range [left, right). Note that it is a half-open interval.
var items = list.GetItems(20, 30).ToArray();

WBSet<T> and WBMultiSet<T>

The basic operations of the WBSet<T> class are similar to that of the System.Collections.Generic.SortedSet<T> class.

var set = new WBSet<int>();

// Clears and constructs a tree with data.
set.Initialize(Enumerable.Range(0, 100));

set.Add(123);
if (set.Contains(123)) { }
set.Remove(123);

Binary Search (Get/Remove Item)

Call the GetFirst or GetLast method with a condition.

var set = new WBSet<int> { 4, 1, 5, 9, 2 }; // 1, 2, 4, 5, 9

var f1 = set.GetFirst(x => x >= 2).Item; // 2
var f2 = set.GetFirst(x => x > 2).Item;  // 4
var l1 = set.GetLast(x => x <= 2).Item;  // 2
var l2 = set.GetLast(x => x < 2).Item;   // 1

var f3 = set.GetFirst(x => x > 9); // null
var l3 = set.GetLast(x => x < 1);  // null

A Node<T> object will be returned from Get*** or Remove*** methods. null denotes that no items satisfy the specified condition.

Binary Search (Get Index)

var set = new WBSet<int> { 4, 1, 5, 9, 2 }; // 1, 2, 4, 5, 9

var fi1 = set.GetFirstIndex(x => x > 2); // 2
var li1 = set.GetLastIndex(x => x < 2);  // 0

var fi2 = set.GetFirstIndex(x => x > 9); // 5 (set.Count)
var li2 = set.GetLastIndex(x => x < 1);  // -1

Binary Search (Get/Remove Items)

var set = new WBMultiSet<int> { 3, 1, 4, 1, 5, 9, 2, 6, 5 }; // 1, 1, 2, 3, 4, 5, 5, 6, 9

var items = set.GetItems(x => x >= 3, x => x < 6).ToArray(); // 3, 4, 5, 5
var count = set.GetCount(x => x >= 3, x => x < 6); // 4
var count5 = set.GetCount(5); // 2

// Returns the removed count.
var removedCount = set.RemoveItems(x => x >= 3, x => x < 6); // 4
var all = set.ToArray(); // 1, 1, 2, 6, 9

Operations by Index

var set = new WBMultiSet<int> { 3, 1, 4, 1, 5, 9, 2, 6, 5 }; // 1, 1, 2, 3, 4, 5, 5, 6, 9

var item = set.GetAt(6).Item; // 5
var node = set.GetAt(-2); // null
var removedItem = set.RemoveAt(8).Item; // 9

// In a range [left, right). Note that it is a half-open interval.
var items = set.GetItems(1, 4).ToArray(); // 1, 2, 3

WBMap<TKey, TValue> and WBMultiMap<TKey, TValue>

The basic operations of the WBMap<T> class are similar to that of the System.Collections.Generic.SortedDictionary<T> class.

var map = new WBMap<int, int>();

// Updates value or adds a key-value pair.
map[123] = 456;
var value = map[123];

// Adds a key-value pair if the specified key is not found.
map.Add(123, 789); // false
if (map.ContainsKey(123)) { }
map.Remove(123);

Binary search and index access of the WBMap<T> and WBMultiMap<T> classes are similar to that of the WBSet<T> and WBMultiSet<T> classes. The WBMultiMap<T> class can hold multiple values for one key:

var map = new WBMultiMap<int, int>
{
	{ 3, 1 },
	{ 4, 1 },
	{ 5, 9 },
	{ 2, 6 },
	{ 5, 3 },
};

var values = map[5].ToArray(); // 9, 3

Provides extension methods for Node<T> or Node<KeyValuePair<TKey, TValue>>.

var map = new WBMap<int, int>
{
	{ 3, 1 },
	{ 4, 1 },
	{ 5, 9 },
	{ 2, 6 },
};

var value5 = map[5]; // 9
var value6 = map.Get(6).GetValueOrDefault(-1); // -1

// priority queue
while (map.RemoveFirst().TryGetValue(out var value))
{
}