mod automata;
pub mod rle_loader;
pub use automata::Automata;
use std::rc::Rc;
use std::collections::HashMap;
use std::collections::hash_map::DefaultHasher;
use std::hash::{Hash, Hasher};
#[derive(Debug)]
pub struct Node {
level: usize,
population: usize,
hash: u64,
children: Option<Children>,
}
impl PartialEq for Node {
fn eq(&self, other: &Node) -> bool {
self.level == other.level && self.population == other.population && self.hash == other.hash
}
}
impl Eq for Node {}
#[derive(Hash, Debug)]
struct Children {
nw: Rc<Node>,
ne: Rc<Node>,
sw: Rc<Node>,
se: Rc<Node>,
}
pub enum Edge {
Torus,
Truncate,
Infinite,
}
struct GrandChildren {
nwnw: Rc<Node>,
nwne: Rc<Node>,
nwsw: Rc<Node>,
nwse: Rc<Node>,
nenw: Rc<Node>,
nene: Rc<Node>,
nesw: Rc<Node>,
nese: Rc<Node>,
swnw: Rc<Node>,
swne: Rc<Node>,
swsw: Rc<Node>,
swse: Rc<Node>,
senw: Rc<Node>,
sene: Rc<Node>,
sesw: Rc<Node>,
sese: Rc<Node>,
}
struct GrandAutomata {
nwnw: Automata,
nwne: Automata,
nwsw: Automata,
nwse: Automata,
nenw: Automata,
nene: Automata,
nesw: Automata,
nese: Automata,
swnw: Automata,
swne: Automata,
swsw: Automata,
swse: Automata,
senw: Automata,
sene: Automata,
sesw: Automata,
sese: Automata,
}
struct Nonants {
nw: Rc<Node>,
ne: Rc<Node>,
sw: Rc<Node>,
se: Rc<Node>,
n_: Rc<Node>,
e_: Rc<Node>,
s_: Rc<Node>,
w_: Rc<Node>,
c_: Rc<Node>,
}
pub struct Hashlife {
cache: Cache,
edge: Edge,
top: Option<Rc<Node>>,
previous: Option<Rc<Node>>,
gen: usize,
}
struct Cache {
join: HashMap<u64, Rc<Node>>,
step: HashMap<Rc<Node>, Rc<Node>>,
dead: Option<Rc<Node>>,
alive: Option<Rc<Node>>,
}
impl Cache {
fn new() -> Self {
Self {
join: HashMap::new(),
step: HashMap::new(),
dead: None,
alive: None,
}
}
}
struct ConstructionParameters<'a> {
level: usize,
vector: &'a Vec<u8>,
width: usize,
height: usize,
bound: BoundingBox,
}
#[derive(Debug)]
pub struct BoundingBox {
top: isize,
bottom: isize,
left: isize,
right: isize,
}
impl BoundingBox {
fn new(x: isize, y: isize, level: usize) -> Self {
let level_delta = level;
let pow2ld = 2isize.pow(level_delta as u32);
let top = y * pow2ld + pow2ld - 1;
let bottom = y * pow2ld;
let left = x * pow2ld;
let right = x * pow2ld + pow2ld - 1;
assert!(top >= bottom, "top: {}, bottom: {}", top, bottom);
assert!(left <= right, "left: {}, right: {}", left, right);
Self { top, bottom, left, right }
}
pub fn from(top: isize, bottom: isize, left: isize, right: isize) -> Self {
Self { top, bottom, left, right }
}
fn collides(&self, other: &BoundingBox) -> bool {
let other_below_self = other.top < self.bottom;
let other_above_self = other.bottom > self.top;
let other_right_of_self = other.left > self.right;
let other_left_of_self = other.right < self.left;
return !(other_below_self || other_above_self || other_right_of_self || other_left_of_self);
}
fn width(&self) -> usize {
(self.right - self.left + 1) as usize
}
fn height(&self) -> usize {
(self.top - self.bottom + 1) as usize
}
fn index(&self, x: isize, y: isize) -> usize {
let width = (self.right - self.left) as usize + 1;
let idx_height = (self.top - self.bottom) as usize;
let x_adjusted = (x - self.left) as usize;
let y_adjusted = (y - self.bottom) as usize;
width * (idx_height - y_adjusted) + x_adjusted
}
}
impl Hashlife {
fn new() -> Self {
Self {
cache: Cache::new(),
edge: Edge::Infinite,
top: None,
previous: None,
gen: 0,
}
}
fn join(&mut self, nw: Rc<Node>, ne: Rc<Node>, sw: Rc<Node>, se: Rc<Node>) -> Rc<Node> {
let children = Children::from(&nw, &ne, &sw, &se);
let level = nw.level + 1;
assert_eq!(nw.level, ne.level);
assert_eq!(nw.level, sw.level);
assert_eq!(nw.level, se.level);
let population = nw.population + ne.population + sw.population + se.population;
let hash = calculate_hash(&children);
if let Some(ref_to_node) = self.cache.join.get(&hash) {
return Rc::clone(ref_to_node);
}
let children = Some(children);
let node = Node {
level,
population,
hash,
children
};
let node = Rc::new(node);
self.cache.join.insert(hash, Rc::clone(&node));
return node;
}
fn into_nonants(&mut self, node: Rc<Node>) -> Nonants {
match &node.level {
0 => panic!("attempted to bread node into 9x9 at level 0"),
1 => panic!("attempted to bread node into 9x9 at level 1"),
2 => panic!("attempted to bread node into 9x9 at level 2"),
_ => ()
};
let c = node.get_children();
let g = node.get_grand_children();
Nonants {
nw: Rc::clone(&c.nw),
ne: Rc::clone(&c.ne),
sw: Rc::clone(&c.sw),
se: Rc::clone(&c.se),
n_: self.join(g.nwne, g.nenw, Rc::clone(&g.nwse), Rc::clone(&g.nesw)),
e_: self.join(Rc::clone(&g.nesw), g.nese, Rc::clone(&g.senw), g.sene),
s_: self.join(Rc::clone(&g.swne), Rc::clone(&g.senw), g.swse, g.sesw),
w_: self.join(g.nwsw, Rc::clone(&g.nwse), g.swnw, Rc::clone(&g.swne)),
c_: self.join(g.nwse, g.nesw, g.swne, g.senw),
}
}
fn join_nonants(&mut self, nodes: Nonants) -> Rc<Node> {
let nw_res = self.join(
Rc::clone(&nodes.nw.get_children().se),
Rc::clone(&nodes.n_.get_children().sw),
Rc::clone(&nodes.w_.get_children().ne),
Rc::clone(&nodes.c_.get_children().nw)
);
let ne_res = self.join(
Rc::clone(&nodes.n_.get_children().se),
Rc::clone(&nodes.ne.get_children().sw),
Rc::clone(&nodes.c_.get_children().ne),
Rc::clone(&nodes.e_.get_children().nw)
);
let sw_res = self.join(
Rc::clone(&nodes.w_.get_children().se),
Rc::clone(&nodes.c_.get_children().sw),
Rc::clone(&nodes.sw.get_children().ne),
Rc::clone(&nodes.s_.get_children().nw)
);
let se_res = self.join(
Rc::clone(&nodes.c_.get_children().se),
Rc::clone(&nodes.e_.get_children().sw),
Rc::clone(&nodes.s_.get_children().ne),
Rc::clone(&nodes.se.get_children().nw),
);
self.join(nw_res, ne_res, sw_res, se_res)
}
fn step(&mut self, node: Rc<Node>) -> Rc<Node> {
if let Some(ref_to_node) = self.cache.step.get(&node) {
return Rc::clone(ref_to_node);
}
let step = match &node.level {
0 => panic!("attempted to step a node with level 0"),
1 => panic!("attempted to step a node with level 1"),
2 => {
let g = node.get_grand_automata();
let nw = automata::simb3s23(g.nwse, g.nwnw, g.nwne, g.nenw, g.nesw, g.senw, g.swne, g.swnw, g.nwsw);
let ne = automata::simb3s23(g.nesw, g.nwne, g.nenw, g.nene, g.nese, g.sene, g.senw, g.swne, g.nwse);
let sw = automata::simb3s23(g.swne, g.nwsw, g.nwse, g.nesw, g.senw, g.sesw, g.swse, g.swsw, g.swnw);
let se = automata::simb3s23(g.senw, g.nwse, g.nesw, g.nese, g.sene, g.sese, g.sesw, g.swse, g.swne);
let nw = self.make_automata(nw);
let ne = self.make_automata(ne);
let sw = self.make_automata(sw);
let se = self.make_automata(se);
self.join(nw, ne, sw, se)
},
_ => {
let mut g9x9 = self.into_nonants(Rc::clone(&node));
g9x9.nw = self.step(g9x9.nw);
g9x9.ne = self.step(g9x9.ne);
g9x9.sw = self.step(g9x9.sw);
g9x9.se = self.step(g9x9.se);
g9x9.n_ = self.step(g9x9.n_);
g9x9.e_ = self.step(g9x9.e_);
g9x9.s_ = self.step(g9x9.s_);
g9x9.w_ = self.step(g9x9.w_);
g9x9.c_ = self.step(g9x9.c_);
self.join_nonants(g9x9)
},
};
self.cache.step.insert(node, Rc::clone(&step));
step
}
fn expand_empty_border(&mut self, node: Rc<Node>) -> Rc<Node> {
let c = node.get_children();
let e = self.empty(node.level-1);
let e = || Rc::clone(&e);
let nw = self.join(e(), e(), e(), Rc::clone(&c.nw));
let ne = self.join(e(), e(), Rc::clone(&c.ne), e());
let sw = self.join(e(), Rc::clone(&c.sw), e(), e());
let se = self.join(Rc::clone(&c.se), e(), e(), e());
self.join(nw, ne, sw, se)
}
pub fn next_generation(&mut self) {
let top = if let Some(top) = &self.top {
Rc::clone(top)
} else {
return;
};
self.previous = Some(Rc::clone(&top));
let next = match self.edge {
Edge::Infinite => {
let expanded = self.expand_empty_border(Rc::clone(&top));
let expanded = self.expand_empty_border(Rc::clone(&expanded));
let step = self.step(expanded);
let g = step.get_grand_children();
let boarder_population = step.population - g.nwse.population - g.nesw.population - g.swne.population - g.senw.population;
if boarder_population == 0 {
self.join(g.nwse, g.nesw, g.swne, g.senw)
} else {
step
}
},
Edge::Torus => {
let c = top.get_children();
let nw = Rc::clone(&c.nw);
let ne = Rc::clone(&c.ne);
let sw = Rc::clone(&c.sw);
let se = Rc::clone(&c.se);
let inverted = self.join(se, sw, ne, nw);
let inverted = || Rc::clone(&inverted);
let expanded = self.join(inverted(), inverted(), inverted(), inverted());
self.step(expanded)
},
Edge::Truncate => {
let expanded = self.expand_empty_border(Rc::clone(&top));
self.step(expanded)
},
};
self.top = Some(next);
self.gen += 1;
}
fn make_automata(&mut self, a: Automata) -> Rc<Node> {
match a {
Automata::Dead => {
if let Some(ref_to_node) = &self.cache.dead {
Rc::clone(ref_to_node)
} else {
let mut state = DefaultHasher::new();
a.hash(&mut state);
let node = Rc::new(Node {
level: 0,
population: a as usize,
children: None,
hash: state.finish(),
});
self.cache.dead = Some(Rc::clone(&node));
node
}
},
Automata::Alive => {
if let Some(ref_to_node) = &self.cache.alive {
Rc::clone(ref_to_node)
} else {
let mut state = DefaultHasher::new();
a.hash(&mut state);
let node = Rc::new(Node {
level: 0,
population: a as usize,
children: None,
hash: state.finish(),
});
self.cache.alive = Some(Rc::clone(&node));
node
}
},
}
}
pub fn from_array(buffer: Vec<u8>, width: usize, height: usize, edge: Edge) -> Self {
assert_eq!(buffer.len(), width * height);
let mut hashlife = Hashlife::new();
hashlife.edge = edge;
let left = -(width as isize / 2);
let right = width as isize + left - 1;
let bottom = -(height as isize / 2);
let top = height as isize + bottom - 1;
let bound = BoundingBox::from(top, bottom, left, right);
let larger_length = *[width, height].iter().max().unwrap_or(&width) as f64;
let size = larger_length.log2().ceil() as usize;
if size == 0 {
hashlife.top = Some(hashlife.make_automata(Automata::from(buffer[0] as usize)));
return hashlife;
}
let params = ConstructionParameters {
level: size,
vector: &buffer,
width,
height,
bound,
};
let nw = hashlife.construct(-1, 0, size - 1, ¶ms);
let ne= hashlife.construct(0, 0, size - 1, ¶ms);
let sw= hashlife.construct(-1, -1, size - 1, ¶ms);
let se= hashlife.construct(0, -1, size - 1, ¶ms);
let top = hashlife.join(nw, ne, sw, se);
hashlife.top = Some(top);
hashlife
}
fn construct(&mut self, x: isize, y: isize, level: usize, params: &ConstructionParameters) -> Rc<Node> {
if level == 0 {
let bound = BoundingBox::new(x, y, level);
if !bound.collides(¶ms.bound) {
return self.empty(0);
}
let xidx = (x - params.bound.left) as usize;
let yidx = params.height - 1 - (y - params.bound.bottom) as usize;
let idx = params.width * yidx + xidx;
let v = params.vector[idx];
let a = Automata::from(v as usize);
return self.make_automata(a);
}
let mut assemble = |dx, dy| {
let bound = BoundingBox::new(x, y, level-1);
if bound.collides(¶ms.bound) {
self.construct(x * 2 + dx, y * 2 + dy, level - 1, ¶ms)
} else {
self.empty(level - 1)
}
};
let nw = assemble(0, 1);
let ne = assemble(1, 1);
let sw = assemble(0, 0);
let se = assemble(1, 0);
self.join(nw, ne, sw, se)
}
fn empty(&mut self, level: usize) -> Rc<Node> {
if level == 0 {
return self.make_automata(Automata::Dead);
}
let child = self.empty(level - 1);
let children = Children {
nw: Rc::clone(&child),
ne: Rc::clone(&child),
sw: Rc::clone(&child),
se: Rc::clone(&child),
};
let hash = calculate_hash(&children);
if let Some(ref_to_node) = self.cache.join.get(&hash) {
return Rc::clone(ref_to_node);
};
let empty = Rc::new(Node {
level,
population: 0,
children: Some(children),
hash,
});
self.cache.join.insert(hash, Rc::clone(&empty));
empty
}
fn get_node_with(&self, x: isize, y: isize, positions: &Vec<(isize, isize)>, node: Rc<Node>) -> Automata {
if node.level == 0 {
return node.as_automata();
}
let position = positions[node.level-1];
let nw = (x*2, y*2+1);
let ne = (x*2+1, y*2+1);
let sw = (x*2, y*2);
let se = (x*2+1, y*2);
let children = node.get_children();
if position == nw {
return self.get_node_with(nw.0, nw.1, positions, Rc::clone(&children.nw));
} else if position == ne {
return self.get_node_with(ne.0, ne.1, positions, Rc::clone(&children.ne));
} else if position == sw {
return self.get_node_with(sw.0, sw.1, positions, Rc::clone(&children.sw));
} else if position == se {
return self.get_node_with(se.0, se.1, positions, Rc::clone(&children.se));
} else {
panic!("invalid coordinate calculated");
}
}
pub fn get(&self, x: isize, y: isize) -> Option<Automata> {
let top = if let Some(top) = self.top.as_ref() {
Rc::clone(top)
} else {
return None;
};
let mut positions = Vec::with_capacity(top.level);
let mut xx = x;
let mut yy = y;
for _ in 0..top.level {
positions.push((xx,yy));
xx = xx.div_euclid(2);
yy = yy.div_euclid(2);
}
let children = top.get_children();
if y < 0 {
if x < 0 {
Some(self.get_node_with(-1, -1, &positions, Rc::clone(&children.sw)))
} else {
Some(self.get_node_with(0, -1, &positions, Rc::clone(&children.se)))
}
} else {
if x < 0 {
Some(self.get_node_with(-1, 0, &positions, Rc::clone(&children.nw)))
} else {
Some(self.get_node_with(0, 0, &positions, Rc::clone(&children.ne)))
}
}
}
fn max_level(&self) -> usize {
if let Some(top) = &self.top {
top.level
} else {
0
}
}
pub fn draw_diff_to_viewport_array(&mut self, buffer: &mut [u8], viewport: BoundingBox) {
if self.max_level() == 0 {
if let Some(top) = self.top.as_ref() {
buffer[0] = top.population as u8;
}
return;
}
let top = if let Some(top) = &self.top {
Rc::clone(top)
} else {
return;
};
let previous = if let Some(previous) = &self.previous {
if previous.level == 0 {
return;
}
Rc::clone(previous)
} else {
return;
};
let top_children = top.get_children();
let previous_children = previous.get_children();
let t_nw = Rc::clone(&top_children.nw);
let t_ne = Rc::clone(&top_children.ne);
let t_sw = Rc::clone(&top_children.sw);
let t_se = Rc::clone(&top_children.se);
let p_nw = Rc::clone(&previous_children.nw);
let p_ne = Rc::clone(&previous_children.ne);
let p_sw = Rc::clone(&previous_children.sw);
let p_se = Rc::clone(&previous_children.se);
if t_nw != p_nw {
self.draw_diff_to_cell(buffer, t_nw, p_nw, &viewport, -1, 0);
}
if t_ne != p_ne {
self.draw_diff_to_cell(buffer, t_ne, p_ne, &viewport, 0, 0);
}
if t_sw != p_sw {
self.draw_diff_to_cell(buffer, t_sw, p_sw, &viewport, -1, -1);
}
if t_se != p_se {
self.draw_diff_to_cell(buffer, t_se, p_se, &viewport, 0, -1);
}
}
fn draw_diff_to_cell(&mut self, buffer: &mut [u8], node: Rc<Node>, previous: Rc<Node>, viewport: &BoundingBox, x: isize, y: isize) {
let area = BoundingBox::new(x, y, node.level);
if !area.collides(&viewport) {
return;
}
if node.level == 0 {
buffer[viewport.index(x, y)] = node.population as u8;
} else {
let mut draw_down = |dx: isize, dy: isize, n: Rc<Node>, p: Rc<Node>| {
if n == p { return; }
self.draw_diff_to_cell(&mut buffer[..], n, p, &viewport, 2*x+dx, 2*y+dy);
};
let c = node.get_children();
let pc = previous.get_children();
draw_down(0, 1, Rc::clone(&c.nw), Rc::clone(&pc.nw));
draw_down(1, 1, Rc::clone(&c.ne), Rc::clone(&pc.ne));
draw_down(0, 0, Rc::clone(&c.sw), Rc::clone(&pc.sw));
draw_down(1, 0, Rc::clone(&c.se), Rc::clone(&pc.se));
}
}
pub fn draw_to_viewport_buffer(&mut self, buffer: &mut [u8], viewport: BoundingBox) {
if self.max_level() == 0 {
if let Some(top) = self.top.as_ref() {
buffer[0] = top.population as u8;
}
return;
}
let top = Rc::clone(self.top.as_ref().unwrap());
let c = top.get_children();
let nw = Rc::clone(&c.nw);
let ne = Rc::clone(&c.ne);
let sw = Rc::clone(&c.sw);
let se = Rc::clone(&c.se);
self.draw_to_cell(buffer, nw, &viewport, -1, 0);
self.draw_to_cell(buffer, ne, &viewport, 0, 0);
self.draw_to_cell(buffer, sw, &viewport, -1, -1);
self.draw_to_cell(buffer, se, &viewport, 0, -1);
}
fn draw_to_cell(&mut self, buffer: &mut [u8], node: Rc<Node>, viewport: &BoundingBox, x: isize, y: isize) {
let area = BoundingBox::new(x, y, node.level);
if !area.collides(&viewport) {
return;
}
if node.level == 0 {
buffer[viewport.index(x, y)] = node.population as u8;
} else {
let mut draw_down = |dx: isize, dy: isize, n: Rc<Node>| {
self.draw_to_cell(&mut buffer[..], n, &viewport, 2*x+dx, 2*y+dy);
};
let c = node.get_children();
draw_down(0, 1, Rc::clone(&c.nw));
draw_down(1, 1, Rc::clone(&c.ne));
draw_down(0, 0, Rc::clone(&c.sw));
draw_down(1, 0, Rc::clone(&c.se));
}
}
fn as_vector(&self) -> Vec<Automata> {
if let Some(top) = &self.top {
top.as_array().into_iter().flatten().collect()
} else {
vec![]
}
}
pub fn get_generation(&self) -> usize {
self.gen
}
}
impl Node {
fn get_children(&self) ->&Children {
&self.children.as_ref().unwrap()
}
fn get_grand_children(&self) -> GrandChildren {
let err1 = "unable to unwrap child (and expecting grand-children)";
let err2 = "unable to unwrap grand-children";
GrandChildren {
nwnw: Rc::clone(&self.children.as_ref().expect(err1).nw.children.as_ref().expect(err2).nw),
nwne: Rc::clone(&self.children.as_ref().expect(err1).nw.children.as_ref().expect(err2).ne),
nwsw: Rc::clone(&self.children.as_ref().expect(err1).nw.children.as_ref().expect(err2).sw),
nwse: Rc::clone(&self.children.as_ref().expect(err1).nw.children.as_ref().expect(err2).se),
nenw: Rc::clone(&self.children.as_ref().expect(err1).ne.children.as_ref().expect(err2).nw),
nene: Rc::clone(&self.children.as_ref().expect(err1).ne.children.as_ref().expect(err2).ne),
nesw: Rc::clone(&self.children.as_ref().expect(err1).ne.children.as_ref().expect(err2).sw),
nese: Rc::clone(&self.children.as_ref().expect(err1).ne.children.as_ref().expect(err2).se),
swnw: Rc::clone(&self.children.as_ref().expect(err1).sw.children.as_ref().expect(err2).nw),
swne: Rc::clone(&self.children.as_ref().expect(err1).sw.children.as_ref().expect(err2).ne),
swsw: Rc::clone(&self.children.as_ref().expect(err1).sw.children.as_ref().expect(err2).sw),
swse: Rc::clone(&self.children.as_ref().expect(err1).sw.children.as_ref().expect(err2).se),
senw: Rc::clone(&self.children.as_ref().expect(err1).se.children.as_ref().expect(err2).nw),
sene: Rc::clone(&self.children.as_ref().expect(err1).se.children.as_ref().expect(err2).ne),
sesw: Rc::clone(&self.children.as_ref().expect(err1).se.children.as_ref().expect(err2).sw),
sese: Rc::clone(&self.children.as_ref().expect(err1).se.children.as_ref().expect(err2).se),
}
}
fn get_grand_automata(&self) -> GrandAutomata {
if self.level != 2 {
panic!("node must be at level 2 to get automatas");
}
let grand_children = self.get_grand_children();
GrandAutomata {
nwnw: grand_children.nwnw.as_automata(),
nwne: grand_children.nwne.as_automata(),
nwsw: grand_children.nwsw.as_automata(),
nwse: grand_children.nwse.as_automata(),
nenw: grand_children.nenw.as_automata(),
nene: grand_children.nene.as_automata(),
nesw: grand_children.nesw.as_automata(),
nese: grand_children.nese.as_automata(),
swnw: grand_children.swnw.as_automata(),
swne: grand_children.swne.as_automata(),
swsw: grand_children.swsw.as_automata(),
swse: grand_children.swse.as_automata(),
senw: grand_children.senw.as_automata(),
sene: grand_children.sene.as_automata(),
sesw: grand_children.sesw.as_automata(),
sese: grand_children.sese.as_automata(),
}
}
fn as_automata(&self) -> Automata {
Automata::from(self.population)
}
fn from_automata(cell: Automata) -> Node {
let mut state = DefaultHasher::new();
cell.hash(&mut state);
Node {
level: 0,
population: cell as usize,
children: None,
hash: state.finish(),
}
}
fn as_array(&self) -> Vec<Vec<Automata>> {
if self.level == 0 {
return vec![vec![self.as_automata()]];
}
let children = self.get_children();
let nw = children.nw.as_array();
let ne = children.ne.as_array();
let sw = children.sw.as_array();
let se = children.se.as_array();
let top = nw.into_iter()
.zip(ne.into_iter())
.map(|(left, right)| {
let mut result = Vec::with_capacity(left.len() + right.len());
result.extend(left);
result.extend(right);
result
})
.collect::<Vec<Vec<Automata>>>();
let bottom = sw.into_iter()
.zip(se.into_iter())
.map(|(left, right)| {
let mut result = Vec::with_capacity(left.len() + right.len());
result.extend(left);
result.extend(right);
result
})
.collect::<Vec<Vec<Automata>>>();
let mut rows = Vec::with_capacity(top.len() + bottom.len());
rows.extend(top);
rows.extend(bottom);
rows
}
}
impl Hash for Node {
fn hash<H: Hasher>(&self, state: &mut H) {
self.hash.hash(state);
}
}
impl Children {
fn from(nw: &Rc<Node>, ne: &Rc<Node>, sw: &Rc<Node>, se: &Rc<Node>) -> Self {
Self {
nw: Rc::clone(nw),
ne: Rc::clone(ne),
sw: Rc::clone(sw),
se: Rc::clone(se),
}
}
}
fn calculate_hash(children: &Children) -> u64 {
let mut state = DefaultHasher::new();
children.hash(&mut state);
state.finish()
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn get3() {
let cell_width = 3;
let cell_height = 3;
let cells = vec![
1,1,1,
1,0,1,
1,1,1,
];
let hashlife = Hashlife::from_array(cells, cell_width, cell_height, Edge::Truncate);
assert_eq!(hashlife.max_level(), 2);
for x in -2..2 {
for y in -2..2 {
if x == 0 && y == 0 { continue; }
if !(x==-2 || y==-2) {
assert_eq!(hashlife.get(x, y), Some(Automata::Alive));
} else {
assert_eq!(hashlife.get(x, y), Some(Automata::Dead));
}
}
}
assert_eq!(hashlife.get(0, 0), Some(Automata::Dead));
}
#[test]
fn get4() {
let cell_width = 4;
let cell_height = 4;
let cells = vec![
1,1,1,1,
1,1,0,1,
1,1,1,1,
1,1,1,1,
];
let hashlife = Hashlife::from_array(cells, cell_width, cell_height, Edge::Truncate);
assert_eq!(hashlife.max_level(), 2);
for x in -2..2 {
for y in -2..2 {
if x == 0 && y == 0 { continue; }
assert_eq!(hashlife.get(x, y), Some(Automata::Alive));
}
}
assert_eq!(hashlife.get(0, 0), Some(Automata::Dead));
}
#[test]
fn get8() {
let cell_width = 8;
let cell_height = 8;
let cells = vec![
1,1,1,1, 1,1,0,1,
1,1,1,1, 1,1,1,1,
1,1,1,1, 1,1,1,1,
1,1,0,1, 1,1,1,1,
1,1,1,1, 1,1,1,1,
1,1,1,1, 1,1,1,1,
1,0,1,1, 1,1,1,1,
1,1,1,1, 1,1,1,1,
];
let hashlife = Hashlife::from_array(cells, cell_width, cell_height, Edge::Truncate);
assert_eq!(hashlife.max_level(), 3);
assert_eq!(hashlife.get(2, 3), Some(Automata::Dead));
assert_eq!(hashlife.get(-2, 0), Some(Automata::Dead));
assert_eq!(hashlife.get(-3, -3), Some(Automata::Dead));
for x in -4..4 {
for y in -4..4 {
if x == 2 && y == 3 { continue; }
if x == -2 && y == 0 { continue; }
if x == -3 && y == -3 { continue; }
assert_eq!(hashlife.get(x, y), Some(Automata::Alive));
}
}
}
#[test]
fn array_construct_even() {
let cell_width = 4;
let cell_height = 6;
let cells = vec![
1,0,0,1,
1,1,0,1,
1,0,1,1,
1,0,0,1,
0,0,1,0,
0,1,0,1
];
let mut hashlife = Hashlife::from_array(cells, cell_width, cell_height, Edge::Truncate);
assert_eq!(hashlife.max_level(), 3);
for x in -4..-2 {
for y in -4..4 {
assert_eq!(hashlife.get(x, y), Some(Automata::Dead));
}
}
for x in 2..4 {
for y in -4..4 {
assert_eq!(hashlife.get(x, y), Some(Automata::Dead));
}
}
for x in -2..2 {
for y in [-4, 3].iter() {
assert_eq!(hashlife.get(x, *y), Some(Automata::Dead));
}
}
assert_eq!(hashlife.get(-2, 2), Some(Automata::Alive));
assert_eq!(hashlife.get(-1, 2), Some(Automata::Dead));
assert_eq!(hashlife.get( 0, 2), Some(Automata::Dead));
assert_eq!(hashlife.get( 1, 2), Some(Automata::Alive));
assert_eq!(hashlife.get(-2, 1), Some(Automata::Alive));
assert_eq!(hashlife.get(-1, 1), Some(Automata::Alive));
assert_eq!(hashlife.get( 0, 1), Some(Automata::Dead));
assert_eq!(hashlife.get( 1, 1), Some(Automata::Alive));
assert_eq!(hashlife.get(-2, 0), Some(Automata::Alive));
assert_eq!(hashlife.get(-1, 0), Some(Automata::Dead));
assert_eq!(hashlife.get( 0, 0), Some(Automata::Alive));
assert_eq!(hashlife.get( 1, 0), Some(Automata::Alive));
assert_eq!(hashlife.get(-2,-1), Some(Automata::Alive));
assert_eq!(hashlife.get(-1,-1), Some(Automata::Dead));
assert_eq!(hashlife.get( 0,-1), Some(Automata::Dead));
assert_eq!(hashlife.get( 1,-1), Some(Automata::Alive));
assert_eq!(hashlife.get(-2,-2), Some(Automata::Dead));
assert_eq!(hashlife.get(-1,-2), Some(Automata::Dead));
assert_eq!(hashlife.get( 0,-2), Some(Automata::Alive));
assert_eq!(hashlife.get( 1,-2), Some(Automata::Dead));
assert_eq!(hashlife.get(-2,-3), Some(Automata::Dead));
assert_eq!(hashlife.get(-1,-3), Some(Automata::Alive));
assert_eq!(hashlife.get( 0,-3), Some(Automata::Dead));
assert_eq!(hashlife.get( 1,-3), Some(Automata::Alive));
}
#[test]
fn bounding_box_single_pt() {
let bound = BoundingBox::from(0,0,0,0);
assert_eq!(bound.width(), 1);
assert_eq!(bound.height(), 1);
assert_eq!(bound.top, 0);
assert_eq!(bound.bottom, 0);
assert_eq!(bound.left, 0);
assert_eq!(bound.right, 0);
}
#[test]
fn new_bounding_box_1() {
let (x, y) = (0,0);
let level = 1;
let b = BoundingBox::new(x, y, level);
assert_eq!(b.left, 0);
assert_eq!(b.right, 1);
assert_eq!(b.bottom, 0);
assert_eq!(b.top, 1);
}
#[test]
fn max_level_eq_0() {
let cell_width = 1;
let cell_height = 1;
let cells = vec![ 1 ];
let hashlife = Hashlife::from_array(cells, cell_width, cell_height, Edge::Truncate);
assert_eq!(hashlife.max_level(), 0);
}
#[test]
fn max_level_eq_1() {
let cell_width = 2;
let cell_height = 2;
let cells = vec![ 1, 0, 1, 0 ];
let hashlife = Hashlife::from_array(cells, cell_width, cell_height, Edge::Truncate);
assert_eq!(hashlife.max_level(), 1);
}
#[test]
fn cell3x2() {
let cell_width = 3;
let cell_height = 2;
let cells = vec![ 1, 0, 1, 0, 0, 1 ];
let hashlife = Hashlife::from_array(cells, cell_width, cell_height, Edge::Truncate);
assert_eq!(hashlife.max_level(), 2);
}
#[test]
fn as_array_trunc_next_gen() {
let cell_width = 4;
let cell_height = 4;
let cells = vec![
0,0,0,0,
0,1,1,1,
0,0,0,0,
0,0,0,0,
];
let cells_next = vec![
0,0,1,0,
0,0,1,0,
0,0,1,0,
0,0,0,0,
];
let mut hashlife = Hashlife::from_array(cells, cell_width, cell_height, Edge::Truncate);
hashlife.next_generation();
let result = hashlife.as_vector().into_iter().map(|a| a as u8).collect::<Vec<u8>>();
assert_eq!(cells_next, result);
}
#[test]
fn draw_diff_viewport_buffer() {
let cell_width = 4;
let cell_height = 6;
let cells = vec![
0,0,0,0,
0,1,1,1,
0,0,0,0,
0,0,0,0,
0,0,1,1,
0,0,1,1
];
let cells_next_expected = vec![
0,0,1,0,
0,0,0,0,
0,0,1,0,
0,0,0,0,
0,0,0,0,
0,0,0,0,
];
let mut buffer = vec![
0,0,0,0,
0,0,0,0,
0,0,0,0,
0,0,0,0,
0,0,0,0,
0,0,0,0,
];
let mut hashlife = Hashlife::from_array(cells, cell_width, cell_height, Edge::Truncate);
hashlife.next_generation();
let bound = BoundingBox::from(2, -3, -2, 1);
hashlife.draw_diff_to_viewport_array(&mut buffer, bound);
assert_eq!(cells_next_expected, buffer);
}
#[test]
fn draw_to_viewport_buffer() {
let cell_width = 4;
let cell_height = 6;
let cells = vec![
0,0,0,0,
0,1,1,1,
0,0,0,0,
0,0,0,0,
0,0,1,1,
0,0,1,1
];
let expected = cells.clone();
let mut buffer = vec![
0,0,0,0,
0,0,0,0,
0,0,0,0,
0,0,0,0,
0,0,0,0,
0,0,0,0,
];
let mut hashlife = Hashlife::from_array(cells, cell_width, cell_height, Edge::Truncate);
let bound = BoundingBox::from(2, -3, -2, 1);
hashlife.draw_to_viewport_buffer(&mut buffer, bound);
assert_eq!(expected, buffer);
}
#[test]
fn empty_border() {
let cell_width = 2;
let cell_height = 2;
let cells = vec![
0,0,
1,1,
];
let cells_next = vec![
0,0,0,0,
0,0,0,0,
0,1,1,0,
0,0,0,0,
];
let mut hashlife = Hashlife::from_array(cells, cell_width, cell_height, Edge::Truncate);
let expanded = hashlife.expand_empty_border(Rc::clone(hashlife.top.as_ref().unwrap()));
let viewport = BoundingBox::from(1, -2, -2, 1);
hashlife.top = Some(expanded);
for x in -2..2 {
for y in -2..2 {
let idx = viewport.index(x, y);
let expected = cells_next[idx] as usize;
let result = hashlife.get(x, y).unwrap() as usize;
assert_eq!(expected, result,
"got {result} when expecting {expected} at abs({x},{y}) [index={idx}]",
expected=expected,
result=result,
x=x,
y=y,
idx=idx
);
}
}
}
}