halp-2-rust

src-ruleset-mx2_monovacancy.rs

use serde;
use serde::de::Deserialize;
use serde_json as json;
use std::collections::BTreeSet;
use itertools::Itertools;

use ::util::MyIteratorExt;
use ::layers::{Layers,Layer};
use ::ruleset::traits::RuleSet;
use ::grid::Hexagonal;
use ::grid::hexagonal::{Node,Cubic,MutualNeighborhood};

#[derive(Serialize, Deserialize)]
#[derive(PartialEq, Eq, Hash, PartialOrd, Ord)]
#[derive(Debug, Clone, Copy)]
pub struct Mx2Monovacancy;

pub type State = Hexagonal<Layers>;

#[allow(unused_attributes)]
#[derive(Serialize, Deserialize, ToJson)]
#[derive(PartialEq, Eq, Hash, PartialOrd, Ord)]
#[derive(Debug, Clone, Copy)]
pub enum Move {
	Form(Node,Layer),
	Move(Node,Node,Layer),
	Flip(Node),
	Trefoil(Trefoil),
}

pub type Trefoil = (Node,Node,Node);
fn sorted3<T:Ord>(mut a:T, mut b:T, mut c:T) -> (T,T,T) {
	minmax_inplace(&mut a, &mut b);
	minmax_inplace(&mut a, &mut c);
	minmax_inplace(&mut a, &mut b);
	(a,b,c)
}
#[inline]
fn minmax_inplace<T:Ord>(a: &mut T, b: &mut T) {
	if a > b { ::std::mem::swap(a, b) };
}

pub struct Event {
	changes: Vec<(Node,Layer)>,
}

pub type Toggle = (Node,Layer);

#[derive(PartialEq, Eq, Hash, PartialOrd, Ord)]
#[derive(Debug, Clone, Copy)]
pub enum Kind {
	Form(bool),
	Flip,
	Trefoil,
	Move{ from: bool, to: bool, metal: bool, comb: bool },
}
static KIND_FORM_0_TO_1: &'static str = "FormFirst";
static KIND_FORM_1_TO_2: &'static str = "FormSecond";
static KIND_TREFOIL: &'static str = "MakeTrefoil";
static KIND_FLIP: &'static str = "Flip";
static KIND_MOVE_PREFIX: &'static str = "Move";
const KIND_MOVE_CHAR_PRESENT: char = 'X';
const KIND_MOVE_CHAR_VACANT:  char = '_';
fn status_kind_char(vacant: bool) -> char {
	if vacant { KIND_MOVE_CHAR_VACANT }
	else { KIND_MOVE_CHAR_PRESENT }
}
fn kind_char_is_vacant(c: char) -> Option<bool> {
	match c {
		KIND_MOVE_CHAR_VACANT  => Some(true),
		KIND_MOVE_CHAR_PRESENT => Some(false),
		_ => None,
	}
}

impl serde::Serialize for Kind {
	fn serialize<S>(&self, serializer: &mut S) -> Result<(), S::Error>
	 where S: serde::Serializer,
	{
		match self {
			&Kind::Form(false) => serializer.serialize_str(KIND_FORM_0_TO_1),
			&Kind::Form(true)  => serializer.serialize_str(KIND_FORM_1_TO_2),
			&Kind::Flip => serializer.serialize_str(KIND_FLIP),
			&Kind::Trefoil => serializer.serialize_str(KIND_TREFOIL),
			&Kind::Move{from,to,metal,comb} => {
				let chars1 = KIND_MOVE_PREFIX.chars();
				let chars2 = vec![from, to, metal, comb]
					.into_iter().map(status_kind_char);

				let s:String = chars1.chain(chars2).collect();
				serializer.serialize_str(&s)
			},
		}
	}
}
impl Deserialize for Kind {
	fn deserialize<D>(deserializer: &mut D) -> Result<Kind, D::Error>
	 where D: serde::Deserializer,
	{ deserializer.deserialize(KindVisitor) }
}
struct KindVisitor;
impl serde::de::Visitor for KindVisitor {
	type Value = Kind;
	fn visit_string<E>(&mut self, s: String) -> Result<Kind, E>
	 where E: ::serde::de::Error,
	{ self.visit_str(&s) }
	fn visit_str<E>(&mut self, s: &str) -> Result<Kind, E>
	 where E: ::serde::de::Error,
	{
		println!("<{}>",s);
		if s == KIND_FLIP { Ok(Kind::Flip) }
		else if s == KIND_TREFOIL { Ok(Kind::Trefoil) }
		else if s == KIND_FORM_0_TO_1 { Ok(Kind::Form(false)) }
		else if s == KIND_FORM_1_TO_2 { Ok(Kind::Form(true)) }
		else if s.starts_with(KIND_MOVE_PREFIX) {
			let mut cs = s[KIND_MOVE_PREFIX.len()..].chars()
				.map(kind_char_is_vacant)
				.map(|opt| opt.expect("bad move char")); // FIXME use Err

			// FIXME use Err
			let from  = cs.next().expect("not enough chars in Move Kind");
			let to    = cs.next().expect("not enough chars in Move Kind");
			let metal = cs.next().expect("not enough chars in Move Kind");
			let comb  = cs.next().expect("not enough chars in Move Kind");
			assert!(cs.next().is_none(), "too many chars in Move Kind");

			Ok(Kind::Move{from:from, to:to, metal:metal, comb:comb})
		}
		else { Err(serde::de::Error::custom("bad prefix for kind")) }
	}
}

#[test]
fn test_kind_serialize_round_trip() {
	println!("");
	for kind in Mx2Monovacancy.all_kinds() {
		println!("ser: <{:?}>", kind);
		let s = json::to_string(&kind).unwrap_or_else(|e| panic!("{}", e));
		println!(" de: <{}>", &s);
		let k2 = json::from_str(&s).unwrap_or_else(|e| panic!("{}", e));
		assert_eq!(kind, k2);
	}
}

impl RuleSet for Mx2Monovacancy {
	type State = State;
	type Move = Move;
	type Event = Event;
	type Toggle = Toggle;
	type Kind = Kind;

	fn all_moves(&self, state: &State) -> Vec<(Move,Kind)> {
		let mut out = vec![];
		for node in state.nodes() {
			for_normal_moves_from(state, node, |x| {out.push(x);});
		}
		out
	}
	fn all_kinds(&self) -> Vec<Kind> {
		let mut out = Vec::new();
		out.push(Kind::Form(true));
		out.push(Kind::Form(false));
		out.push(Kind::Flip);
		out.push(Kind::Trefoil);
		out.extend((0..16).map(|n|
			Kind::Move {
				from:  n&1 == 1,
				to:    n&2 == 2,
				metal: n&4 == 4,
				comb:  n&8 == 8,
			}
		));
		out
	}
	fn affected_moves(&self, ev: &Event, state: &State) -> Vec<(Move,Kind)> {
		let &Event { ref changes } = ev;

		// Nodes up to one tile away
		let mut nodes = changes.iter().map(|&(node,_)| node).collect(): BTreeSet<_>;
		let clone = nodes.clone();
		nodes.extend(clone.into_iter().flat_map(|n| state.neighbors(n)));

		let mut out = vec![];
		for node in nodes.iter().cloned() {
			for_normal_moves_from(state, node, |x| {out.push(x);});
		}

		for_trefoil_moves_involving(state, nodes, |x| {out.push(x);});

		debug_assert_eq!(out.len(), out.iter().cloned().map(|(m,_)| m).unique().count());
		out
	}
	fn move_event(&self, mv: Move, _state: &State) -> Event {
		let changes = match mv {
			Move::Form(node,layer)    => vec![(node,layer)],
			Move::Flip(node)          => vec![(node,1), (node,2)],
			Move::Move(old,new,layer) => vec![(old,layer), (new,layer)],
			Move::Trefoil((a,b,c))    => vec![(a,1),(a,2),(b,1),(b,2),(c,1),(c,2)],
		};
		Event { changes: changes }
	}
	fn perform(&self, ev: &Event, state: &mut State) {
		let &Event { ref changes } = ev;
		for (node,layer) in changes.iter().cloned() {
			let layers = state[node].invert_layer(layer);
			state[node] = layers;
		}
	}
	fn event_toggles(&self, ev: &Event) -> Vec<Toggle> {
		let &Event { ref changes } = ev;
		changes.clone()
	}
	fn all_toggles(&self, state: &State) -> Vec<Toggle> {
		state.iter_with_nodes()
			.flat_map(|(node,layers)| layers.into_iter().map(move |x| (node,x)))
			.collect()
	}
}

pub(self) fn for_normal_moves_from<F>(state: &State, node: Node, mut cb: F)
 where F: FnMut((Move,Kind)),
{
	let layers = state[node];
	for layer in layers.invert() {
		(cb)((
			Move::Form(node,layer),
			Kind::Form(!layers.is_empty()),
		))
	}
	if layers.is_single() {
		(cb)((
			Move::Flip(node),
			Kind::Flip,
		))
	}
	state.for_mutual_neighborhoods(node, |hood| {
		let MutualNeighborhood { neighbor, pos_mutual, neg_mutual } = hood;
		for layer in layers {
			if state[neighbor].has_layer(layer) { continue }
			let mv = Move::Move(node,neighbor,layer);
			let kind = Kind::Move {
				from:  state[node].is_double(),
				to:    !state[neighbor].is_empty(),
				metal: state[pos_mutual].has_layer(layer),
				comb:  state[neg_mutual].has_layer(layer),
			};
			(cb)((mv,kind))
		}
	})
}

/// One of the six possible displacements (in cubic coords)
/// between two nodes in a trefoil defect.
const TREFOIL_NEIGHBOR_DISP: Cubic = (2,-2,0);

fn for_trefoil_moves_involving<I,F>(state: &State, nodes: I, mut cb: F)
 where F: FnMut((Move,Kind)), I: IntoIterator<Item=Node>,
{
	// We seek groups of three divacancies all mutually related by
	// trefoil displacements, of which at least one is in `nodes`.

	// That is, for each divacancy in `nodes`...
	nodes.into_iter().filter(|&x| state[x].is_double())

	// ...find pairs of two divacancies related to it...
	.flat_map(|node|
		state.rotations_60(node, TREFOIL_NEIGHBOR_DISP)
		.filter(|&x| state[x].is_double())
		.combinations_n(2)

		// ...which are also related to each other.
		.filter(|pair| state.rotations_60(pair[0], TREFOIL_NEIGHBOR_DISP).any_eq(&pair[1]))

		// Put them into a canonical form.
		.map(move |pair| sorted3(node, pair[0], pair[1]))
	)

	// The same trefoil will have been produced multiple times if more than
	//  one of its nodes are in `nodes`.
	.unique()

	.map(|tref| (Move::Trefoil(tref), Kind::Trefoil))
	.foreach(|x| (cb)(x)) // emit results
}

#[cfg(test)]
pub mod tests {
	use std::collections::BTreeSet;
	use std::iter::FromIterator;
	use super::*;
	use itertools::Itertools;
	use ::grid::hexagonal::{Node,Hexagonal};
	use ::layers::Layers;
	use super::for_normal_moves_from;

	fn moves_from_node(state: &State, node: Node) -> BTreeSet<(Move,Kind)> {
		let mut out = vec![];
		for_normal_moves_from(state, node, |x| {out.push(x);});

		assert_eq!(out.len(), out.iter().cloned().map(|(m,_)| m).unique().count());
		out.into_iter().collect()
	}

	#[test]
	fn empty_node_moves() {
		let state = Hexagonal::new_from_const((10,10), Layers::new_empty());
		assert_eq!(
			moves_from_node(&state, (5,5)),
			BTreeSet::from_iter(vec![
				(Move::Form((5,5),1), Kind::Form(false)),
				(Move::Form((5,5),2), Kind::Form(false)),
			])
		);
	}

	#[test]
	fn single_node_moves() {
		let mut state = Hexagonal::new_from_const((10,10), Layers::new_empty());
		state[(5,5)] = Layers::new_single(2);

		let mv_kind = Kind::Move{ from:false, to:false, metal:false, comb:false };
		assert_eq!(
			moves_from_node(&state, (5,5)),
			BTreeSet::from_iter(vec![
				(Move::Flip, Kind::Flip),
				(Move::Form((5,5)), Kind::Form(true)),
				(Move::Move((5,5),(4,6),2), mv_kind), // -+
				(Move::Move((5,5),(6,4),2), mv_kind), // +-
				(Move::Move((5,5),(6,5),2), mv_kind), // +0
				(Move::Move((5,5),(4,5),2), mv_kind), // -0
				(Move::Move((5,5),(5,4),2), mv_kind), // 0-
				(Move::Move((5,5),(5,6),2), mv_kind), // 0+
			])
		);
	}

	#[test]
	fn move_kinds() {
		let mut state = Hexagonal::new_from_const((10,10), Layers::new_empty());
		state[(5,5)] = Layers::new_single(1);
		let from_kind  = Kind::Move{ from:true,  to:false, metal:false, comb:false };
		let to_kind    = Kind::Move{ from:false, to:true,  metal:false, comb:false };
		let metal_kind = Kind::Move{ from:false, to:false, metal:true,  comb:false };
		let comb_kind  = Kind::Move{ from:false, to:false, metal:false, comb:true  };

		// closures to temporarily place a vacancy somewhere and test whether it
		//   has a given move
		let mut require_move = |from, to, layer, kind| {
			state[from] = Layers::new_single(layer);
			assert!(moves_from_node(&state, from)
				.any_eq(&Move::Move(from,to,layer), kind));
			state[from] = Layers::new_empty();
		};

		let mut require_no_move = |from, to, layer| {
			state[from] = Layers::new_single(layer);
			assert!(moves_from_node(&state, from).map(|(m,_)| m)
				.all(|(m != &Move::Move(from,to,layer))));
			state[from] = Layers::new_empty();
		}

		require_move((5,5), (4,5), 2, from_kind);
		require_move((5,5), (4,5), 2, to_kind); // FIXME should fail
		require_move((4,5), (5,5), 1, from_kind); // FIXME should fail
		require_move((4,5), (5,5), 2, to_kind);
		require_no_move((4,5), (5,5), 1);
		require_no_move((4,5), (5,5), 2); // FIXME should fail
		require_no_move((

		assert!(moves_from_node(&state, (5,5)).contains(&(Move::Move((5,5),(4,6),2), mv_kind)));
			BTreeSet::from_iter(vec![
				(Move::Flip, Kind::Flip),
				(Move::Form((5,5)), Kind::Form(true)),
				(Move::Move((5,5),(4,6),2), mv_kind), // -+
				(Move::Move((5,5),(6,4),2), mv_kind), // +-
				(Move::Move((5,5),(6,5),2), mv_kind), // +0
				(Move::Move((5,5),(4,5),2), mv_kind), // -0
				(Move::Move((5,5),(5,4),2), mv_kind), // 0-
				(Move::Move((5,5),(5,6),2), mv_kind), // 0+
			])
		);
	}

	#[test]
	fn trefoil_moves() {
		let mut state = Hexagonal::new_from_const((10,10), Layers::new_empty());
		
	// FIXME many more
	}
}