algoxcc 0.1.2

use serde::{Deserialize, Serialize};

use self::param_error::ParamError;
use crate::solver::{
    items::Items,
    node::{Node, NodeType},
    problem::Problem,
};
use std::collections::{HashMap, HashSet};

pub mod items;
mod node;
pub mod option;
pub mod param_error;
pub mod problem;

/// eXact Cover with Colors solutions
///
/// See examples for solve function
#[derive(Debug, Eq, PartialEq, Clone, PartialOrd, Ord, Hash, Default, Serialize, Deserialize)]
pub struct Solutions(Vec<Vec<String>>);

impl Solutions {
    /// get all solutions found
    pub fn all(&self) -> &Vec<Vec<String>> {
        &self.0
    }
    /// get number of solutions found
    pub fn count(&self) -> usize {
        self.0.len()
    }
    /// get first solution found
    pub fn first(&self) -> Result<&Vec<String>, ParamError> {
        if self.count() == 0 {
            return Err(ParamError::new("No solutions found".to_string()));
        }
        Ok(&self.0[0])
    }
}

/// Implementation using Dancing Cells data
/// structure and the logic used by the main solve function
#[derive(Debug)]
pub struct DancingCells {
    // items in problem
    items: Items,
    // options in problem
    nodes: Vec<Node>,
    // option labels for solutions
    option_labels: Vec<String>,
    // stop after first solution found
    stop_after_first: bool,
    // first found status
    first_found: bool,
    // found solutions
    pub solutions: Vec<Vec<usize>>,
}

impl DancingCells {
    /// Initialize items with sets, nodes and option labels
    pub fn new(problem: &Problem) -> Result<Self, ParamError> {
        // validate input
        if problem.primary_items.len() == 0 {
            let message = format!("The input problem have no primary items!");
            return Err(ParamError::new(message));
        }

        let primary_unique: HashSet<&String> = problem.primary_items.iter().collect();
        let mut item_names = problem.primary_items.iter().collect::<Vec<&String>>();
        item_names.extend(problem.secondary_items.iter());
        let item_map = item_names
            .iter()
            .enumerate()
            .map(|(i, v)| (v, i))
            .collect::<HashMap<_, _>>();
        // bidirectional storage of colors
        let mut color_names = vec![];
        let mut color_map = HashMap::new();
        // 0 = blank = no color (primary) or unique color (secondary)
        let blank = "".to_string();
        color_names.push(blank.clone());
        color_map.insert(&blank, 0);

        // count ocurrences of each primary item and track color names on secondary items
        let mut item_count: HashMap<&String, usize> = HashMap::new();
        for option in &problem.options {
            for item in &option.primary_items {
                if !item_names.contains(&&item) {
                    let message = format!("Unknown primary item {} in option", item);
                    return Err(ParamError::new(message));
                }
                // update item_count
                let count = item_count.entry(&item).or_insert(0);
                *count += 1;
            }
            for (item, color) in &option.secondary_items {
                if !item_names.contains(&&item) {
                    let message = format!("Unknown secondary item {} in option", item);
                    return Err(ParamError::new(message));
                }
                // update colors
                if !color.is_empty() && !color_map.contains_key(&color) {
                    color_names.push(color.clone());
                    color_map.insert(&color, color_names.len() - 1);
                }
                // update item_count
                let count = item_count.entry(&item).or_insert(0);
                *count += 1;
            }
        }

        // validate primary items from options
        for item in &problem.primary_items {
            let count = item_count.get(item);
            if count == None || count == Some(&0) {
                let message = format!("Primary {item} not found in options");
                return Err(ParamError::new(message));
            }
        }

        let mut items = Items::new(&item_names, &item_count, &primary_unique);

        // fill nodes with options with separators where
        // item/loc = lenght of option before/after
        let mut nodes: Vec<Node> = Vec::new();
        // start with a separator
        nodes.push(Node::separator(0));
        // sets index for next item
        let mut next_item = items.list.clone();
        // link to rows in nodes
        // let mut rows = Vec::new();
        for r in 0..problem.options.len() {
            let option = &problem.options[r];
            let mut length = 0;
            // primary items
            for item in &option.primary_items {
                let item_ix = item_map[&&item];
                length += 1;
                // add item for option
                nodes.push(Node::item(items.list[item_ix], next_item[item_ix], r, 0));
                items.sets[next_item[item_ix]] = nodes.len() - 1;
                next_item[item_ix] += 1;
            }
            // secondary items
            for (item, color) in &option.secondary_items {
                let item_ix = item_map[&&item];
                length += 1;
                // add item for option
                nodes.push(Node::item(
                    items.list[item_ix],
                    next_item[item_ix],
                    r,
                    color_map[&color].try_into().unwrap(),
                ));
                items.sets[next_item[item_ix]] = nodes.len() - 1;
                next_item[item_ix] += 1;
            }
            // final separator
            nodes.push(Node::separator(length));
        }

        let option_labels = problem.options.iter().map(|o| o.label.clone()).collect();
        let stop_after_first = false;
        let first_found = false;
        let solutions = vec![];

        Ok(Self {
            items,
            nodes,
            option_labels,
            stop_after_first,
            first_found,
            solutions,
        })
    }

    /// Hide other items in options with item
    ///
    /// Hide if item is primary, unique secondary or secondary with different color
    ///
    /// Optionally flag if an item runs out of options (return false)
    fn hide(&mut self, item: &usize, color: usize, flag_out_of_options: bool) -> bool {
        // get all options with item
        for opt_ix in 0..self.items.get_size(item) {
            // link to item in option
            let node_ix = self.items.sets[item + opt_ix];
            if color == 0 || color != self.nodes[node_ix].color {
                // for all siblings other_node_ix of node_ix
                let mut other_node_ix = node_ix + 1;
                while other_node_ix != node_ix {
                    // if separator go to first item in option
                    if self.nodes[other_node_ix].is_separator() {
                        // by subtracting length of option from ix
                        other_node_ix -= self.nodes[other_node_ix].lenght();
                    } else {
                        let other_item = &self.nodes[other_node_ix].item;
                        if self.items.was_active(other_item) {
                            let new_size = self.items.get_size(other_item) - 1;
                            if new_size == 0
                                && flag_out_of_options
                                && self.items.is_primary(other_item)
                                && self.items.is_active(other_item)
                            {
                                // we are out of options for uncovered primary item
                                return false;
                            } else {
                                // move item option to inactive (swap with last active)
                                self.items.set_size(other_item, new_size);
                                let last_active = self.items.sets[other_item + new_size];
                                let last_active_ix = self.nodes[other_node_ix].loc;
                                self.items.sets[other_item + new_size] = other_node_ix;
                                self.nodes[other_node_ix].loc = other_item + new_size;
                                self.items.sets[last_active_ix] = last_active;
                                self.nodes[last_active].loc = last_active_ix;
                            }
                        }
                        // next item in option
                        other_node_ix += 1;
                    }
                }
            }
        }
        true
    }

    /// Pick primary item with smallest size
    ///
    /// item in items[k]
    /// - item is primary
    /// - where k in {0:active-1}
    /// - and size = min(size(item))
    ///
    /// return column (= item)
    fn pick_primary(&self) -> (usize, usize) {
        let mut picked_item = 0;
        let mut item_size = 0;
        for i in 0..self.items.active {
            let item = self.items.list[i];
            let size = self.items.get_size(&item);
            if self.items.is_primary(&item) && (item_size == 0 || &size < &item_size) {
                item_size = size;
                picked_item = self.items.list[i];
            }
        }
        (picked_item, item_size)
    }

    /// Cover a primary item by deactivating an then hiding other
    /// items from options with this primary item
    fn cover_primary(&mut self, item: &usize) {
        self.items.deactivate_item(item);
        self.items.previous_active = self.items.active;
        self.hide(item, 0, false);
    }

    /// Deactivate other items in option
    fn deactivate_other_option_items(&mut self, option: &usize) {
        self.items.previous_active = self.items.active;
        let mut other_option = option + 1;
        while &other_option != option {
            if self.nodes[other_option].node_type == NodeType::Separator {
                other_option = other_option - self.nodes[other_option].item;
            } else {
                let item = &self.nodes[other_option].item;
                self.items.deactivate_item(item);
                other_option += 1;
            }
        }
    }

    /// Hide options for other items in options
    ///
    /// Return false if an uncovered item runs out of options
    fn hide_other_option_items(&mut self, option: &usize) -> bool {
        let mut other_option = option + 1;
        while &other_option != option {
            if self.nodes[other_option].node_type == NodeType::Separator {
                other_option = other_option - self.nodes[other_option].item;
            } else {
                let item = self.nodes[other_option].item;
                if self.items.is_primary(&item) || self.items.was_active(&item) {
                    if !self.hide(&item, self.nodes[other_option].color, true) {
                        // item without options -> stop
                        return false;
                    }
                }
                other_option += 1;
            }
        }
        true
    }

    /// One step in the recursions trying different options
    ///
    /// With input list of picked options from prevous steps
    fn solve_step(&mut self, previously_picked_options: Vec<usize>) {
        if self.stop_after_first && self.first_found {
            // one solution found and only one solution needed
            return;
        }
        if self.items.solution_found() {
            if self.stop_after_first {
                // flag solution found if only first solution needed
                self.first_found = true;
            }
            // all items covered -> save picked options as a solution and return
            self.solutions.push(previously_picked_options);
            return;
        }
        let (picked_item, size) = self.pick_primary();
        if size == 0 {
            // item without options -> return
            return;
        }

        self.cover_primary(&picked_item);

        // get state before trying options
        let state = self.items.get_state();

        // try all options in picked_item
        for opt_ix in 0..self.items.get_size(&picked_item) {
            let other_option = self.items.sets[picked_item + opt_ix];
            self.deactivate_other_option_items(&other_option);
            if self.hide_other_option_items(&other_option) {
                let mut picked_options = previously_picked_options.clone();
                picked_options.push(self.nodes[self.items.sets[picked_item + opt_ix]].option);
                self.solve_step(picked_options);
            }
            // go back to previous state
            self.items.reset(&state);
        }
    }

    fn find_solutions(&mut self, stop_after_first: bool) {
        self.stop_after_first = stop_after_first;
        self.solve_step(vec![]);
    }

    fn get_solutions(&self) -> Solutions {
        let mut all_vec = vec![];
        for solution in &self.solutions {
            let mut sol_options = solution
                .iter()
                .map(|option| self.option_labels[*option].clone())
                .collect::<Vec<String>>();
            sol_options.sort();
            all_vec.push(sol_options);
        }
        Solutions(all_vec)
    }

    /// solve and return all possible solutions
    pub fn solve_all(&mut self) -> Solutions {
        self.find_solutions(false);
        self.get_solutions()
    }

    /// solve and return first solution found
    pub fn solve_first(&mut self) -> Solutions {
        self.find_solutions(true);
        self.get_solutions()
    }

    #[cfg(test)]
    fn get_option_locations(&self) -> Vec<usize> {
        self.nodes.iter().map(|n| n.loc).collect()
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use option::Option;

    #[test]
    fn test_solutions() {
        let no_solutions = Solutions(vec![]);
        assert_eq!(no_solutions.count(), 0);
        let result = no_solutions.first();
        assert!(result.is_err());
        let two_solutions = Solutions(vec![
            vec!["o1".to_string(), "o2".to_string()],
            vec!["o3".to_string()],
        ]);
        assert_eq!(two_solutions.count(), 2);
        let result = two_solutions.first();
        assert!(result.is_ok());
        let first = result.unwrap();
        assert_eq!(first.len(), 2);
        assert_eq!(first[0], "o1");
        let result = serde_json::to_string(&two_solutions);
        assert!(result.is_ok());
        let json = result.unwrap();
        assert_eq!(json, r#"[["o1","o2"],["o3"]]"#)
    }

    #[test]
    fn test_problem_no_primary() {
        // no primary items
        let problem = Problem::new(
            &vec![],
            &vec![],
            &vec![Option::new("o1", &vec!["p1", "p2"], &vec![("s1", ""), ("s2", "")]).unwrap()],
        )
        .unwrap();
        let result = DancingCells::new(&problem);
        assert!(result.is_err());
        let message = "The input problem have no primary items!".to_string();
        assert_eq!(result.err(), Some(ParamError::new(message)));
    }

    #[test]
    fn test_problem_unknown_item() {
        let problem = Problem::new(
            &vec!["p1", "p2", "p3"],
            &vec![],
            &vec![
                Option::new("o1", &vec!["p1", "p2"], &vec![]).unwrap(),
                Option::new("o2", &vec!["p1", "p4"], &vec![]).unwrap(),
            ],
        )
        .unwrap();
        let result = DancingCells::new(&problem);
        assert!(result.is_err());
        let message = "Unknown primary item p4 in option".to_string();
        assert_eq!(result.err(), Some(ParamError::new(message)));
    }

    #[test]
    fn test_problem_missing_item() {
        let problem = Problem::new(
            &vec!["p1", "p2", "p3"],
            &vec![],
            &vec![
                Option::new("o1", &vec!["p1", "p2"], &vec![]).unwrap(),
                Option::new("o2", &vec!["p1"], &vec![]).unwrap(),
            ],
        )
        .unwrap();
        let result = DancingCells::new(&problem);
        assert!(result.is_err());
        let message = "Primary p3 not found in options".to_string();
        assert_eq!(result.err(), Some(ParamError::new(message)));
    }

    #[test]
    fn test_new_problem() {
        let problem = get_problem_knuth();
        let dc = DancingCells::new(&problem).unwrap();
        assert_eq!(dc.items.active, 5);
        // verify item list
        assert_eq!(dc.items.list, [2, 7, 11, 15, 21]);
        assert!(dc.items.primary_items.contains(&2));
        assert!(dc.items.primary_items.contains(&7));
        assert!(dc.items.primary_items.contains(&11));
        assert_eq!(dc.items.active, 5);
        assert_eq!(dc.items.previous_active, 5);
        assert_eq!(dc.items.primary_active, 3);
        // verify sets
        assert_eq!(dc.items.sets[0..5], [0, 3, 1, 6, 11]);
        assert_eq!(dc.items.sets[5..9], [1, 2, 2, 14]);
        assert_eq!(dc.items.sets[9..13], [2, 2, 7, 17]);
        assert_eq!(dc.items.sets[13..19], [3, 4, 3, 8, 12, 15]);
        assert_eq!(dc.items.sets[19..24], [4, 3, 4, 9, 18]);
        // verify nodes
        assert_eq!(dc.nodes[0].node_type, NodeType::Separator);
        assert_eq!(dc.nodes[0].item, 0);
        // p, q, x, y:A
        assert_eq!(dc.nodes[1].node_type, NodeType::Item);
        assert_eq!(dc.nodes[1].loc, 2);
        assert_eq!(dc.nodes[1].item, 2);
        assert_eq!(dc.nodes[1].color, 0);
        assert_eq!(dc.nodes[1].option, 0);
        assert_eq!(dc.nodes[2].node_type, NodeType::Item);
        assert_eq!(dc.nodes[2].loc, 7);
        assert_eq!(dc.nodes[2].item, 7);
        assert_eq!(dc.nodes[2].color, 0);
        assert_eq!(dc.nodes[2].option, 0);
        assert_eq!(dc.nodes[3].node_type, NodeType::Item);
        assert_eq!(dc.nodes[3].loc, 15);
        assert_eq!(dc.nodes[3].item, 15);
        assert_eq!(dc.nodes[3].color, 0);
        assert_eq!(dc.nodes[3].option, 0);
        assert_eq!(dc.nodes[4].node_type, NodeType::Item);
        assert_eq!(dc.nodes[4].loc, 21);
        assert_eq!(dc.nodes[4].item, 21);
        assert_eq!(dc.nodes[4].color, 1);
        assert_eq!(dc.nodes[4].option, 0);
        //
        assert_eq!(dc.nodes[5].node_type, NodeType::Separator);
        assert_eq!(dc.nodes[5].item, 4);
        // p, r, x:A, y
        assert_eq!(dc.nodes[6].node_type, NodeType::Item);
        assert_eq!(dc.nodes[6].loc, 3);
        assert_eq!(dc.nodes[6].item, 2);
        assert_eq!(dc.nodes[6].color, 0);
        assert_eq!(dc.nodes[6].option, 1);
        assert_eq!(dc.nodes[7].node_type, NodeType::Item);
        assert_eq!(dc.nodes[7].loc, 11);
        assert_eq!(dc.nodes[7].item, 11);
        assert_eq!(dc.nodes[7].color, 0);
        assert_eq!(dc.nodes[7].option, 1);
        assert_eq!(dc.nodes[8].node_type, NodeType::Item);
        assert_eq!(dc.nodes[8].loc, 16);
        assert_eq!(dc.nodes[8].item, 15);
        assert_eq!(dc.nodes[8].color, 1);
        assert_eq!(dc.nodes[8].option, 1);
        assert_eq!(dc.nodes[9].node_type, NodeType::Item);
        assert_eq!(dc.nodes[9].loc, 22);
        assert_eq!(dc.nodes[9].item, 21);
        assert_eq!(dc.nodes[9].color, 0);
        assert_eq!(dc.nodes[9].option, 1);
        //
        assert_eq!(dc.nodes[10].node_type, NodeType::Separator);
        assert_eq!(dc.nodes[10].item, 4);
        // p, x:B
        assert_eq!(dc.nodes[11].node_type, NodeType::Item);
        assert_eq!(dc.nodes[11].loc, 4);
        assert_eq!(dc.nodes[11].item, 2);
        assert_eq!(dc.nodes[11].color, 0);
        assert_eq!(dc.nodes[11].option, 2);
        assert_eq!(dc.nodes[12].node_type, NodeType::Item);
        assert_eq!(dc.nodes[12].loc, 17);
        assert_eq!(dc.nodes[12].item, 15);
        assert_eq!(dc.nodes[12].color, 2);
        assert_eq!(dc.nodes[12].option, 2);
        //
        assert_eq!(dc.nodes[13].node_type, NodeType::Separator);
        assert_eq!(dc.nodes[13].item, 2);
        // q, x:A
        assert_eq!(dc.nodes[14].node_type, NodeType::Item);
        assert_eq!(dc.nodes[14].loc, 8);
        assert_eq!(dc.nodes[14].item, 7);
        assert_eq!(dc.nodes[14].color, 0);
        assert_eq!(dc.nodes[14].option, 3);
        assert_eq!(dc.nodes[15].node_type, NodeType::Item);
        assert_eq!(dc.nodes[15].loc, 18);
        assert_eq!(dc.nodes[15].item, 15);
        assert_eq!(dc.nodes[15].color, 1);
        assert_eq!(dc.nodes[15].option, 3);
        //
        assert_eq!(dc.nodes[16].node_type, NodeType::Separator);
        assert_eq!(dc.nodes[16].item, 2);
        // r, Y:B
        assert_eq!(dc.nodes[17].node_type, NodeType::Item);
        assert_eq!(dc.nodes[17].loc, 12);
        assert_eq!(dc.nodes[17].item, 11);
        assert_eq!(dc.nodes[17].color, 0);
        assert_eq!(dc.nodes[17].option, 4);
        assert_eq!(dc.nodes[18].node_type, NodeType::Item);
        assert_eq!(dc.nodes[18].loc, 23);
        assert_eq!(dc.nodes[18].item, 21);
        assert_eq!(dc.nodes[18].color, 2);
        assert_eq!(dc.nodes[18].option, 4);
        //
        assert_eq!(dc.nodes[19].node_type, NodeType::Separator);
        assert_eq!(dc.nodes[19].item, 2);
    }

    #[test]
    fn test_pick_primary() {
        let problem = get_problem_knuth();
        let dc = DancingCells::new(&problem).unwrap();
        let (item, size) = dc.pick_primary();
        assert_eq!(item, dc.items.list[1]);
        assert_eq!(size, 2);
    }

    #[test]
    fn test_hide_q() {
        let problem = get_problem_knuth();
        let mut dc = DancingCells::new(&problem).unwrap();
        // hide primary item q (item with position 7)
        dc.hide(&7, 0, false);
        // expect options with q to have other items removed
        // - p, q, x, y:A
        // - q, x:A
        assert_eq!(
            dc.items.sets[0..5],
            [0, 2, 11, 6, 1],
            "p has size 2 and 1 and 11 is swapped"
        );
        assert_eq!(dc.items.sets[5..9], [1, 2, 2, 14], "q no changes");
        assert_eq!(dc.items.sets[9..13], [2, 2, 7, 17], "r no changes");
        assert_eq!(
            dc.items.sets[13..19],
            [3, 2, 12, 8, 15, 3],
            "x has size 2. 3 and 15 swapped, 15 and 12 swapped"
        );
        assert_eq!(
            dc.items.sets[19..24],
            [4, 2, 18, 9, 4],
            "y has size 2 and 4 and 18 is swapped"
        );
        // verify nodes
        let loc = dc.get_option_locations();
        assert_eq!(loc[1..5], [4, 7, 18, 23], "p, q, x, y:A");
        assert_eq!(loc[6..10], [3, 11, 16, 22], "p, r, x:A, y");
        assert_eq!(loc[11..13], [2, 15], "p, x:B");
        assert_eq!(loc[14..16], [8, 17], "q, x:A");
        assert_eq!(loc[17..19], [12, 21], "r, Y:B");
    }

    #[test]
    fn test_hide_x_a() {
        let problem = get_problem_knuth();
        let mut dc = DancingCells::new(&problem).unwrap();
        // hide secondary item x (item with position 15) with color A (ix = 1)
        dc.hide(&15, 1, false);
        // expect options with x and other colors to have other items removed
        // p, q, x, y:A
        // p, x:B
        assert_eq!(
            dc.items.sets[0..5],
            [0, 1, 6, 11, 1],
            "p has size 1. 1 and 11 swapped, 11 and 6 swapped"
        );
        assert_eq!(
            dc.items.sets[5..9],
            [1, 1, 14, 2],
            "q has size 1. 2 and 14 swapped"
        );
        assert_eq!(dc.items.sets[9..13], [2, 2, 7, 17], "r no changes");
        assert_eq!(dc.items.sets[13..19], [3, 4, 3, 8, 12, 15], "x no changes");
        assert_eq!(
            dc.items.sets[19..24],
            [4, 2, 18, 9, 4],
            "y has size 2. 4 and 18 swapped"
        );
        // verify nodes
        let loc = dc.get_option_locations();
        assert_eq!(loc[1..5], [4, 8, 15, 23], "p, q, x, y:A");
        assert_eq!(loc[6..10], [2, 11, 16, 22], "p, r, x:A, y");
        assert_eq!(loc[11..13], [3, 17], "p, x:B");
        assert_eq!(loc[14..16], [7, 18], "q, x:A");
        assert_eq!(loc[17..19], [12, 21], "r, Y:B");
    }

    #[test]
    fn test_cover_primary_q() {
        let problem = get_problem_knuth();
        let mut dc = DancingCells::new(&problem).unwrap();
        // hide primary item q
        dc.cover_primary(&7);
        // q is deactivated in items
        assert_eq!(dc.items.list, [2, 21, 11, 15, 7]);
        assert_eq!(dc.items.active, 4);
        // expect options with q to have other items removed
        // - p, q, x, y:A
        // - q, x:A
        assert_eq!(
            dc.items.sets[0..5],
            [0, 2, 11, 6, 1],
            "p has size 2 and 1 and 11 is swapped"
        );
        assert_eq!(dc.items.sets[5..9], [4, 2, 2, 14], "q deactivated -> pos=4");
        assert_eq!(dc.items.sets[9..13], [2, 2, 7, 17], "r no changes");
        assert_eq!(
            dc.items.sets[13..19],
            [3, 2, 12, 8, 15, 3],
            "x has size 2. 3 and 15 swapped, 15 and 12 swapped"
        );
        assert_eq!(
            dc.items.sets[19..24],
            [1, 2, 18, 9, 4],
            "y moved when q activated (pos=1), y has size 2 and 4 and 18 is swapped"
        );
        // verify nodes
        let loc = dc.get_option_locations();
        assert_eq!(loc[1..5], [4, 7, 18, 23], "p, q, x, y:A");
        assert_eq!(loc[6..10], [3, 11, 16, 22], "p, r, x:A, y");
        assert_eq!(loc[11..13], [2, 15], "p, x:B");
        assert_eq!(loc[14..16], [8, 17], "q, x:A");
        assert_eq!(loc[17..19], [12, 21], "r, Y:B");
    }

    #[test]
    fn test_solve_levels() {
        // test solve levels until all solutions found
        let problem = get_problem_knuth();
        let mut dc = DancingCells::new(&problem).unwrap();
        let mut picked_rows = vec![];
        // LEVEL 0
        // get primary item
        let (primary_item_0, size) = dc.pick_primary();
        assert_eq!(primary_item_0, dc.items.list[1]);
        assert_eq!(size, 2);
        // cover primary item
        dc.cover_primary(&primary_item_0);
        // q is deactivated in items
        assert_eq!(dc.items.list, [2, 21, 11, 15, 7]);
        assert_eq!(dc.items.active, 4);
        assert_eq!(dc.items.primary_active, 2);
        // expect options with q to have other items removed
        // - p, q, x, y:A
        // - q, x:A
        assert_eq!(
            dc.items.sets[0..5],
            [0, 2, 11, 6, 1],
            "p has size 2 and 1 and 11 is swapped"
        );
        assert_eq!(dc.items.sets[5..9], [4, 2, 2, 14], "q deactivated -> pos=4");
        assert_eq!(dc.items.sets[9..13], [2, 2, 7, 17], "r no changes");
        assert_eq!(
            dc.items.sets[13..19],
            [3, 2, 12, 8, 15, 3],
            "x has size 2. 3 and 15 swapped, 15 and 12 swapped"
        );
        assert_eq!(
            dc.items.sets[19..24],
            [1, 2, 18, 9, 4],
            "y moved when q activated (pos=1), y has size 2 and 4 and 18 is swapped"
        );
        // verify nodes
        let loc = dc.get_option_locations();
        assert_eq!(loc[1..5], [4, 7, 18, 23], "p, q, x, y:A");
        assert_eq!(loc[6..10], [3, 11, 16, 22], "p, r, x:A, y");
        assert_eq!(loc[11..13], [2, 15], "p, x:B");
        assert_eq!(loc[14..16], [8, 17], "q, x:A");
        assert_eq!(loc[17..19], [12, 21], "r, Y:B");
        // get state
        let state_0 = dc.items.get_state();
        assert_eq!(state_0.active, 4, "4 active items");
        assert_eq!(state_0.sizes.len(), 4, "4 active items");
        assert_eq!(state_0.primary_active, 2, "2 active primary items");
        assert_eq!(state_0.sizes[0], (2, 2));
        assert_eq!(state_0.sizes[1], (21, 2));
        assert_eq!(state_0.sizes[2], (11, 2));
        assert_eq!(state_0.sizes[3], (15, 2));
        assert_eq!(state_0.active, 4);
        // try first option for q: p,q,x,y:A
        // - deactivate other option items in order:, x,y,p
        let other_option = dc.items.sets[primary_item_0];
        dc.deactivate_other_option_items(&other_option);
        assert_eq!(dc.items.active, 1, "1 active item - r");
        assert_eq!(dc.items.primary_active, 1, "1 active primary item - r");
        assert_eq!(
            dc.items.list,
            [11, 2, 21, 15, 7],
            "x no longer active, y swap with r, p swap with r"
        );
        assert_eq!(
            dc.items.sets[0..5],
            [1, 2, 11, 6, 1],
            "p deactivated -> pos=1"
        );
        assert_eq!(dc.items.sets[5..9], [4, 2, 2, 14], "q deactivated -> pos=4");
        assert_eq!(dc.items.sets[9..13], [0, 2, 7, 17], "r moved -> pos=0");
        assert_eq!(
            dc.items.sets[13..19],
            [3, 2, 12, 8, 15, 3],
            "x deactivated -> pos=3"
        );
        assert_eq!(
            dc.items.sets[19..24],
            [2, 2, 18, 9, 4],
            "y deactivated -> pos=2"
        );
        let status = dc.hide_other_option_items(&other_option);
        assert_eq!(status, false, "no options for item r");
        assert_eq!(dc.items.sets[0..5], [1, 0, 6, 11, 1]);
        assert_eq!(dc.items.sets[5..9], [4, 2, 2, 14]);
        assert_eq!(dc.items.sets[9..13], [0, 1, 17, 7]);
        assert_eq!(dc.items.sets[13..19], [3, 2, 12, 8, 15, 3]);
        assert_eq!(dc.items.sets[19..24], [2, 1, 18, 9, 4]);
        let loc = dc.get_option_locations();
        assert_eq!(loc[1..5], [4, 7, 18, 23], "p, q, x, y:A");
        assert_eq!(loc[6..10], [2, 12, 16, 22], "p, r, x:A, y");
        assert_eq!(loc[11..13], [3, 15], "p, x:B");
        assert_eq!(loc[14..16], [8, 17], "q, x:A");
        assert_eq!(loc[17..19], [11, 21], "r, Y:B");
        dc.items.reset(&state_0);
        assert_eq!(dc.items.active, 4);
        assert_eq!(dc.items.primary_active, 2);
        assert_eq!(dc.items.list, [11, 2, 21, 15, 7]);
        assert_eq!(dc.items.sets[0..5], [1, 2, 6, 11, 1]);
        assert_eq!(dc.items.sets[5..9], [4, 2, 2, 14]);
        assert_eq!(dc.items.sets[9..13], [0, 2, 17, 7]);
        assert_eq!(dc.items.sets[13..19], [3, 2, 12, 8, 15, 3]);
        assert_eq!(dc.items.sets[19..24], [2, 2, 18, 9, 4]);
        // try second option for q: q, x:A
        // - deactivate other option items in order:, x
        let other_option = dc.items.sets[primary_item_0 + 1];
        dc.deactivate_other_option_items(&other_option);
        assert_eq!(dc.items.active, 3, "p, r, y");
        assert_eq!(dc.items.primary_active, 2, "p, r");
        assert_eq!(dc.items.list, [11, 2, 21, 15, 7], "x no longer active");
        assert_eq!(dc.items.sets[0..5], [1, 2, 6, 11, 1]);
        assert_eq!(dc.items.sets[5..9], [4, 2, 2, 14]);
        assert_eq!(dc.items.sets[9..13], [0, 2, 17, 7]);
        assert_eq!(dc.items.sets[13..19], [3, 2, 12, 8, 15, 3]);
        assert_eq!(dc.items.sets[19..24], [2, 2, 18, 9, 4]);
        let status = dc.hide_other_option_items(&other_option);
        assert_eq!(status, true, "go to next level");
        assert_eq!(dc.items.sets[0..5], [1, 1, 6, 11, 1]);
        assert_eq!(dc.items.sets[5..9], [4, 2, 2, 14]);
        assert_eq!(dc.items.sets[9..13], [0, 2, 17, 7]);
        assert_eq!(dc.items.sets[13..19], [3, 2, 12, 8, 15, 3]);
        assert_eq!(dc.items.sets[19..24], [2, 2, 18, 9, 4]);
        let loc = dc.get_option_locations();
        assert_eq!(loc[1..5], [4, 7, 18, 23], "p, q, x, y:A");
        assert_eq!(loc[6..10], [2, 12, 16, 22], "p, r, x:A, y");
        assert_eq!(loc[11..13], [3, 15], "p, x:B");
        assert_eq!(loc[14..16], [8, 17], "q, x:A");
        assert_eq!(loc[17..19], [11, 21], "r, Y:B");
        // LEVEL 1
        picked_rows.push(dc.nodes[dc.items.sets[primary_item_0 + 1]].option);
        // get primary item p
        let (primary_item_1, size) = dc.pick_primary();
        assert_eq!(primary_item_1, dc.items.list[1]);
        assert_eq!(size, 1);
        // cover primary item p
        dc.cover_primary(&primary_item_1);
        // p is deactivated in items
        assert_eq!(dc.items.list, [11, 21, 2, 15, 7]);
        assert_eq!(dc.items.active, 2);
        assert_eq!(dc.items.primary_active, 1);
        // expect options with p to have other items removed
        // - p, r, x:A, y
        assert_eq!(dc.items.sets[0..5], [2, 1, 6, 11, 1]);
        assert_eq!(dc.items.sets[5..9], [4, 2, 2, 14]);
        assert_eq!(dc.items.sets[9..13], [0, 1, 17, 7]);
        assert_eq!(dc.items.sets[13..19], [3, 2, 12, 8, 15, 3]);
        assert_eq!(dc.items.sets[19..24], [1, 1, 18, 9, 4]);
        // verify nodes
        let loc = dc.get_option_locations();
        // separators
        assert_eq!(loc[1..5], [4, 7, 18, 23], "p, q, x, y:A");
        assert_eq!(loc[6..10], [2, 12, 16, 22], "p, r, x:A, y");
        assert_eq!(loc[11..13], [3, 15], "p, x:B");
        assert_eq!(loc[14..16], [8, 17], "q, x:A");
        assert_eq!(loc[17..19], [11, 21], "r, Y:B");
        // get state
        let state_1 = dc.items.get_state();
        assert_eq!(state_1.active, 2, "2 active items");
        assert_eq!(state_1.sizes.len(), 2, "2 active items");
        assert_eq!(state_1.primary_active, 1, "1 active primary items");
        assert_eq!(state_1.sizes[0], (11, 1));
        assert_eq!(state_1.sizes[1], (21, 1));
        // try first option for p: p, r, x:A, y
        // - deactivate other option items in order: r,y
        let other_option = dc.items.sets[primary_item_1];
        dc.deactivate_other_option_items(&other_option);
        assert_eq!(dc.items.list, [21, 11, 2, 15, 7]);
        assert_eq!(dc.items.active, 0);
        assert_eq!(dc.items.primary_active, 0);
        assert_eq!(dc.items.sets[0..5], [2, 1, 6, 11, 1]);
        assert_eq!(dc.items.sets[5..9], [4, 2, 2, 14]);
        assert_eq!(dc.items.sets[9..13], [1, 1, 17, 7]);
        assert_eq!(dc.items.sets[13..19], [3, 2, 12, 8, 15, 3]);
        assert_eq!(dc.items.sets[19..24], [0, 1, 18, 9, 4]);
        let status = dc.hide_other_option_items(&other_option);
        assert_eq!(status, true, "go to next level");
        assert_eq!(dc.items.sets[0..5], [2, 1, 6, 11, 1]);
        assert_eq!(dc.items.sets[5..9], [4, 2, 2, 14]);
        assert_eq!(dc.items.sets[9..13], [1, 1, 17, 7]);
        assert_eq!(dc.items.sets[13..19], [3, 2, 12, 8, 15, 3]);
        assert_eq!(dc.items.sets[19..24], [0, 0, 18, 9, 4]);
        let loc = dc.get_option_locations();
        assert_eq!(loc[1..5], [4, 7, 18, 23], "p, q, x, y:A");
        assert_eq!(loc[6..10], [2, 12, 16, 22], "p, r, x:A, y");
        assert_eq!(loc[11..13], [3, 15], "p, x:B");
        assert_eq!(loc[14..16], [8, 17], "q, x:A");
        assert_eq!(loc[17..19], [11, 21], "r, Y:B");
        // LEVEL 2
        picked_rows.push(dc.nodes[dc.items.sets[primary_item_1]].option);
        assert_eq!(picked_rows, [3, 1])
    }

    fn get_problem_knuth() -> Problem {
        let primary_items = vec!["p", "q", "r"];
        let secondary_items = vec!["x", "y"];
        let options = vec![
            Option::new_validated("p q x y:A", &vec!["p", "q"], &vec![("x", ""), ("y", "A")]),
            Option::new_validated("p r x:A y", &vec!["p", "r"], &vec![("x", "A"), ("y", "")]),
            Option::new_validated("p x:B", &vec!["p"], &vec![("x", "B")]),
            Option::new_validated("q x:A", &vec!["q"], &vec![("x", "A")]),
            Option::new_validated("r y:B", &vec!["r"], &vec![("y", "B")]),
        ];
        Problem::new_validated(&primary_items, &secondary_items, &options)
    }

    #[test]
    fn test_knuth() {
        let problem = get_problem_knuth();
        let mut dc = DancingCells::new(&problem).unwrap();
        let solutions = dc.solve_all();
        assert_eq!(solutions.count(), 1);
        assert_eq!(solutions.first().unwrap().clone(), ["p r x:A y", "q x:A"]);
    }

    fn get_n_queen_problem(n: i32) -> Problem {
        // primary items: a single queen in each row and column
        let mut primary_items_owned = vec![];
        for x in 1..(n + 1) {
            primary_items_owned.push(format!("r{}", x));
            primary_items_owned.push(format!("c{}", x));
        }
        let primary_items = primary_items_owned.iter().map(|i| i.as_str()).collect();

        // secondary_items: at most one queen in each diagonal
        let mut secondary_items_owned = vec![];
        for x in 1..(n * 2) {
            secondary_items_owned.push(format!("u{}", x));
            secondary_items_owned.push(format!("d{}", x));
        }
        let secondary_items = secondary_items_owned.iter().map(|i| i.as_str()).collect();

        // an option for each field on the board
        let mut options = vec![];
        for x in 1..(n + 1) {
            for y in 1..(n + 1) {
                options.push(Option::new_validated(
                    format!("{},{}", x, y).as_str(),
                    &vec![format!("r{}", x).as_str(), format!("c{}", y).as_str()],
                    &vec![
                        (format!("u{}", n - x + y).as_str(), ""),
                        (format!("d{}", x + y - 1).as_str(), ""),
                    ],
                ));
            }
        }

        Problem::new_validated(&primary_items, &secondary_items, &options)
    }

    #[test]
    fn test_8queen() {
        let problem = get_n_queen_problem(8);
        let mut dc_all = DancingCells::new(&problem).unwrap();
        let solutions = dc_all.solve_all();
        assert_eq!(solutions.count(), 92);
        let mut dc_first = DancingCells::new(&problem).unwrap();
        let solutions = dc_first.solve_first();
        assert_eq!(solutions.count(), 1);
    }

    #[test]
    fn test_4queen() {
        let problem = get_n_queen_problem(4);
        let mut dc_all = DancingCells::new(&problem).unwrap();
        let solutions = dc_all.solve_all();
        assert_eq!(solutions.all().len(), 2);
        let sol_str = solutions
            .all()
            .iter()
            .map(|s| s.iter().map(|x| format!("({})", x)).collect::<String>())
            .collect::<Vec<String>>();
        assert!(sol_str.contains(&"(1,2)(2,4)(3,1)(4,3)".to_string()));
        let mut dc_first = DancingCells::new(&problem).unwrap();
        let solutions = dc_first.solve_first();
        assert_eq!(solutions.all().len(), 1);
    }

    fn get_box(r: i32, c: i32) -> i32 {
        // derive 4x4 sudoku box from row and column
        let box_row = (r - 1) / 2;
        let box_col = (c - 1) / 2 + 1;
        box_row * 2 + box_col
    }

    fn get_sudoku_4x4_problem() -> Problem {
        // 4 x 4 sudoku with known cells:
        // r1c2#4, r2c4#1, r4c3#1, r4c4#3
        // | |4| | |
        // | | | |1|
        // | | | | |
        // | | |1|3|

        // solution:
        // |1|4|3|2|
        // |2|3|4|1|
        // |3|1|2|4|
        // |4|2|1|3|

        // all (primary) items
        let mut primary_items_owned = vec![];
        for x in 1..5 {
            for y in 1..5 {
                // all cells filled: r1c1, r1c2, ...
                primary_items_owned.push(format!("r{}c{}", x, y));
                // all 4 numbers in all 4 rows: r1#1, r1#2, ...
                primary_items_owned.push(format!("r{}#{}", x, y));
                // all 4 numbers in all 4 columns: c1#1, c1#2, ...
                primary_items_owned.push(format!("c{}#{}", x, y));
                // all 4 numbers in all 4 boxes: b1#1, b1#2, ...
                primary_items_owned.push(format!("b{}#{}", x, y));
            }
        }
        let primary_items = primary_items_owned.iter().map(|i| i.as_str()).collect();

        // options from filled cells
        let mut options = vec![
            Option::new_validated("r1c2#4", &vec!["r1c2", "r1#4", "c2#4", "b1#4"], &vec![]),
            Option::new_validated("r2c4#1", &vec!["r2c4", "r2#1", "c4#1", "b2#1"], &vec![]),
            Option::new_validated("r4c3#1", &vec!["r4c3", "r4#1", "c3#1", "b4#1"], &vec![]),
            Option::new_validated("r4c4#3", &vec!["r4c4", "r4#3", "c4#3", "b4#3"], &vec![]),
        ];

        // options from empty cells
        for r in 1..5 {
            for c in 1..5 {
                // avoid filled cells
                if ![(1, 2), (2, 4), (4, 3), (4, 4)].contains(&(r, c)) {
                    for n in 1..5 {
                        options.push(Option::new_validated(
                            format!("r{}c{}#{}", r, c, n).as_str(),
                            &vec![
                                format!("r{}c{}", r, c).as_str(),
                                format!("r{}#{}", r, n).as_str(),
                                format!("c{}#{}", c, n).as_str(),
                                format!("b{}#{}", get_box(r, c), n).as_str(),
                            ],
                            &vec![],
                        ));
                    }
                }
            }
        }

        let secondary_items = vec![];
        Problem::new_validated(&primary_items, &secondary_items, &options)
    }

    #[test]
    fn test_sudoku_4x4() {
        let problem = get_sudoku_4x4_problem();
        let mut dc = DancingCells::new(&problem).unwrap();
        dc.solve_step(vec![]);
        assert_eq!(dc.solutions.len(), 1);
        let solutions = dc.get_solutions();
        assert_eq!(solutions.count(), 1);
        let mut solution = solutions.first().unwrap().clone();
        solution.sort();
        assert_eq!(solution[0], "r1c1#1");
        let sol_string = solution
            .iter()
            .map(|x| x.chars().last().unwrap())
            .collect::<String>();
        assert_eq!(sol_string, "1432234131244213");
    }

    #[test]
    fn test_get_solutions() {
        let problem = get_problem_knuth();
        let mut dc = DancingCells::new(&problem).unwrap();
        dc.solutions = vec![vec![3, 1]];
        let solutions = dc.get_solutions();
        assert_eq!(solutions.count(), 1);
        let first = solutions.first().unwrap();
        assert_eq!(first.len(), 2);
        assert_eq!(first[0], "p r x:A y");
        assert_eq!(first[1], "q x:A");
    }
}