Insertion order stable associative storage

magic_tree.d

import std.container.rbtree;

struct Node
{
	int opCmp(ref const Node other) const
	{
		if (other.key > this.key)
			return -1;
		if (other.key < this.key)
			return 1;
		if (other.insertOrder > this.insertOrder)
			return -1;
		return other.insertOrder < this.insertOrder;
	}

	int opCmp(int k)
	{
		if (k < key)
			return -1;
		return k > key;
	}

	this(int* insertOrder, int key, int value)
	{
		this.key = key;
		this.value = value;
		this.insertOrder = *insertOrder;
		*insertOrder = *insertOrder + 1;
	}

	int key;
	int insertOrder;
	int value;
}

void main(string[] args)
{
	import std.stdio:writeln;
	import std.format:format;
	import std.algorithm:map;
	int counter;
	auto t = new RedBlackTree!(Node, "a < b", true);
	t.insert(Node(&counter, 10, 100));
	t.insert(Node(&counter, 5, 101));
	t.insert(Node(&counter, 5, 102));
	t.insert(Node(&counter, 5, 104));
	t.insert(Node(&counter, 5, 105));
	t.insert(Node(&counter, 20, 106));
	t.insert(Node(&counter, 1, 107));
	writeln(t[].map!(a => "order: %d, key: %d, value: %d".format(a.insertOrder, a.key, a.value)));
}