tesseract  5.0.0
kdpair.h
Go to the documentation of this file.
1 // Copyright 2012 Google Inc. All Rights Reserved.
2 // Author: rays@google.com (Ray Smith)
4 // File: kdpair.h
5 // Description: Template pair class like STL pair but geared towards
6 // the Key+Data design pattern in which some data needs
7 // to be sorted or kept in a heap sorted on some separate key.
8 // Author: Ray Smith.
9 //
10 // (C) Copyright 2012, Google Inc.
11 // Licensed under the Apache License, Version 2.0 (the "License");
12 // you may not use this file except in compliance with the License.
13 // You may obtain a copy of the License at
14 // http://www.apache.org/licenses/LICENSE-2.0
15 // Unless required by applicable law or agreed to in writing, software
16 // distributed under the License is distributed on an "AS IS" BASIS,
17 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
18 // See the License for the specific language governing permissions and
19 // limitations under the License.
20 //
22 
23 #ifndef TESSERACT_CCUTIL_KDPAIR_H_
24 #define TESSERACT_CCUTIL_KDPAIR_H_
25 
26 #include <vector>
27 
28 namespace tesseract {
29 
30 // A useful base struct to facilitate the common operation of sorting a vector
31 // of simple or smart-pointer data using a separate key. Similar to STL pair.
32 template <typename Key, typename Data>
33 struct KDPair {
34  KDPair() = default;
35  KDPair(Key k, Data d) : data_(d), key_(k) {}
36 
37  int operator==(const KDPair<Key, Data> &other) const {
38  return key_ == other.key_;
39  }
40 
41  Data &data() {
42  return data_;
43  }
44  const Data &data() const {
45  return data_;
46  }
47  Key &key() {
48  return key_;
49  }
50  const Key &key() const {
51  return key_;
52  }
53 
54  // WARNING! Keep data as the first element! KDPairInc and KDPairDec depend
55  // on the order of these elements so they can downcast pointers appropriately
56  // for use by GenericHeap::Reshuffle.
57  Data data_;
58  Key key_;
59 };
60 // Specialization of KDPair to provide operator< for sorting in increasing order
61 // and recasting of data pointers for use with DoublePtr.
62 template <typename Key, typename Data>
63 struct KDPairInc : public KDPair<Key, Data> {
64  KDPairInc() = default;
65  KDPairInc(Key k, Data d) : KDPair<Key, Data>(k, d) {}
66  // Operator< facilitates sorting in increasing order.
67  int operator<(const KDPairInc<Key, Data> &other) const {
68  return this->key() < other.key();
69  }
70  // Returns the input Data pointer recast to a KDPairInc pointer.
71  // Just casts a pointer to the first element to a pointer to the whole struct.
72  static KDPairInc *RecastDataPointer(Data *data_ptr) {
73  return reinterpret_cast<KDPairInc *>(data_ptr);
74  }
75 };
76 // Specialization of KDPair to provide operator< for sorting in decreasing order
77 // and recasting of data pointers for use with DoublePtr.
78 template <typename Key, typename Data>
79 struct KDPairDec : public KDPair<Key, Data> {
80  KDPairDec() = default;
81  KDPairDec(Key k, Data d) : KDPair<Key, Data>(k, d) {}
82  // Operator< facilitates sorting in decreasing order by using operator> on
83  // the key values.
84  int operator<(const KDPairDec<Key, Data> &other) const {
85  return this->key() > other.key();
86  }
87  // Returns the input Data pointer recast to a KDPairDec pointer.
88  // Just casts a pointer to the first element to a pointer to the whole struct.
89  static KDPairDec *RecastDataPointer(Data *data_ptr) {
90  return reinterpret_cast<KDPairDec *>(data_ptr);
91  }
92 };
93 
94 // A useful base class to facilitate the common operation of sorting a vector
95 // of owned pointer data using a separate key. This class owns its data pointer,
96 // deleting it when it has finished with it, and providing copy constructor and
97 // operator= that have move semantics so that the data does not get copied and
98 // only a single instance of KDPtrPair holds a specific data pointer.
99 template <typename Key, typename Data>
100 class KDPtrPair {
101 public:
102  KDPtrPair() : data_(nullptr) {}
103  KDPtrPair(Key k, Data *d) : data_(d), key_(k) {}
104  // Copy constructor steals the pointer from src and nulls it in src, thereby
105  // moving the (single) ownership of the data.
106  KDPtrPair(const KDPtrPair &src) : data_(src.data_), key_(src.key_) {
107  ((KDPtrPair &)src).data_ = nullptr;
108  }
109  // Destructor deletes data, assuming it is the sole owner.
111  delete this->data_;
112  this->data_ = nullptr;
113  }
114  // Operator= steals the pointer from src and nulls it in src, thereby
115  // moving the (single) ownership of the data.
116  void operator=(const KDPtrPair &src) {
117  delete this->data_;
118  this->data_ = src.data_;
119  ((KDPtrPair &)src).data_ = nullptr;
120  this->key_ = src.key_;
121  }
122 
123  int operator==(const KDPtrPair<Key, Data> &other) const {
124  return key_ == other.key_;
125  }
126 
127  // Accessors.
128  const Key &key() const {
129  return key_;
130  }
131  void set_key(const Key &new_key) {
132  key_ = new_key;
133  }
134  const Data *data() const {
135  return data_;
136  }
137  // Sets the data pointer, taking ownership of the data.
138  void set_data(Data *new_data) {
139  delete data_;
140  data_ = new_data;
141  }
142  // Relinquishes ownership of the data pointer (setting it to nullptr).
143  Data *extract_data() {
144  Data *result = data_;
145  data_ = nullptr;
146  return result;
147  }
148 
149 private:
150  // Data members are private to keep deletion of data_ encapsulated.
151  Data *data_;
152  Key key_;
153 };
154 // Specialization of KDPtrPair to provide operator< for sorting in increasing
155 // order.
156 template <typename Key, typename Data>
157 struct KDPtrPairInc : public KDPtrPair<Key, Data> {
158  // Since we are doing non-standard stuff we have to duplicate *all* the
159  // constructors and operator=.
160  KDPtrPairInc() : KDPtrPair<Key, Data>() {}
161  KDPtrPairInc(Key k, Data *d) : KDPtrPair<Key, Data>(k, d) {}
162  KDPtrPairInc(const KDPtrPairInc &src) : KDPtrPair<Key, Data>(src) {}
163  void operator=(const KDPtrPairInc &src) {
165  }
166  // Operator< facilitates sorting in increasing order.
167  int operator<(const KDPtrPairInc<Key, Data> &other) const {
168  return this->key() < other.key();
169  }
170 };
171 // Specialization of KDPtrPair to provide operator< for sorting in decreasing
172 // order.
173 template <typename Key, typename Data>
174 struct KDPtrPairDec : public KDPtrPair<Key, Data> {
175  // Since we are doing non-standard stuff we have to duplicate *all* the
176  // constructors and operator=.
177  KDPtrPairDec() : KDPtrPair<Key, Data>() {}
178  KDPtrPairDec(Key k, Data *d) : KDPtrPair<Key, Data>(k, d) {}
179  KDPtrPairDec(const KDPtrPairDec &src) : KDPtrPair<Key, Data>(src) {}
180  void operator=(const KDPtrPairDec &src) {
182  }
183  // Operator< facilitates sorting in decreasing order by using operator> on
184  // the key values.
185  int operator<(const KDPtrPairDec<Key, Data> &other) const {
186  return this->key() > other.key();
187  }
188 };
189 
190 // Specialization for a pair of ints in increasing order.
192 
193 // Vector of IntKDPair.
194 class KDVector : public std::vector<IntKDPair> {
195  // TODO(rays) Add some code to manipulate a KDVector. For now there
196  // is nothing and this class is effectively a specialization typedef.
197 };
198 
199 } // namespace tesseract
200 
201 #endif // TESSERACT_CCUTIL_KDPAIR_H_
Key & key()
Definition: kdpair.h:47
const Data & data() const
Definition: kdpair.h:44
int operator==(const KDPair< Key, Data > &other) const
Definition: kdpair.h:37
KDPair(Key k, Data d)
Definition: kdpair.h:35
Data & data()
Definition: kdpair.h:41
const Key & key() const
Definition: kdpair.h:50
int operator<(const KDPairInc< Key, Data > &other) const
Definition: kdpair.h:67
KDPairInc(Key k, Data d)
Definition: kdpair.h:65
static KDPairInc * RecastDataPointer(Data *data_ptr)
Definition: kdpair.h:72
KDPairDec(Key k, Data d)
Definition: kdpair.h:81
int operator<(const KDPairDec< Key, Data > &other) const
Definition: kdpair.h:84
static KDPairDec * RecastDataPointer(Data *data_ptr)
Definition: kdpair.h:89
void operator=(const KDPtrPair &src)
Definition: kdpair.h:116
void set_data(Data *new_data)
Definition: kdpair.h:138
const Key & key() const
Definition: kdpair.h:128
void set_key(const Key &new_key)
Definition: kdpair.h:131
KDPtrPair(const KDPtrPair &src)
Definition: kdpair.h:106
Data * extract_data()
Definition: kdpair.h:143
int operator==(const KDPtrPair< Key, Data > &other) const
Definition: kdpair.h:123
const Data * data() const
Definition: kdpair.h:134
KDPtrPair(Key k, Data *d)
Definition: kdpair.h:103
int operator<(const KDPtrPairInc< Key, Data > &other) const
Definition: kdpair.h:167
void operator=(const KDPtrPairInc &src)
Definition: kdpair.h:163
KDPtrPairInc(const KDPtrPairInc &src)
Definition: kdpair.h:162
KDPtrPairInc(Key k, Data *d)
Definition: kdpair.h:161
void operator=(const KDPtrPairDec &src)
Definition: kdpair.h:180
int operator<(const KDPtrPairDec< Key, Data > &other) const
Definition: kdpair.h:185
KDPtrPairDec(const KDPtrPairDec &src)
Definition: kdpair.h:179
KDPtrPairDec(Key k, Data *d)
Definition: kdpair.h:178