//! 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;
//! assert_eq!(vec!["!foo", "f!oo", "fo!o", "foo!"], "foo".inserts(&['!']).collect::<Vec<String>>());
//! ```
//!
#[cfg(test)]
mod tests;
use std::collections::HashSet;

/// The characters from 'a'..='z'.
pub const ASCII_LOWERCASE: &[char] = &[
    'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's',
    't', 'u', 'v', 'w', 'x', 'y', 'z',
];

/// The characters from 'A'..='Z'.
pub const ASCII_UPPERCASE: &[char] = &[
    'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S',
    'T', 'U', 'V', 'W', 'X', 'Y', 'Z',
];
/// 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().map(|(q, r)| (q.to_string(), r.to_string())).collect();
    /// assert_eq!(want, got);
    /// ```
    fn splits(&self) -> Splits {
        Splits {
            word: self.as_ref(),
            i: 0,
        }
    }

    /// create an iterator over all distance-1 transpositions of a word
    /// ```
    /// # use stringedits::Edit;
    /// # use std::collections::HashSet;
    /// let transpositions = "bar".transposes().collect::<Vec<String>>().join(" ");
    /// assert_eq!(transpositions, "abr bra");
    /// ```
    fn transposes(&self) -> Transposes {
        Transposes(self.splits())
    }

    /// an iterator over all distance-1 replacements with a lowercase ASCII letter (`'a'..='z'`)
    /// ```
    /// # use stringedits::Edit;
    /// let replaces = "ab".replaces_ascii_lowercase().collect::<Vec<String>>().join(" ");
    /// let want = concat!(
    ///     "ab bb cb db eb fb gb hb ib jb kb lb mb nb ob pb qb rb sb tb ub vb wb xb yb zb ", // replace 'a'
    ///     "aa ab ac ad ae af ag ah ai aj ak al am an ao ap aq ar as at au av aw ax ay az", // replace 'b'
    /// );
    /// assert_eq!(want, replaces)
    /// ```
    fn replaces_ascii_lowercase(&self) -> CustomReplaces {
        CustomReplaces {
            splits: self.splits(),
            current: None,
            i: 0,
            alphabet: ASCII_LOWERCASE,
        }
    }

    /// create an iterator over all distance-1 insertions of a lowercase ASCII letter (`'b'a..=b'z'`)
    /// ```
    /// # use stringedits::{Edit, ASCII_LOWERCASE};
    /// let a_inserts = "a".inserts(ASCII_LOWERCASE).collect::<Vec<String>>().join(" ");
    /// let want = concat!(
    ///    "aa ba ca da ea fa ga ha ia ja ka la ma na oa pa qa ra sa ta ua va wa xa ya za ", // insert before a
    ///    "aa ab ac ad ae af ag ah ai aj ak al am an ao ap aq ar as at au av aw ax ay az" // insert after a
    /// );
    /// assert_eq!(want, a_inserts);
    /// ```
    fn inserts_ascii_lowercase(&self) -> CustomInsert {
        CustomInsert {
            splits: self.splits(),
            i: 0,
            current: None,
            alphabet: ASCII_LOWERCASE,
        }
    }

    /// create an iterator over all single-character deletions of a word
    /// ```
    /// # use stringedits::Edit;
    /// let deletions = "bar".deletions().collect::<Vec<String>>().join(" ");
    /// assert_eq!("ar br ba", deletions);
    /// ```
    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, ASCII_LOWERCASE};
    /// # use std::collections::HashSet;
    /// let got: HashSet<String> = "bar".dist1edits(ASCII_LOWERCASE).collect();
    /// assert!(got.contains("br")); // deletion
    /// assert!(got.contains("bbar")); // addition
    /// assert!(got.contains("bra")); // transposition
    /// assert!(got.contains("baz")); // substitution
    /// ```
    fn dist1edits<'a>(&'a self, alphabet: &'a [char]) -> Dist1Edits {
        Dist1Edits {
            deletes: self.deletions(),
            transposes: self.transposes(),
            replaces: self.replaces(alphabet),
            inserts: self.inserts(alphabet),
        }
    }
    /// an iterator over all distance-2 edits of the string; that is, the combinations of up two transpositions, replacements, insertions, and/or deletions
    /// ```
    /// # use stringedits::{Edit, ASCII_LOWERCASE};
    /// # use std::collections::HashSet;
    /// let dist2: HashSet<String> = "foo".dist2edits(ASCII_LOWERCASE).collect();
    /// assert!(dist2.contains("f")); // two deletions
    /// assert!(dist2.contains("afooa")); // two additions
    /// assert!(dist2.contains("of")); // delete & transpose
    /// assert!(dist2.contains("ofog")); // transposition and addition
    /// ```
    fn dist2edits<'a>(&'a self, alphabet: &'a [char]) -> Dist2Edits {
        let mut d1 = self
            .dist1edits(alphabet)
            .collect::<HashSet<String>>()
            .into_iter();
        let current_d2 = d1
            .next()
            .unwrap()
            .dist1edits(alphabet)
            .collect::<Vec<String>>()
            .into_iter();
        Dist2Edits {
            d1,
            current_d2,
            alphabet,
        }
    }

    /// An iterator over all distance_1 replacements into the string using the provided alphabet. ("bar" -> "baa", "baz")
    /// ```
    /// # use stringedits::{Edit, ASCII_LOWERCASE};
    /// assert_eq!("foo".replaces(ASCII_LOWERCASE).collect::<String>(), "foo".replaces(ASCII_LOWERCASE).collect::<String>());
    /// assert_eq!("!oo f!o fo!", "foo".replaces(&['!']).collect::<Vec<String>>().join(" "));
    /// ```
    fn replaces<'a>(&'a self, alphabet: &'a [char]) -> CustomReplaces<'a> {
        CustomReplaces {
            splits: self.splits(),
            i: 0,
            current: None,
            alphabet,
        }
    }

    /// An iterator over all distance-1 insertions into the string using the provided alphabet. ("bar" -> "bard", "boar")
    /// These insertions include before the first character and after the last one; however, an empty string will only be inserted into once.
    /// See [ASCII_LOWERCASE] and [ASCII_UPPERCASE] for useful alphabets.
    /// ```
    /// # use stringedits::{Edit, ASCII_LOWERCASE};
    /// assert_eq!(vec!["!foo", "f!oo", "fo!o", "foo!"], "foo".inserts(&['!']).collect::<Vec<String>>());  
    /// assert_eq!("1234", "".inserts(&['1', '2', '3', '4']).collect::<String>());
    /// ```
    fn inserts<'a>(&'a self, alphabet: &'a [char]) -> CustomInsert<'a> {
        CustomInsert {
            splits: self.splits(),
            i: 0,
            current: None,
            alphabet,
        }
    }
}

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

/// Iterator over all the distance-2 edits of a word. See [Edit::dist2edits]
/// This stores a fairly large hashset & vector (of distance-1 edits) internally,
/// so it's not nearly as lightweight as the other iterator adaptors.
/// I'd like to come up with a more elegant solution if I can, but I'd have to wrestle with lifetimes a lot.
///
pub struct Dist2Edits<'a> {
    d1: <std::collections::HashSet<String> as IntoIterator>::IntoIter,
    current_d2: <Vec<String> as IntoIterator>::IntoIter,
    alphabet: &'a [char],
}

///Iterator over all the splits at a single position of a word. See [Edit::splits]
#[derive(Debug, Clone)]
pub struct Splits<'a> {
    word: &'a str,
    i: usize,
}
/// Iterator over all transpositions of a single position of a word. See [Edit::transposes]
#[derive(Debug, Clone)]
pub struct Transposes<'a>(Splits<'a>);
///Iterator over all the words formed from the delition of a single character from a word.
/// See [Edit::deletions]
#[derive(Debug, Clone)]
pub struct Deletions<'a>(Splits<'a>);

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

///Iterator over all the words formed from the replacement of a character in a word with each letter in it's custom alphabet
/// see [Edit::replaces]
#[derive(Debug, Clone)]
pub struct CustomReplaces<'a> {
    splits: Splits<'a>,
    current: Option<(&'a str, &'a str)>,
    alphabet: &'a [char],
    i: usize,
}

#[derive(Debug, Clone)]
pub struct CustomInsert<'a> {
    splits: Splits<'a>,
    current: Option<(&'a str, &'a str)>,
    alphabet: &'a [char],
    i: usize,
}

/// 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]
#[derive(Debug, Clone)]
pub struct Inserts<'a> {
    splits: Splits<'a>,
    current: Option<(String, String)>,
    c: 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]
#[derive(Debug, Clone)]
pub struct Dist1Edits<'a> {
    deletes: Deletions<'a>,
    transposes: Transposes<'a>,
    replaces: CustomReplaces<'a>,
    inserts: CustomInsert<'a>,
}

//  -------- ITERATORS  ------

impl<'a> Iterator for Dist2Edits<'a> {
    type Item = String;
    fn next(&mut self) -> Option<String> {
        if let Some(d2) = self.current_d2.next() {
            return Some(d2);
        }
        if let Some(s) = self.d1.next() {
            self.current_d2 = s
                .dist1edits(self.alphabet)
                .collect::<Vec<String>>()
                .into_iter();
            self.next()
        } else {
            None
        }
    }
}
impl<'a> Iterator for CustomReplaces<'a> {
    type Item = String;
    fn next(&mut self) -> Option<Self::Item> {
        match self {
            CustomReplaces {
                current: Some((a, b)),
                i,
                alphabet,
                ..
            } if *i < alphabet.len() && !a.is_empty() => {
                let mut replace = a.to_string();
                replace.pop();
                replace.push(alphabet[*i] as char);
                *i += 1;

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

impl<'a> Iterator for CustomInsert<'a> {
    type Item = String;
    fn next(&mut self) -> Option<Self::Item> {
        match self {
            CustomInsert {
                current: Some((a, b)),
                i,
                alphabet,
                ..
            } if *i < alphabet.len() => {
                let mut replace = a.to_string();
                replace.push(alphabet[*i] as char);
                *i += 1;

                Some(replace + b)
            }
            _ => match self.splits.next() {
                None => None,
                Some((a, b)) => {
                    self.i = 0;
                    self.current = Some((a, b));
                    self.next()
                }
            },
        }
    }
}
impl<'a> Iterator for Deletions<'a> {
    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.to_owned() + &b[1..]),
        }
    }
}

impl<'a> Iterator for Transposes<'a> {
    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<'a> Iterator for Splits<'a> {
    type Item = (&'a str, &'a str);
    fn next(&mut self) -> Option<Self::Item> {
        if self.i > self.word.len() {
            return None;
        }
        let n = self.i;
        self.i += 1;
        Some((&self.word[..n], &self.word[n..]))
    }
}

impl<'a> Iterator for Dist1Edits<'a> {
    type Item = String;
    fn next(&mut self) -> Option<String> {
        self.deletes
            .next()
            .or_else(|| self.transposes.next())
            .or_else(|| self.inserts.next())
            .or_else(|| self.replaces.next())
    }
}