Blame view
src/util/const-integer-set.h
2.91 KB
8dcb6dfcb
first commit
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 |
// util/const-integer-set.h
// Copyright 2009-2011 Microsoft Corporation
// See ../../COPYING for clarification regarding multiple authors
//
// 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
//
// THIS CODE IS PROVIDED *AS IS* BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
// KIND, EITHER EXPRESS OR IMPLIED, INCLUDING WITHOUT LIMITATION ANY IMPLIED
// WARRANTIES OR CONDITIONS OF TITLE, FITNESS FOR A PARTICULAR PURPOSE,
// MERCHANTABLITY OR NON-INFRINGEMENT.
// See the Apache 2 License for the specific language governing permissions and
// limitations under the License.
#ifndef KALDI_UTIL_CONST_INTEGER_SET_H_
#define KALDI_UTIL_CONST_INTEGER_SET_H_
#include <vector>
#include <set>
#include <algorithm>
#include <limits>
#include <cassert>
#include "util/stl-utils.h"
/* ConstIntegerSet is a way to efficiently test whether something is in a
supplied set of integers. It can be initialized from a vector or set, but
never changed after that. It either uses a sorted vector or an array of
bool, depending on the input. It behaves like a const version of an STL set, with
only a subset of the functionality, except all the member functions are
upper-case.
Note that we could get rid of the member slow_set_, but we'd have to
do more work to implement an iterator type. This would save memory.
*/
namespace kaldi {
template<class I> class ConstIntegerSet {
public:
ConstIntegerSet(): lowest_member_(1), highest_member_(0) { }
void Init(const std::vector<I> &input) {
slow_set_ = input;
SortAndUniq(&slow_set_);
InitInternal();
}
void Init(const std::set<I> &input) {
CopySetToVector(input, &slow_set_);
InitInternal();
}
explicit ConstIntegerSet(const std::vector<I> &input): slow_set_(input) {
SortAndUniq(&slow_set_);
InitInternal();
}
explicit ConstIntegerSet(const std::set<I> &input) {
CopySetToVector(input, &slow_set_);
InitInternal();
}
explicit ConstIntegerSet(const ConstIntegerSet<I> &other):
slow_set_(other.slow_set_) {
InitInternal();
}
int count(I i) const; // returns 1 or 0.
typedef typename std::vector<I>::const_iterator iterator;
iterator begin() const { return slow_set_.begin(); }
iterator end() const { return slow_set_.end(); }
size_t size() const { return slow_set_.size(); }
bool empty() const { return slow_set_.empty(); }
void Write(std::ostream &os, bool binary) const;
void Read(std::istream &is, bool binary);
private:
I lowest_member_;
I highest_member_;
bool contiguous_;
bool quick_;
std::vector<bool> quick_set_;
std::vector<I> slow_set_;
void InitInternal();
};
} // end namespace kaldi
#include "util/const-integer-set-inl.h"
#endif // KALDI_UTIL_CONST_INTEGER_SET_H_
|