datas_log.rs

use std::collections::VecDeque;
use std::collections::HashSet;
use std::hash::{Hash, Hasher};
use std::time::Instant;

fn main() {
    let start = Instant::now();
    let result = bfs(Board3::new(vec![0,2,5,6,8,3,4,7,1]));
    let elapsed = start.elapsed();
    println!("{:?}", elapsed);
    println!("{:?}", result);
}

#[derive(Debug, Eq, PartialEq, PartialOrd, Ord, Copy, Clone)]
enum Direction {
    Left = 0,
    Right = 1,
    Up = 2,
    Down = 3,
}

fn bfs<T: Board>(board: T) -> Option<Vec<Direction>> {
    let mut frontier: VecDeque<T> = VecDeque::new();
    let mut explored: HashSet<T> = HashSet::new();
    let mut log: AppendLog<Direction> = AppendLog::new();
    let solved = T::solved();
    frontier.push_front(board);

    while !frontier.is_empty() {
        let state: T = frontier.pop_front().unwrap();
        explored.insert(state.clone());

        if state.eq(&solved) {
            return Some(log.read(state.moves()));
        }

        if state.can_move(Direction::Up) {
            let new_board = state.move_direction(Direction::Up, &mut log);
            if explored.get(&new_board).is_none() {
                frontier.push_back(new_board);
            }
        }
        if state.can_move(Direction::Down) {
            let new_board = state.move_direction(Direction::Down, &mut log);
            if explored.get(&new_board).is_none() {
                frontier.push_back(new_board);
            }
        }
        if state.can_move(Direction::Left) {
            let new_board = state.move_direction(Direction::Left, &mut log);
            if explored.get(&new_board).is_none() {
                frontier.push_back(new_board);
            }

        }
        if state.can_move(Direction::Right) {
            let new_board = state.move_direction(Direction::Right, &mut log);
            if explored.get(&new_board).is_none() {
                frontier.push_back(new_board);
            }
        }
    }
    None
}

trait Board: Hash + Eq + Clone {
    /// Creates a new board from a raw vector of values.
    /// Does verification that the board is correct and should not be used in
    /// a tight loop.
    fn new(values: Vec<u8>) -> Self;

    /// Returns the cannonical solved board for the given size.
    fn solved() -> Self;

    /// Will moving in the provided direction yield a valid board.
    fn can_move(&self, direction: Direction) -> bool;

    /// Directions the empty piece in the given direction.
    /// Does not check if it is valid, guard with can_Direction.
    fn move_direction(&self, direction: Direction, log: &mut AppendLog<Direction>) -> Self;

    fn moves(&self) -> FakePointer;
}

#[derive(Debug)]
struct Board2 {
    values: [u8; 4],
    empty_slot: usize,
    moves: FakePointer,
}

impl Board for Board2 {
    fn new(values: Vec<u8>) -> Board2 {
        assert!(values.len() == 4);
        let mut zero_loc = 0;
        for i in 0..values.len() {
            if values[i] == 0 {
                zero_loc = i;
                break;
            }
        }
        Board2 {
            values: [values[0], values[1], values[2], values[3]],
            empty_slot: zero_loc,
            moves: 0,
        }
    }

    fn solved() -> Board2 {
        Board2 {
            values: [0, 1, 2, 3],
            empty_slot: 0,
            moves: 0,
        }
    }

    fn moves(&self) -> FakePointer {
        self.moves
    }

    #[inline]
    fn can_move(&self, direction: Direction) -> bool {
        match direction {
            Direction::Left => self.empty_slot == 1 || self.empty_slot == 3,
            Direction::Right => self.empty_slot == 0 || self.empty_slot == 2,
            Direction::Up => self.empty_slot >= 2,
            Direction::Down => self.empty_slot < 2,
        }
    }

    fn move_direction(&self, direction: Direction, log: &mut AppendLog<Direction>) -> Board2 {
        let mut new_board = self.values.clone();
        let new_empty = match direction {
            Direction::Left => self.empty_slot - 1,
            Direction::Right => self.empty_slot + 1,
            Direction::Up => self.empty_slot - 2,
            Direction::Down => self.empty_slot + 2,
        };
       let new_move = log.append_node(direction, self.moves);
       new_board.swap(new_empty, self.empty_slot);

        Board2 {
            values: new_board,
            moves: new_move,
            empty_slot: new_empty,
        }
    }
}

impl PartialEq for Board2 {
    fn eq(&self, other: &Board2) -> bool {
        self.values[0] == other.values[0] && self.values[1] == other.values[1] &&
        self.values[2] == other.values[2] && self.values[3] == other.values[3]
    }
}

impl Eq for Board2 {}

impl Hash for Board2 {
    fn hash<H: Hasher>(&self, state: &mut H) {
        self.values[0].hash(state);
        self.values[1].hash(state);
        self.values[2].hash(state);
        self.values[3].hash(state);
    }
}

impl Clone for Board2 {
    fn clone(&self) -> Board2 {
        Board2 {
            values: self.values.clone(),
            moves: self.moves,
            empty_slot: self.empty_slot,
        }
    }
}



#[derive(Debug)]
struct Board3 {
    values: [u8; 9],
    empty_slot: usize,
    moves: FakePointer,
}

impl Board for Board3 {
    fn new(values: Vec<u8>) -> Board3 {
        assert!(values.len() == 9);
        let mut zero_loc = 0;
        for i in 0..values.len() {
            if values[i] == 0 {
                zero_loc = i;
                break;
            }
        }
        Board3 {
            values: [values[0], values[1], values[2], values[3], values[4], values[5], values[6],
                     values[7], values[8]],
            empty_slot: zero_loc,
            moves: 0,
        }
    }

    fn solved() -> Board3 {
        Board3 {
            values: [0, 1, 2, 3, 4, 5, 6, 7, 8],
            empty_slot: 0,
            moves: 0,
        }
    }
    
    fn moves(&self) -> FakePointer {
        self.moves
    }

    #[inline]
    fn can_move(&self, direction: Direction) -> bool {
        match direction {
            Direction::Left => self.empty_slot != 0 && self.empty_slot != 3 && self.empty_slot != 6,
            Direction::Right => self.empty_slot != 2 && self.empty_slot != 5 && self.empty_slot != 8,
            Direction::Up => self.empty_slot > 2,
            Direction::Down => self.empty_slot <= 5,
        }
    }

    fn move_direction(&self, direction: Direction, log: &mut AppendLog<Direction>) -> Board3 {
        let mut new_board = self.values.clone();
        let new_empty = match direction {
            Direction::Left => self.empty_slot - 1,
            Direction::Right => self.empty_slot + 1,
            Direction::Up => self.empty_slot - 3,
            Direction::Down => self.empty_slot + 3,
        };
        let new_move = log.append_node(direction, self.moves);
        new_board.swap(new_empty, self.empty_slot);

        Board3 {
            values: new_board,
            moves: new_move,
            empty_slot: new_empty,
        }
    }
}

impl PartialEq for Board3 {
    fn eq(&self, other: &Board3) -> bool {
        self.values[0] == other.values[0] && self.values[1] == other.values[1] &&
        self.values[2] == other.values[2] && self.values[3] == other.values[3] &&
        self.values[4] == other.values[4] && self.values[5] == other.values[5] &&
        self.values[6] == other.values[6] &&
        self.values[7] == other.values[7] && self.values[8] == other.values[8]
    }
}

impl Eq for Board3 {}

impl Hash for Board3 {
    fn hash<H: Hasher>(&self, state: &mut H) {
        self.values[0].hash(state);
        self.values[1].hash(state);
        self.values[2].hash(state);
        self.values[3].hash(state);
        self.values[4].hash(state);
        self.values[5].hash(state);
        self.values[6].hash(state);
        self.values[7].hash(state);
        self.values[8].hash(state);
    }
}

impl Clone for Board3 {
    fn clone(&self) -> Board3 {
        Board3 {
            values: self.values.clone(),
            moves: self.moves,
            empty_slot: self.empty_slot,
        }
    }
}

type FakePointer = usize;

struct AppendNode<T: Copy + Clone> {
    parent: Option<FakePointer>,
    data: T
}


/// An append only log for tracking the moves used to get to a board state,
/// without copying.
/// Uses an arena style allocation.
struct AppendLog<T: Copy + Clone> {
    nodes: Vec<AppendNode<T>>,
    next_pointer: FakePointer,
}


impl<T: Copy + Clone> AppendLog<T> {
    fn new() -> AppendLog<T> {
        AppendLog {
            nodes: Vec::new(),
            next_pointer: 0,
        }
    }

    fn append_node(&mut self, data: T, parent: FakePointer) -> FakePointer {
        self.nodes.push(AppendNode {
            parent: Some(parent),
            data: data,
        });
        let location = self.next_pointer;
        self.next_pointer += 1;
        location
    }

    fn read(&self, start: FakePointer) -> Vec<T> {
        let mut result: Vec<T> = Vec::new();
        let mut index = start;
        loop {
            let node = &self.nodes[index];
            result.push(node.data);
            match node.parent {
                None => { break; },
                Some(id) => {
                    if index == id {
                        break;
                    }
                    index = id;
                }
            }
        }
        result
    }
}