DPaste - Paste #3476 - pastebin, online compiler and collaboration tool dedicated to D Programming Language

sortImpl slice problem example

Code

import std.algorithm;
import std.conv;
import std.exception;
import std.math;
import std.range;
import std.traits;
import std.string;

struct Iterator(T,S) {
	private T deque;
	private long idx;
	private long idxHigh;

package this(T deque) {
		this.deque = deque;
		this.idx = 0;
		this.idxHigh = this.deque.length() - 1;
	}

private this(T deque, const long idx, const long highIdx) {
		this.deque = deque;
		this.idx = idx;
		this.idxHigh = highIdx;
	}

public @property ref S front() {
		return this.deque[idx];
	}

public @property ref S back() {
		return this.deque[idxHigh];
	}

public @property bool empty() const {
		return this.idx > this.idxHigh || this.idxHigh < 0;
	}

public @property Iterator!(T,S) save() {
		return Iterator!(T,S)(this.deque, this.idx, this.idxHigh);
	}

public void popFront() {
		this.idx++;
	}
	
	public void popBack() {
		this.idxHigh--;
	}

public pure @property size_t length() const {
		return to!size_t((this.idxHigh - this.idx)+1);
	}

public Iterator!(T,S) opSlice(size_t l, size_t h) {
		return Iterator!(T,S)(this.deque, this.idx+l, this.idx+h);
	}

public ref S opIndex(size_t i) {
		return this.deque[this.idx+i];
	}
}

unittest { // check range for iterator properties
	assert(isForwardRange!(Iterator!(Deque!(int), int)));
	assert(isRandomAccessRange!(Iterator!(Deque!(int), int)));
	assert(isInputRange!(Iterator!(Deque!(int), int)));
}

/** The Deque class provides a random access container where appending and
 * removing takes amaorized O(1).
 *
 * Authors: Robert "burner" Schadek, rburners@gmail.com
 */
public class Deque(T) {
	private T[] data; /// the actual stored data
	private long head; /// insert first than move
	private long tail; /// move first than insert

/** Constructs a Deque of given type. Sets the head as well as tail index
	 * to zero. If the two indices point to the same element the Deque is
	 * empty.
	 *
	 * Params:
	 *	size = The intial size of the Deque to create.
	 *
	 * Examples:
	 * --------------
	 *	Deque!(int) de1 = new Deque!(int)();
	 *	Deque!(int) de2 = new Deque!(int)(1337);
	 * --------------
	 */
	public this(const size_t size = 16) {
		enforce(size, 
			xformat("The given size of %u is not bigger than 0." ~
			  "	This is invalid", size));
		this.data = new T[to!size_t(size)];
		this.head = 0;
		this.tail = 0;
	}

public this(T[] arr) {
		this(arr.length*2);
		assert(this.data.length == arr.length*2);
		foreach(it; arr) {
			this.pushBack(it);
		}
	}

public void pushBack(T toPush) {
		if((this.tail+1) % this.data.length == this.head) {
			this.growCapacity();
		}	
		this.tail = (this.tail+1) % this.data.length;
		this.data[to!size_t(this.tail)] = toPush;
	}

private void growCapacity() {
		T[] n = new T[this.data.length*2];
		assert(n !is null);

long idx = 0;
		foreach(it; this) {
			n[to!size_t(idx++)] = it;
		}

assert(this.data !is null);
		this.data = n;
		this.head = n.length-1;
		this.tail = idx-1;
	}

public pure ref T front() {
		if(this.head == this.tail) {
			throw new Exception(
				"Impossible to get front element of an empty Deque");
		}
		long head = (this.head+1) % this.data.length;
		return this.data[to!size_t(head)];
	}

public pure ref T back() {
		if(this.head == this.tail) {
			throw new Exception(
				"Impossible to get back element of an empty Deque");
		}
		return this.data[to!size_t(this.tail)];
	}

public pure T popFront() {
		if(this.head == this.tail) {
			throw new Exception(
				"Impossible to pop front element of an empty Deque");
		}
		this.head = (this.head+1) % this.data.length;
		T ret = this.data[to!size_t(this.head)];
		return ret;
	}

public pure T popBack() {
		if(this.head == this.tail) {
			throw new Exception(
				"Impossible to pop back element of an empty Deque");
		}

T ret = this.data[to!size_t(this.tail)];
		this.tail = this.tail-1;
		if(this.tail > this.data.length) {
			this.tail = this.data.length-1;
		}
		return ret;
	}

private void checkIdx(const long idx) const {
		if( (idx > 0 && idx >= this.length()) || this.empty() ||
				(idx < 0 &&  abs(idx) > this.length()) ) {
			throw new Exception(
				xformat("Deque.length(%u) given index %u", this.length, idx)
			);
		}
	}

private size_t getIdx(const long idx) const {
		this.checkIdx(idx);

if(idx >= 0) {
			return to!size_t((this.head + idx + 1) % this.data.length);
		} else {
			if(this.head < this.tail) {
				// plus one because the tail moves after insert
				return to!size_t(this.tail - abs(idx) + 1);
			} else {
				if(this.tail - abs(idx) + 1 < 0) {
					long tmp = abs(this.tail - abs(idx) +1);
					return to!size_t(this.data.length - tmp);
				} else {
					return to!size_t(this.tail - abs(idx) + 1);
				}

}
		}
		assert(false, "not reachable");
	}

public ref T opIndex(const long idx) {
		return this.data[to!size_t(this.getIdx(idx))];
	}

public Deque!(T) opIndexAssign(T value, const long idx) {
		long assignIdx = this.getIdx(idx);
		this.data[to!size_t(assignIdx)] = value;
		return this;
	}
	@property public pure bool empty() const nothrow {
		return this.head == this.tail;
	}

@property public pure size_t length() const { 
		if(this.empty()) {
			return 0;
		} else if(this.tail > this.head) {
			return to!size_t(this.tail-this.head);
		} else {
			return to!size_t(this.tail + (this.data.length-this.head));
		}
	}

public Deque!(T) save() {
		auto ret = new Deque!(T)();
		foreach(it;this) {
			ret.pushBack(it);
		}
		return ret;
	}

public Iterator!(Deque!(T), T) opSlice() {
		return Iterator!(Deque!(T), T)(this, head, tail-1);
	}

public Iterator!(Deque!(T), T) opSlice(size_t low, size_t high) {
		if(high > this.length) {
			throw new Exception(xformat("The given upper bound of" ~
				" %u is bigger than the Deque.length(%d)", high,
				this.length));
		}
		return Iterator!(Deque!(T), T)(this, low, high-1);
	}
}

unittest { // check range properties
	assert(isInputRange!(Deque!(int)));
	assert(isForwardRange!(Deque!(int)));
	assert(isRandomAccessRange!(Deque!(int)));
}

unittest { // sort test
	Deque!(int) de = new Deque!(int)([4,5,7,3,2,1,0]);
	// std.algorithm.sort!("a < b")(de.range()); This works as excepted
	std.algorithm.sort!("a < b")(de[]);
	for(size_t i = 0; i < de.length-1; i++) {
		assert(de[i] <= de[i+1]);
	}
}

void main() {
}

Paste info

Author: Guest

Views: 99

Private: no

Expires: Never

Uploaded: 25.11.12 16:22

Parent: #163a9600

Votes: 0

Compilation

Compiler: DMD 2.060

Pointer size: m64

Code

Paste info

Compilation

Actions

Confirm

Confirm