tord 0.1.7

#![allow(dead_code, unused)]

use std::fmt::Debug;
use std::collections::hash_map::Entry;
use std::fmt::{LowerExp, Write};
use std::hash::Hash;
use std::collections::{HashMap, HashSet};
use std::cmp::Ord;
use std::println;

///
/// Simple data structure to store Transitive relations
/// 
/// Example
/// ```rust
/// use tord::Tord;
/// 
/// fn main() {
///     let mut t = Tord::new();
///     t.insert(5, 6);
///     t.insert(6, 10);
///     t.insert(10, 19);
/// 
///     // We did not add (19, 6) but because of transitivity,
///     // this relation exists
///     match t.check_relation(19, 6) {
///         Some(b) => {
///             if b {
///                 println!("Relation exists");
///             } else {
///                 println!("Not a valid relation");
///             }
///         }
///         
///         None => {
///             println!("Relation does not exist");
///         }
///     }
/// }
/// ```
/// 

#[derive(Debug, PartialEq)]
pub enum TordError {
    IncorrectOrdering,
    RelationalCycle
}

impl std::fmt::Display for TordError{
    fn fmt(&self, w: &mut std::fmt::Formatter<'_>) -> Result<(), std::fmt::Error> {
        match self {
            TordError::IncorrectOrdering => w.write_str("Incorrect ordering"),
            TordError::RelationalCycle => w.write_str("Relational cycle detected")
        }
    }
}

/// Data structure to store transitive relations
#[derive(Debug)]
pub struct Tord<T: Hash + PartialEq + Eq + PartialOrd + Clone + Debug> {
    relations: HashMap<T, HashSet<T>>,
}

impl<T: Hash + PartialEq + Eq + PartialOrd + Clone + Debug> Tord<T> {
    /// Creates a new object
    pub fn new() -> Self {
        Self {
            relations: HashMap::new()
        }
    }

    /// Inserts a relation to the data structure
    pub fn insert(&mut self, lower: T, higher: T) -> Result<(), TordError> {
        // 1. If Equal, its ok
        if lower == higher {
            return Ok(());
        }

        // 2. Find relations from higher->lower and check if the relation exists
        let res = match self.relations.get(&higher) {
            Some(e) => e.contains(&lower),
            None => false,
        };

        // Relation exists
        if res {
            return Ok(());
        }

        // 3. Find relations from lower->higher and check if the relaiton exists
        let res = match self.relations.get(&lower) {
            Some(e) => e.contains(&higher),
            None => false,
        };

        // Relation exists and should be invalid
        if res {
            return Err(TordError::IncorrectOrdering);
        }

        // 4. Update all previous relations
        
        // 4.a Create higher->lower relation
        {
            match self.relations.entry(higher.clone()) {
                Entry::Occupied(mut v) => {
                    v.get_mut().insert(lower.clone());
                },
                Entry::Vacant(e) => {
                    let mut hs = HashSet::new();
                    hs.insert(lower.clone());
                    e.insert(hs);
                }
            }
        }


        // 4.b Get lower->lowers into higher
        {
            if let Some(vals) = self.relations.get(&lower) {
                let c = vals.clone();

                let hset = self.relations.get_mut(&higher).unwrap();

                for val in c.iter() {
                    if *val == higher {
                        return Err(TordError::RelationalCycle);
                    }

                    hset.insert(val.clone());
                } 
                
            }
        }

        // 4.c Handle lessers
        // 4.d Handle greater
        {
            let mut lesser_vec = vec![];
            self.lessers(&mut lesser_vec, lower.clone());

            if let Some(vals) = self.relations.get_mut(&higher) {
                for val in lesser_vec.iter() {
                    if *val == higher {
                        return Err(TordError::RelationalCycle);
                    }

                    vals.insert(val.clone());
                }
            }

            for (k, v) in self.relations.iter_mut() {
                if v.contains(&higher) {
                    for val in lesser_vec.iter() {
                        v.insert(val.clone());
                    }
                }
            }
        }

        return Ok(());
    }

    /// Check if relation exists
    /// Returns `Some` and either `true` or `false` depending on if the relation was found.
    /// Otherwise, returns `None` when no relations for a `higher->lower` relation is found.
    pub fn check_relation(&self, lower: T, higher: T) -> Option<bool> {
        if lower == higher {
            return Some(true);
        }

        match self.relations.get(&higher) {
            Some(v) => return Some(v.contains(&lower)),
            None => return None,
        }
    }

    /// Check the number of independent entry records in data structure.
    /// This function does not represent the actual number of relations that the structure
    /// holds at runtime.
    pub fn size(&self) -> usize {
        self.relations.len()
    }

    fn lessers(&mut self, result: &mut Vec<T>, lower: T) {
        if result.contains(&lower) {
            return;
        }

        match self.relations.get(&lower.clone()) {
            None => return,
            Some(lesser_vals) => {
                let lesser_vals = lesser_vals.clone();

                for val in lesser_vals {
                    if !result.contains(&val) {
                        result.push(val.clone());
                        self.lessers(result, val);    
                    }
                }
            }
        }
    }
}


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

    #[test]
    fn insert() {
        let mut tord = Tord::new();

        tord.insert(5, 6);
        assert_eq!(tord.size(), 1);


        tord.insert(6, 10);
        assert_eq!(tord.size(), 2);

        tord.insert(10, 1);
        assert_eq!(tord.size(), 3);
    }

    #[test]
    fn check_relation() {
        let mut tord = Tord::new();

        tord.insert(5, 6);
        tord.insert(6, 10);
        tord.insert(10, 1);

        tord.insert(0, 0);

        assert_eq!(tord.check_relation(0, 0), Some(true));
        assert_eq!(tord.check_relation(5, 6), Some(true));
        assert_eq!(tord.check_relation(6, 5), None);

        // assert_eq!(tord.check_relation(5, 6), Some(true));
        // assert_eq!(tord.check_relation(6, 5), Some(false));
        // assert_eq!(tord.check_relation(10, 5), Some(false));
        // assert_eq!(tord.check_relation(6, 9), Some(false));
        // assert_eq!(tord.check_relation(100, 101), None);
    }

    #[test]
    fn relational_cycles() {
        let mut tord = Tord::new();

        println!("1. {:?}", tord);
        assert_eq!(tord.insert(2, 3).is_ok(), true);
        println!("2. {:?}", tord);
        assert_eq!(tord.insert(0, 1).is_ok(), true);
        println!("3. {:?}", tord);
        assert_eq!(tord.insert(1, 2).is_ok(), true);
        println!("4. {:?}", tord);
        assert_eq!(tord.insert(3, 0).unwrap_err(), TordError::IncorrectOrdering);
        println!("5. {:?}", tord);
    }
}