Tesseract 3.02

- Main Page
- Related Pages
- Modules
- Namespaces
- Classes
- Files

- File List
- File Members

All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
sorthelper.h
Go to the documentation of this file.
1
2 // File: sorthelper.h
3 // Description: Generic sort and maxfinding class.
4 // Author: Ray Smith
5 // Created: Thu May 20 17:48:21 PDT 2010
6 //
7 // (C) Copyright 2010, Google Inc.
8 // Licensed under the Apache License, Version 2.0 (the "License");
9 // you may not use this file except in compliance with the License.
10 // You may obtain a copy of the License at
11 // http://www.apache.org/licenses/LICENSE-2.0
12 // Unless required by applicable law or agreed to in writing, software
13 // distributed under the License is distributed on an "AS IS" BASIS,
14 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15 // See the License for the specific language governing permissions and
16 // limitations under the License.
17 //
19
20 #ifndef TESSERACT_CCUTIL_SORTHELPER_H_
21 #define TESSERACT_CCUTIL_SORTHELPER_H_
22
23 #include <stdlib.h>
24 #include "genericvector.h"
25
26 // Generic class to provide functions based on a <value,count> pair.
27 // T is the value type.
28 // The class keeps a count of each value and can return the most frequent
29 // value or a sorted array of the values with counts.
30 // Note that this class uses linear search for adding. It is better
31 // to use the STATS class to get the mode of a large number of values
32 // in a small space. SortHelper is better to get the mode of a small number
33 // of values from a large space.
34 // T must have a copy constructor.
35 template <typename T>
36 class SortHelper {
37 public:
38 // Simple pair class to hold the values and counts.
39 template<typename PairT> struct SortPair {
40 PairT value;
41 int count;
42 };
43 // qsort function to sort by decreasing count.
44 static int SortPairsByCount(const void* v1, const void* v2) {
45 const SortPair<T>* p1 = reinterpret_cast<const SortPair<T>*>(v1);
46 const SortPair<T>* p2 = reinterpret_cast<const SortPair<T>*>(v2);
47 return p2->count - p1->count;
48 }
49 // qsort function to sort by decreasing value.
50 static int SortPairsByValue(const void* v1, const void* v2) {
51 const SortPair<T>* p1 = reinterpret_cast<const SortPair<T>*>(v1);
52 const SortPair<T>* p2 = reinterpret_cast<const SortPair<T>*>(v2);
53 if (p2->value - p1->value < 0) return -1;
54 if (p2->value - p1->value > 0) return 1;
55 return 0;
56 }
57
58 // Constructor takes a hint of the array size, but it need not be accurate.
59 explicit SortHelper(int sizehint) : counts_(sizehint) {}
60
61 // Add a value that may be a duplicate of an existing value.
62 // Uses a linear search.
63 void Add(T value, int count) {
64 // Linear search for value.
65 for (int i = 0; i < counts_.size(); ++i) {
66 if (counts_[i].value == value) {
67 counts_[i].count += count;
68 return;
69 }
70 }
71 SortPair<T> new_pair = {value, count};
72 counts_.push_back(SortPair<T>(new_pair));
73 }
74
75 // Returns the frequency of the most frequent value.
76 // If max_value is not NULL, returns the most frequent value.
77 // If the array is empty, returns -MAX_INT32 and max_value is unchanged.
78 int MaxCount(T* max_value) const {
79 int best_count = -MAX_INT32;
80 for (int i = 0; i < counts_.size(); ++i) {
81 if (counts_[i].count > best_count) {
82 best_count = counts_[i].count;
83 if (max_value != NULL)
84 *max_value = counts_[i].value;
85 }
86 }
87 return best_count;
88 }
89
90 // Returns the data array sorted by decreasing frequency.
91 const GenericVector<SortPair<T> >& SortByCount() {
92 counts_.sort(&SortPairsByCount);
93 return counts_;
94 }
95 // Returns the data array sorted by decreasing value.
96 const GenericVector<SortPair<T> >& SortByValue() {
97 counts_.sort(&SortPairsByValue);
98 return counts_;
99 }
100
101 private:
102 GenericVector<SortPair<T> > counts_;
103 };
104
105
106 #endif // TESSERACT_CCUTIL_SORTHELPER_H_.