1 files changed, 0 insertions, 110 deletions
diff --git a/kaldi_io/src/tools/openfst/include/fst/union-find.h b/kaldi_io/src/tools/openfst/include/fst/union-find.h
deleted file mode 100644
index c8633e0..0000000
--- a/kaldi_io/src/tools/openfst/include/fst/union-find.h
+++ /dev/null
@@ -1,110 +0,0 @@
-
-// Licensed under the Apache License, Version 2.0 (the "License");
-// you may not use this file except in compliance with the License.
-// You may obtain a copy of the License at
-//
-// http://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing, software
-// distributed under the License is distributed on an "AS IS" BASIS,
-// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-// See the License for the specific language governing permissions and
-// limitations under the License.
-//
-// Copyright 2005-2010 Google, Inc.
-// Author: [email protected] (Wojciech Skut)
-//
-// \file Union-Find algorithm for dense sets of non-negative
-// integers. Implemented using disjoint tree forests with rank
-// heuristics and path compression.
-
-#ifndef __fst_union_find_inl_h__
-#define __fst_union_find_inl_h__
-
-#include <stack>
-#include <vector>
-using std::vector;
-#include <fst/types.h>
-
-namespace fst {
-
-// Union-Find algorithm for dense sets of non-negative integers
-// (exact type: T).
-template <class T>
-class UnionFind {
- public:
- // Ctor: creates a disjoint set forest for the range [0;max).
- // 'fail' is a value indicating that an element hasn't been
- // initialized using MakeSet(...). The upper bound of the range
- // can be reset (increased) using MakeSet(...).
- UnionFind(T max, T fail)
- : parent_(max, fail), rank_(max), fail_(fail) { }
-
- // Finds the representative of the set 'item' belongs to.
- // Performs path compression if needed.
- T FindSet(T item) {
- if (item >= parent_.size()
- || item == fail_
- || parent_[item] == fail_) return fail_;
-
- T *p = &parent_[item];
- for (; *p != item; item = *p, p = &parent_[item]) {
- exec_stack_.push(p);
- }
- for (; ! exec_stack_.empty(); exec_stack_.pop()) {
- *exec_stack_.top() = *p;
- }
- return *p;
- }
-
- // Creates the (destructive) union of the sets x and y belong to.
- void Union(T x, T y) {
- Link(FindSet(x), FindSet(y));
- }
-
- // Initialization of an element: creates a singleton set containing
- // 'item'. The range [0;max) is reset if item >= max.
- T MakeSet(T item) {
- if (item >= parent_.size()) {
- // New value in parent_ should be initialized to fail_
- size_t nitem = item > 0 ? 2 * item : 2;
- parent_.resize(nitem, fail_);
- rank_.resize(nitem);
- }
- parent_[item] = item;
- return item;
- }
-
- // Initialization of all elements starting from 0 to max - 1 to distinct sets
- void MakeAllSet(T max) {
- parent_.resize(max);
- for (T item = 0; item < max; ++item) {
- parent_[item] = item;
- }
- }
-
- private:
- vector<T> parent_; // Parent nodes.
- vector<int> rank_; // Rank of an element = min. depth in tree.
- T fail_; // Value indicating lookup failure.
- stack<T*> exec_stack_; // Used for path compression.
-
- // Links trees rooted in 'x' and 'y'.
- void Link(T x, T y) {
- if (x == y) return;
-
- if (rank_[x] > rank_[y]) {
- parent_[y] = x;
- } else {
- parent_[x] = y;
- if (rank_[x] == rank_[y]) {
- ++rank_[y];
- }
- }
- }
- DISALLOW_COPY_AND_ASSIGN(UnionFind);
-};
-
-} // namespace fst
-
-#endif // __fst_union_find_inl_h__