Skip to content

Instantly share code, notes, and snippets.

@timjb
Last active January 23, 2018 10:01
Show Gist options
  • Save timjb/dbcc65a4cfbaac7e0c9974b805c08768 to your computer and use it in GitHub Desktop.
Save timjb/dbcc65a4cfbaac7e0c9974b805c08768 to your computer and use it in GitHub Desktop.
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);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment