union-find.h revision 4a68b3365c8c50aa93505e99ead2565ab73dcdb0
14a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// union-find.h
24a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project//
34a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Licensed under the Apache License, Version 2.0 (the "License");
44a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// you may not use this file except in compliance with the License.
54a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// You may obtain a copy of the License at
64a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project//
74a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project//      http://www.apache.org/licenses/LICENSE-2.0
84a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project//
94a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Unless required by applicable law or agreed to in writing, software
104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// distributed under the License is distributed on an "AS IS" BASIS,
114a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// See the License for the specific language governing permissions and
134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// limitations under the License.
144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project//
154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project//
164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// \file Union-Find algorithm for dense sets of non-negative
174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// integers. Implemented using disjoint tree forests with rank
184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// heuristics and path compression.
194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#ifndef __fst_union_find_inl_h__
214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#define __fst_union_find_inl_h__
224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include <stack>
244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include <vector>
254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectnamespace fst {
274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Union-Find algorithm for dense sets of non-negative integers
294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// (exact type: T).
304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <class T>
314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectclass UnionFind {
324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project public:
334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  // Ctor: creates a disjoint set forest for the range [0;max).
344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  // 'fail' is a value indicating that an element hasn't been
354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  // initialized using MakeSet(...). The upper bound of the range
364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  // can be reset (increased) using MakeSet(...).
374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  UnionFind(T max, T fail)
384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project      : parent_(max, fail), rank_(max), fail_(fail) { }
394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  // Finds the representative of the set 'item' belongs to.
414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  // Performs path compression if needed.
424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  T FindSet(T item) {
434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    if (item >= parent_.size()
444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project        || item == fail_
454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project        || parent_[item] == fail_) return fail_;
464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    CHECK(exec_stack_.empty());
484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    T *p = &parent_[item];
494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    for (; *p != item; item = *p, p = &parent_[item]) {
504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project      exec_stack_.push(p);
514a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    }
524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    for (; ! exec_stack_.empty(); exec_stack_.pop()) {
534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project      *exec_stack_.top() = *p;
544a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    }
554a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    return *p;
564a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  }
574a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
584a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  // Creates the (destructive) union of the sets x and y belong to.
594a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  void Union(T x, T y) {
604a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    Link(FindSet(x), FindSet(y));
614a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  }
624a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
634a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  // Initialization of an element: creates a singleton set containing
644a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  // 'item'. The range [0;max) is reset if item >= max.
654a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  T MakeSet(T item) {
664a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    if (item >= parent_.size()) {
674a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project      // New value in parent_ should be initialized to fail_
684a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project      parent_.resize(2 * item, fail_);
694a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project      rank_.resize(2 * item);
704a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    }
714a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    parent_[item] = item;
724a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    return item;
734a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  }
744a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
754a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  // Initialization of all elements starting from 0 to max - 1 to distinct sets
764a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  void MakeAllSet(T max) {
774a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    parent_.resize(max);
784a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    for (T item = 0; item < max; ++item) {
794a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project      parent_[item] = item;
804a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    }
814a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  }
824a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
834a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project private:
844a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  vector<T> parent_;      // Parent nodes.
854a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  vector<int> rank_;      // Rank of an element = min. depth in tree.
864a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  T fail_;                // Value indicating lookup failure.
874a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  stack<T*> exec_stack_;  // Used for path compression.
884a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
894a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  // Links trees rooted in 'x' and 'y'.
904a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  void Link(T x, T y) {
914a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    if (x == y) return;
924a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
934a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    if (rank_[x] > rank_[y]) {
944a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project      parent_[y] = x;
954a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    } else {
964a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project      parent_[x] = y;
974a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project      if (rank_[x] == rank_[y]) {
984a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project        ++rank_[y];
994a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project      }
1004a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project    }
1014a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  }
1024a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project  DISALLOW_EVIL_CONSTRUCTORS(UnionFind);
1034a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project};
1044a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
1054a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project}
1064a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project
1074a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#endif  // __fst_union_find_inl_h__
108