tesseract 4.1.1
Loading...
Searching...
No Matches
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
27#include "genericvector.h"
28
29namespace 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.
33template <typename Key, typename Data>
34struct 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.
50template <typename Key, typename Data>
51struct 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.
66template <typename Key, typename Data>
67struct 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.
87template <typename Key, typename Data>
88class 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.
144template <typename Key, typename Data>
145struct 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) {}
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.
161template <typename Key, typename Data>
162struct 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) {}
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.
182class 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_
int operator==(const KDPair< Key, Data > &other) const
Definition: kdpair.h:38
KDPair(Key k, Data d)
Definition: kdpair.h:36
int operator<(const KDPairInc< Key, Data > &other) const
Definition: kdpair.h:55
static KDPairInc * RecastDataPointer(Data *data_ptr)
Definition: kdpair.h:60
KDPairInc(Key k, Data d)
Definition: kdpair.h:53
KDPairDec(Key k, Data d)
Definition: kdpair.h:69
static KDPairDec * RecastDataPointer(Data *data_ptr)
Definition: kdpair.h:77
int operator<(const KDPairDec< Key, Data > &other) const
Definition: kdpair.h:72
void set_data(Data *new_data)
Definition: kdpair.h:126
const Data * data() const
Definition: kdpair.h:122
KDPtrPair(KDPtrPair &src)
Definition: kdpair.h:94
const Key & key() const
Definition: kdpair.h:116
void set_key(const Key &new_key)
Definition: kdpair.h:119
Data * extract_data()
Definition: kdpair.h:131
int operator==(const KDPtrPair< Key, Data > &other) const
Definition: kdpair.h:111
void operator=(KDPtrPair &src)
Definition: kdpair.h:104
KDPtrPair(Key k, Data *d)
Definition: kdpair.h:91
int operator<(const KDPtrPairInc< Key, Data > &other) const
Definition: kdpair.h:155
void operator=(KDPtrPairInc &src)
Definition: kdpair.h:151
KDPtrPairInc(KDPtrPairInc &src)
Definition: kdpair.h:150
KDPtrPairInc(Key k, Data *d)
Definition: kdpair.h:149
int operator<(const KDPtrPairDec< Key, Data > &other) const
Definition: kdpair.h:173
KDPtrPairDec(KDPtrPairDec &src)
Definition: kdpair.h:167
void operator=(KDPtrPairDec &src)
Definition: kdpair.h:168
KDPtrPairDec(Key k, Data *d)
Definition: kdpair.h:166