1 
2 // Licensed under the Apache License, Version 2.0 (the "License");
3 // you may not use this file except in compliance with the License.
4 // You may obtain a copy of the License at
5 //
6 //     http://www.apache.org/licenses/LICENSE-2.0
7 //
8 // Unless required by applicable law or agreed to in writing, software
9 // distributed under the License is distributed on an "AS IS" BASIS,
10 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11 // See the License for the specific language governing permissions and
12 // limitations under the License.
13 //
14 // Copyright 2005-2010 Google, Inc.
15 // Author: wojciech@google.com (Wojciech Skut)
16 //
17 // \file Union-Find algorithm for dense sets of non-negative
18 // integers. Implemented using disjoint tree forests with rank
19 // heuristics and path compression.
20 
21 #ifndef __fst_union_find_inl_h__
22 #define __fst_union_find_inl_h__
23 
24 #include <stack>
25 #include <vector>
26 using std::vector;
27 #include <fst/types.h>
28 
29 namespace fst {
30 
31 // Union-Find algorithm for dense sets of non-negative integers
32 // (exact type: T).
33 template <class T>
34 class UnionFind {
35  public:
36   // Ctor: creates a disjoint set forest for the range [0;max).
37   // 'fail' is a value indicating that an element hasn't been
38   // initialized using MakeSet(...). The upper bound of the range
39   // can be reset (increased) using MakeSet(...).
UnionFind(T max,T fail)40   UnionFind(T max, T fail)
41       : parent_(max, fail), rank_(max), fail_(fail) { }
42 
43   // Finds the representative of the set 'item' belongs to.
44   // Performs path compression if needed.
FindSet(T item)45   T FindSet(T item) {
46     if (item >= parent_.size()
47         || item == fail_
48         || parent_[item] == fail_) return fail_;
49 
50     T *p = &parent_[item];
51     for (; *p != item; item = *p, p = &parent_[item]) {
52       exec_stack_.push(p);
53     }
54     for (; ! exec_stack_.empty(); exec_stack_.pop()) {
55       *exec_stack_.top() = *p;
56     }
57     return *p;
58   }
59 
60   // Creates the (destructive) union of the sets x and y belong to.
Union(T x,T y)61   void Union(T x, T y) {
62     Link(FindSet(x), FindSet(y));
63   }
64 
65   // Initialization of an element: creates a singleton set containing
66   // 'item'. The range [0;max) is reset if item >= max.
MakeSet(T item)67   T MakeSet(T item) {
68     if (item >= parent_.size()) {
69       // New value in parent_ should be initialized to fail_
70       size_t nitem = item > 0 ? 2 * item : 2;
71       parent_.resize(nitem, fail_);
72       rank_.resize(nitem);
73     }
74     parent_[item] = item;
75     return item;
76   }
77 
78   // Initialization of all elements starting from 0 to max - 1 to distinct sets
MakeAllSet(T max)79   void MakeAllSet(T max) {
80     parent_.resize(max);
81     for (T item = 0; item < max; ++item) {
82       parent_[item] = item;
83     }
84   }
85 
86  private:
87   vector<T> parent_;      // Parent nodes.
88   vector<int> rank_;      // Rank of an element = min. depth in tree.
89   T fail_;                // Value indicating lookup failure.
90   stack<T*> exec_stack_;  // Used for path compression.
91 
92   // Links trees rooted in 'x' and 'y'.
Link(T x,T y)93   void Link(T x, T y) {
94     if (x == y) return;
95 
96     if (rank_[x] > rank_[y]) {
97       parent_[y] = x;
98     } else {
99       parent_[x] = y;
100       if (rank_[x] == rank_[y]) {
101         ++rank_[y];
102       }
103     }
104   }
105   DISALLOW_COPY_AND_ASSIGN(UnionFind);
106 };
107 
108 }  // namespace fst
109 
110 #endif  // __fst_union_find_inl_h__
111