//! A namespace looks like `abc::def::ghi`.
//!
//! Namespaces are more subtle than one would naively assume. For namespaces to be genuinely
//! extensible, they cannot know anything beyond their scope. This means that they don't have an
//! absolute index. They can be positioned relative to another namespace only by a 'sliding'
//! match. This matching can potentially be ambiguous, so if multiple matches occur an error is
//! returned. Namespaces can never be empty.

use std::cmp::Ordering;
use std::fmt;
use std::ops::Index;

// Separator
// The separator length is fixed at 2.

const SEP1: char = ':';
const SEP2: char = ':';

#[derive(Debug, PartialEq)]
pub enum NSErr {
    Parse(String, usize),
    NoMatch,
    NoRemainder,
    MultipleMatch,
    Remove,
    OutOfBounds,
}

impl fmt::Display for NSErr {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        match self {
            NSErr::Parse(s, pos)   => write!(f, "Could not parse \"{}\" at position {}.", s, pos),
            NSErr::NoMatch         => write!(f, "No match."),
            NSErr::MultipleMatch   => write!(f, "Multiple matches."),
            NSErr::Remove          => write!(f, "Removed too many segments."),
            NSErr::NoRemainder     => write!(f, "No remainder."),
            NSErr::OutOfBounds     => write!(f, "Index out of bounds."),
        }
    }
}


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

// To work with a Namespace we can use an iterator of of `Slice`s into `s`.
// These are generated by the `Iterator`'s `next()` function.
//
/// `Namespace` cannot be empty. It always contains at least one segment.
///
#[derive(Clone, Hash)]
pub struct Namespace {
    // Contains the string passed in by new() with separators removed.
    pub s:          String,

    // Contains usize pointers into the Vec representation of s.
    pub segments:   Vec<usize>,
}

impl Namespace {

    /// ```
    /// let ns = Namespace::new("a::b::c").unwrap();
    /// ```
    ///
    pub fn new(s: &str) -> Result<Self, NSErr> {
        let mut parser_state            = PS::SegmentStart;
        let mut leftpos                 = 0usize;
        let mut segments: Vec<usize>    = Vec::new();

        for (pos, ch) in s.char_indices() {
            match (&parser_state, ch) {

                (_, '\n') => {
                    return Err(NSErr::Parse(s.to_string(), pos))
                },

                (PS::SegmentStart, SEP1) => {
                    return Err(NSErr::Parse(s.to_string(), pos))
                },

                // Required if SEP2 != SEP1
                //
                // (PS::SegmentStart, SEP2) => {
                //     return Err(NSErr::Parse(s.to_string(), pos))
                // },

                (PS::SegmentStart, ch) => {
                    if ch.is_whitespace() {
                        return Err(NSErr::Parse(s.to_string(), pos));
                    } else {
                        leftpos = pos;
                        parser_state = PS::Segment;
                    }
                },

                // First ':' in separator.
                (PS::Segment, SEP1) => {
                    parser_state = PS::Separator;
                },

                (PS::Segment, _) => {},

                // Second ':' in separator.
                (PS::Separator, SEP2) => {
                    segments.push(leftpos);
                    leftpos = pos + 1;
                    parser_state = PS::SegmentStart;
                },

                (PS::Separator, _) => {
                    return Err(NSErr::Parse(s.to_string(), pos))
                },
            }
        }
        // Save last segment.
        match parser_state {
            PS::Segment => { segments.push(leftpos) },
            _           => { return Err(NSErr::Parse(s.to_string(), s.len())) },
        };
        Ok(Namespace {
            s:          s.to_string(),
            segments:   segments,
        })
    }


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

    /// Appends a new namespace to the end of `Self`. For example,
    ///
    /// ```
    /// let ns1 = Namespace::new("a::b").unwrap();
    /// let ns2 = Namespace::new("b::c").unwrap();
    /// let ns = ns1.append(&ns2);
    ///
    /// assert!(ns, "a::b::b::c");
    /// ```
    pub fn append(&self, other: &Namespace) -> Namespace {

        // Append strings.
        let mut s = self.s.clone();
        s.push(SEP1);
        s.push(SEP2);
        s.push_str(&other.s);

        let mut segs = self.segments.clone();
        for n in other.segments.clone().iter() {
            segs.push(n + self.s.len() + 2)
        }

        Namespace {
            s:          s,
            segments:   segs,
        }
    }

    /// Appends a new namespace at index. Returns an error if the `n > self.len()`.
    ///
    /// ```rust
    /// let ns1 = Namespace::new("a::b::c").unwrap();
    /// let ns2 = Namespace::new("d").unwrap();
    /// assert_eq!(ns1.append_at(&ns2, 1), "a::d");
    /// ```
    pub fn append_at(&self, other: &Namespace, n: usize) -> Result<Namespace, NSErr> {
        if n > self.len() {
            Err(NSErr::OutOfBounds)
        } else if n == 0 {
            Ok(other.clone())
        } else {
            Ok(self.truncate(n).unwrap().append(other))
        }
    }

    /// Remove `n` segments from the right-hand side of `Self`. Namespaces cannot be empty so
    /// returns an error if all segments are removed.
    ///
    /// ```rust
    /// assert_eq!(
    ///     Namespace::new("a::b::c").unwrap()
    ///         .remove(2)
    ///         .unwrap()
    ///         .to_string(),
    ///     "a"
    /// );
    /// ```
    ///
    pub fn remove(&self, n: usize) -> Result<Namespace, NSErr> {
        if n == 0 {
            // No-op.
            Ok(self.clone())
        } else if n < self.len() {
            let segs = self.len() - 1 - n;
            Ok(Namespace {
                s:          self.s[0..(self.segments[segs + 1] - 2)].to_string(),
                segments:   self.segments[0..=segs].to_vec(),
            })
        } else {
            Err(NSErr::Remove)
        }
    }

    /// Truncate the namespace to the first `n` segments. In other words truncate to length `n`.
    /// Returns an error if `n > self.len()`.
    ///
    pub fn truncate(&self, n: usize) -> Result<Namespace, NSErr> {
        let out = self.clone();
        if n == 0 || n > self.len() {
            Err(NSErr::OutOfBounds)
        } else {
            out.remove(self.len() - n)
        }
    }

    /// Tries to find a sliding match. Returns the index of the position in self aligned to the
    /// first segment of other. Note that this value can be negative. If there are no matches
    /// returns an empty `Vec`.
    ///
    /// ```rust
    /// let ns1 = Namespace::new("a::b::c").unwrap();
    /// let ns2 = Namespace::new("c::d").unwrap();
    /// assert_eq!(
    ///     ns1.sliding_match(&ns),
    ///     vec!(2)
    /// );
    /// ```
    ///
    pub fn sliding_match(&self, other: &Namespace) -> Vec<isize> {
        let slen = self.len() as isize;
        let olen = other.len() as isize;

        let mut v: Vec<isize> = Vec::with_capacity(slen.max(olen) as usize);
    
        for offset in (0 - olen + 1)..slen {
            if self.offset_match(other, offset) { v.push(offset) }
        };
        v
    }

    /// The offset is the index of the position in self aligned to the first segment of other.
    /// Returns true if all aligned segments match.
    ///
    pub fn offset_match(&self, other: &Namespace, offset: isize) -> bool {
        //        ls       rs
        //        v        v
        // self  [        ]
        // other     [         ]
        //            ^         ^
        //            lo        ro
        let ls = 0;
        let rs = self.len() as isize;
        let lo = offset;
        let ro = other.len() as isize + offset;

        for i in ls.max(lo)..rs.min(ro) {
            if self[i as usize] != other[(i - offset) as usize] { return false }
        };
        true
    }

    #[test]
    fn test_sliding_match() {
        let ns = Namespace::new("a::b::c").unwrap();

        let other = Namespace::new("c::b::a").unwrap();
        assert_eq!(
            ns.sliding_match(&other)[1],
            2
        );
    
        let other = Namespace::new("a").unwrap();
        assert_eq!(
            ns.sliding_match(&other)[0],
            0
        );
    
        let other = Namespace::new("a::b::c").unwrap();
        assert_eq!(
            ns.sliding_match(&other)[0],
            0
        );
    
        let other = Namespace::new("x::y").unwrap();
        assert!(
            ns.sliding_match(&other).is_empty()
        );
    }

    /// Returns the remainder of `other`. If there is no match, multiple matches or no remainder,
    /// returns an error.
    ///
    /// ```rust
    /// let ns1 = Namespace::new("a::b::c").unwrap();
    /// let ns2 = Namespace::new("c::d::e").unwrap();
    /// assert_eq!(
    ///     ns.remainder(&ns2).unwrap().to_string(),
    ///     "d::e"
    /// );
    /// ```
    pub fn remainder(&self, other: &Namespace) -> Result<Namespace, NSErr> {
         let offset = check_unique(&self.sliding_match(&other))?;

         // The only valid condition is:
         //
         //                offset
         //                |         other.len()
         //                v         |
         // self:    [         ]     v
         // other:        [         ]
         //                     ^
         //                     |
         //                     rem_ix
         //
         if offset + other.len() as isize > self.len() as isize {
            let rem_ix = self.len() - offset as usize;
            Ok(
                Namespace {
                    s:          String::from(&other.s[other.segments[rem_ix]..]),
                    segments:   other.segments[rem_ix..].to_vec(),
                }
            )
         } else {
             Err(NSErr::NoRemainder)
         }
    }

    /// If there is a unique sliding_match, returns `self` appended with the the remainder of
    /// `other`, otherwise returns an error.
    ///
    /// ```rust
    /// let ns = Namespace::new("a::b").unwrap();
    /// let other = Namespace::new("b::c").unwrap();
    /// ns.sliding_join(&other);
    /// assert_eq!(
    ///     ns.sliding_join(&other).unwrap().to_string(),
    ///     "a::b::c",
    /// );
    /// ```
    ///
    pub fn sliding_join(&self, other: &Namespace) -> Result<Namespace, NSErr> {
         let ns = self.clone();
         Ok(ns.append(&self.remainder(other)?))
    }

    pub fn iter(&self) -> NamespaceIter {
        NamespaceIter {
            ns:     &self,
            index:  0usize,
        }
    }
}

impl Index<usize> for Namespace {
    type Output = str;

    fn index(&self, n: usize) -> &Self::Output {
        match n.cmp(&(self.segments.len() - 1)) {
            Ordering::Less      => &self.s[self.segments[n]..self.segments[n + 1] - 2],
            Ordering::Equal     => &self.s[self.segments[n]..],               
            Ordering::Greater   => panic!("Index on Namespace out of bounds."),
        }
    }
}

#[test]
fn test_index_1() {
    let ns = Namespace::new("a::bc::d").unwrap();
    assert_eq!(
        ns[0],
        "a"
    );
}

pub struct NamespaceIter<'a> {
    ns:     &'a Namespace,
    index:  usize,
}

// Think implement a whole lot of functions<&Segment> for Namespace.

impl<'a> Iterator for NamespaceIter<'a> {
    type Item = &'a str;

    fn next(&mut self) -> Option<Self::Item> {
        let i = self.index;
        self.index += 1;

        if i < self.ns.len() {
            Some(&self.ns[i])
        } else {
            None
        }
    }
}

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

impl fmt::Debug for Namespace {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "{}", self.to_string())
    }
}

// If namespaces are not the same length returns false
impl PartialEq for Namespace {
    fn eq(&self, other: &Namespace) -> bool {
        self.s == other.s
    }
}

impl Eq for Namespace {}

// Supplement to slide_match() which checks that there is only one match, otherwise returns an
// error.
fn check_unique(v: &Vec<isize>) -> Result<isize, NSErr> {
    match v.len() {
        0 => Err(NSErr::NoMatch),
        1 => Ok(v[0]),
        _ => Err(NSErr::MultipleMatch),
    }
}