algoxcc 0.1.2

use std::collections::{HashMap, HashSet};

/// Solver step state for Items
#[derive(Debug, PartialEq)]
pub(crate) struct State {
    /// Number of primary active items in list
    pub(crate) primary_active: usize,
    /// Number of (all) active items in list
    pub(crate) active: usize,
    /// Size (number of active options with item) for all items in list
    ///
    /// Two element tuples with item from list and size
    pub(crate) sizes: Vec<(usize, usize)>,
}

/// Solver items
#[derive(Debug)]
pub(crate) struct Items {
    /// List of items linking to item in sets
    pub(crate) list: Vec<usize>,
    /// Sets of items linked to options in nodes
    ///
    /// Where list of items link to index ix in sets, and
    /// - ix (and ix+) link to options in nodes with item
    ///
    /// and each ix have two control positions:s
    /// - ix-1: current size (number of active options with item)
    /// - ix-2: current position in (link back to) item list
    pub(crate) sets: Vec<usize>,
    /// Set with primary items in problem
    pub(crate) primary_items: HashSet<usize>,
    /// Number of (all) currently active items
    pub(crate) active: usize,
    /// Number of currently active primary items
    pub(crate) primary_active: usize,
    /// Storage for previous value of active
    pub(crate) previous_active: usize,
}

impl Items {
    /// Initialize items
    ///
    /// # Attributes
    ///
    /// - `names`: list of item names
    /// - `sizes`: map with item name and number of options it belongs to
    /// - `primary`: set of names of primary items
    ///
    pub(crate) fn new(
        names: &Vec<&String>,
        sizes: &HashMap<&String, usize>,
        primary: &HashSet<&String>,
    ) -> Self {
        // sets with 2 control positions
        let pos = 2;
        let mut col_ix = pos;
        let mut list: Vec<usize> = Vec::new();
        let mut primary_items = HashSet::new();
        let mut sets: Vec<usize> = Vec::new();

        for i in 0..names.len() {
            let item = names[i];
            list.push(col_ix);
            if primary.contains(item) {
                primary_items.insert(col_ix);
            }
            // next index = current index + current size + control
            col_ix += pos + sizes[item];
            // column position (initially same as position)
            sets.push(i);
            // size
            sets.push(sizes[item]);
            // links to nodes (initial 0)
            for _ in 0..sizes[item] {
                sets.push(0);
            }
        }

        let active = list.len();
        let previous_active = list.len();
        let primary_active = primary_items.len();
        Self {
            list,
            sets,
            primary_items,
            active,
            previous_active,
            primary_active,
        }
    }

    /// Returns true if an item from list is primary
    pub(crate) fn is_primary(&self, item: &usize) -> bool {
        self.primary_items.contains(&item)
    }

    /// Get the current state of items
    pub(crate) fn get_state(&self) -> State {
        let mut sizes = vec![];
        for item_ix in 0..self.active {
            sizes.push((self.list[item_ix], self.get_size(&self.list[item_ix])));
        }
        State {
            sizes,
            active: self.active,
            primary_active: self.primary_active,
        }
    }

    /// Reset items to a previous state
    pub(crate) fn reset(&mut self, state: &State) {
        // reset items
        self.active = state.active;
        self.primary_active = state.primary_active;
        // reset item options
        for (item, size) in &state.sizes {
            self.set_size(item, *size);
        }
    }

    /// Get an item's position in list
    pub(crate) fn get_position(&self, item: &usize) -> &usize {
        &self.sets[item - 2]
    }

    /// Swap position in list of two items in sets
    pub(crate) fn swap_position(&mut self, item_a: &usize, item_b: &usize) {
        self.sets.swap(item_a - 2, item_b - 2);
    }

    /// Get the size of an item (number of active options with item)
    pub(crate) fn get_size(&self, item: &usize) -> usize {
        self.sets[item - 1]
    }

    /// Set the size (number of active options with item) of an item from list
    pub(crate) fn set_size(&mut self, item: &usize, size: usize) {
        self.sets[item - 1] = size;
    }

    /// Is input item active in list
    pub(crate) fn is_active(&self, item: &usize) -> bool {
        self.get_position(item) < &self.active
    }

    /// Was input item active in state
    pub(crate) fn was_active(&self, item: &usize) -> bool {
        self.get_position(item) < &self.previous_active
    }

    /// If no more primary items active we have foudn a solution
    pub(crate) fn solution_found(&self) -> bool {
        self.primary_active == 0
    }

    fn is_last_active(&self, item: &usize) -> bool {
        item == &self.list[self.active - 1]
    }

    /// Deactivate an item
    ///
    /// Deactivates an item in list and update positions in
    /// sets if needed.
    pub(crate) fn deactivate_item(&mut self, item: &usize) {
        // no need to activate if item not active
        if self.is_active(item) {
            // no need to swap as item already last
            if !self.is_last_active(item) {
                // swap with last active
                let item_ix = *self.get_position(item);
                let last_active = self.list[self.active - 1];
                self.list.swap(item_ix, self.active - 1);
                self.swap_position(&item, &last_active);
            }

            // reduce active count by 1
            self.active -= 1;

            // if primary reduce primary active count by 1
            if self.is_primary(item) {
                self.primary_active -= 1;
            }
        }
    }
}

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

    fn get_items() -> Items {
        let s: Vec<String> = vec!["i0", "i1", "i2", "i3"]
            .iter()
            .map(|x| x.to_string())
            .collect();
        let names = vec![&s[1], &s[2], &s[3]];
        let sizes: HashMap<&String, usize> = [(&s[1], 1), (&s[2], 2), (&s[3], 3)].into();
        let primary: HashSet<&String> = [&s[1], &s[2]].into();
        Items::new(&names, &sizes, &primary)
    }

    #[test]
    fn test_items() {
        let items = get_items();

        // initial version
        assert_eq!(items.list, [2, 5, 9]);
        assert_eq!(items.sets, [0, 1, 0, 1, 2, 0, 0, 2, 3, 0, 0, 0]);
        assert_eq!(items.primary_items, [2, 5].into());
        assert_eq!(items.active, 3);
        assert_eq!(items.previous_active, 3);
        assert_eq!(items.primary_active, 2);

        let last_item = items.list.last().unwrap();
        assert_eq!(items.get_position(last_item), &2);
        assert_eq!(items.get_size(last_item), 3);
        assert!(items.is_active(last_item));
        assert!(items.was_active(last_item));
        assert!(!items.solution_found());
        assert_eq!(
            items.get_state(),
            State {
                sizes: vec![(2, 1), (5, 2), (9, 3)],
                primary_active: 2,
                active: 3
            }
        )
    }

    #[test]
    fn test_deactivate_last_item() {
        let mut items = get_items();
        let last_item = *items.list.last().unwrap();
        items.deactivate_item(&last_item);
        assert_eq!(items.list, [2, 5, 9]);
        assert_eq!(items.sets, [0, 1, 0, 1, 2, 0, 0, 2, 3, 0, 0, 0]);
        assert_eq!(items.primary_items, [2, 5].into());
        assert_eq!(items.active, 2);
        assert_eq!(items.previous_active, 3);
        assert_eq!(items.primary_active, 2);
    }

    #[test]
    fn test_deactivate_first_item() {
        let mut items = get_items();
        let first_item = *items.list.first().unwrap();
        items.deactivate_item(&first_item);
        assert_eq!(items.list, [9, 5, 2]);
        assert_eq!(items.sets, [2, 1, 0, 1, 2, 0, 0, 0, 3, 0, 0, 0]);
        assert_eq!(items.primary_items, [2, 5].into());
        assert_eq!(items.active, 2);
        assert_eq!(items.previous_active, 3);
        assert_eq!(items.primary_active, 1);
    }

    #[test]
    fn test_get_state_reset_state() {
        let mut items = get_items();
        let state = items.get_state();
        let first_item = *items.list.first().unwrap();
        items.deactivate_item(&first_item);
        assert_eq!(
            items.get_state(),
            State {
                sizes: vec![(9, 3), (5, 2)],
                primary_active: 1,
                active: 2
            }
        );
        let current_last_item = items.list[1];
        assert_eq!(current_last_item, 5);
        items.set_size(&current_last_item, 1);
        assert_eq!(
            items.get_state(),
            State {
                sizes: vec![(9, 3), (5, 1)],
                primary_active: 1,
                active: 2
            }
        );
        items.reset(&state);
        assert_eq!(
            items.get_state(),
            State {
                sizes: vec![(9, 3), (5, 2), (2, 1)],
                primary_active: 2,
                active: 3
            }
        );
    }
}