Implement a lazy selection sort for move ordering

3 files changed, 87 insertions, 13 deletions

diff --git a/engine/src/eval.rs b/engine/src/eval.rs
index b0b52df..5754343 100644
--- a/engine/src/eval.rs
+++ b/engine/src/eval.rs
@@ -6,7 +6,7 @@ use std::{
 
 use model::{CheckersBitBoard, Move, PieceColor, PossibleMoves};
 
-use crate::transposition_table::TranspositionTableRef;
+use crate::{lazysort::LazySort, transposition_table::TranspositionTableRef};
 
 const KING_WORTH: u32 = 2;
 
@@ -182,17 +182,12 @@ fn eval_jumps(
 
 unsafe fn sort_moves(
 	a: &Move,
-	b: &Move,
 	board: CheckersBitBoard,
 	table: TranspositionTableRef,
-) -> std::cmp::Ordering {
-	let a_entry = table
+) -> Evaluation {
+	table
 		.get_any_depth(a.apply_to(board))
-		.unwrap_or(Evaluation::DRAW);
-	let b_entry = table
-		.get_any_depth(b.apply_to(board))
-		.unwrap_or(Evaluation::DRAW);
-	a_entry.cmp(&b_entry)
+		.unwrap_or(Evaluation::DRAW)
 }
 
 pub fn negamax(
@@ -215,15 +210,14 @@ pub fn negamax(
 
 		let turn = board.turn();
 		let mut best_eval = Evaluation::LOSS;
-		let mut moves: Vec<Move> = PossibleMoves::moves(board).into_iter().collect();
+		let moves: Box<[Move]> = PossibleMoves::moves(board).into_iter().collect();
 
 		if moves.is_empty() {
 			return Evaluation::LOSS;
 		}
 
-		moves.sort_unstable_by(|a, b| unsafe { sort_moves(a, b, board, table) });
-
-		for current_move in moves {
+		let sorter = LazySort::new(moves, |m| unsafe { sort_moves(m, board, table) });
+		for current_move in sorter.into_iter() {
 			let board = unsafe { current_move.apply_to(board) };
 			let current_eval = if board.turn() == turn {
 				negamax(depth - 1, alpha, beta, board, table).increment()
diff --git a/engine/src/lazysort.rs b/engine/src/lazysort.rs
new file mode 100644
index 0000000..e2d6a3f
--- /dev/null
+++ b/engine/src/lazysort.rs
@@ -0,0 +1,79 @@
+#[derive(Debug, Clone, PartialEq, Eq)]
+pub struct LazySort<T, F: Fn(&T) -> R, R: Ord> {
+	collection: Box<[T]>,
+	sorted: usize,
+	sort_by: F,
+}
+
+pub struct LazySortIter<T, F: Fn(&T) -> R, R: Ord> {
+	sorter: LazySort<T, F, R>,
+	index: usize,
+}
+
+impl<T, F: Fn(&T) -> R, R: Ord> LazySort<T, F, R> {
+	pub fn new(collection: Box<[T]>, sort_by: F) -> Self {
+		Self {
+			collection,
+			sort_by,
+			sorted: 0,
+		}
+	}
+
+	fn len(&self) -> usize {
+		self.collection.len()
+	}
+
+	fn sort(&mut self, index: usize) {
+		let mut min: Option<R> = None;
+		let mut min_index = None;
+		for i in index..self.collection.len() {
+			if let Some(min) = &mut min {
+				let res = (self.sort_by)(&self.collection[i]);
+				if res < *min {
+					*min = res;
+					min_index = Some(i);
+				}
+			}
+		}
+
+		if let Some(min_index) = min_index {
+			self.collection.swap(index, min_index);
+		}
+	}
+
+	fn sort_between(&mut self, start: usize, end: usize) {
+		for i in start..=end {
+			self.sort(i);
+		}
+	}
+
+	pub fn get(&mut self, index: usize) -> Option<&T> {
+		if index >= self.sorted {
+			self.sort_between(self.sorted, index)
+		}
+
+		self.collection.get(index)
+	}
+}
+
+impl<T: Copy, F: Fn(&T) -> R, R: Ord> IntoIterator for LazySort<T, F, R> {
+	type IntoIter = LazySortIter<T, F, R>;
+	type Item = T;
+
+	fn into_iter(self) -> Self::IntoIter {
+		LazySortIter {
+			sorter: self,
+			index: 0,
+		}
+	}
+}
+
+impl<T: Copy, F: Fn(&T) -> R, R: Ord> Iterator for LazySortIter<T, F, R> {
+	type Item = T;
+
+	fn next(&mut self) -> Option<Self::Item> {
+		let r = self.sorter.get(self.index);
+		self.index += 1;
+		r.cloned()
+	}
+}
diff --git a/engine/src/lib.rs b/engine/src/lib.rs
index d29169b..6cb7e33 100644
--- a/engine/src/lib.rs
+++ b/engine/src/lib.rs
@@ -6,5 +6,6 @@ pub use model::{CheckersBitBoard, Move, PieceColor, PossibleMoves};
 pub use transposition_table::{TranspositionTable, TranspositionTableRef};
 
 mod eval;
+mod lazysort;
 mod tablebase;
 mod transposition_table;