keytree/

path.rs

//! A namespace represents a position on a multi-leaf tree. There is only one root node. A
//! namespace can look like `abc::def::ghi`, which implictly means `abc[0]::def[0]::ghi[..]`. The
//! index `abc[0]`represents the first child leaf of a node. `ghi[..]` refers to all child leaves
//! of a node.

use core::cmp::Ordering;
use core::fmt;
use core::hash::{Hash, Hasher};

#[derive(Debug, PartialEq)]
pub enum PathError {
    MultipleMatch,
    NoMatch,
    NoRemainder,
    NotUnique,
    OutOfBounds,
    Parse(String, usize),
    PathNotUnique,
    Remove,
    RootIndex,
    SegmentImmut,
}

impl fmt::Display for PathError {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        match self {
            PathError::MultipleMatch   => write!(f, "Multiple matches."),
            PathError::NoMatch         => write!(f, "No match."),
            PathError::NoRemainder     => write!(f, "No remainder."),
            PathError::NotUnique       => write!(f, "Path not unique."),
            PathError::OutOfBounds     => write!(f, "Index out of bounds."),
            PathError::Parse(s, pos)   => write!(f, "Could not parse \"{}\" at position {}.", s, pos),
            PathError::PathNotUnique   => write!(f, "Can't get last index of non-unique path."),
            PathError::Remove          => write!(f, "Removed too many segments."),
            PathError::RootIndex       => write!(f, "Root index is not zero."),
            PathError::SegmentImmut    => write!(f, "Cannot mutate unique segment."),
        }
    }
}

// Parser state.
enum PS {
    Segment,
    Separator,
}

// Represents a pointer into the Path String. Also represents a node in a tree. If the node
// has one leaf it is Unique. If the node has multiple leaves it is Mult.
#[derive(Clone)]
pub struct Segment {
    pub index:  usize,
    start:      usize,
    end:        usize,
}

impl Segment {

    fn new(index: usize, start: usize, end: usize) -> Segment {
        Segment {
            index:  index,
            start:  start,
            end:    end,
        }
    }

    // Shifts the pointer into the string to the right by n. Used by append functions. 
    fn right_shift(&self, n: usize) -> Segment {
        Segment {
            start:  self.start + n,
            end:    self.end + n,
            index:  self.index,
        }
    }

    // Shifts the pointer into the string to the left by n.
    fn left_shift(&self, n: usize) -> Segment {
        Segment {
            start:  self.start - n,
            end:    self.end - n,
            index:  self.index,
        }
    }
}

impl fmt::Debug for Segment {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "({}, {})[{}]", self.start, self.end, self.index)
    }
}

// Represents the name of a path in a tree with a single leaf node.
#[derive(Clone)]
pub struct UniquePath {
    s:          String,
    segments:   Vec<Segment>,
}

impl UniquePath {

    pub fn new() -> Self {
        UniquePath {
            s:          String::new(),
            segments:   Vec::new(),
        }
    }

    pub fn from(s: &str) -> Result<Self, PathError> {
        Ok(
            NonUniquePath::from(s)?
                .unique(0)
        )
    }

    // Sets the path to non-unique.
    pub fn non_unique(self) -> NonUniquePath {
        NonUniquePath {
            s:          self.s,
            segments:   self.segments,
        }
    }

    // Sets the last index to `index`.
    pub fn set_last_index(&mut self, index: usize) {
        let len = self.len() - 1;
        self.segments[len].index = index;
    }

    pub fn index(&self, index: usize) -> usize {
        if index > self.len() - 1 {
            panic!("Out of bounds.")
        } else {
            self.segments[index].index
        }
    }

    // Checks the equality of two UniquePaths as NonUniquePaths, i.e. ignoring the last index. 
    pub fn eq_base(&self, other: &UniquePath) -> bool {
        self.clone().non_unique() == other.clone().non_unique()
    }

    // Return the last index.
    pub fn last_index(&self) -> usize {
        self.segments[self.len() - 1].index
    }

    pub fn is_empty(&self) -> bool {
        self.s.is_empty()
    }
    
    pub fn segment_str(&self, n: usize) -> &str {
        &self.s[self.segments[n].start..=self.segments[n].end]
    }

    /// Returns the number of segments in a namespace.
    ///
    pub fn len(&self) -> usize {
        self.segments.len()
    }

    // Appends `other` to `self`, consuming `other`. Returns an error if `self` is not a unique
    // path, or if the root of `other` does not have an index of 0.
    pub fn append_unique(self, other: &UniquePath) -> UniquePath {

        if self.is_empty()  { return other.clone() };
        if other.is_empty() { return self };

        // Handle segments.

        let mut segments = self.segments;
        let rshift = self.s.len() + 2;
        for seg in other.segments.iter() {
            segments.push(seg.right_shift(rshift));
        }

        // Handle s.

        let mut s = self.s;
        if s != "" { s.push_str("::") };
        s.push_str(&other.s);

        UniquePath {
            s:          s,
            segments:   segments,
        }
    }

    // Consumes self and appends a NonUniquePath with other appended. If `other` is empty then the
    // result will be unique which contradictions the return type, so the function fails if `other`
    // is empty.
    pub fn append_non_unique(self, other: &NonUniquePath) -> NonUniquePath {

        if self.is_empty()  { return other.clone() };
        if other.is_empty() { panic!("other must not be empty.") };

        // Handle segments.
        let mut segments = self.segments;
        let rshift = self.s.len() + 2;
        for seg in other.segments.iter() {
            segments.push(seg.right_shift(rshift));
        }

        // Handle s.
        let mut s = self.s;
        if s != "" { s.push_str("::") };
        s.push_str(&other.s);

        // Return
        NonUniquePath {
            s:          s,
            segments:   segments,
        }
    }

    // Truncate's behaviour is a little unusual in that it returns a new value. This is because for
    // both Self as UniquePath and Self as NonUnique path, this function should return a
    // UniquePath. Also n has to be between 0 and length - 1, so that truncate can perform
    // consistently on both UniquePath and NonUniquePath. Panics if bounds are exceeded.
    pub fn truncate(self, n: usize) -> UniquePath {
        if n == 0 {
            UniquePath {
                s:          String::new(),
                segments:   Vec::new(),
            }
        } else if n <= self.len() {
            let l = self.segments[0].start;
            let r = self.segments[n - 1].end;
            let mut segments = self.segments;
            segments.truncate(n);
            UniquePath {
                s:          self.s[l..=r].to_string(),
                segments:   segments,
            }
        } else {
            panic!("Out of bounds.");
        }
    }

    pub fn remove(self, n: usize) -> UniquePath {
        if n > self.len() { panic!("remove() Out of bounds") };
        let len = self.len();
        self.truncate(len - n)
    }

    pub fn debug(&self) -> String {
        format!("{:?}", self)
    }
}

impl PartialEq for UniquePath {

    fn eq(&self, other: &Self) -> bool {
        if self.len()  != other.len()  { return false };
        (0..self.len())
            .all(|i| {
                self.segment_str(i) == other.segment_str(i) &&
                self.segments[i].index == other.segments[i].index
            })
    }
}

impl Hash for UniquePath {

    fn hash<H: Hasher>(&self, state: &mut H) {
        self
            .segments
            .iter()
            .map(|seg| seg.index)
            .for_each(|i| i.hash(state));
    }
}

impl Eq for UniquePath {}

impl Ord for UniquePath {

    // Sort by
    // 1. length
    // 2. string section
    // 3. index
    //
    fn cmp(&self, other: &Self) -> Ordering {
        let min = self.len().min(other.len());
        for n in 0..min {

            // compare length
            match self.len().cmp(&other.len()) {
                Ordering::Less      => { return Ordering::Less      },
                Ordering::Greater   => { return Ordering::Greater   },
                Ordering::Equal     => {

                    // compare name
                    match self.segment_str(n).cmp(other.segment_str(n)) {
                        Ordering::Less    => { return Ordering::Less    },
                        Ordering::Greater => { return Ordering::Greater },
                        Ordering::Equal   => {

                            // compare index
                            match (self.segments[n].index).cmp(&other.segments[n].index) {
                                Ordering::Less      => { return Ordering::Less      },
                                Ordering::Greater   => { return Ordering::Greater   },
                                Ordering::Equal     => { continue                   },

                            }
                        },
                    }
                },
            }
        };
        Ordering::Equal
    }
}

impl PartialOrd for UniquePath {
    fn partial_cmp(&self, other: &UniquePath) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

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

impl fmt::Debug for UniquePath {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        if self.is_empty() {
            write!(f, "{}", "(empty)")
        } else {
            let mut s = String::new();
            for i in 0..self.len() {
                s.push_str(self.segment_str(i));
                if i < self.len() {

                    // all but last segment
                    s.push_str(&format!("[{}]", self.index(i)));
                    s.push_str("::");
                }
            };
            s.pop();
            s.pop();
            write!(f, "{}", s)
        }
    }
}

// Represents the name of a path in a tree with potentially many leaf nodes.
#[derive(Clone)]
pub struct NonUniquePath {
    s:          String,
    segments:   Vec<Segment>,
}

impl NonUniquePath {

    pub fn len(&self) -> usize {
        self.segments.len()
    }

    // Returns Self as UniquePath.
    pub fn unique(self, index: usize) -> UniquePath {
        let mut segments = self.segments;
        let len = segments.len() - 1;
        segments[len].index = index;
        UniquePath {
            s:          self.s,
            segments:   segments,
        }
    }

    // Return the index at index.
    pub fn index(&self, index: usize) -> usize {
        if index <= self.len() - 2 {
            self.segments[index].index
        } else {
            panic!("Out of bounds.");
        }
    }

    pub fn is_empty(&self) -> bool {
        self.s.is_empty()
    }

    pub fn segment_str(&self, n: usize) -> &str {
        &self.s[self.segments[n].start..=self.segments[n].end]
    }

    // Parse a &str into a NonUniquePath
    pub fn from(s: &str) -> Result<Self, PathError> {
        let mut parser_state = PS::Segment;
        let mut leftpos = 0usize;
        let mut segments: Vec<Segment> = Vec::new();

        if s == "" {
            return Ok(
                NonUniquePath {
                    s:          String::new(),
                    segments:   segments,
                }
            )
        };

        for (pos, ch) in s.char_indices() {
            match (&parser_state, ch) {
                (_, '\n') => {
                    return Err(PathError::Parse(s.to_string(), pos))
                },
                
                // If we are in a segment and arrive at a separator.
                (PS::Segment, ':') => {
                    if pos > leftpos {
                        segments.push(Segment::new(0, leftpos, pos - 1));
                        parser_state = PS::Separator;
                    } else {
                        return Err(PathError::Parse(s.to_string(), pos))
                    }
                },

                // If we are in a segment and arrive at a char then check that the
                // char is not whitespace;
                (PS::Segment, ch) => {
                    if ch.is_whitespace() {
                        return Err(PathError::Parse(s.to_string(), pos));
                    }
                },

                // If we are in a separator and we arrive at a ':' set leftpos.
                (PS::Separator, ':') => {
                    leftpos = pos + 1;
                    parser_state = PS::Segment;
                },

                // If we are in a separator and we arrive at something other than ':'
                (PS::Separator, _) => {
                    return Err(PathError::Parse(s.to_string(), pos))
                },
            }
        };

        // Check that last segment exists.
        if leftpos == s.len() {
            return Err(PathError::Parse(s.to_string(), s.len()))
        };

        // Save last segment.
        match parser_state {
            PS::Segment => segments.push(Segment::new(0, leftpos, s.len() - 1)),
            _           => return Err(PathError::Parse(s.to_string(), s.len())),
        };

        Ok(NonUniquePath {
            s:          s.to_string(),
            segments:   segments,
        })
    }

    // Truncate's behaviour is a little unusual in that it returns a new value. This is because for
    // both Self as UniquePath and Self as NonUnique path, this function should return a
    // UniquePath.
    pub fn truncate(&self, n: usize) -> Result<UniquePath, PathError> {
        if n == 0 {
            Ok(
                UniquePath {
                    s:          String::new(),
                    segments:   Vec::new(),
                }
            )
        } else if n > self.len() - 1 {
            Err(PathError::OutOfBounds)
        } else {
            let s = self.s
                .clone()[self.segments[0].start..=self.segments[n].end]
                .to_string();
            let mut segments = self.segments.clone();
            segments.truncate(n);
            Ok(
                UniquePath {
                    s:          s,
                    segments:   segments,
                }
            )
        }
    }

    // Returns a NonUniquePath with the first element. If self is empty, then returns empty.
    pub fn tail(self) -> NonUniquePath {
        if self.is_empty() {
            self
        } else if self.len() == 1 {
            NonUniquePath {
                s:          String::new(),
                segments:   Vec::new(),
            }
        } else {
            let len = self.segments.len();
            let s = self.s[self.segments[1].start..=self.segments[len - 1].end]
                .to_string();
            let lshift = self.segments[0].end - self.segments[0].start + 3;
            let segments = self.segments[1..]
                .iter()
                .map(|seg| {
                    seg.left_shift(lshift)
                })
                .collect();
            NonUniquePath {
                s:          s,
                segments:   segments,
            }
        }
    }

    pub fn debug(&self) -> String {
        format!("{:?}", self)
    }
}

impl Hash for NonUniquePath {
    fn hash<H: Hasher>(&self, state: &mut H) {

        &self.s.hash(state);

        // Hash the indices if they exist.
        if self.len() > 1 {

            // Leave off last segment.
            let len = self.segments.len() - 2;

            self
                .segments
                .iter()
                .take(len)
                .map(|seg| seg.index)
                .for_each(|i| i.hash(state));
        };
    }
}

impl PartialEq for NonUniquePath {
    fn eq(&self, other: &Self) -> bool {
        if self.len()  != other.len()  { return false };
        (0..self.len() - 1)
            .all(|i| {
                self.segment_str(i) == other.segment_str(i) &&
                self.segments[i].index == other.segments[i].index
            })
        &&
        self.segment_str(self.len() - 1) == other.segment_str(self.len() - 1)
    }
}

impl Eq for NonUniquePath {}

impl Ord for NonUniquePath {

    // Iterate over all but last segment. First compare the string value and then compare the
    // index. Then compare the string value of the last segment. Then compare length.
    fn cmp(&self, other: &Self) -> Ordering {
        let min = self.len().min(other.len());
        for n in 0..min - 1 {

            // Compare name.
            match self.segment_str(n).cmp(other.segment_str(n)) {
                Ordering::Less    => { return Ordering::Less    },
                Ordering::Greater => { return Ordering::Greater },
                Ordering::Equal   => {

                    // Compare index.
                    match (self.segments[n].index).cmp(&other.segments[n].index) {
                        Ordering::Less      => { return Ordering::Less },
                        Ordering::Greater   => { return Ordering::Greater },
                        Ordering::Equal     => continue,
                    };
                },
            };
        };
        
        // Last segment.
        match self.segment_str(min - 1).cmp(other.segment_str(min - 1)) {
            Ordering::Less      => { return Ordering::Less },
            Ordering::Greater   => { return Ordering::Greater },
            Ordering::Equal     => { return self.len().cmp(&other.len()) },
        };
    }
}

impl PartialOrd for NonUniquePath {
    fn partial_cmp(&self, other: &NonUniquePath) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

impl fmt::Debug for NonUniquePath {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        let mut s = String::new();
        if self.is_empty() {
            write!(f, "{}", "(empty)")
        } else {
            for i in 0..self.len() - 1 {
                s.push_str(&format!("{}[{}]::", self.segment_str(i), self.index(i)));
            };
            s.push_str(&format!("{}[..]", self.segment_str(self.len() - 1)));
            write!(f, "{}", s)
        }
    }
}