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