WIP, possibly abandoned, higher-order sorted container

sortedcontainer.d

module std.container.sortedcontainer;

import std.stdio;

import std.array : empty, front, popFront;
import std.range : ElementType, SortedRange, assumeSorted, hasAssignableElements, isInputRange, isRandomAccessRange;

// SortedRange should really support this
private auto internalLowerBound(Range, alias pred, T)(SortedRange!(Range, pred) range, T x)
	if(is(T : ElementType!Range))
{
	static if(isRandomAccessRange!Range)
	{
		return range.lowerBound(x);
	}
	else
	{
		import std.algorithm : countUntil;
		import std.functional : binaryFun, not;
		import std.range : takeExactly;
		size_t pivot = 0;
		auto r = range.save;
		while(!r.empty && binaryFun!pred(r.front, x))
		{
			++pivot;
			r.popFront();
		}
		return range.release().takeExactly(pivot).assumeSorted!pred();
	}
}

// Ditto
private auto internalUpperBound(Range, alias pred, T)(SortedRange!(Range, pred) range, T x)
	if(is(T : ElementType!Range))
{
	static if(isRandomAccessRange!Range)
	{
		return range.upperBound(x);
	}
	else
	{
		import std.algorithm : find;
		import std.functional : binaryFun, not;
		return range.find!(not!(binaryFun!pred))(x).find!((a, b) => a != b)(x);
	}
}

// Ditto
private auto internalEqualRange(Range, alias pred, T)(SortedRange!(Range, pred) range, T x)
	if(is(T : ElementType!Range))
{
	static if(isRandomAccessRange!Range)
	{
		return range.equalRange(x);
	}
	else
	{
		import std.algorithm : find;
		import std.functional : not;
		import std.range : takeExactly;
		auto equalRange = range.release().find(x);
		size_t pivot = 0;
		auto r = equalRange.save;
		while(!r.empty && r.front == x)
		{
			++pivot;
			r.popFront();
		}
		return equalRange.takeExactly(pivot).assumeSorted!pred();
	}
}

// assumes c[], c.front and c.empty are the fundamental container primitives
/**
 * Generic sorted container.
 *
 * Elements remain sorted at all times, also after insertion
 * and removal actions. The underlying container can be any other container.
 * This container provides insertion, removal and search algorithms depending
 * on the capabilities of the underlying container.
 *
 * This container's range type is guaranteed to be a $(XREF range, SortedRange).
 *
 * Note:
 * As with $(D SortedRange), as a concession to practicality, this container provides
 * mutable access to elements. If elements are changed in ways that break
 * the sortedness of the container, $(D SortedContainer) will behave erratically.
 *
 * Params:
 *   Container = underlying storage container
 *   pred = order of elements
 * See_Also:
 *   $(XREF range, SortedRange). See $(XREF algorithm, sort) for how $(D pred) decides ordering.
 */
struct SortedContainer(Container, alias pred = "a < b")
	if(isInputRange!(typeof((Container.init)[])) && hasAssignableElements!(typeof((Container.init)[])))
{
	import std.functional : binaryFun;
	import std.range;
	import std.traits : isDynamicArray;

	private:
	Container container;

	this()(Container container) // For .dup
	{
		this.container = container;
	}

	alias predFun = binaryFun!pred;
	enum hasInsertFront = __traits(hasMember, Container, "insertFront");
	enum hasInsertBack = __traits(hasMember, Container, "hasInsertBack");
	enum hasInsertAfter = __traits(hasMember, Container, "insertAfter");
	enum hasInsertBefore = __traits(hasMember, Container, "hasInsertBefore");

	public:
	/// Range type of this container.
	/// See_Also: $(XREF range, SortedRange)
	static if(isDynamicArray!Container)
		alias Range = SortedRange!(Container, pred);
	else
		alias Range = SortedRange!(Container.Range, pred);

	/**
	 * Construct the sorted container from a sorted range of items.
	 * Complexity: $(BIGOH n$(SUB range)).
	 */
	this(Stuff)(SortedRange!(Stuff, pred) range)
		if(is(ElementType!Stuff : ElementType!Container))
	{
		import std.container : make;
		this.container = make!Container(range);
	}

	static if(isRandomAccessRange!Range)
	{
		private void construct(R)(R range)
		{
			import std.algorithm : sort, SwapStrategy;

			static if(isDynamicArray!Container)
			{
				import std.array : array;
				this.container = array(range);
			}
			else
			{
				import std.container : make;
				this.container = make!Container(range);
			}

			sort!(pred, SwapStrategy.stable)(this.container[]);
		}

		/**
	 	 * Construct the sorted container from an unsorted range of items.
	 	 * Complexity: $(BIGOH n$(SUB range) + log n$(SUB range)).
	 	 */
		this(R)(R range)
			if(isInputRange!R && is(ElementType!R : ElementType!Container))
		{
			construct(range);
		}

		/// Ditto
		this(ElementType!Range[] items...)
		{
			construct(items);
		}

		/**
	 	 * Construct the sorted container from the elements of another container.
	 	 *
	 	 * Complexity depends on the capabilities of $(D otherContainer)'s range type.
	 	 */
		this(OtherContainer)(OtherContainer otherContainer)
			if(!isInputRange!OtherContainer && isInputRange!(typeof(otherContainer[]))
				&& is(ElementType!(typeof(otherContainer[])) : ElementType!Container))
		{
			this(otherContainer[]);
		}
	}
	else
	{
		this(OtherContainer)(OtherContainer otherContainer)
			if(!isInputRange!OtherContainer &&
				is(OtherContainer.Range : SortedRange!(R, pred), R) &&
				is(ElementType!R : ElementType!Container))
		{
			this(otherContainer[]);
		}
	}

	/// Acquire a sorted range over the elements in the sorted container.
	Range opSlice()
	{
		return Range(container[]);
	}

	static if(hasSlicing!Container)
	{
		/// Acquire a sorted range over a subset of the elements in the sorted container.
		Range opSlice(size_t from, size_t to)
		{
			return Range(container[from .. to]);
		}
	}

	static if(isDynamicArray!Container)
	{
		void insert(ElementType!Container item)
		{
			import std.array : insertInPlace;
			auto upperBound = this[].upperBound(item);
			insertInPlace(container, container.length - upperBound.length, item);
		}

		void insert(Stuff)(Stuff items)
			if(isInputRange!Stuff && is(ElementType!Stuff : ElementType!Container))
		{
			foreach(ref item; items)
				insert(item);
		}

		void insert(Stuff)(SortedRange!(Stuff, pred) items)
			if(is(ElementType!Stuff : ElementType!Container))
		{
			import std.array : insertInPlace;
			auto upper = this[];
			while(!items.empty)
			{
				upper = upper.upperBound(items.front);
				if(upper.empty)
				{
					insertInPlace(container, container.length - 1, items);
					break;
				}

				auto split = items.findSplitBefore!(not!pred)(only(upper.front));
				insertInPlace(container, container.length - upperBound.length, split[0]);
				items = split[1];
			}
		}

		alias linearInsert = insert;
	}
	else static if(isRandomAccessRange!Range)
	{
		void insert(ElementType!Container item)
		{
			auto upperBound = this[].upperBound(item).release();

			static if(hasInsertFront)
			{
				if(upperBound.empty)
				{
					container.insertFront(item);
				}
			}

			static if(hasInsertBefore)
				container.insertBefore(upperBound, item);
			{
				container.insertBack(container.back);

				auto prev = upperBound.moveFront;
				upperBound.front = x;
				upperBound.popFront();
				for(; !upperBound.empty; upperBound.popFront())
				{
					auto tmp = upperBound.moveFront;
					upperBound.front = prev;
					prev = tmp;
				}
			}
		}

		void insert(Stuff)(Stuff items)
			if(isInputRange!Stuff && is(ElementType!Stuff : ElementType!Container))
		{
			foreach(ref item; items)
				insert(item);
		}

		void insert(Stuff)(SortedRange!(Stuff, pred) items)
			if(is(ElementType!Stuff : ElementType!Container))
		{
			auto upper = this[];

			static if(hasInsertFront)
			{
				if(upper.empty)
				{
					container.insertFront(items);
					return;
				}
			}

			while(!items.empty)
			{
				upper = upper.upperBound(items.front);
				if(upper.empty)
				{
					container.insertBack(items);
					break;
				}

				auto split = items.findSplitBefore!(not!pred)(only(upper.front));

				static if(hasInsertBefore)
					container.insertBefore(upper, split[0]);
				{
					container.insertBack(container.back);

					auto prev = upperBound.moveFront;
					upperBound.front = x;
					upperBound.popFront();
					for(; !upperBound.empty; upperBound.popFront())
					{
						auto tmp = upperBound.moveFront;
						upperBound.front = prev;
						prev = tmp;
					}
				}

				items = split[1];
			}
		}

		alias linearInsert = insert;
	}
	else
	{
		/**
		 * Insert a single item into the sorted container.
		 * Complexity: $(BIGOH n$(SUB this)).
		 */
		void linearInsert(ElementType!Container item)
		{
			auto r = container[];

			if(r.empty || predFun(item, r.front))
			{
				container.insertFront(item);
				return;
			}

			Container.Range insertionPoint;
			do
			{
				insertionPoint = r.save;
				r.popFront();
			}
			while(!r.empty && (predFun(r.front, item) || r.front == item));

			container.insertAfter(insertionPoint.take(1), item);
		}

		/**
		 * Merge a list of sorted items into the sorted container.
		 * Complexity: $(BIGOH n$(SUB this) + n$(SUB items)).
		 */
		void linearInsert(Stuff)(SortedRange!(Stuff, pred) items)
			if(is(ElementType!Stuff : ElementType!Container))
		{
			import std.functional : not;

			auto r = container[];
			if(r.empty)
			{
				container.insertFront(items);
				return;
			}

			auto split = items.findSplitBefore!(not!pred)(only(r.front));
			if(!split[0].empty)
			{
				writeln("Inserting ", split[0], " at the front");
				container.insertFront(split[0]);
				items = split[1];
			}

			while(!items.empty)
			{
				Container.Range insertionPoint;
				do
				{
					insertionPoint = r.save;
					r.popFront();
					if(r.empty)
					{
						writeln("Inserting ", items, " at the back, after ", insertionPoint.take(1));
						container.insertAfter(insertionPoint.take(1), items);
						return;
					}
				}
				while(predFun(r.front, items.front) || r.front == items.front);

				split = items.findSplitBefore!(not!pred)(only(r.front));

				writeln("Inserting ", split[0], " between ", insertionPoint.front, " and ", r.front);

				container.stableInsertAfter(insertionPoint.take(1), split[0]);
				items = split[1];
			}
		}
	}

	static if(isDynamicArray!Container)
	{
		void remove(ElementType!Container x)
		{
			auto equalRange = internalEqualRange(x);
			if(!equalRange.empty)
			{
				import std.algorithm : remove;
				container = remove(container, (equalRange.ptr - container.ptr) + equalRange.length - 1);
			}
		}

		alias linearRemove = remove;

		void removeAll(ElementType!Container x)
		{
			import std.algorithm : bringToFront;
			auto equalRange = internalEqualRange(x);
			if(!equalRange.empty)
			{
				auto back = (equalRange.ptr + equalRange.length)[0 .. (container.ptr + container.length) - equalRange.ptr];
				bringToFront(equalRange, back);
				container = container[0 .. container.length - equalRange.length];
			}
		}

		alias linearRemoveAll = removeAll;
	}

	static if(__traits(hasMember, Container, "remove"))
	{
		void remove(ElementType!Container x)
		{
			import std.range : takeExactly;
			auto equalRange = this[].internalEqualRange(x).release();
			if(!equalRange.empty)
				container.remove(takeExactly(equalRange, 1));
		}

		void removeAll(ElementType!Container x)
		{
			auto equalRange = internalEqualRange(x);
			if(!equalRange.empty)
				container.remove(equalRange);
		}
	}

	static if(__traits(hasMember, Container, "linearRemove"))
	{
		void linearRemove(ElementType!Container x)
		{
			import std.range : takeExactly;
			auto equalRange = this[].internalEqualRange(x).release();
			if(!equalRange.empty)
				container.linearRemove(takeExactly(equalRange, 1));
		}

		void linearRemoveAll(ElementType!Container x)
		{
			auto equalRange = this[].internalEqualRange(x).release();
			if(!equalRange.empty)
				container.linearRemove(equalRange);
		}
	}

	/// Forwarded container primitives.
	bool empty() @property
	{
		return container.empty;
	}

	/// Ditto
	auto ref front() @property
	{
		return container.front;
	}

	static if(__traits(__compiles, Container.init.front = ElementType!Container.init)
	{
		/// Ditto
		void front(ElementType!Container x) @property
		{
			container.front = x;
		}
	}

	static if(__traits(compiles, Container.init.back))
	{
		/// Ditto
		auto ref back() @property
		{
			return container.back;
		}

		static if(__traits(__compiles, Container.init.back = ElementType!Container.init)
		{
			/// Ditto
			void back(ElementType!Container x) @property
			{
				container.back = x;
			}
		}
	}

	static if(hasLength!Container)
	{
		/// Ditto
		auto length() @property
		{
			return container.length;
		}

		/// Ditto
		alias opDollar = length;
	}

	static if(__traits(compiles, container[size_t.init]))
	{
		/// Ditto
		auto ref opIndex(size_t i)
		{
			return container[i];
		}

		static if(__traits(compiles, container[size_t.init] = ElementType!Container.init))
		{
			/// Ditto
			void opIndexAssign(ElementType!Container x, size_t i)
			{
				container[i] = x;
			}
		}
	}

	static if(__traits(compiles, container.reserve(size_t.init)))
	{
		/// Ditto
		void reserve(size_t n)
		{
			container.reserve(n);
		}
	}

	static if(__traits(compiles, container.capacity))
	{
		/// Ditto
		auto capacity() @property
		{
			return container.capacity;
		}
	}

	static if(__traits(compiles, container.dup))
	{
		/// Ditto
		SortedContainer dup() @property
		{
			return SortedContainer(container.dup);
		}
	}

	static if(isRandomAccessRange!Range)
	{
		/// Ditto
		bool opBinaryRight(string op : "in")(ElementType!Container x)
		{
			return this[].contains(x);
		}

		/// Ditto
		auto lowerBound(ElementType!Container x)
		{
			return this[].lowerBound(x);
		}

		/// Ditto
		auto upperBound(ElementType!Container x)
		{
			return this[].upperBound(x);
		}

		/// Ditto
		auto equalRange(ElementType!Container x)
		{
			return this[].equalRange(x);
		}
	}
}

/// Sorted array:
unittest
{
	// Sorted containers can be constructed from an unsorted list of items
	// as long as the underlying container supports random access.
	auto sortedArray = make!(SortedContainer!(Array!int))(3, 1, 9, 4);

	// Elements are kept sorted at all times.
	assert(sortedArray[].equal([1, 3, 4, 9]));

	// Logarithmic insertion is provided when the underlying container supports it.
	sortedArray.insert(2);
	sortedArray.insert([6, 5]);

	// SortedContainer.insert specializes for faster insertion of sorted ranges.
	sortedArray.insert([7, 8].assumeSorted());

	assert(sortedArray[].equal([1, 2, 3, 4, 5, 6, 7, 8, 9]));

	// Random access containers support the logarithmic container search algorithms.
	assert(3 in sortedArray);
	assert(10 !in sortedArray);
	assert(sortedArray.upperBound(5).equal([6, 7, 8, 9]));

	// Random access containers support logarithmic removal.
	sortedArray.remove(1);
	sortedArray.remove([3, 2]);
	sortedArray.remove([4, 5].assumeSorted());

	assert(sortedArray[].equal([6, 7, 8, 9]));
}

/// Sorted singly linked list:
unittest
{
	// When the underlying container does not support random access,
	// the sorted container must be constructed from a sorted range.
	auto sortedList = make!(SortedContainer!(SList!int))([1, 3, 4, 7].assumeSorted());

	// Linear insertion of items is supported.
	sortedList.linearInsert(2);

	// Inserting a range of items is supported in linear time if the range is sorted.
	sortedList.linearInsert([5, 6, 7, 8].assumeSorted());

	assert(sortedList[].equal([1, 2, 3, 4, 5, 6, 7, 8, 9]));

	// Linear removal is supported as long as the input is sorted.
	sortedList.linearRemove(1);
	sortedList.linearRemove([2, 3, 4, 5].assumeSorted());

	assert(sortedList.equal([6, 7, 8, 9]));
}

unittest
{
	auto list = make!(SortedContainer!(SList!int))();
}

void main()
{
	import std.algorithm : equal, isSorted, sort;
	import std.container : Array, SList, make;
	import std.typetuple : TypeTuple;
	import std.range : assumeSorted, take;

	static immutable pred = "b < a";
	static cheatsheet = [3, 5, 1, 4, 4, 2, 19, 20, 21, 15, 16, 16, 18, 19, 20, 28];

	sort!pred(cheatsheet);
	assert(isSorted!pred(cheatsheet));

	void test(C)()
	{
		auto sorted = make!(SortedContainer!(C, pred))();
		assert(sorted.empty);
		sorted.insert(3);
		assert(sorted[].isSorted!pred());
		sorted.insert(5);
		assert(sorted[].isSorted!pred());
		sorted.insert(1);
		assert(sorted[].isSorted!pred());
		sorted.insert(4);
		assert(sorted[].isSorted!pred());
		sorted.insert(4);
		assert(sorted[].isSorted!pred());
		sorted.insert(2);
		assert(sorted[].isSorted!pred());
		sorted.insert(19);
		assert(sorted[].isSorted!pred());
		sorted.insert(20);
		assert(sorted[].isSorted!pred());
		sorted.insert(21);
		assert(sorted[].isSorted!pred());
		sorted.insert(15);
		assert(sorted[].isSorted!pred());
		sorted.insert(16);
		assert(sorted[].isSorted!pred());
		sorted.insert(16);
		assert(sorted[].isSorted!pred());

		auto a = sort!pred([18, 19, 20, 28]);
		writeln("Inserting ", a, " into ", sorted[]);
		sorted.linearInsert(a);
		assert(sorted[].equal(cheatsheet));
		foreach(i; sorted[])
			write(i, " ");
		writeln();
	}

/+
	alias Containers = TypeTuple!(/*Array!int,*/ SList!int/*, int[]*/);
	foreach(C; Containers)
		test!C();
+/


	auto container = SortedContainer!(SList!int)([1, 2, 2, 2, 2, 11].assumeSorted());
	auto stuff = [2, 3, 13].assumeSorted();
	writeln("Inserting ", stuff, " into ", container[]);
	container.linearInsert(stuff);
	writeln("Result: ", container[]);
	assert(container[].isSorted());

	ubyte stuff2 = 4;
	writeln("Inserting ", stuff2, " into ", container[]);
	container.linearInsert(stuff2);
	writeln("Result: ", container[]);
	assert(container[].isSorted());
}