offline-delete-min.rs

use std::cmp::Ordering;

struct UnionFindEntry {
  parent: usize,
  rank: usize,
}

struct UnionFind {
  trees: Vec<UnionFindEntry>,
}

impl UnionFind {
  pub fn new(size: usize) -> UnionFind {
    let mut v = Vec::with_capacity(size);
    for i in 0..size {
      v.push(UnionFindEntry { parent: i, rank: 0 });
    }
    return UnionFind { trees: v };
  }

  pub fn find(&mut self, mut k: usize) -> usize {
    let mut l = k;
    while l != self.trees[l].parent {
      l = self.trees[l].parent;
    }
    while l != self.trees[k].parent {
      let tmp = self.trees[k].parent;
      self.trees[k].parent = l;
      k = tmp;
    }
    return l;
  }

  pub fn union(&mut self, mut v: usize, mut w: usize) -> usize {
    v = self.find(v);
    w = self.find(w);
    let v_rank = self.trees[v].rank;
    let w_rank = self.trees[w].rank;
    match v_rank.cmp(&w_rank) {
      Ordering::Less => {
        self.trees[v].parent = w;
        return w;
      }
      Ordering::Greater => {
        self.trees[w].parent = v;
        return v;
      }
      Ordering::Equal => {
        self.trees[w].parent = v;
        self.trees[w].rank += 1;
        return v;
      }
    }
  }
}

struct BetterUnionFind {
  basic_union_find: UnionFind,
  internal_to_external: Vec<usize>,
  external_to_internal: Vec<usize>,
}

impl BetterUnionFind {
  pub fn new(size: usize) -> BetterUnionFind {
    let basic_union_find = UnionFind::new(size);
    let mut internal_to_external = Vec::with_capacity(size);
    let mut external_to_internal = Vec::with_capacity(size);
    for i in 0..size {
      internal_to_external.push(i);
      external_to_internal.push(i);
    }
    return BetterUnionFind {
      basic_union_find: basic_union_find,
      internal_to_external: internal_to_external,
      external_to_internal: external_to_internal
    }
  }

  pub fn find(&mut self, k: usize) -> usize {
    return self.internal_to_external[self.basic_union_find.find(self.external_to_internal[k])];
  }

  pub fn union(&mut self, v: usize, w: usize) -> usize {
    let u = self.basic_union_find.union(self.external_to_internal[v], self.external_to_internal[w]);
    self.external_to_internal[v] = u;
    self.external_to_internal[w] = u;
    self.internal_to_external[u] = v;
    return v;
  }
}

#[derive(Copy, Clone)]
enum Operation {
  Delete,
  Insert(usize)
}

fn offline_min(operations: &[Operation]) -> Vec<usize> {
  if operations.len() == 0 { return vec![]; }
  let mut max_number = 0;
  let mut num_delete_ops = 0;
  for op in operations {
    match *op {
      Operation::Insert(l) => { max_number = std::cmp::max(max_number, l); }
      Operation::Delete    => { num_delete_ops += 1; }
    }
  }
  let mut union_find = BetterUnionFind::new((num_delete_ops + 1) + (max_number + 1));

  // initialize union_find
  let mut last_op = operations[0];
  let mut delete_index = 0;
  for op in operations.iter().skip(1) {
    match (last_op, *op) {
      (Operation::Insert(l), Operation::Delete) => {
        union_find.union(delete_index, num_delete_ops+1+l);
        delete_index += 1;
      }
      (Operation::Insert(l), Operation::Insert(k)) => {
        union_find.union(num_delete_ops+1+k, num_delete_ops+1+l);
      }
      (Operation::Delete, Operation::Delete) => {
        delete_index += 1;
      }
      (Operation::Delete, Operation::Insert(_)) => {}
    }
    last_op = *op;
  }

  // compute results
  let mut results = std::iter::repeat(0).take(num_delete_ops).collect::<Vec<_>>();
  for i in 0..max_number {
    let d = union_find.find(num_delete_ops+1+i);
    if d < num_delete_ops {
      results[d] = i;
      let next_delete = union_find.find(d+1);
      union_find.union(next_delete, d);
    }
  }

  return results;
}

fn main() {
  let test_vec = vec![
    Operation::Insert(2), Operation::Insert(3), Operation::Delete, Operation::Insert(4),
    Operation::Insert(1), Operation::Delete, Operation::Delete
  ];
  let result = offline_min(&test_vec);
  for (delete_index, deleted_number) in result.iter().enumerate() {
    println!("The DELETE operation #{} deletes {}", delete_index, deleted_number);
  }
}