hadean-std 0.1.6

//! A scalable distributed list datastructure.

use std::{mem,cmp,ops,ptr,iter,num,rc,vec};
use std::rc::Rc;
use std::cell::UnsafeCell;
use odds;

enum Shift {
	Left(isize),
	Right(isize)
}

struct Chunk<T> {
	array: [T; 1024],
	head: usize,
	tail: usize
}
impl<T> Chunk<T> {
	fn init(self_: &mut Self) { // self_ must be uninitialized
		unsafe{ptr::write(&mut self_.head, 0)};
		unsafe{ptr::write(&mut self_.tail, 0)};
	}
	// TODO: this is shitty code.
	fn replace<R,I>(&mut self, range: R, replacement: I) -> Shift where I: IntoIterator<Item=T>, I::IntoIter: ExactSizeIterator, R: odds::IndexRange {
		let mut replacement = replacement.into_iter();
		let replacement_len = replacement.size_hint().0;
		let length = self.tail - self.head; assert!(length <= self.array.len()); //if (length < 0) length += self.array.len();
		let r = range.start().unwrap_or(self.head)..range.end().unwrap_or(self.tail);
		assert!(self.head <= r.start && r.start <= r.end && r.end <= self.tail);// && !(r.start == r.end && replacement_len == 0));
		assert!(length - (r.end-r.start) + replacement_len <= self.array.len());
		{
			let mut start_a = r.start; if start_a >= self.array.len() { start_a -= self.array.len() };
			let end_a = cmp::min(start_a+(r.end-r.start), self.array.len());
			let start_b = 0;
			let end_b = (r.end-r.start)-(end_a-start_a);
			assert!(start_a <= end_a && end_a <= self.array.len() && start_b <= end_b && end_b <= self.array.len());
			for i in start_a..end_a {
				unsafe{ptr::drop_in_place(&mut self.array[i])};
			}
			for i in start_b..end_b {
				unsafe{ptr::drop_in_place(&mut self.array[i])};
			}
		}
		let d: isize = replacement_len as isize - (r.end-r.start) as isize;
		let shift = Shift::Right(d);
		// let shift = if self.tail-r.end > r.start-self.head { Shift::Left(d) } else { Shift::Right(d) };
		if d != 0 {
			if let Shift::Right(_) = shift {
				if d < 0 {
					let d = -d as usize;
					let mut from = r.end; if from >= self.array.len() { from -= self.array.len() };
					let mut to = if d < from { from - d } else { from + self.array.len() - d }; if to >= self.array.len() { to -= self.array.len() };
					assert!(from < self.array.len() && to < self.array.len());
					for _ in r.end..self.tail {
						unsafe{ptr::write(&mut self.array[to], ptr::read(&self.array[from]))};
						from += 1;
						to += 1;
						if from == self.array.len() {
							from = 0;
						}
						if to == self.array.len() {
							to = 0;
						}
					}
					assert!(from == self.tail % self.array.len());
					assert!(to == (self.tail-d) % self.array.len());
					self.tail -= d;
				} else {
					let d = d as usize;
					let mut from = self.tail; if from >= self.array.len() { from -= self.array.len() };
					let mut to = from + d; if to >= self.array.len() { to -= self.array.len() };
					assert!(from < self.array.len() && to < self.array.len());
					for _ in r.end..self.tail {
						if from == 0 {
							from = self.array.len();
						}
						if to == 0 {
							to = self.array.len();
						}
						from -= 1;
						to -= 1;
						unsafe{ptr::write(&mut self.array[to], ptr::read(&self.array[from]))};
					}
					assert!(from == r.end % self.array.len());
					assert!(to == (r.end+d) % self.array.len());
					self.tail += d;
				}
			} else {
				if d < 0 {
					let d = -d as usize;
					let mut from = r.start; if from >= self.array.len() { from -= self.array.len() };
					let mut to = from + d; if to >= self.array.len() { to -= self.array.len() };
					assert!(from < self.array.len() && to < self.array.len());
					for _ in self.head..r.start {
						if from == 0 {
							from = self.array.len();
						}
						if to == 0 {
							to = self.array.len();
						}
						from -= 1;
						to -= 1;
						unsafe{ptr::write(&mut self.array[to], ptr::read(&self.array[from]))};
					}
					assert!(from == self.head % self.array.len());
					assert!(to == (self.head+d) % self.array.len());
					self.head += d;
					if self.head >= self.array.len() {
						self.head -= self.array.len();
						self.tail -= self.array.len();
					}
				} else {
					let d = d as usize;
					let mut from = self.head;
					let mut to = if d < from { from - d } else { from + self.array.len() - d }; if to >= self.array.len() { to -= self.array.len() };
					assert!(from < self.array.len() && to < self.array.len());
					for _ in self.head..r.start {
						unsafe{ptr::write(&mut self.array[to], ptr::read(&self.array[from]))};
						from += 1;
						to += 1;
						if from == self.array.len() {
							from = 0;
						}
						if to == self.array.len() {
							to = 0;
						}
					}
					assert!(from == r.start % self.array.len());
					assert!(to == (r.start+self.array.len()-d) % self.array.len());
					if self.head < d {
						self.head += self.array.len();
						self.tail += self.array.len();
					}
					self.head -= d;
				}
			}
		}
		let mut start_a = if let Shift::Right(_) = shift { r.start } else { (r.start as isize + self.array.len() as isize - d) as usize % self.array.len() }; if start_a >= self.array.len() { start_a -= self.array.len() };
		let end_a = cmp::min(start_a+replacement_len, self.array.len());
		let start_b = 0;
		let end_b = replacement_len-(end_a-start_a);
		assert!(start_a <= end_a && end_a <= self.array.len() && start_b <= end_b && end_b <= self.array.len());
		for i in start_a..end_a {
			unsafe{ptr::write(&mut self.array[i], replacement.next().unwrap())};
		}
		for i in start_b..end_b {
			unsafe{ptr::write(&mut self.array[i], replacement.next().unwrap())};
		}
		assert!(replacement.next().is_none());
		assert!(self.head < self.array.len() && self.head <= self.tail && self.tail - self.head <= self.array.len() && self.tail < self.array.len()*2);
		shift
	}
	fn read<R>(&mut self, range: R, dst: &mut [T]) where R: odds::IndexRange, T: Copy {
		let r = range.start().unwrap_or(self.head)..range.end().unwrap_or(self.tail);
		assert!(self.head <= r.start && r.start <= r.end && r.end <= self.tail && self.tail - self.head <= self.array.len());
		assert!(r.end - r.start == dst.len());
		let x = r.start;
		for i in r {
			dst[i-x] = self.array[(i+self.head)%self.array.len()];
		}
	}
}


fn take<T,T1>(iter: &mut T, count: usize) -> vec::IntoIter<T1> where T: Iterator<Item=T1> {
	let mut x = Vec::with_capacity(count);
	for _ in 0..count {
		x.push(iter.next().unwrap());
	}
	x.into_iter()
}

enum FixupIndex<'a> {
	Left(&'a mut LeafIndex),
	Right(&'a mut LeafIndex)
}

/// A scalable distributed list datastructure.
/// Provides **O(1)** insertion and deletion.
/// Indexed by a `LeafIndex`, which can be incremented or decremented in **O(1)**.
/// `LeafIndex`s for each of the start and end of the list can be retreived in **O(1)**.
///
/// Here's an example:
///
/// ```
/// let mut leaf: Box<Leaf<u8>> = box unsafe{mem::uninitialized()};
/// Leaf::init(&mut leaf);
/// let mut replace_start_index = leaf.start();
/// let mut replace_end_index = replace_start_index.clone_right();
/// leaf.replace(&mut replace_start_index, &mut replace_end_index, &[1,2,3]);
/// leaf.increment(&mut replace_start_index);
/// leaf.increment(&mut replace_start_index);
/// leaf.replace(&mut replace_start_index, &mut replace_end_index, &[4,5,6]);
/// let mut start = leaf.start();
/// let mut end = leaf.end();
/// for num in leaf.read(&mut start, &mut end) {
/// 	println!("{}", num);
/// }
/// // prints: 1 2 4 5 6
/// ```

pub struct Leaf<T> {
	chunks: [(usize,usize,Chunk<T>); 102400],
	free: usize,
	frees: [usize; 102400],
	start: LeafIndex,
	end: LeafIndex,
	// len: usize
}
impl<T> Leaf<T> {
	/// Initialises a new, empty `Leaf<T>`. `self_` must be uninitialized. Returns the start and end `LeafIndex`es.
	pub fn init(self_: &mut Self) -> (LeafIndex, LeafIndex) { // self_ must be uninitialized
		let mut start = LeafIndex(Box::new(UnsafeCell::new(RawLeafIndex{prev:None,next:None,chunk:0,offset:0}))); // LeafIndex::new(None,None,0,0);
		let mut end = LeafIndex(Box::new(UnsafeCell::new(RawLeafIndex{prev:Some(start.get_mut()),next:None,chunk:0,offset:0}))); // LeafIndex::new(Some(&mut *start),None,0,0);
		start.get_mut().next = Some(end.get_mut() as *mut _);
		unsafe{ptr::write(&mut self_.free, 0)};
		unsafe{ptr::write(&mut self_.start, start)};
		unsafe{ptr::write(&mut self_.end, end)};
		// unsafe{ptr::write(&mut self_.len, 0)};
		for chunk in self_.chunks.iter_mut() {
			unsafe{ptr::write(chunk, (0,0,mem::uninitialized()))};
			Chunk::init(&mut chunk.2);
		}
		for (i,free) in self_.frees.iter_mut().enumerate() {
			unsafe{ptr::write(free, i+1)};
		}
		assert!(self_.alloc_chunk().unwrap() == 0);
		unsafe{ptr::write(&mut self_.chunks[0].0, self_.chunks.len())};
		unsafe{ptr::write(&mut self_.chunks[0].1, self_.chunks.len())};
		self_.assert();
		(self_.start.clone_right(), self_.end.clone_left())
	}
	fn alloc_chunk(&mut self) -> Option<usize> {
		let ret = self.free;
		if ret == self.chunks.len() {
			None
		} else {
			self.free = self.frees[ret];
			self.frees[ret] = self.chunks.len()+1;
			Some(ret)
		}
	}
	fn free_chunk(&mut self, chunk: usize) {
		assert!(self.frees[chunk] == self.chunks.len()+1);
		self.frees[chunk] = self.free;
		self.free = chunk;
	}
	fn fixup(&mut self, mut index: FixupIndex, shift: Shift) {
		match shift {
			Shift::Left(d) => {
				let mut cur = match &mut index {
					&mut FixupIndex::Left(ref mut index) => index.get_mut(),
					&mut FixupIndex::Right(ref mut index) => index.get_mut()
				};
				let chunk = cur.chunk;
				if let FixupIndex::Right(_) = index {
					cur = unsafe{mem::transmute(cur.prev.unwrap())};
				}
				while cur.chunk == chunk {
					assert!(&cur.chunk as *const usize != &chunk);
					cur.offset = (cur.offset as isize - d) as usize;
					match cur.prev {
						Some(x) => cur = unsafe{mem::transmute(x)},
						None => break
					};
				}
			}
			Shift::Right(d) => {
				let mut cur = match &mut index {
					&mut FixupIndex::Left(ref mut index) => index.get_mut(),
					&mut FixupIndex::Right(ref mut index) => index.get_mut()
				};
				let chunk = cur.chunk;
				if let FixupIndex::Left(_) = index {
					cur = unsafe{mem::transmute(cur.next.unwrap())};
				}
				while cur.chunk == chunk {
					assert!(&cur.chunk as *const usize != &chunk);
					cur.offset = (cur.offset as isize + d) as usize;
					match cur.next {
						Some(x) => cur = unsafe{mem::transmute(x)},
						None => break
					};
				}
			}
		}
	}
	/// Replace the elements between two `LeafIndex`es. Currently panics if the `Leaf` runs out of space.
	pub fn replace<I>(&mut self, start: &mut LeafIndex, end: &mut LeafIndex, replacement: I) where I: IntoIterator<Item=T>, I::IntoIter: ExactSizeIterator, T: Copy {
		assert!(&start.get().chunk as *const usize != &end.get().chunk);
		assert!(start.get().next.unwrap() as *const RawLeafIndex == end.get() as *const _);
		assert!(self.frees[start.get().chunk] == self.chunks.len()+1 && self.frees[end.get().chunk] == self.chunks.len()+1);
		assert!(self.chunks[start.get().chunk].2.head <= start.get().offset && start.get().offset <= self.chunks[start.get().chunk].2.tail && self.chunks[end.get().chunk].2.head <= end.get().offset && end.get().offset <= self.chunks[end.get().chunk].2.tail);
		self.assert();
		let mut replacement = replacement.into_iter();
		let mut replacement_len = replacement.size_hint().0;
		// assert!(!(start.get().chunk == end.get().chunk && start.get().offset == end.get().offset && replacement_len == 0));
		// println!("replace {}-{} => {}: {}.{}–{}.{}", {let self_start = self.start(); self.len(&self_start, start)}, {let self_start = self.start(); self.len(&self_start, end)}, replacement_len, start.get().chunk, start.get().offset, end.get().chunk, end.get().offset);
		let starting_len = self.len(&self.start, &self.end);
		let replacing_len = self.len(start, end);
		let ultimate_len = starting_len - replacing_len + replacement_len;
		if start.get().chunk == end.get().chunk {
			let rem_len = self.chunks[start.get().chunk].2.tail - end.get().offset;
			let del_len = self.chunks[start.get().chunk].2.tail - start.get().offset;
			let mut rem = Vec::with_capacity(rem_len); unsafe{rem.set_len(rem_len)};
			self.chunks[start.get().chunk].2.read(end.get().offset.., &mut *rem);
			let d = self.chunks[start.get().chunk].2.replace(start.get().offset.., iter::empty());
			if let Shift::Left(_) = d {
				self.fixup(FixupIndex::Left(start), d);
			}
			let new_chunk = self.alloc_chunk().expect("Leaf ran out of space");
			self.chunks[new_chunk].1 = self.chunks[start.get().chunk].1;
			self.chunks[start.get().chunk].1 = new_chunk;
			self.chunks[new_chunk].0 = start.get().chunk;
			self.chunks[new_chunk].2.replace(.., rem);
			if self.chunks[new_chunk].1 != self.chunks.len() {
				self.chunks[self.chunks[new_chunk].1].0 = new_chunk;
			}
			{
				let end_offset = end.get().offset;
				let mut index = end.get_mut();
				while index.chunk == start.get().chunk {
					assert!(&index.chunk as *const usize != &start.get().chunk);
					index.chunk = new_chunk;
					assert!(self.chunks[start.get().chunk].2.head <= start.get().offset && start.get().offset <= end_offset && end_offset <= index.offset && index.offset <= self.chunks[start.get().chunk].2.tail + del_len);
					index.offset -= end_offset;
					index.offset += self.chunks[new_chunk].2.head;
					assert!(self.chunks[new_chunk].2.head <= index.offset && index.offset <= self.chunks[new_chunk].2.tail);
					match index.next {
						Some(x) => index = unsafe{mem::transmute(x)},
						None => break
					};
				}
			}
			// println!("initial split");
		} else {
			let mut cur_chunk = self.chunks[start.get().chunk].1;
			while cur_chunk != end.get().chunk {
				let next_chunk = self.chunks[cur_chunk].1;
				self.free_chunk(cur_chunk);
				cur_chunk = next_chunk;
			}
			self.chunks[start.get().chunk].1 = end.get().chunk;
			self.chunks[end.get().chunk].0 = start.get().chunk;
			assert!(self.chunks[start.get().chunk].2.head <= start.get().offset && start.get().offset <= self.chunks[start.get().chunk].2.tail);
			let d = self.chunks[start.get().chunk].2.replace(start.get().offset.., iter::empty());
			self.fixup(FixupIndex::Left(start), d);
			assert!(self.chunks[start.get().chunk].2.head <= start.get().offset && start.get().offset <= self.chunks[start.get().chunk].2.tail);
			assert!(self.chunks[end.get().chunk].2.head <= end.get().offset && end.get().offset <= self.chunks[end.get().chunk].2.tail);
			let d = self.chunks[end.get().chunk].2.replace(..end.get().offset, iter::empty());
			self.fixup(FixupIndex::Right(end), d);
			assert!(self.chunks[end.get().chunk].2.head <= end.get().offset && end.get().offset <= self.chunks[end.get().chunk].2.tail);
			// println!("initial del");
		}
		let current_len = self.len(&self.start, &self.end);
		assert!(current_len == starting_len - replacing_len);
		self.assert();
		assert!(start.get().chunk != end.get().chunk);
		assert!(start.get().offset == self.chunks[start.get().chunk].2.tail && end.get().offset == self.chunks[end.get().chunk].2.head);
		let start_len = self.chunks[start.get().chunk].2.tail-self.chunks[start.get().chunk].2.head;
		let end_len = self.chunks[end.get().chunk].2.tail-self.chunks[end.get().chunk].2.head;
		let mut total = start_len + replacement_len + end_len;
		let mut chunks = cmp::max(dv_round_up(total, self.chunks[start.get().chunk].2.array.len()), 2);
		let first = cmp::min((total/chunks).saturating_sub(start_len), replacement_len);
		let x = self.chunks[start.get().chunk].2.tail;
		let d = self.chunks[start.get().chunk].2.replace(x.., take(&mut replacement, first)); replacement_len -= first;
		if let Shift::Left(_) = d {
			self.fixup(FixupIndex::Left(start), d);
		}
		assert!(start.get().offset + first == self.chunks[start.get().chunk].2.tail);
		total -= start_len + first;
		chunks -= 1;
		let last = cmp::min((total/chunks).saturating_sub(end_len), replacement_len);
		total -= end_len + last;
		chunks -= 1;
		let mut prev_chunk = start.get().chunk;
		for _ in 0..chunks {
			let chunk = self.alloc_chunk().expect("Leaf ran out of space");
			self.chunks[prev_chunk].1 = chunk;
			self.chunks[chunk].0 = prev_chunk;
			let len = total/chunks;
			self.chunks[chunk].2.replace(.., take(&mut replacement, len)); replacement_len -= len;
			total -= len;
			chunks -= 1;
			prev_chunk = chunk;
		}
		assert!(total == 0);
		self.chunks[prev_chunk].1 = end.get().chunk;
		self.chunks[end.get().chunk].0 = prev_chunk;
		let x = self.chunks[end.get().chunk].2.head;
		let d = self.chunks[end.get().chunk].2.replace(..x, take(&mut replacement, last)); replacement_len -= last;
		if let Shift::Right(_) = d {
			self.fixup(FixupIndex::Right(end), d);
		}
		assert!(end.get().offset - last == self.chunks[end.get().chunk].2.head);
		// println!("insert");
		assert!(replacement.next().is_none() && replacement_len == 0);
		assert!(self.len(&self.start, &self.end) == ultimate_len);
		self.assert();
	}
	/// Calculate the number of elements between two `LeafIndex`es.
	pub fn len(&self, start: &LeafIndex, end: &LeafIndex) -> usize {
		assert!(self.frees[start.get().chunk] == self.chunks.len()+1 && self.frees[end.get().chunk] == self.chunks.len()+1);
		assert!(self.chunks[start.get().chunk].2.head <= start.get().offset && start.get().offset <= self.chunks[start.get().chunk].2.tail && self.chunks[end.get().chunk].2.head <= end.get().offset && end.get().offset <= self.chunks[end.get().chunk].2.tail);
		let mut ret = 0;
		if start.get().chunk == end.get().chunk {
			ret += end.get().offset - start.get().offset;
		} else {
			ret += self.chunks[start.get().chunk].2.tail - start.get().offset;
			let mut chunk = self.chunks[start.get().chunk].1;
			while chunk != end.get().chunk {
				ret += self.chunks[chunk].2.tail - self.chunks[chunk].2.head;
				chunk = self.chunks[chunk].1;
			}
			ret += end.get().offset - self.chunks[end.get().chunk].2.head;
		}
		ret
	}
	/// Read the elements between two `LeafIndex`es into a `Vec<T>`.
	pub fn read(&mut self, start: &LeafIndex, end: &LeafIndex) -> Vec<T> where T: Copy {
		assert!(self.frees[start.get().chunk] == self.chunks.len()+1 && self.frees[end.get().chunk] == self.chunks.len()+1);
		assert!(self.chunks[start.get().chunk].2.head <= start.get().offset && start.get().offset <= self.chunks[start.get().chunk].2.tail && self.chunks[end.get().chunk].2.head <= end.get().offset && end.get().offset <= self.chunks[end.get().chunk].2.tail);
		let mut ret = Vec::new();
		if start.get().chunk == end.get().chunk {
			for i in start.get().offset..end.get().offset {
				ret.push(self.chunks[start.get().chunk].2.array[i%self.chunks[start.get().chunk].2.array.len()]);
			}
		} else {
			for i in start.get().offset..self.chunks[start.get().chunk].2.tail {
				ret.push(self.chunks[start.get().chunk].2.array[i%self.chunks[start.get().chunk].2.array.len()]);
			}
			let mut chunk = self.chunks[start.get().chunk].1;
			while chunk != end.get().chunk {
				for i in self.chunks[chunk].2.head..self.chunks[chunk].2.tail {
					ret.push(self.chunks[chunk].2.array[i%self.chunks[chunk].2.array.len()]);
				}
				chunk = self.chunks[chunk].1;
			}
			for i in self.chunks[end.get().chunk].2.head..end.get().offset {
				ret.push(self.chunks[end.get().chunk].2.array[i%self.chunks[end.get().chunk].2.array.len()]);
			}
		}
		ret
	}
	/// Increment a `LeafIndex` by one element.
	#[inline]
	pub fn increment(&mut self, index: &mut LeafIndex) {
		self.assert();
		assert!(self.chunks[index.get().chunk].2.head <= index.get().offset && index.get().offset <= self.chunks[index.get().chunk].2.tail);
		loop {
			if index.get().offset != self.chunks[index.get().chunk].2.tail {
				index.get_mut().offset += 1;
				break;
			} else {
				index.get_mut().chunk = self.chunks[index.get().chunk].1;
				index.get_mut().offset = self.chunks[index.get().chunk].2.head;
			}
		}
		self.assert();
	}
	/// Decrement a `LeafIndex` by one element.
	#[inline]
	pub fn decrement(&mut self, index: &mut LeafIndex) {
		self.assert();
		assert!(self.chunks[index.get().chunk].2.head <= index.get().offset && index.get().offset <= self.chunks[index.get().chunk].2.tail);
		loop {
			if index.get().offset == 0 {
				index.get_mut().chunk = self.chunks[index.get().chunk].0;
				index.get_mut().offset = self.chunks[index.get().chunk].2.tail;
			} else {
				index.get_mut().offset -= 1;
				break;
			}
		}
		self.assert();
	}
	fn assert(&self) {
		// println!("assert {} -> {}", self.start.get().chunk, self.end.get().chunk);
		let mut count = 0;
		for i in 0..self.chunks.len() {
			if self.frees[i] == self.chunks.len()+1 {
				count += 1;
			}
		}
		let mut prev_chunk = self.chunks.len();
		let mut chunk = self.start.get().chunk;
		let mut count2 = 1;
		loop {
			// println!("{} {} {}", prev_chunk, chunk, self.chunks[chunk].1);
			assert!(self.frees[chunk] == self.chunks.len()+1);
			assert!(self.chunks[chunk].0 == prev_chunk);
			if chunk == self.end.get().chunk {
				break;
			}
			prev_chunk = chunk;
			chunk = self.chunks[chunk].1;
			count2 += 1;
		}
		assert!(self.chunks[chunk].1 == self.chunks.len());
		assert!(count == count2);

		let mut prev_index = None;
		let mut index = self.start.get();
		loop {
			assert!(index.prev == prev_index);
			assert!(self.frees[index.chunk] == self.chunks.len()+1);
			assert!(self.chunks[index.chunk].2.head <= index.offset && index.offset <= self.chunks[index.chunk].2.tail);
			if index as *const _ == self.end.get() {
				break;
			}
			prev_index = Some(index as *const _ as *mut _);
			index = unsafe{mem::transmute(index.next.unwrap() as *const _)};
		}
		assert!(index.next == None);
		assert!(self.start.get().offset == self.chunks[self.start.get().chunk].2.head);
		assert!(self.end.get().offset == self.chunks[self.end.get().chunk].2.tail);
	}
}

pub struct LeafIndex(Box<UnsafeCell<RawLeafIndex>>);

impl LeafIndex {
	fn new<T>(leaf: &mut Leaf<T>, prev: *mut RawLeafIndex, next: *mut RawLeafIndex, chunk: usize, offset: usize) -> LeafIndex {
		let mut start_chunk = unsafe{&mut *prev}.chunk;
		let start_offset = unsafe{&mut *prev}.offset;
		let end_chunk = unsafe{&mut *next}.chunk;
		let end_offset = unsafe{&mut *next}.offset;
		if start_chunk == chunk {
			assert!(start_offset <= offset);
		}
		if end_chunk == chunk {
			assert!(offset <= end_offset);
		}
		let mut prev_chunk = leaf.chunks[start_chunk].0;
		let mut got = false;
		loop {
			assert!(leaf.frees[start_chunk] == leaf.chunks.len()+1);
			assert!(leaf.chunks[start_chunk].0 == prev_chunk);
			if start_chunk == chunk {
				got = true;
			}
			if start_chunk == end_chunk {
				break;
			}
			prev_chunk = start_chunk;
			start_chunk = leaf.chunks[start_chunk].1;
		}
		assert!(leaf.chunks[chunk].1 == leaf.chunks.len());
		assert!(got);
		Self::new_(prev, next, chunk, offset)
	}
	fn new_(prev: *mut RawLeafIndex, next: *mut RawLeafIndex, chunk: usize, offset: usize) -> LeafIndex {
		assert!(unsafe{&mut *prev}.next == Some(next) && unsafe{&mut *next}.prev == Some(prev));
		let mut ret = LeafIndex(Box::new(UnsafeCell::new(RawLeafIndex{prev:Some(prev),next:Some(next),chunk:chunk,offset:offset})));
		if let Some(prev) = ret.get().prev {
			unsafe{&mut *prev}.next = Some(ret.get_mut());
		}
		if let Some(next) = ret.get().next {
			unsafe{&mut *next}.prev = Some(ret.get_mut());
		}
		ret
	}
	pub fn clone_left(&mut self) -> Self {
		LeafIndex::new_(self.get().prev.unwrap(), self.get_mut(), self.get().chunk, self.get().offset)
	}
	pub fn clone_right(&mut self) -> Self {
		LeafIndex::new_(self.get_mut(), self.get().next.unwrap(), self.get().chunk, self.get().offset)
	}
	fn get(&self) -> &RawLeafIndex {
		unsafe{&*self.0.get()}
	}
	fn get_mut(&mut self) -> &mut RawLeafIndex {
		unsafe{&mut *self.0.get()}
	}
}
impl PartialEq<LeafIndex> for LeafIndex {
	fn eq(&self, other: &Self) -> bool {
		self.get() == other.get()
	}
}
impl Eq for LeafIndex {}

struct RawLeafIndex {
	prev: Option<*mut RawLeafIndex>,
	next: Option<*mut RawLeafIndex>,
	chunk: usize,
	offset: usize
}
impl Drop for RawLeafIndex {
	fn drop(&mut self) {
		if let Some(prev) = self.prev {
			unsafe{&mut *prev}.next = self.next;
		}
		if let Some(next) = self.next {
			unsafe{&mut *next}.prev = self.prev;
		}
	}
}
impl PartialEq<RawLeafIndex> for RawLeafIndex {
	fn eq(&self, other: &Self) -> bool {
		self.chunk == other.chunk && self.offset == other.offset
	}
}
impl Eq for RawLeafIndex {}

#[cfg(test)]
mod tests {
	use std::{mem};
	use rand;
    use super::*;
    use super::Chunk;
	use rand::Rng;
	use rand::SeedableRng;
	use odds::vec::VecExt;
	trait ToHex {
		fn to_hex(&self) -> String;
	}
	const CHARS: &'static [u8] = b"0123456789abcdef";
	impl ToHex for [u8] {
		fn to_hex(&self) -> String {
			let mut v = Vec::with_capacity(self.len() * 3);
			for &byte in self {
				v.push(CHARS[(byte >> 4) as usize]);
				v.push(CHARS[(byte & 0xf) as usize]);
				v.push(b' ');
			}
			unsafe{String::from_utf8_unchecked(v)}
		}
	}
	#[test]
	#[ignore]
	fn list() {
		let mut leaf: Box<Leaf<u8>> = box unsafe{mem::uninitialized()};
		Leaf::init(&mut leaf);
		let mut rng = rand::StdRng::new().unwrap();
		// let mut rng = rand::XorShiftRng::from_seed([1,2,3,4]);
		let a = 10000;
		let mut vec: Vec<u8> = Vec::new();
		let mut buf: Vec<u8> = Vec::with_capacity(a);
		let mut len = 0;
		for i in 0..1000000 {
			println!("{}", i);
			let mut replace_start_index = leaf.start_mut().clone_right();
			let mut replace_end_index = replace_start_index.clone_right();
			let replace_start = rng.gen_range(0, len+1);
			let replace_end = rng.gen_range(replace_start, len+1);
			let replace_len = rng.gen_range(0, a+1);
			// println!("{}-{} -> {}", replace_start, replace_end, replace_len);
			for _ in 0..replace_end {
				leaf.increment(&mut replace_end_index);
			}
			for _ in 0..replace_start {
				leaf.increment(&mut replace_start_index);
			}
			unsafe{buf.set_len(replace_len)};
			rng.fill_bytes(unsafe{mem::transmute(&mut *buf)});
			leaf.replace(&mut replace_start_index, &mut replace_end_index, buf.iter().map(|&x|x)); // http://doc.rust-lang.org/std/iter/trait.Iterator.html#method.cloned
			len -= replace_end-replace_start;
			len += replace_len;
			vec.splice(replace_start..replace_end, buf.drain(..));
			assert!(len == vec.len());
			let leaf_start = leaf.start_mut().clone_right();
			let leaf_end = leaf.end_mut().clone_left();
			let as_vec = leaf.read(&leaf_start, &leaf_end);
			assert!(as_vec == vec);
		}
	}

	#[test]
	#[ignore]
	fn leaf_chunk_allocator() {
		let mut rng = rand::StdRng::new().unwrap();
		let mut leaf: Box<Leaf<u8>> = box unsafe{mem::uninitialized()};
		Leaf::init(&mut leaf);
		let chunks_len = leaf.chunks.len();
		leaf.free_chunk(0);
		for _ in 0..100000 {
			for _ in 0..chunks_len {
				leaf.alloc_chunk().unwrap();
			}
			assert!(leaf.alloc_chunk().is_none());
			let flip = rng.gen_weighted_bool(2);
			for j in 0..chunks_len {
				leaf.free_chunk(if flip { j } else { chunks_len-1 - j });
			}
		}
	}

	#[test]
	#[ignore]
	fn chunk_replace() {
		let mut rng = rand::StdRng::new().unwrap();
		let mut chunk: Box<Chunk<u32>> = box unsafe{mem::uninitialized()};
		Chunk::init(&mut chunk);
		let mut vec: Vec<u32> = Vec::new();
		let mut buf: Vec<u32> = Vec::with_capacity(chunk.array.len());
		for _ in 0..1000000 { assert!(buf.capacity() == chunk.array.len());
			let chunk_len = chunk.tail-chunk.head;
			let start = rng.gen_range(0, chunk_len+1);
			let end = rng.gen_range(start, chunk_len+1);
			let length = chunk.array.len()-chunk_len+(end-start);
			let length = rng.gen_range(0, length+1);
			// println!("{}: {}-{} -> {}", vec.to_hex(), start, end, length);
			unsafe{buf.set_len(length)};
			rng.fill_bytes(unsafe{mem::transmute(&mut *buf)});
			let x = chunk.head;
			chunk.replace(x+start..x+end, buf.iter().map(|&x|x)); // http://doc.rust-lang.org/std/iter/trait.Iterator.html#method.cloned
			vec.splice(start..end, buf.drain(..));
			assert!(chunk.tail-chunk.head == vec.len());
			for i in 0..vec.len() {
				// if chunk[i] != vec[i] {
				// 	println!("{}", vec.to_hex());
				// 	let mut v = Vec::with_capacity(vec.len() * 3);
				// 	for j in 0..vec.len() {
				// 		let byte = chunk[j];
				// 		v.push(CHARS[(byte >> 4) as usize]);
				// 		v.push(CHARS[(byte & 0xf) as usize]);
				// 		v.push(b' ');
				// 	}
				// 	println!("{}", unsafe{String::from_utf8_unchecked(v)});
				// }
				assert!(chunk.array[(i+chunk.head)%chunk.array.len()] == vec[i]);
			}
			// println!("");
		}
	}
}

fn dv_round_up<T: Copy + num::One + ops::Add<Output = T> + ops::Sub<Output = T> + ops::Div<Output = T>>(lhs: T, rhs: T) -> T {
	(lhs + rhs - T::one()) / rhs
}

/*

How to stop dropping of (uninitialised) members of struct on struct drop?

*/