luka 0.4.0

use std::fmt;

#[allow(clippy::upper_case_acronyms)]
pub struct DSU {
    parents: Vec::<usize>,
    ranks: Vec::<usize>
}

#[allow(clippy::upper_case_acronyms)]
#[derive(Debug, Clone)]
pub struct DSUError {
    msg: String
}

impl DSUError {
    fn new(msg: &str) -> Self {
        DSUError{
            msg: msg.to_string()
        }
    }
}

impl fmt::Display for DSUError {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(f, "{}", self.msg)
    }
}

impl DSU {
    pub fn new(n: usize) -> Self {
        DSU {
            parents: vec![0; n],
            ranks: vec![1; n]
        }
    }
    pub fn make_set(&mut self, value: usize) -> Result<(), DSUError> {
        if value == 0 {
            return Err(DSUError::new("Cannot create item with value 0"));
        }
        if value < self.parents.len() {
            self.parents[value] = value;
            return Ok(());
        }
        Err(DSUError::new("Cannot create item exceeds set size"))
    }

    pub fn find_set(&mut self, value: usize) -> Option<usize> {
        if value >= self.parents.len() || value == 0 {
            return None;
        }
        if value == self.parents[value] {
            return Some(value);
        }
        match self.find_set(self.parents[value]) {
            Some(next) => {
                self.parents[value] = next;
                match next {
                    0 => None,
                    _ => Some(next)
                }
            }
            None => None
        }
    }

    pub fn union_sets(&mut self, first: usize, second: usize) -> Result<(), DSUError>{
        let first = self.find_set(first);
        let second = self.find_set(second);
        if first.is_none() || second.is_none() {
            return Err(DSUError::new("Some elements are missing from the set. Unification is not possible"));
        }
        let first = first.unwrap();
        let second = second.unwrap();
        if first != second {
            if self.ranks[first] < self.ranks[second] {
                self.ranks.swap(first, second);
            }
            self.parents[second] = first;
            if self.ranks[first] == self.ranks[second] {
                self.ranks[first] += 1;
            }
        }
        Ok(())
    }
}

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

    #[test]
    fn test_dsu() {
        let mut dsu = DSU::new(10);

        dsu.make_set(1).unwrap();
        dsu.make_set(2).unwrap();
        dsu.make_set(3).unwrap();
        dsu.make_set(7).unwrap();
        dsu.make_set(8).unwrap();

        dsu.union_sets(1, 2).unwrap();
        dsu.union_sets(2, 3).unwrap();
        dsu.union_sets(2, 7).unwrap();

        assert_eq!(dsu.union_sets(0, 7).is_err(), true);
        assert_eq!(dsu.find_set(2).unwrap(), dsu.find_set(7).unwrap());
        assert_eq!(dsu.find_set(1).unwrap(), dsu.find_set(3).unwrap());
        assert_ne!(dsu.find_set(1).unwrap(), dsu.find_set(8).unwrap());
        assert_eq!(dsu.find_set(29), None);
        assert_eq!(dsu.union_sets(9, 2).is_err(), true);
    }

    #[test]
    #[should_panic]
    fn test_dsu_panic() {
        let mut dsu = DSU::new(10);
        dsu.make_set(77).unwrap();
        assert!(dsu.make_set(77).is_err())
    }
}