Skip to content

Instantly share code, notes, and snippets.

@JakobOvrum
Created November 8, 2014 04:27
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save JakobOvrum/f1738d31bb7ba7a46581 to your computer and use it in GitHub Desktop.
WIP, possibly abandoned, higher-order sorted container
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());
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment