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

pub fn strip_dag(original_dag: &str, vertice_to_strip: &str) -> String {
    let dag = original_dag.split(",").collect::<Vec<&str>>();
    let original_dag_len = 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(original_dag_len);

    // 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(original_dag_len);

    // The index that will allow us to peek within iterations to know if we're able to create a branch from a single vertice
    let mut next_idx: 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();
            next_idx = idx + 1;

            // Check if we're able to create a branch
            while let Some(next_vertex) = check_next_vertex(
                &dag,
                &next_idx,
                &stripped_vertex_len,
                vertice_to_strip,
                &stripped_vertex,
                &strip_pattern_1,
                &strip_pattern_2,
                &strip_pattern_3,
            ) {
                push_if_not_duplicate(next_vertex, &mut new_dag, &idx);
                idx_to_skip.push(next_idx);
                next_idx += 1;
            }
            continue;
        }

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

    new_dag.sort();

    new_dag.join(",")
}

fn push_if_not_duplicate(current_vertex: String, new_dag: &mut Vec<String>, idx: &usize) -> () {
    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 {
        // If idx is 0, there can't be any potential duplicate behind, we can just push
        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>,
    next_idx: &'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(*next_idx) {
            // 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(next_vertex) if next_vertex.contains(vertice_to_strip) => {
                let stripped_lookahead_vertex = strip_vertice(
                    strip_pattern_1,
                    strip_pattern_2,
                    strip_pattern_3,
                    next_vertex,
                );

                Some(format!(
                    "{}-{}",
                    previous_stripped_vertex, stripped_lookahead_vertex
                ))
            }
            _ => None,
        }
    }
}