//! stringedits contains the [Edit] trait, which provides access to a number of iterators for small edits to strings.
//! Based off the article [How to Write A Spelling Corrector](https://norvig.com/spell-correct.html) by Peter Norvig.
//! Available under the MIT license.
//!
//! Usage:
//! ```
//! use stringedits::Edit;
//! "foo".dist1edits();
//! ```
//!
#[cfg(test)]
mod tests;
use std::collections::HashSet;

/// The Edit trait provides access to a number of iterators for single-and-double character edits of a string.
/// It is implemented for any type that implements `AsRef<str>`.
pub trait Edit: AsRef<str> {
    /// create an iterator over all the splits at a single position of a word.
    /// ```
    /// # use stringedits::Edit;
    /// # use std::collections::HashSet;
    /// let want: HashSet<(String, String)> = vec![("", "foo"), ("f", "oo"), ("fo", "o"), ("foo", "")]
    ///     .into_iter()
    ///     .map(|(a, b)| (a.to_string(), b.to_string()))
    ///     .collect();
    /// let got: HashSet<(String, String)> = "foo".splits().collect();
    /// assert_eq!(want, got);
    /// ```
    fn splits(&self) -> Splits {
        Splits {
            word: self.as_ref().to_string(),
            i: 0,
        }
    }

    /// create an iterator over all distance-1 transpositions of a word
    /// ```
    /// # use stringedits::Edit;
    /// # use std::collections::HashSet;
    /// let got: HashSet<String> = "bar".replaces().collect();
    /// assert!(got.contains("bzr"));
    /// assert!(got.contains("xar"));
    /// ```
    fn transposes(&self) -> Transposes {
        Transposes(self.splits())
    }

    /// create an iterator over all distance-1 replacements with a lowercase ASCII letter (`'b'a..=b'z'`)
    /// ```
    /// # use stringedits::Edit;
    /// # use std::collections::HashSet;
    /// let got: HashSet<String> = "bar".replaces().collect();
    /// assert!(got.contains("bzr"));
    /// assert!(got.contains("xar"));
    /// ```
    fn replaces(&self) -> Replaces {
        Replaces {
            splits: self.splits(),
            current: None,
            i: 0,
        }
    }

    /// create an iterator over all distance-1 insertions of a lowercase ASCII letter (`'b'a..=b'z'`)
    /// ```
    /// # use stringedits::Edit;
    /// # use std::collections::HashSet;
    /// let got: HashSet<String> = "bar".inserts().collect();
    /// assert!(got.contains("abar"));
    /// assert!(got.contains("bbar"));
    /// assert!(got.contains("bacr"));
    /// assert!(got.contains("bard"));
    /// ```
    fn inserts(&self) -> Inserts {
        Inserts {
            splits: self.splits(),
            i: 0,
            current: None,
        }
    }

    /// create an iterator over all single-character deletions of a word
    /// ```
    /// # use stringedits::Edit;
    /// # use std::collections::HashSet;
    /// let got: HashSet<String> = "bar".deletions().collect();
    /// let mut want: HashSet<String> = vec!["ar", "ba", "br"].into_iter().map(|s| s.to_string()).collect();
    /// assert_eq!(want, got);
    /// ```
    fn deletions(&self) -> Deletions {
        Deletions(self.splits())
    }

    /// create an iterator over all distance-1 edits of the string; that is, the transposes, replacements, insertions, and deletions
    /// ```
    /// # use stringedits::Edit;
    /// # use std::collections::HashSet;
    /// let got: HashSet<String> = "bar".dist1edits().collect();
    /// assert!(got.contains("br")); // deletion
    /// assert!(got.contains("bbar")); // addition
    /// assert!(got.contains("bra")); // transposition
    /// assert!(got.contains("baz")); // substitution
    /// ```
    fn dist1edits(&self) -> Dist1Edits {
        Dist1Edits {
            deletes: self.deletions(),
            transposes: self.transposes(),
            replaces: self.replaces(),
            inserts: self.inserts(),
        }
    }

    /// create an iterator over all distance-2 edits of the string; that is, choose two (with replacement) from transposition, replacement with `b'a..=b'z'`, insertion of `b'a'..=b'z'`, and deletion
    /// ```
    /// # use stringedits::Edit;
    /// # use std::collections::HashSet;
    /// let got: HashSet<String> = "bar".dist2edits().collect();
    /// assert!(got.contains("b")); // deletion 2
    /// assert!(got.contains("bbra")); // addition and substitution
    /// assert!(got.contains("rba")); // transposition 2
    /// assert!(got.contains("bz")); // substitution and deletion
    /// ```
    fn dist2edits(&self) -> Dist2Edits {
        Dist2Edits {
            current: self.dist1edits(),
            dist1: self
                .dist1edits()
                .collect::<HashSet<_>>()
                .into_iter()
                .collect::<Vec<_>>(),
            i: 0,
        }
    }
}

impl<T: AsRef<str>> Edit for T {}

///Iterator over all the splits at a single position of a word. See [Edit::splits]
pub struct Splits {
    word: String,
    i: usize,
}
/// Iterator over all transpositions of a single position of a word. See [Edit::transposes]
pub struct Transposes(Splits);
///Iterator over all the words formed from the delition of a single character from a word.
/// See [Edit::deletions]
pub struct Deletions(Splits);

///Iterator over all the words formed from the replacement of a character in a word with a letter in a...z
/// see [Edit::replaces]
pub struct Replaces {
    splits: Splits,
    current: Option<(String, String)>,
    i: u8,
}

/// Iterator over all the words formed from the insertion of a letter in a...z in any position in a word, including before the first character and after the last
/// see [Edit::inserts]
pub struct Inserts {
    splits: Splits,
    current: Option<(String, String)>,
    i: u8,
}

///Iterator over all the distance-1 edits of a word; deletion, insertion, or replacement of one character,
///or transposition of two characters. See [Edit::dist1edits]
pub struct Dist1Edits {
    deletes: Deletions,
    transposes: Transposes,
    replaces: Replaces,
    inserts: Inserts,
}

///Iterator over all the distance-2 edits of a word; deletion, insertion, or replacement of one character,
/// or transposition of two characters. See [Edit::dist2edits]
pub struct Dist2Edits {
    current: Dist1Edits,
    dist1: Vec<String>,
    i: usize,
}

#[inline]
fn nth_letter(n: u8) -> char {
    (b'a' + n) as char
}

//  -------- ITERATORS  ------
impl Iterator for Inserts {
    type Item = String;
    fn next(&mut self) -> Option<Self::Item> {
        if let (Some((ref a, ref b)), n @ 0...25) = (&self.current, self.i) {
            self.i += 1;
            let mut insert = a.to_string();
            insert.push(nth_letter(n));
            return Some(insert + b);
        };
        match self.splits.next() {
            None => None,
            Some((a, b)) => {
                self.i = 0;
                self.current = Some((a, b));
                self.next()
            }
        }
    }
}

impl Iterator for Dist2Edits {
    type Item = String;
    fn next(&mut self) -> Option<Self::Item> {
        match self.current.next() {
            Some(edit) => Some(edit),
            None if self.i < self.dist1.len() => {
                self.current = self.dist1[self.i].dist1edits();
                self.i += 1;
                self.next()
            }
            None => None,
        }
    }
}

impl Iterator for Dist1Edits {
    type Item = String;
    fn next(&mut self) -> Option<Self::Item> {
        (self.deletes.next())
            .or_else(|| self.transposes.next())
            .or_else(|| self.replaces.next())
            .or_else(|| self.inserts.next())
    }
}
impl Iterator for Replaces {
    type Item = String;
    fn next(&mut self) -> Option<Self::Item> {
        match (&self.current, self.i) {
            (Some((ref a, ref b)), n @ 0...25) if !a.is_empty() => {
                self.i += 1;
                let mut replace = a.to_string();
                replace.pop();
                replace.push(nth_letter(n));
                return Some(replace + b);
            }
            _ => {}
        };

        match self.splits.next() {
            None => None,
            Some((a, b)) => {
                self.i = 0;
                self.current = Some((a, b));
                self.next()
            }
        }
    }
}

impl Iterator for Deletions {
    type Item = String;
    fn next(&mut self) -> Option<Self::Item> {
        match self.0.next() {
            None => None,
            Some((_, ref b)) if b.is_empty() => self.next(),
            Some((a, b)) => Some(a + &b[1..]),
        }
    }
}

impl Iterator for Transposes {
    type Item = String;
    fn next(&mut self) -> Option<Self::Item> {
        match self.0.next() {
            None => None,
            Some((_, ref b)) if b.len() < 2 => self.next(), //we can only transpose the rightmost two characters if there are two or more
            Some((a, b)) => {
                let mut transpose = a.to_string();
                let chars: Vec<char> = b.chars().collect();
                transpose.push(chars[1]);
                transpose.push(chars[0]);
                transpose.extend(&chars[2..]);
                Some(transpose)
            }
        }
    }
}

impl Iterator for Splits {
    type Item = (String, String);
    fn next(&mut self) -> Option<Self::Item> {
        if self.i > self.word.len() {
            return None;
        }
        let n = self.i;
        self.i += 1;
        Some((String::from(&self.word[..n]), String::from(&self.word[n..])))
    }
}