Tesseract  3.02
 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.
92  counts_.sort(&SortPairsByCount);
93  return counts_;
94  }
95  // Returns the data array sorted by decreasing value.
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_.