1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158

pub fn strip_dag(vertex: &str, vertice_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!("-{}", vertice_to_strip);
    let strip_pattern_2 = format!("{}-", vertice_to_strip);
    let strip_pattern_3 = format!("{}", vertice_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 idx_to_skip: 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, vertex) in dag.iter().enumerate() {
        if idx_to_skip.contains(&idx) {
            continue;
        }

        if vertex.contains(vertice_to_strip) {
            let stripped_vertex =
                strip_vertice(&strip_pattern_1, &strip_pattern_2, &strip_pattern_3, vertex);
            let stripped_vertex_len = stripped_vertex.len();
            idx_lookahead = idx + 1;

            // Check if we're able to create a branch
            while let Some(lookahead_vertex) = check_next_vertex(
                &dag,
                &idx_lookahead,
                &stripped_vertex_len,
                vertice_to_strip,
                &stripped_vertex,
                &strip_pattern_1,
                &strip_pattern_2,
                &strip_pattern_3,
            ) {
                push_if_not_duplicate(lookahead_vertex, &mut new_dag, &idx);
                idx_to_skip.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(*vertex), &mut new_dag, &idx)
    }

    new_dag.sort();

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

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(vertice1), Some(vertice2)) if vertice1 == vertice2 => (),
                _ => 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,
    vertex: &&str,
) -> String {
    vertex
        .replace(&*strip_pattern_1, "")
        .replace(&*strip_pattern_2, "")
        .replace(&*strip_pattern_3, "")
}

fn check_next_vertex<'a>(
    dag: &Vec<&str>,
    idx_lookahead: &'a usize,
    vertex_len: &usize,
    vertice_to_strip: &str,
    previous_stripped_vertex: &String,
    strip_pattern_1: &String,
    strip_pattern_2: &String,
    strip_pattern_3: &String,
) -> Option<String> {
    if vertex_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_vertex) if lookahead_vertex.contains(vertice_to_strip) => {
                let stripped_lookahead_vertex = strip_vertice(
                    strip_pattern_1,
                    strip_pattern_2,
                    strip_pattern_3,
                    lookahead_vertex,
                );

                let new_vertex = Some(format!(
                    "{}-{}",
                    previous_stripped_vertex, stripped_lookahead_vertex
                ));

                new_vertex
            }
            _ => 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";
        // What is the utility of non-branched vertices? (single vertices)
        let stripped_dag = strip_dag(original_dag, vertice_to_strip);

        assert_eq!(expected_dag_result, stripped_dag);
    }
}