dag_stripper 0.1.3

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;

    // a-b,b-d,d,d => a-b,b-d

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

        if vert.contains(char_to_strip) {
            let stripped_vertex =
                strip_vertice(&strip_pattern_1, &strip_pattern_2, &strip_pattern_3, vert);
            let stripped_vertice_len = stripped_vertex.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_vertex,
                &strip_pattern_1,
                &strip_pattern_2,
                &strip_pattern_3,
            ) {
                push_if_not_duplicate(lookahead_vertice, &mut new_dag, &idx);
                done_idx.push(idx_lookahead);
                idx_lookahead += 1;
            }

            continue;
        }

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

    new_dag.sort();

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

    formatted_dag
}

fn push_if_not_duplicate(current_vertex: String, new_dag: &mut Vec<String>, idx: &usize) -> () {
    // If idx is 0, there can't be any potential duplicate behind, we can just push
    if *idx != 0 {
        if let Some(vertex) = new_dag.get(idx - 1) {
            match (vertex.chars().last(), current_vertex.chars().last()) {
                // The last char of the previous vertex is equal to the last char of the current vertex (eg : "a-b,b" or "a-b,b-b"). We don't push
                (Some(char1), Some(char2)) if char1 == char2 => (),
                _ => new_dag.push(current_vertex),
            }
        }
    } else {
        new_dag.push(current_vertex);
    }
}

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) => {
                let stripped_lookahead_vertice = strip_vertice(
                    strip_pattern_1,
                    strip_pattern_2,
                    strip_pattern_3,
                    lookahead_vertice,
                );

                let new_vertice = Some(format!(
                    "{}-{}",
                    first_stripped_vertice, stripped_lookahead_vertice
                ));

                new_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";
        let stripped_dag = strip_dag(original_dag, vertice_to_strip);

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

        let vertice_to_strip = "x";

        let expected_dag_result = "a-b,b-c,c-d";
        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,b-d,d,d";
        let vertice_to_strip = "c";

        let expected_dag_result = "a-b,b-d";
        // In reality, should we merge the two d vertices together? or are they too far apart? Should we leave untouched the single vertices that do not contain the characters to strip?
        let stripped_dag = strip_dag(original_dag, vertice_to_strip);

        assert_eq!(expected_dag_result, stripped_dag);
    }
}