lsystems 0.2.1

//! A library that makes working with L-systems simple. Works
//! with `char`s as predecessors and `String`s as successors.
//!
//! # Examples
//!
//! ```rust
//! use lsystems::LSystem;
//! let mut system = LSystem::with_axiom("b");
//! system.add_rule('a', "ab");
//! ```

extern crate rand;

use std::cmp::Ordering;
use std::collections::HashMap;

use rand::{thread_rng, sample};

/// Alias for an L-System predecessor.
type Predecessor = (Option<String>, char, Option<String>);

/// Alias for distribution function
type Fun = Box<Fn(&Vec<String>) -> String>;

/// Represents a Lindenmayer system
pub struct LSystem {
    /// The starting value for the L-system
    axiom: String,

    /// The current state of the L-system
    state: String,

    /// The L-system's set of productions. Each production is stored
    /// as a tuple with optional predecessor/successors for the production.
    rules: HashMap<Predecessor, Vec<String>>,

    /// Probability distributions for nondeterministic L-systems
    distributions: HashMap<Predecessor, Fun>,
}


impl LSystem {
    /// Creates a new L-system with the given axiom
    pub fn with_axiom(axiom: &str) -> LSystem {
        LSystem {
            axiom: axiom.into(),
            state: "".into(),
            rules: HashMap::new(),
            distributions: HashMap::new(),
        }
    }

    /// Adds a context-free rule.
    ///
    /// Equivalent to calling `LSystem::add_context_rule` with the path
    /// and tree set to `None`.
    pub fn add_rule(&mut self, predecessor: char, successor: &str) {
        self.add_context_rule::<String>((None, predecessor, None), successor);
    }

    /// Adds a context-sensitive rule.
    ///
    /// `predecessor` is a 3-tuple where the first and third elements
    /// are the path and tree, respectively, and the middle element
    /// is the predecessor.
    pub fn add_context_rule<T>(&mut self, predecessor: (Option<T>, char, Option<T>), successor: &str) where T: Into<String> {
        // Convert path from using &str to String
        let path = predecessor.0.map(|p| p.into());
        let tree = predecessor.2.map(|t| t.into());

        self.rules.entry((path, predecessor.1, tree)).or_insert(Vec::new()).push(successor.into());
    }

    /// Adds a probability distribution for context-free predecessor.
    pub fn add_distribution(&mut self, predecessor: char, distribution: Fun) {
        self.distributions.insert((None, predecessor, None), distribution);
    }

    /// Adds a probability distribution for context-sensitive predecessor.
    pub fn add_context_distribution(&mut self, predecessor: Predecessor, distribution: Fun) {
        self.distributions.insert(predecessor, distribution);
    }

    /// Resets the current state of the L-system so that the
    /// next state generated is equal to the axiom.
    pub fn reset(&mut self) {
        self.state = "".into();
    }

    /// Default distribution if one is unassigned.
    fn default(vals: &Vec<String>) -> String {
        // TODO: This could probably be more efficient.
        let mut rng = thread_rng();
        sample(&mut rng, vals.into_iter(), 1)[0].clone()
    }

    /// Since the HashMap is unordered, we need to manually sort
    /// the items when iterating over them to force the context-
    /// sensitive rules to be matched before the context-free rules.
    fn get_sorted_rules(&self) -> Vec<(&Predecessor, &Vec<String>)> {
        // Collect vec of key-value tuples
        let mut rules: Vec<_> = self.rules.iter().collect();

        rules.sort_by(|a, b| {
            let key_1 = a.0;
            let key_2 = b.0;

            match (key_1, key_2) {
                // key_1 is a context-sensitive rule and key_2 is context-free
                (&(Some(_), _, Some(_)), &(None, _, None)) => Ordering::Less,
                (&(Some(_), _, None   ), &(None, _, None)) => Ordering::Less,
                (&(None,    _, Some(_)), &(None, _, None)) => Ordering::Less,

                // key_1 is a context-free rule and key_2 is context-sensitive
                (&(None, _, None), &(Some(_), _, Some(_))) => Ordering::Greater,
                (&(None, _, None), &(Some(_), _, None   )) => Ordering::Greater,
                (&(None, _, None), &(None,    _, Some(_))) => Ordering::Greater,

                // Both keys are either context-free or context-sensitive, so the
                // order isn't particularly important.
                _ => key_1.cmp(key_2),
            }
        });

        rules
    }

    /// Gets the successor for a particular character. Accepts an index
    /// argument to do context-sensitive matching with. Since the rules
    /// are stored as keys in a hashmap with the predecessors/successors,
    /// this function will iterate over each key in the hashmap until it
    /// finds a match, instead of doing a normal `O(1)` lookup.
    fn get_successor(&self, ch: char, i: usize) -> Option<String> {
        for (key, value) in self.get_sorted_rules() {
            if key.1 != ch {
                continue;
            }

            let (before, after) = self.state.split_at(i);

            // Look backwards in the string for the path
            let before_matches = match key.0 {
                Some(ref k) => {
                    let b = before
                        .to_string()
                        .chars()
                        .into_iter()
                        .rev()
                        .take(k.len())
                        .collect::<String>();
                    b == *k
                }
                None => true,
            };

            // Look forwards in the string for the tree
            let after_matches = match key.2 {
                Some(ref k) => {
                    let a = after
                        .to_string()
                        .chars()
                        .into_iter()
                        .take(k.len())
                        .collect::<String>();
                    a == *k
                }
                None => true,
            };

            // If we've got a match, use the distribution to select
            // a particular successor.
            if before_matches && after_matches {
                return Some(match self.distributions.get(&key) {
                    Some(f) => f(&value),
                    None => LSystem::default(&value),
                });
            }
        }

        None
    }
}


impl Iterator for LSystem {
    type Item = String;

    fn next(&mut self) -> Option<String> {
        let mut next = String::new();

        // The first iteration is just the axiom.
        if self.state == "" {
            self.state = self.axiom.clone();
            return Some(self.state.clone());
        }

        // Loop through each character in the current state
        // and find a replacement, or replace it with itself.
        for (i, ch) in self.state.chars().enumerate() {
            match self.get_successor(ch, i) {
                Some(successor) => {
                    next.push_str(&successor);
                    continue;
                }
                None => next.push(ch),
            };
        }

        self.state = next.clone();

        Some(next)
    }
}