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

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);
    }
}