Add `package slice`; New `sort.Interface` with default `sort.sort`

3 files changed, 708 insertions, 0 deletions

diff --git a/core/slice/ptr.odin b/core/slice/ptr.odin
new file mode 100644
index 000000000..defd144fa
--- /dev/null
+++ b/core/slice/ptr.odin
@@ -0,0 +1,72 @@
+package slice
+
+import "core:mem"
+
+ptr_add :: proc(p: $P/^$T, x: int) -> ^T {
+	return (^T)(uintptr(p) + size_of(T)*x);
+}
+ptr_sub :: proc(p: $P/^$T, x: int) -> ^T {
+	return inline ptr_add(p, -x);
+}
+
+ptr_swap_non_overlapping :: proc(x, y: rawptr, len: int) {
+	if len <= 0 {
+		return;
+	}
+	if x == y { // Ignore pointers that are the same
+		return;
+	}
+
+	Block :: distinct [4]u64;
+	BLOCK_SIZE :: size_of(Block);
+
+	i := 0;
+	t := &Block{};
+	for ; i + BLOCK_SIZE <= len; i += BLOCK_SIZE {
+		a := rawptr(uintptr(x) + uintptr(i));
+		b := rawptr(uintptr(y) + uintptr(i));
+
+		mem.copy(t, a, BLOCK_SIZE);
+		mem.copy(a, b, BLOCK_SIZE);
+		mem.copy(b, t, BLOCK_SIZE);
+	}
+
+	if i < len {
+		rem := len - i;
+
+		a := rawptr(uintptr(x) + uintptr(i));
+		b := rawptr(uintptr(y) + uintptr(i));
+
+		mem.copy(t, a, rem);
+		mem.copy(a, b, rem);
+		mem.copy(b, t, rem);
+	}
+}
+
+
+ptr_rotate :: proc(left: int, mid: ^$T, right: int) {
+	when size_of(T) != 0 {
+		left, mid, right := left, mid, right;
+
+		// TODO(bill): Optimization with a buffer for smaller ranges
+		if left >= right {
+			for {
+				ptr_swap_non_overlapping(ptr_sub(mid, right), mid, right);
+				mid = ptr_sub(mid, right);
+
+				left -= right;
+				if left < right {
+					break;
+				}
+			}
+		} else {
+			ptr_swap_non_overlapping(ptr_sub(mid, left), mid, left);
+			mid = ptr_add(mid, left);
+
+			right -= left;
+			if right < left {
+				break;
+			}
+		}
+	}
+}
diff --git a/core/slice/slice.odin b/core/slice/slice.odin
new file mode 100644
index 000000000..764eb6334
--- /dev/null
+++ b/core/slice/slice.odin
@@ -0,0 +1,254 @@
+package slice
+
+import "intrinsics"
+import "core:math/bits"
+import "core:mem"
+
+_ :: intrinsics;
+_ :: bits;
+_ :: mem;
+
+
+swap :: proc(array: $T/[]$E, a, b: int, loc := #caller_location) {
+	when size_of(E) > 8 {
+		ptr_swap_non_overlapping(&array[a], &array[b], size_of(E));
+	} else {
+		array[a], array[b] = array[b], array[a];
+	}
+}
+
+
+reverse :: proc(array: $T/[]$E) {
+	n := len(array)/2;
+	for i in 0..<n {
+		a, b := i, len(array)-i-1;
+		array[a], array[b] = array[b], array[a];
+	}
+}
+
+
+contains :: proc(array: $T/[]$E, value: E) -> bool where intrinsics.type_is_comparable(E) {
+	_, found := linear_search(array, value);
+	return found;
+}
+
+linear_search :: proc(array: $A/[]$T, key: T) -> (index: int, found: bool)
+	where intrinsics.type_is_comparable(T) #no_bounds_check {
+	for x, i in array {
+		if x == key {
+			return i, true;
+		}
+	}
+	return -1, false;
+}
+
+binary_search :: proc(array: $A/[]$T, key: T) -> (index: int, found: bool)
+	where intrinsics.type_is_ordered(T) #no_bounds_check {
+
+	n := len(array);
+	switch n {
+	case 0:
+		return -1, false;
+	case 1:
+		if array[0] == key {
+			return 0, true;
+		}
+		return -1, false;
+	}
+
+	lo, hi := 0, n-1;
+
+	for array[hi] != array[lo] && key >= array[lo] && key <= array[hi] {
+		when intrinsics.type_is_ordered_numeric(T) {
+			// NOTE(bill): This is technically interpolation search
+			m := lo + int((key - array[lo]) * T(hi - lo) / (array[hi] - array[lo]));
+		} else {
+			m := (lo + hi)/2;
+		}
+		switch {
+		case array[m] < key:
+			lo = m + 1;
+		case key < array[m]:
+			hi = m - 1;
+		case:
+			return m, true;
+		}
+	}
+
+	if key == array[lo] {
+		return lo, true;
+	}
+	return -1, false;
+}
+
+equal :: proc(a, b: $T/[]$E) -> bool where intrinsics.type_is_comparable(E) {
+	if len(a) != len(b) {
+		return false;
+	}
+	when intrinsics.type_is_simple_compare(E) {
+		return mem.compare_ptrs(raw_data(a), raw_data(b), len(a)*size_of(E)) == 0;
+	} else {
+		for i in 0..<len(a) {
+			if a[i] != b[i] {
+				return false;
+			}
+		}
+		return true;
+	}
+}
+
+simple_equal :: proc(a, b: $T/[]$E) -> bool where intrinsics.type_is_simple_compare(E) {
+	if len(a) != len(b) {
+		return false;
+	}
+	return mem.compare_ptrs(raw_data(a), raw_data(b), len(a)*size_of(E)) == 0;
+}
+
+
+has_prefix :: proc(array: $T/[]$E, needle: T) -> bool where intrinsics.type_is_comparable(E) {
+	n := len(needle);
+	if len(array) >= n {
+		return equal(array[:n], needle);
+	}
+	return false;
+}
+
+
+has_suffix :: proc(array: $T/[]$E, needle: T) -> bool where intrinsics.type_is_comparable(E) {
+	array := array;
+	m, n := len(array), len(needle);
+	if m >= n {
+		return equal(array[m-n:], needle);
+	}
+	return false;
+}
+
+fill :: proc(array: $T/[]$E, value: T) {
+	for _, i in array {
+		array[i] = value;
+	}
+}
+
+rotate_left :: proc(array: $T/[]$E, k: int) {
+	n := len(array);
+	m := mid %% n;
+	k := n - m;
+	p := raw_data(array);
+	ptr_rotate(mid, ptr_add(p, mid), k);
+}
+rotate_right :: proc(array: $T/[]$E, k: int) {
+	rotate_left(array, -k);
+}
+
+swap_with_slice :: proc(a, b: $T/[]$E, loc := #caller_location) {
+	assert(len(a) == len(b), "miss matching slice lengths", loc);
+
+	ptr_swap_non_overlapping(raw_data(a), raw_data(b), len(a)*size_of(E));
+}
+
+concatenate :: proc(a: []$T/[]$E, allocator := context.allocator) -> (res: T) {
+	if len(a) == 0 {
+		return;
+	}
+	n := 0;
+	for s in a {
+		n += len(s);
+	}
+	res = make(T, n, allocator);
+	i := 0;
+	for s in a {
+		i += copy(b[i:], s);
+	}
+	return;
+}
+
+// copies slice into a new dynamic array
+clone :: proc(a: $T/[]$E, allocator := context.allocator) -> []E {
+	d := make([]E, len(a), allocator);
+	copy(d[:], a);
+	return d;
+}
+
+
+// copies slice into a new dynamic array
+to_dynamic :: proc(a: $T/[]$E, allocator := context.allocator) -> [dynamic]E {
+	d := make([dynamic]E, len(a), allocator);
+	copy(d[:], a);
+	return d;
+}
+
+// Converts slice into a dynamic array without cloning or allocating memory
+into_dynamic :: proc(a: $T/[]$E) -> [dynamic]E {
+	s := transmute(mem.Raw_Slice)a;
+	d := mem.Raw_Dynamic_Array{
+		data = s.data,
+		len  = 0,
+		cap  = s.len,
+		allocator = mem.nil_allocator(),
+	};
+	return transmute([dynamic]E)d;
+}
+
+
+length :: proc(a: $T/[]$E) -> int {
+	return len(a);
+}
+is_empty :: proc(a: $T/[]$E) -> bool {
+	return len(a) == 0;
+}
+
+
+
+
+split_at :: proc(array: $T/[]$E, index: int) -> (a, b: T) {
+	return array[:index], array[index:];
+}
+
+
+split_first :: proc(array: $T/[]$E) -> (first: E, rest: T) {
+	return array[0], array[1:];
+}
+split_last :: proc(array: $T/[]$E) -> (rest: T, last: E) {
+	n := len(array)-1;
+	return array[:n], array[n];
+}
+
+first :: proc(array: $T/[]$E) -> E {
+	return array[0];
+}
+last :: proc(array: $T/[]$E) -> ^E {
+	return array[len(array)-1];
+}
+
+
+first_ptr :: proc(array: $T/[]$E) -> ^E {
+	if len(array) != 0 {
+		return &array[0];
+	}
+	return nil;
+}
+last_ptr :: proc(array: $T/[]$E) -> ^E {
+	if len(array) != 0 {
+		return &array[len(array)-1];
+	}
+	return nil;
+}
+
+get :: proc(array: $T/[]$E, index: int) -> (value: E, ok: bool) {
+	if 0 <= index && index < len(array) {
+		value = array[index];
+		ok = true;
+	}
+	return;
+}
+get_ptr :: proc(array: $T/[]$E, index: int) -> (value: ^E, ok: bool) {
+	if 0 <= index && index < len(array) {
+		value = &array[index];
+		ok = true;
+	}
+	return;
+}
+
+as_ptr :: proc(array: $T/[]$E) -> ^E {
+	return raw_data(array);
+}
diff --git a/core/slice/sort.odin b/core/slice/sort.odin
new file mode 100644
index 000000000..04199eef6
--- /dev/null
+++ b/core/slice/sort.odin
@@ -0,0 +1,382 @@
+package slice
+
+import "intrinsics"
+_ :: intrinsics;
+
+ORD :: intrinsics.type_is_ordered;
+
+
+// sort sorts a slice
+// This sort is not guaranteed to be stable
+sort :: proc(data: $T/[]$E) where ORD(E) {
+	when size_of(E) != 0 {
+		if n := len(data); n > 1 {
+			_quick_sort(data, 0, n, _max_depth(n));
+		}
+	}
+}
+
+// sort_proc sorts a slice with a given procedure to test whether two values are ordered "i < j"
+// This sort is not guaranteed to be stable
+sort_proc :: proc(data: $T/[]$E, less: proc(i, j: E) -> bool) {
+	when size_of(E) != 0 {
+		if n := len(data); n > 1 {
+			_quick_sort_proc(data, 0, n, _max_depth(n), less);
+		}
+	}
+}
+
+reverse_sort :: proc(data: $T/[]$E) where ORD(E) {
+	sort_proc(data, proc(i, j: E) -> bool {
+		return j < i;
+	});
+}
+
+
+
+
+is_sorted :: proc(array: $T/[]$E) -> bool where ORD(E) {
+	for i := len(array)-1; i > 0; i -= 1 {
+		if array[i] < array[i-1] {
+			return false;
+		}
+	}
+	return true;
+}
+
+is_sorted_proc :: proc(array: $T/[]$E, less: proc(i, j: E) -> bool) -> bool {
+	for i := len(array)-1; i > 0; i -= 1 {
+		if less(array[i], array[i-1]) {
+			return false;
+		}
+	}
+	return true;
+}
+
+
+
+@(private)
+_max_depth :: proc(n: int) -> int { // 2*ceil(log2(n+1))
+	depth: int;
+	for i := n; i > 0; i >>= 1 {
+		depth += 1;
+	}
+	return depth * 2;
+}
+
+@(private)
+_quick_sort :: proc(data: $T/[]$E, a, b, max_depth: int) where ORD(E) {
+	median3 :: proc(data: T, m1, m0, m2: int) {
+		if data[m1] < data[m0] {
+			swap(data, m1, m0);
+		}
+		if data[m2] < data[m1] {
+			swap(data, m2, m1);
+			if data[m1] < data[m0] {
+				swap(data, m1, m0);
+			}
+		}
+	}
+
+	do_pivot :: proc(data: T, lo, hi: int) -> (midlo, midhi: int) {
+		m := int(uint(lo+hi)>>1);
+		if hi-lo > 40 {
+			s := (hi-lo)/8;
+			median3(data, lo, lo+s, lo+s*2);
+			median3(data, m, m-s, m+s);
+			median3(data, hi-1, hi-1-s, hi-1-s*2);
+		}
+		median3(data, lo, m, hi-1);
+
+
+		pivot := lo;
+		a, c := lo+1, hi-1;
+
+		for ; a < c && data[a] < data[pivot]; a += 1 {
+		}
+		b := a;
+
+		for {
+			for ; b < c && !(data[pivot] < data[b]); b += 1 { // data[b] <= pivot
+			}
+			for ; b < c && data[pivot] < data[c-1]; c -=1 { // data[c-1] > pivot
+			}
+			if b >= c {
+				break;
+			}
+
+			swap(data, b, c-1);
+			b += 1;
+			c -= 1;
+		}
+
+		protect := hi-c < 5;
+		if !protect && hi-c < (hi-lo)/4 {
+			dups := 0;
+			if !(data[pivot] < data[hi-1]) {
+				swap(data, c, hi-1);
+				c += 1;
+				dups += 1;
+			}
+			if !(data[b-1] < data[pivot]) {
+				b -= 1;
+				dups += 1;
+			}
+
+			if !(data[m] < data[pivot]) {
+				swap(data, m, b-1);
+				b -= 1;
+				dups += 1;
+			}
+			protect = dups > 1;
+		}
+		if protect {
+			for {
+				for ; a < b && !(data[b-1] < data[pivot]); b -= 1 {
+				}
+				for ; a < b && data[a] < data[pivot]; a += 1 {
+				}
+				if a >= b {
+					break;
+				}
+				swap(data, a, b-1);
+				a += 1;
+				b -= 1;
+			}
+		}
+		swap(data, pivot, b-1);
+		return b-1, c;
+	}
+
+
+	a, b, max_depth := a, b, max_depth;
+
+	if b-a > 12 { // only use shell sort for lengths <= 12
+		if max_depth == 0 {
+			_heap_sort(data, a, b);
+			return;
+		}
+		max_depth -= 1;
+		mlo, mhi := do_pivot(data, a, b);
+		if mlo-a < b-mhi {
+			_quick_sort(data, a, mlo, max_depth);
+			a = mhi;
+		} else {
+			_quick_sort(data, mhi, b, max_depth);
+			b = mlo;
+		}
+	}
+	if b-a > 1 {
+		// Shell short with gap 6
+		for i in a+6..<b {
+			if data[i] < data[i-6] {
+				swap(data, i, i-6);
+			}
+		}
+		_insertion_sort(data, a, b);
+	}
+}
+
+@(private)
+_insertion_sort :: proc(data: $T/[]$E, a, b: int) where ORD(E) {
+	for i in a+1..<b {
+		for j := i; j > a && data[j] < data[j-1]; j -= 1 {
+			swap(data, j, j-1);
+		}
+	}
+}
+
+@(private)
+_heap_sort :: proc(data: $T/[]$E, a, b: int) where ORD(E) {
+	sift_down :: proc(data: T, lo, hi, first: int) {
+		root := lo;
+		for {
+			child := 2*root + 1;
+			if child >= hi {
+				break;
+			}
+			if child+1 < hi && data[first+child] < data[first+child+1] {
+				child += 1;
+			}
+			if !(data[first+root] < data[first+child]) {
+				return;
+			}
+			swap(data, first+root, first+child);
+			root = child;
+		}
+	}
+
+
+	first, lo, hi := a, 0, b-a;
+
+	for i := (hi-1)/2; i >= 0; i -= 1 {
+		sift_down(data, i, hi, first);
+	}
+
+	for i := hi-1; i >= 0; i -= 1 {
+		swap(data, first, first+i);
+		sift_down(data, lo, i, first);
+	}
+}
+
+
+
+
+
+
+@(private)
+_quick_sort_proc :: proc(data: $T/[]$E, a, b, max_depth: int, less: proc(i, j: E) -> bool) {
+	median3 :: proc(data: T, m1, m0, m2: int, less: proc(i, j: E) -> bool) {
+		if less(data[m1], data[m0]) {
+			swap(data, m1, m0);
+		}
+		if less(data[m2], data[m1]) {
+			swap(data, m2, m1);
+			if less(data[m1], data[m0]) {
+				swap(data, m1, m0);
+			}
+		}
+	}
+
+	do_pivot :: proc(data: T, lo, hi: int, less: proc(i, j: E) -> bool) -> (midlo, midhi: int) {
+		m := int(uint(lo+hi)>>1);
+		if hi-lo > 40 {
+			s := (hi-lo)/8;
+			median3(data, lo, lo+s, lo+s*2, less);
+			median3(data, m, m-s, m+s, less);
+			median3(data, hi-1, hi-1-s, hi-1-s*2, less);
+		}
+		median3(data, lo, m, hi-1, less);
+
+		pivot := lo;
+		a, c := lo+1, hi-1;
+
+		for ; a < c && less(data[a], data[pivot]); a += 1 {
+		}
+		b := a;
+
+		for {
+			for ; b < c && !less(data[pivot], data[b]); b += 1 { // data[b] <= pivot
+			}
+			for ; b < c && less(data[pivot], data[c-1]); c -=1 { // data[c-1] > pivot
+			}
+			if b >= c {
+				break;
+			}
+
+			swap(data, b, c-1);
+			b += 1;
+			c -= 1;
+		}
+
+		protect := hi-c < 5;
+		if !protect && hi-c < (hi-lo)/4 {
+			dups := 0;
+			if !less(data[pivot], data[hi-1]) {
+				swap(data, c, hi-1);
+				c += 1;
+				dups += 1;
+			}
+			if !less(data[b-1], data[pivot]) {
+				b -= 1;
+				dups += 1;
+			}
+
+			if !less(data[m], data[pivot]) {
+				swap(data, m, b-1);
+				b -= 1;
+				dups += 1;
+			}
+			protect = dups > 1;
+		}
+		if protect {
+			for {
+				for ; a < b && !less(data[b-1], data[pivot]); b -= 1 {
+				}
+				for ; a < b && less(data[a], data[pivot]); a += 1 {
+				}
+				if a >= b {
+					break;
+				}
+				swap(data, a, b-1);
+				a += 1;
+				b -= 1;
+			}
+		}
+		swap(data, pivot, b-1);
+		return b-1, c;
+	}
+
+
+	a, b, max_depth := a, b, max_depth;
+
+	if b-a > 12 { // only use shell sort for lengths <= 12
+		if max_depth == 0 {
+			_heap_sort_proc(data, a, b, less);
+			return;
+		}
+		max_depth -= 1;
+		mlo, mhi := do_pivot(data, a, b, less);
+		if mlo-a < b-mhi {
+			_quick_sort_proc(data, a, mlo, max_depth, less);
+			a = mhi;
+		} else {
+			_quick_sort_proc(data, mhi, b, max_depth, less);
+			b = mlo;
+		}
+	}
+	if b-a > 1 {
+		// Shell short with gap 6
+		for i in a+6..<b {
+			if less(data[i], data[i-6]) {
+				swap(data, i, i-6);
+			}
+		}
+		_insertion_sort_proc(data, a, b, less);
+	}
+}
+
+@(private)
+_insertion_sort_proc :: proc(data: $T/[]$E, a, b: int, less: proc(i, j: E) -> bool) {
+	for i in a+1..<b {
+		for j := i; j > a && less(data[j], data[j-1]); j -= 1 {
+			swap(data, j, j-1);
+		}
+	}
+}
+
+@(private)
+_heap_sort_proc :: proc(data: $T/[]$E, a, b: int, less: proc(i, j: E) -> bool) {
+	sift_down :: proc(data: T, lo, hi, first: int, less: proc(i, j: E) -> bool) {
+		root := lo;
+		for {
+			child := 2*root + 1;
+			if child >= hi {
+				break;
+			}
+			if child+1 < hi && less(data[first+child], data[first+child+1]) {
+				child += 1;
+			}
+			if !less(data[first+root], data[first+child]) {
+				return;
+			}
+			swap(data, first+root, first+child);
+			root = child;
+		}
+	}
+
+
+	first, lo, hi := a, 0, b-a;
+
+	for i := (hi-1)/2; i >= 0; i -= 1 {
+		sift_down(data, i, hi, first, less);
+	}
+
+	for i := hi-1; i >= 0; i -= 1 {
+		swap(data, first, first+i);
+		sift_down(data, lo, i, first, less);
+	}
+}
+
+
+