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