dag_stripper 0.1.0

pub fn strip_dag(vertex: &str, char_to_strip: &str) -> String {
    let dag = vertex.split(",").collect::<Vec<&str>>();
    let dag_original_length = dag.len();

    // Allocating the patterns to strip given a character
    let strip_pattern_1 = format!("-{}", char_to_strip);
    let strip_pattern_2 = format!("{}-", char_to_strip);
    let strip_pattern_3 = format!("{}", char_to_strip);

    // Allocating a mutable vec to create the newly formatted dag. We know the length won't exceed the original's
    let mut new_dag: Vec<String> = Vec::with_capacity(dag_original_length);

    // Keeping track of the indexes we've connected branches from to avoid unnecessary iterations. We know the length won't exceed the original's
    let mut done_idx: Vec<usize> = Vec::with_capacity(dag_original_length);

    // The index that will allow us to look ahead from an interation to know if we're able to create a branch from a single vertice
    let mut idx_lookahead: usize;

    for (idx, vert) in dag.iter().enumerate() {
        if done_idx.contains(&idx) {
            continue;
        }

        if vert.contains(char_to_strip) {
            let mut stripped_vertice =
                strip_vertice(&strip_pattern_1, &strip_pattern_2, &strip_pattern_3, vert);
            let stripped_vertice_len = stripped_vertice.len();
            idx_lookahead = idx + 1;

            // Check if we're able to create a branch
            while let Some(lookahead_vertice) = check_next_vertice(
                &dag,
                &idx_lookahead,
                &stripped_vertice_len,
                char_to_strip,
                &stripped_vertice,
                &strip_pattern_1,
                &strip_pattern_2,
                &strip_pattern_3,
            ) {
                stripped_vertice = lookahead_vertice;
                done_idx.push(idx_lookahead);
                idx_lookahead += 1;
            }

            new_dag.push(stripped_vertice);
            continue;
        }

        // Nothing special to do on this vertice, and it wasn't modified used to create a branch. We just push it
        new_dag.push(String::from(*vert))
    }

    new_dag.sort();

    // Joins the dag back into desired format (e.g "a-b,b-c,c-d")
    new_dag.join(",")
}

fn strip_vertice(
    strip_pattern_1: &String,
    strip_pattern_2: &String,
    strip_pattern_3: &String,
    vertice: &&str,
) -> String {
    vertice
        .replace(&*strip_pattern_1, "")
        .replace(&*strip_pattern_2, "")
        .replace(&*strip_pattern_3, "")
}

fn check_next_vertice<'a>(
    dag: &Vec<&str>,
    idx_lookahead: &'a usize,
    vertice_len: &usize,
    char_to_strip: &str,
    first_stripped_vertice: &String,
    strip_pattern_1: &String,
    strip_pattern_2: &String,
    strip_pattern_3: &String,
) -> Option<String> {
    if vertice_len > &1 {
        // We've already got a branch
        None
    } else {
        match dag.get(*idx_lookahead) {
            // We have an unconnected vertice, and the next vertice will also be unconnected once its character to strip is removed. We create a branch from the two
            Some(lookahead_vertice) if lookahead_vertice.contains(char_to_strip) => Some(format!(
                "{}-{}",
                first_stripped_vertice,
                strip_vertice(
                    strip_pattern_1,
                    strip_pattern_2,
                    strip_pattern_3,
                    lookahead_vertice
                )
            )),
            _ => None,
        }
    }
}

#[cfg(test)]
mod test {
    use super::strip_dag;
    #[test]
    fn strips_dag_successfully() {
        let original_dag = "a-b,b-c,c-d,c-d";
        let vertice_to_strip = "d";

        let expected_dag_result = "a-b,b-c,c-c";
        let stripped_dag = strip_dag(original_dag, vertice_to_strip);

        assert_eq!(expected_dag_result, stripped_dag);
    }
    #[test]
    fn nothing_to_strip() {
        let original_dag = "a-b,b-c,c-d,c-d";
        let vertice_to_strip = "x";

        let expected_dag_result = original_dag;
        let stripped_dag = strip_dag(original_dag, vertice_to_strip);

        assert_eq!(expected_dag_result, stripped_dag);
    }

    #[test]
    fn strip_alphabetically() {
        let original_dag = "a-b,d-c,b-d,c-d";
        let vertice_to_strip = "c";

        let expected_dag_result = "a-b,b-d,d,d";
        // In reality, should we merge the two d vertices together? or are they too far apart?
        let stripped_dag = strip_dag(original_dag, vertice_to_strip);

        assert_eq!(expected_dag_result, stripped_dag);
    }
}