//module RedBlackTree;
import tango.util.collection.model.Comparator,
tango.util.collection.model.GuardIterator,
tango.util.collection.model.Iterator;
// TODO should these be in Basic Node?
// The two children of a node
enum {Left = 0, Right}
// Tags the links of a node
enum Tag {Thread = 0, Child}
/*******************************************************************************
The basic structure of a node needed for the RedBlackTree.
Remarks:
This class is meant to be overriden using the Curriosly Reoccuring Template
Pattern (CRTP). Each subclass must expose a default constructor.
Examples:
---
class Node(V) : BasicNode!(V, Node!(V)) {
alias V KeyType;
this() {}
}
---
*******************************************************************************/
abstract class BasicNode(KeyType, NodeType) {
alias KeyType KeyTypeT;
protected:
// the data used in comparison
protected KeyType key;
/****************************************************************
Construct a new node.
Params:
value = the value to store in the node
****************************************************************/
this(KeyType value) {
this();
key = value;
}
/****************************************************************
Construct a new node without any data.
****************************************************************/
this() {
red = true;
link[Left] = null;
link[Right] = null;
tag[Left] = Tag.Thread;
tag[Right] = Tag.Thread;
}
protected:
// is the node red (as opposed to black)
bool red;
// the two children/thread nodes
NodeType[2] link;
// tag the links as children or threads
Tag[2] tag;
/****************************************************************
Get either the first or last descendant of the sub-tree.
Params:
dir = which direction to go, use Left or Right.
Remarks:
Traverse down the tree, returning the the node containing
either the smallest or the largest value, depending on dir
and the comparotor in use.
Returns:
The right- or left-most node of the sub-tree
****************************************************************/
NodeType end(int dir) {
NodeType n = cast(NodeType)this;
while (n.tag[dir])
n = n.link[dir];
return n;
}
/****************************************************************
Produce a deep copy of the node
Returns the copied node.
****************************************************************/
protected NodeType copyOf() {
NodeType newNode = new NodeType();
newNode.key = key;
newNode.link[0] = link[0].copyOf();
newNode.link[1] = link[1].copyOf();
newNode.tag[] = tag;
return newNode;
}
}
template RBIterMixins(KeyType, Node, ParentIterator) {
// the current node
protected Node mNode;
// how many items left to enumerate
uint countLeft;
public Node node() {
return mNode;
}
// the direction we are iterating
private const int mDir;
static if (is(ParentIterator : GuardIterator!(KeyType))) {
// the latest tree version
private const uint* mLatestVersion;
// the tree version we are used to
private const uint mVersion;
/***************************************************************
Construct a new iterator.
Params:
ver = the tree version number
node = the start node of the iteration
dir = the direction the iteration is going (default: Right)
***************************************************************/
this(uint* ver, Node node, int dir = Right) {
mNode = node;
mDir = dir;
mVersion = *ver;
mLatestVersion = ver;
}
bool corrupted() {
return mVersion != *mLatestVersion;
}
uint remaining() {
return countLeft;
}
} else {
this (Node node, int dir = Right) {
mNode = node;
mDir = dir;
}
}
/****************************************************************
Ask whether the enumeration can continue.
Remarks:
This iterator has more elements if the base tree has more
elements and hasn't changed since the iterator's construction.
Returns:
True if the enumeration can continue, false otherwise
****************************************************************/
bool more() {
static if (is(ParentIterator : GuardIterator!(KeyType))) {
if (corrupted())
return false;
}
return mNode !is null;
}
/****************************************************************
Get the next element from the iteration.
Remarks:
Returns the next element of the collection and advances the
iterator. O(log n).
Results are undefined if !more().
Returns:
The next element of the collection.
****************************************************************/
KeyType get() {
assert(more());
KeyType data = mNode.value();
advanceNode();
return data;
}
protected void advanceNode() {
// if the next element is a thread, follow it
if (!mNode.tag[mDir]) {
mNode = mNode.link[mDir];
// get the next descendant
} else {
mNode = mNode.link[mDir].end(!mDir);
}
countLeft--;
}
}
/******************************************************************************
A genericized RedBlackTree
Params:
TODO
Remarks:
TODO
******************************************************************************/
abstract class RedBlackTree(alias Traits) : Traits.ParentCollectionT {
alias Traits.NodeT Node;
alias Traits.KeyTypeT KeyType;
alias Traits.ValueTypeT ValueType;
alias Traits.IteratorT IteratorT;
alias Traits.GuardIteratorT GuardIteratorT;
alias Traits.SINGLETON SINGLETON;
alias Traits.DUAL_ITERATION DUAL_ITERATION;
alias Comparator!(KeyType) ComparatorT;
// the root of the tree
protected Node mRoot;
// the comparing function
protected ComparatorT mComparator;
/***************************************************************
Construct an empty RedBlackTree.
Remarks:
The objects natural ordering will be used.
***************************************************************/
this() {
this(null, null, 0);
}
/***************************************************************
Construct a RedBlackTree using this comparator
Params:
c =
***************************************************************/
this(ComparatorT c, Node root, uint size) {
//mRoot = root;
vershion = 0;
count = size;
mComparator = c is null ? &compare : c;
}
/*
*/
override void clear() {
vershion = 0;
mRoot = null;
count = 0;
}
/*
*/
protected Node first() {
if (mRoot is null)
return null;
return mRoot.end(Left);
}
/*
*/
protected Node last() {
if (mRoot is null)
return null;
return mRoot.end(Right);
}
/*
*/
GuardIteratorT elements() {
return new GuardIteratorT(&vershion, first());
}
/*
*/
GuardIteratorT reverseElements() {
return new GuardIteratorT(&vershion, last(), Left);
}
/*
*/
IteratorT iterator() {
return new IteratorT(first());
}
/*
*/
IteratorT reverseIterator() {
return new IteratorT(last(), Left);
}
/*
*/
protected bool contains_(KeyType obj) {
return getFirstElement(obj) !is null;
}
/*
*/
protected Node insert_(KeyType obj, lazy Node newNode, bool singletons=true) {
if (mRoot is null) {
mRoot = newNode;
mRoot.red = false;
setCount(1);
return mRoot;
}
bool isInserted = false;
auto fakeHead = new Node();
int dir = Left, last = Left;
Node great = fakeHead;
Node grand = null;
Node parent = null;
Node current = fakeHead.link[Right] = mRoot;
Tag grandTag = Tag.Thread;
Tag parentTag = Tag.Child;
for (;;) {
if (!parentTag) {
current = newNode;
current.link[dir] = parent.link[dir];
current.link[!dir] = parent;
parent.link[dir] = current;
parent.tag[dir] = parentTag = Tag.Child;
isInserted = true;
incCount();
}
// color flip
else if (isRed(current, Left) && isRed(current, Right)) {
current.red = true;
current.link[Left].red = false;
current.link[Right].red = false;
}
// fix red violation
if (isRed(current, parentTag) && isRed(parent, grandTag)) {
int dir2 = great.link[Right] is grand;
if (current is parent.link[last])
great.link[dir2] = singleRotate(grand, !last);
else
great.link[dir2] = doubleRotate(grand, !last);
}
// Stop if found
int cmp = mComparator(current.key, obj);
static if (SINGLETON) {
if (!cmp)
break;
} else {
if (!cmp && (singletons || isInserted)) {
break;
}
}
last = dir;
dir = cmp < 0;
// update helpers
if (grand !is null) {
great = grand;
}
grand = parent;
parent = current;
current = current.link[dir];
grandTag = parentTag;
parentTag = parent.tag[dir];
}
// update the root and make it black
mRoot = fakeHead.link[Right];
mRoot.red = false;
return current;
}
/*
*/
void remove(KeyType obj) {
if (mRoot is null)
return;// false;
Node fakeHead = new Node();
fakeHead.link[Right] = mRoot;
fakeHead.tag[Right] = Tag.Child;
Node current = fakeHead;
Node parent = null;
Node grand = null;
Node found = null;
int dir = Right;
// search and push down red node
while (current.tag[dir]) {
int last = dir;
// update helpers
grand = parent;
parent = current;
current = current.link[dir];
int cmp = mComparator(current.key, obj);
dir = cmp < 0;
// save the found node
if (!cmp) {
found = current;
}
// push the red node down
if (!isRed(current, parent.tag[last]) && !isRed(current, dir)) {
if (isRed(current, !dir)) {
parent = parent.link[last] = singleRotate(current, dir);
} else {
Node save = parent.link[!last];
if (parent.tag[!last]) {
if (!isRed(save, Left) && !isRed(save, Right)) {
// Color flip
parent.red = false;
save.red = true;
current.red = true;
} else {
int dir2 = grand.link[Right] is parent;
if (isRed(save, last))
grand.link[dir2] = doubleRotate(parent, last);
else
grand.link[dir2] = singleRotate(parent, last);
// ensure correct coloring
Node uncle = grand.link[dir2];
current.red = uncle.red = true;
uncle.link[Left].red = false;
uncle.link[Right].red = false;
}
}
}
}
} // end while
// replace and remove if found
if (found !is null) {
found.key = current.key;
decCount();
int replacementDir = parent.link[Right] is current;
int otherDir = !replacementDir;
//assert(!current.tag[otherDir]);
//assert(current.link[otherDir] is parent || parent is fakeHead);
parent.link[replacementDir] = current.link[replacementDir];
parent.tag[replacementDir] = Tag.Thread;
}
// update the root and make it black
mRoot = fakeHead.link[Right];
if (mRoot !is null) {
mRoot.red = false;
}
// return found !is null;
}
/*
*/
void comparator(ComparatorT c) {
if (c == null)
mComparator = &compare;
if (mComparator is c || !count)
return;
scope auto iter = iterator();
auto node = iter.node;
iter.get();
while (iter.more()) {
node.link[0] = node.link[1] = null;
node.tag[0] = node.tag[1] = Tag.Thread;
insert_(node.key, node);
iter.get();
node = iter.node;
}
node.link[0] = node.link[1] = null;
node.tag[0] = node.tag[1] = Tag.Thread;
insert_(node.key, node);
}
/*
*/
int opApply(int delegate(inout ValueType) dg) {
auto scope iter = elements();
return iter.opApply(dg);
}
/*
*/
int opApplyReverse(int delegate(inout ValueType) dg) {
auto scope iter = reverseElements();
return iter.opApply(dg);
}
/*
*/
static if (DUAL_ITERATION) {
int opApply(int delegate(inout KeyType, inout ValueType) dg) {
scope auto iter = elements();
return iter.opApply(dg);
}
int opApplyReverse(int delegate(inout KeyType, inout ValueType) dg) {
scope auto iter = reverseElements();
return iter.opApply(dg);
}
}
// default comparison function
private int compare(KeyType a, KeyType b) {
static if (is(KeyType : Object)) {
if (a is b)
return 0;
return a.opCmp(b);
} else {
KeyType cmp = a - b;
return cmp < 0 ? -1 : cmp > 0 ? 1 : 0;
}
}
/*
*/
protected Node getFirstElement(KeyType obj) {
if (mRoot is null) return null;
Node cur = mRoot;
auto parentTag = Tag.Child;
while (parentTag) {
int cmp = mComparator(cur.key, obj);
if (!cmp)
return cur;
int dir = cmp < 0;
parentTag = cur.tag[dir];
cur = cur.link[dir];
}
return null;
}
static if (false) {
invariant {
int checkImpl(Node n) {
int lh, rh;
if (n is null)
return 1;
auto ln = n.link[0];
auto rn = n.link[1];
/* Consecutive red */
if (isRed(n, Tag.Child)) {
if (isRed(ln, n.tag[0]) || isRed(rn, n.tag[1])) {
//Stdout("Red violation");
assert(false);
}
}
lh = n.tag[0] ? checkImpl(ln) : 0;
rh = n.tag[1] ? checkImpl(rn) : 0;
/* invalid bst */
if ((n.tag[0] && mComparator(ln.key, n.key) > 0) ||
n.tag[1] && mComparator(rn.key, n.key) < 0) {
//Stdout("BST Violation");
assert(false);
}
// black height mismatch
if (lh != 0 && rh != 0 && lh != rh) {
//Stdout("Black Violation");
assert(false);
}
if (lh != 0 && rh != 0) {
return isRed(n, Tag.Child) ? lh : lh + 1;
}
return 0;
}
checkImpl(mRoot);
}
}
private static:
// helper methods
Node singleRotate(Node node, int dir) {
int otherDir = !dir;
Node save = node.link[otherDir];
// If save's thread points back to node, then just fix the tags
if (!save.tag[dir]) {
save.tag[dir] = Tag.Child;
node.tag[otherDir] = Tag.Thread;
// otherwise swap children
} else {
node.link[otherDir] = save.link[dir];
save.link[dir] = node;
}
node.red = true;
save.red = false;
return save;
}
Node doubleRotate(Node node, int dir) {
int otherDir = !dir;
node.link[otherDir] = singleRotate(node.link[otherDir], otherDir);
return singleRotate(node, dir);
}
bool isRed(Node node, Tag tag) {
return tag && node.red;
}
bool isRed(Node node, int dir) {
return isRed(node.link[dir], node.tag[dir]);
}
}
/++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++/
/++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++/
/++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++/
/++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++/
/++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++/
/++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++/
/++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++/
/++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++/
//module SingleRedBlackTree;
//import RedBlackTree;
import tango.util.collection.model.SortedValues;
/******************************************************************************
An Iterator that iterates over the elements of a RedBlackTree.
Params:
Node = the node type of the collection.
Remarks:
Iterates over the elements of a RedBlackTree in the direction specified in
the constructor. If the tree changes, iteration will stop even if there are
more elements to enumerate.
******************************************************************************/
class RBIterator(KeyType, Node, ParentIterator) : ParentIterator {
mixin RBIterMixins!(KeyType, Node, ParentIterator);
/****************************************************************
Apply a delegate to the rest of the elements in the enumeration.
Params:
dg = a delegate to apply to each element of the iteration.
Remarks:
Although the paramater to the delegate is an inout, changing
the value will not change the value in the underlying collection.
This is to maintain order in the collection and speed in the
enumeration.
Returns:
If the delegate returns a non-zero value, that value is returned.
Otherwise, when all elements have been enumerated, 0 is returned.
****************************************************************/
int opApply(int delegate(inout KeyType value) dg) {
while (more()) {
KeyType t = get();
int ret = dg(t);
if (ret) return ret;
}
return 0;
}
}
/*
*/
class Node(V) : public BasicNode!(V, Node!(V)) {
/*
*/
this(V v) {
super(v);
}
/*
*/
this () {
}
/*
*/
V value() {
return key;
}
}
/*
*/
template SingleRedBlackTreeTraitsMixin(V) {
alias V KeyTypeT;
alias V ValueTypeT;
alias Node!(V) NodeT;
alias RBIterator!(V, NodeT, Iterator!(V)) IteratorT;
alias RBIterator!(V, NodeT, GuardIterator!(V)) GuardIteratorT;
const bool DUAL_ITERATION = false;
}
/*
*/
abstract class SingleRedBlackTree(alias Traits) :
RedBlackTree!(Traits), SortedValues!(Traits.KeyTypeT) {
/*
*/
this() {}
/*
*/
this(ComparatorT cmp, Node tree, uint size) {
super(cmp, tree, size);
}
/*
*/
bool contains(ValueType v) {
return contains_(v);
}
/*
*/
ComparatorT comparator() {
return mComparator;
}
/*
*/
void add(KeyType obj) {
insert_(obj, new Node(obj), SINGLETON);
}
/*
*/
void replace(KeyType oldElement, KeyType newElement) {
uint size = count;
remove(oldElement);
if (count != size) {
add(newElement);
}
}
/*
*/
void replaceAll(KeyType oldElement, KeyType newElement) {
scope auto iter = new IteratorT(getFirstElement(oldElement));
while (iter.more()) {
KeyType v = iter.get();
if (v != oldElement)
break;
remove(v);
add(newElement);
}
}
/*
*/
void removeAll(KeyType obj) {
int startSize = 0;
while (startSize != count) {
startSize = count;
remove(obj);
}
}
/*
*/
ValueType take() {
checkIndex(0);
KeyType value = mRoot.key;
remove(value);
return value;
}
/*
*/
uint instances(ValueType obj) {
scope auto iter = new IteratorT(getFirstElement(obj));
uint count = 0;
while (iter.more()) {
ValueType t = iter.get();
if (mComparator(t, obj))
break;
count++;
}
return count;
}
}
/++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++/
/++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++/
/++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++/
/++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++/
/++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++/
/++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++/
/++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++/
/++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++/
/++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++/
/++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++/
//import SingleRedBlackTree;
import tango.util.collection.impl.BagCollection;
/*
*/
template BagTraits(V) {
mixin SingleRedBlackTreeTraitsMixin!(V);
alias BagCollection!(V) ParentCollectionT;
const bool SINGLETON = false;
}
/*
*/
class BagTree(V) : SingleRedBlackTree!(BagTraits!(V)) {
/*
*/
BagTree!(KeyType) duplicate() {
if (drained()) {
return new BagTree(mComparator, null, 0);
}
return new BagTree(mComparator, mRoot.copyOf(), count);
}
/*
*/
this() {}
/*
*/
protected this(ComparatorT c, Node tree, uint size) {
super(c, tree, size);
}
/*
*/
void addIf(KeyType obj) {
insert_(obj, new Node(obj), true);
}
}
/++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++/
/++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++/
/++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++/
/++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++/
/++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++/
/++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++/
/++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++/
//import SingleRedBlackTree;
import tango.util.collection.impl.SetCollection;
/*
*/
template SetTraits(V) {
mixin SingleRedBlackTreeTraits!(V);
alias SetCollection!(V) ParentCollectionT;
const bool SINGLETON = true;
}
/*
*/
class SetTree(V) : SingleRedBlackTree!(SetTraits!(V)) {
/*
*/
this(ComparatorT c) {
super(c, null, 0);
}
/*
*/
private this(ComparatorT cmp, Node tree, uint size) {
super(cmp, tree, size);
}
/*
*/
this() { }
/*
*/
SetTree!(KeyType) duplicate() {
if (drained()) {
return new SetTree(mComparator, null, 0);
}
return new SetTree(mComparator, mRoot.copyOf(), count);
}
}
/+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++/
/*
module MapTree;
import RedBlackTree;
*/
import tango.util.collection.impl.MapCollection,
tango.util.collection.model.SortedKeys,
tango.util.collection.model.Iterator,
tango.util.collection.model.GuardIterator;
class PairNode(K, V) : public BasicNode!(K, PairNode!(K, V)) {
V mValue;
this(K k, V v) {
super(k);
mValue = v;
}
this() {
super();
}
V value() {
return mValue;
}
}
class PairRedBlackIterator(KeyType, ValueType, Node, ParentIterator) : ParentIterator {
mixin RBIterMixins!(ValueType, Node, ParentIterator);
ValueType get() {
KeyType k;
return get(k);
}
ValueType get(inout KeyType key) {
assert(more());
ValueType data = mNode.mValue;
key = mNode.key;
advanceNode();
return data;
}
int opApply(int delegate(inout KeyType, inout ValueType) dg) {
while (more()) {
auto curNode = mNode;
KeyType t = curNode.key;
advanceNode();
int ret = dg(t, curNode.mValue);
if (ret) return ret;
}
return 0;
}
int opApply(int delegate(inout ValueType) dg) {
while (more()) {
auto curNode = mNode;
advanceNode();
int ret = dg(curNode.mValue);
if (ret) return ret;
}
return 0;
}
}
template MapTraits(K, V) {
alias K KeyTypeT;
alias V ValueTypeT;
alias PairNode!(K, V) NodeT;
alias PairRedBlackIterator!(K, V, NodeT, Iterator!(V)) IteratorT;
alias PairRedBlackIterator!(K, V, NodeT, PairIterator!(K, V)) GuardIteratorT;
alias MapCollection!(K, V) ParentCollectionT;
const bool SINGLETON = true;
const bool DUAL_ITERATION = true;
}
class MapTree(KeyType, V) : RedBlackTree!(MapTraits!(KeyType, V)), SortedKeys!(KeyType, V) {
this() {}
protected this(ComparatorT cmp, Node n, int size) {
super(cmp, n, size);
}
void add(KeyType k, ValueType v) {
uint startCount = count;
Node n = insert_(k, new Node(k, v));
if (count == startCount) {
n.mValue = v;
}
}
ComparatorT comparator() {
return mComparator;
}
void removeKey(KeyType k) {
return super.remove(k);
}
bool containsKey(KeyType k) {
return contains_(k);
}
GuardIteratorT keys() {
return elements;
}
uint instances(ValueType obj) {
scope auto iter = iterator();
uint count = 0;
while (iter.more()) {
ValueType v = iter.get();
if (v == obj) {
count++;
}
}
return count;
}
bool contains(ValueType obj) {
scope auto iter = iterator();
while (iter.more()) {
ValueType v = iter.get();
if (v == obj)
return true;
}
return false;
}
bool get(KeyType k, inout ValueType v) {
auto n = getFirstElement(k);
if (n is null)
return false;
v = n.mValue;
return true;
}
ValueType get(KeyType k) {
ValueType v;
if (!get(k, v))
checkIndex(count);
return v;
}
bool containsPair(KeyType k, ValueType v) {
auto n = getFirstElement(k);
return !(n is null || v == n.mValue) ;
}
bool keyOf(inout KeyType k, ValueType v) {
scope auto iter = iterator();
while (iter.more()) {
ValueType ov = iter.get(k);
if (ov == v)
return true;
}
return false;
}
MapTree!(KeyType, ValueType) duplicate() {
if (drained()) {
return new MapTree(mComparator, null, 0);
}
return new MapTree(mComparator, mRoot.copyOf(), count);
}
void remove(ValueType v) {
foreach (k, ov; this) {
if (ov == v) {
removeKey(k);
break;
}
}
}
void replacePair(KeyType key, ValueType oldValue, ValueType newValue) {
Node n = getFirstElement(key);
if (n is null)
return;
if (n.mValue == oldValue) {
n.mValue = newValue;
}
}
ValueType take() {
checkIndex(0);
ValueType v = mRoot.mValue;
removeKey(mRoot.key);
return v;
}
void removeAll(ValueType v) {
foreach (k, ov; iterator()) {
if (ov == v) {
removeKey(k);
}
}
}
void replace(ValueType oldElement, ValueType newElement) {
foreach (k, ov; this) {
if (ov == oldElement) {
ov = newElement;
break;
}
}
}
void replaceAll(ValueType oldElement, ValueType newElement) {
foreach (k, ov; this) {
if (ov == oldElement) {
ov = newElement;
}
}
}
}
import tango.io.Stdout;
int main() {
auto t = new MapTree!(int, double);
t.add(1, 4.1);
t.add(2, 4.1);
t.add(2, 5.1);
t[4] = 5;
t.removeAll(4.1);
double v;
foreach_reverse (i, j; t)
Stdout(i)(' ')(j).newline;
foreach (i; t)
Stdout(i).newline;
Stdout("Size =")(t.size).newline;
try {
foreach (j;t) {
t.remove(j);
Stdout("removing! Size=")(t.size).newline;
}
} catch {
Stdout("Caught!");
}
return 0;
}
grignaak
-
D,
pasted
on Jul 3: