tesseract  3.05.01
genericvector.h
Go to the documentation of this file.
1 // File: genericvector.h
3 // Description: Generic vector class
4 // Author: Daria Antonova
5 // Created: Mon Jun 23 11:26:43 PDT 2008
6 //
7 // (C) Copyright 2007, 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_GENERICVECTOR_H_
21 #define TESSERACT_CCUTIL_GENERICVECTOR_H_
22 
23 #include <assert.h>
24 #include <stdio.h>
25 #include <stdlib.h>
26 
27 #include "tesscallback.h"
28 #include "errcode.h"
29 #include "helpers.h"
30 #include "ndminx.h"
31 #include "serialis.h"
32 #include "strngs.h"
33 
34 // Use PointerVector<T> below in preference to GenericVector<T*>, as that
35 // provides automatic deletion of pointers, [De]Serialize that works, and
36 // sort that works.
37 template <typename T>
38 class GenericVector {
39  public:
41  clear_cb_(NULL), compare_cb_(NULL) {}
42 
43  GenericVector(int size, T init_val) {
44  init(size);
45  init_to_size(size, init_val);
46  }
47 
48  // Copy
49  GenericVector(const GenericVector& other) {
50  this->init(other.size());
51  this->operator+=(other);
52  }
55 
57 
58  // Reserve some memory.
59  void reserve(int size);
60  // Double the size of the internal array.
61  void double_the_size();
62 
63  // Resizes to size and sets all values to t.
64  void init_to_size(int size, T t);
65  // Resizes to size without any initialization.
66  void resize_no_init(int size) {
67  reserve(size);
68  size_used_ = size;
69  }
70 
71  // Return the size used.
72  int size() const {
73  return size_used_;
74  }
75  int size_reserved() const {
76  return size_reserved_;
77  }
78 
79  int length() const {
80  return size_used_;
81  }
82 
83  // Return true if empty.
84  bool empty() const {
85  return size_used_ == 0;
86  }
87 
88  // Return the object from an index.
89  T &get(int index) const;
90  T &back() const;
91  T &operator[](int index) const;
92  // Returns the last object and removes it.
93  T pop_back();
94 
95  // Return the index of the T object.
96  // This method NEEDS a compare_callback to be passed to
97  // set_compare_callback.
98  int get_index(T object) const;
99 
100  // Return true if T is in the array
101  bool contains(T object) const;
102 
103  // Return true if the index is valid
104  T contains_index(int index) const;
105 
106  // Push an element in the end of the array
107  int push_back(T object);
108  void operator+=(T t);
109 
110  // Push an element in the end of the array if the same
111  // element is not already contained in the array.
112  int push_back_new(T object);
113 
114  // Push an element in the front of the array
115  // Note: This function is O(n)
116  int push_front(T object);
117 
118  // Set the value at the given index
119  void set(T t, int index);
120 
121  // Insert t at the given index, push other elements to the right.
122  void insert(T t, int index);
123 
124  // Removes an element at the given index and
125  // shifts the remaining elements to the left.
126  void remove(int index);
127 
128  // Truncates the array to the given size by removing the end.
129  // If the current size is less, the array is not expanded.
130  void truncate(int size) {
131  if (size < size_used_)
132  size_used_ = size;
133  }
134 
135  // Add a callback to be called to delete the elements when the array took
136  // their ownership.
138 
139  // Add a callback to be called to compare the elements when needed (contains,
140  // get_id, ...)
142 
143  // Clear the array, calling the clear callback function if any.
144  // All the owned callbacks are also deleted.
145  // If you don't want the callbacks to be deleted, before calling clear, set
146  // the callback to NULL.
147  void clear();
148 
149  // Delete objects pointed to by data_[i]
150  void delete_data_pointers();
151 
152  // This method clears the current object, then, does a shallow copy of
153  // its argument, and finally invalidates its argument.
154  // Callbacks are moved to the current object;
155  void move(GenericVector<T>* from);
156 
157  // Read/Write the array to a file. This does _NOT_ read/write the callbacks.
158  // The callback given must be permanent since they will be called more than
159  // once. The given callback will be deleted at the end.
160  // If the callbacks are NULL, then the data is simply read/written using
161  // fread (and swapping)/fwrite.
162  // Returns false on error or if the callback returns false.
163  // DEPRECATED. Use [De]Serialize[Classes] instead.
164  bool write(FILE* f, TessResultCallback2<bool, FILE*, T const &>* cb) const;
165  bool read(FILE* f, TessResultCallback3<bool, FILE*, T*, bool>* cb, bool swap);
166  // Writes a vector of simple types to the given file. Assumes that bitwise
167  // read/write of T will work. Returns false in case of error.
168  // TODO(rays) Change all callers to use TFile and remove deprecated methods.
169  bool Serialize(FILE* fp) const;
170  bool Serialize(tesseract::TFile* fp) const;
171  // Reads a vector of simple types from the given file. Assumes that bitwise
172  // read/write will work with ReverseN according to sizeof(T).
173  // Returns false in case of error.
174  // If swap is true, assumes a big/little-endian swap is needed.
175  bool DeSerialize(bool swap, FILE* fp);
176  bool DeSerialize(bool swap, tesseract::TFile* fp);
177  // Skips the deserialization of the vector.
178  static bool SkipDeSerialize(bool swap, tesseract::TFile* fp);
179  // Writes a vector of classes to the given file. Assumes the existence of
180  // bool T::Serialize(FILE* fp) const that returns false in case of error.
181  // Returns false in case of error.
182  bool SerializeClasses(FILE* fp) const;
183  bool SerializeClasses(tesseract::TFile* fp) const;
184  // Reads a vector of classes from the given file. Assumes the existence of
185  // bool T::Deserialize(bool swap, FILE* fp) that returns false in case of
186  // error. Also needs T::T() and T::T(constT&), as init_to_size is used in
187  // this function. Returns false in case of error.
188  // If swap is true, assumes a big/little-endian swap is needed.
189  bool DeSerializeClasses(bool swap, FILE* fp);
190  bool DeSerializeClasses(bool swap, tesseract::TFile* fp);
191  // Calls SkipDeSerialize on the elements of the vector.
192  static bool SkipDeSerializeClasses(bool swap, tesseract::TFile* fp);
193 
194  // Allocates a new array of double the current_size, copies over the
195  // information from data to the new location, deletes data and returns
196  // the pointed to the new larger array.
197  // This function uses memcpy to copy the data, instead of invoking
198  // operator=() for each element like double_the_size() does.
199  static T *double_the_size_memcpy(int current_size, T *data) {
200  T *data_new = new T[current_size * 2];
201  memcpy(data_new, data, sizeof(T) * current_size);
202  delete[] data;
203  return data_new;
204  }
205 
206  // Reverses the elements of the vector.
207  void reverse() {
208  for (int i = 0; i < size_used_ / 2; ++i)
209  Swap(&data_[i], &data_[size_used_ - 1 - i]);
210  }
211 
212  // Sorts the members of this vector using the less than comparator (cmp_lt),
213  // which compares the values. Useful for GenericVectors to primitive types.
214  // Will not work so great for pointers (unless you just want to sort some
215  // pointers). You need to provide a specialization to sort_cmp to use
216  // your type.
217  void sort();
218 
219  // Sort the array into the order defined by the qsort function comparator.
220  // The comparator function is as defined by qsort, ie. it receives pointers
221  // to two Ts and returns negative if the first element is to appear earlier
222  // in the result and positive if it is to appear later, with 0 for equal.
223  void sort(int (*comparator)(const void*, const void*)) {
224  qsort(data_, size_used_, sizeof(*data_), comparator);
225  }
226 
227  // Searches the array (assuming sorted in ascending order, using sort()) for
228  // an element equal to target and returns true if it is present.
229  // Use binary_search to get the index of target, or its nearest candidate.
230  bool bool_binary_search(const T& target) const {
231  int index = binary_search(target);
232  if (index >= size_used_)
233  return false;
234  return data_[index] == target;
235  }
236  // Searches the array (assuming sorted in ascending order, using sort()) for
237  // an element equal to target and returns the index of the best candidate.
238  // The return value is conceptually the largest index i such that
239  // data_[i] <= target or 0 if target < the whole vector.
240  // NOTE that this function uses operator> so really the return value is
241  // the largest index i such that data_[i] > target is false.
242  int binary_search(const T& target) const {
243  int bottom = 0;
244  int top = size_used_;
245  while (top - bottom > 1) {
246  int middle = (bottom + top) / 2;
247  if (data_[middle] > target)
248  top = middle;
249  else
250  bottom = middle;
251  }
252  return bottom;
253  }
254 
255  // Compact the vector by deleting elements using operator!= on basic types.
256  // The vector must be sorted.
257  void compact_sorted() {
258  if (size_used_ == 0)
259  return;
260 
261  // First element is in no matter what, hence the i = 1.
262  int last_write = 0;
263  for (int i = 1; i < size_used_; ++i) {
264  // Finds next unique item and writes it.
265  if (data_[last_write] != data_[i])
266  data_[++last_write] = data_[i];
267  }
268  // last_write is the index of a valid data cell, so add 1.
269  size_used_ = last_write + 1;
270  }
271 
272  // Compact the vector by deleting elements for which delete_cb returns
273  // true. delete_cb is a permanent callback and will be deleted.
275  int new_size = 0;
276  int old_index = 0;
277  // Until the callback returns true, the elements stay the same.
278  while (old_index < size_used_ && !delete_cb->Run(old_index++))
279  ++new_size;
280  // Now just copy anything else that gets false from delete_cb.
281  for (; old_index < size_used_; ++old_index) {
282  if (!delete_cb->Run(old_index)) {
283  data_[new_size++] = data_[old_index];
284  }
285  }
286  size_used_ = new_size;
287  delete delete_cb;
288  }
289 
290  T dot_product(const GenericVector<T>& other) const {
291  T result = static_cast<T>(0);
292  for (int i = MIN(size_used_, other.size_used_) - 1; i >= 0; --i)
293  result += data_[i] * other.data_[i];
294  return result;
295  }
296 
297  // Returns the index of what would be the target_index_th item in the array
298  // if the members were sorted, without actually sorting. Members are
299  // shuffled around, but it takes O(n) time.
300  // NOTE: uses operator< and operator== on the members.
301  int choose_nth_item(int target_index) {
302  // Make sure target_index is legal.
303  if (target_index < 0)
304  target_index = 0; // ensure legal
305  else if (target_index >= size_used_)
306  target_index = size_used_ - 1;
307  unsigned int seed = 1;
308  return choose_nth_item(target_index, 0, size_used_, &seed);
309  }
310 
311  // Swaps the elements with the given indices.
312  void swap(int index1, int index2) {
313  if (index1 != index2) {
314  T tmp = data_[index1];
315  data_[index1] = data_[index2];
316  data_[index2] = tmp;
317  }
318  }
319  // Returns true if all elements of *this are within the given range.
320  // Only uses operator<
321  bool WithinBounds(const T& rangemin, const T& rangemax) const {
322  for (int i = 0; i < size_used_; ++i) {
323  if (data_[i] < rangemin || rangemax < data_[i])
324  return false;
325  }
326  return true;
327  }
328 
329  protected:
330  // Internal recursive version of choose_nth_item.
331  int choose_nth_item(int target_index, int start, int end, unsigned int* seed);
332 
333  // Init the object, allocating size memory.
334  void init(int size);
335 
336  // We are assuming that the object generally placed in thie
337  // vector are small enough that for efficiency it makes sense
338  // to start with a larger initial size.
339  static const int kDefaultVectorSize = 4;
342  T* data_;
344  // Mutable because Run method is not const
346 };
347 
348 namespace tesseract {
349 
350 // Function to read a GenericVector<char> from a whole file.
351 // Returns false on failure.
352 typedef bool (*FileReader)(const STRING& filename, GenericVector<char>* data);
353 // Function to write a GenericVector<char> to a whole file.
354 // Returns false on failure.
355 typedef bool (*FileWriter)(const GenericVector<char>& data,
356  const STRING& filename);
357 // The default FileReader loads the whole file into the vector of char,
358 // returning false on error.
359 inline bool LoadDataFromFile(const STRING& filename,
360  GenericVector<char>* data) {
361  bool result = false;
362  FILE* fp = fopen(filename.string(), "rb");
363  if (fp != NULL) {
364  fseek(fp, 0, SEEK_END);
365  size_t size = ftell(fp);
366  fseek(fp, 0, SEEK_SET);
367  if (size > 0) {
368  data->resize_no_init(size);
369  result = fread(&(*data)[0], 1, size, fp) == size;
370  }
371  fclose(fp);
372  }
373  return result;
374 }
375 // The default FileWriter writes the vector of char to the filename file,
376 // returning false on error.
377 inline bool SaveDataToFile(const GenericVector<char>& data,
378  const STRING& filename) {
379  FILE* fp = fopen(filename.string(), "wb");
380  if (fp == NULL) return false;
381  bool result =
382  static_cast<int>(fwrite(&data[0], 1, data.size(), fp)) == data.size();
383  fclose(fp);
384  return result;
385 }
386 
387 template <typename T>
388 bool cmp_eq(T const & t1, T const & t2) {
389  return t1 == t2;
390 }
391 
392 // Used by sort()
393 // return < 0 if t1 < t2
394 // return 0 if t1 == t2
395 // return > 0 if t1 > t2
396 template <typename T>
397 int sort_cmp(const void* t1, const void* t2) {
398  const T* a = static_cast<const T *> (t1);
399  const T* b = static_cast<const T *> (t2);
400  if (*a < *b) {
401  return -1;
402  } else if (*b < *a) {
403  return 1;
404  } else {
405  return 0;
406  }
407 }
408 
409 // Used by PointerVector::sort()
410 // return < 0 if t1 < t2
411 // return 0 if t1 == t2
412 // return > 0 if t1 > t2
413 template <typename T>
414 int sort_ptr_cmp(const void* t1, const void* t2) {
415  const T* a = *reinterpret_cast<T * const *>(t1);
416  const T* b = *reinterpret_cast<T * const *>(t2);
417  if (*a < *b) {
418  return -1;
419  } else if (*b < *a) {
420  return 1;
421  } else {
422  return 0;
423  }
424 }
425 
426 // Subclass for a vector of pointers. Use in preference to GenericVector<T*>
427 // as it provides automatic deletion and correct serialization, with the
428 // corollary that all copy operations are deep copies of the pointed-to objects.
429 template<typename T>
430 class PointerVector : public GenericVector<T*> {
431  public:
433  explicit PointerVector(int size) : GenericVector<T*>(size) { }
435  // Clear must be called here, even though it is called again by the base,
436  // as the base will call the wrong clear.
437  clear();
438  }
439  // Copy must be deep, as the pointers will be automatically deleted on
440  // destruction.
441  PointerVector(const PointerVector& other) : GenericVector<T*>(other) {
442  this->init(other.size());
443  this->operator+=(other);
444  }
446  this->reserve(this->size_used_ + other.size_used_);
447  for (int i = 0; i < other.size(); ++i) {
448  this->push_back(new T(*other.data_[i]));
449  }
450  return *this;
451  }
452 
454  if (&other != this) {
455  this->truncate(0);
456  this->operator+=(other);
457  }
458  return *this;
459  }
460 
461  // Removes an element at the given index and
462  // shifts the remaining elements to the left.
463  void remove(int index) {
464  delete GenericVector<T*>::data_[index];
466  }
467 
468  // Truncates the array to the given size by removing the end.
469  // If the current size is less, the array is not expanded.
470  void truncate(int size) {
471  for (int i = size; i < GenericVector<T*>::size_used_; ++i)
472  delete GenericVector<T*>::data_[i];
474  }
475 
476  // Compact the vector by deleting elements for which delete_cb returns
477  // true. delete_cb is a permanent callback and will be deleted.
479  int new_size = 0;
480  int old_index = 0;
481  // Until the callback returns true, the elements stay the same.
482  while (old_index < GenericVector<T*>::size_used_ &&
483  !delete_cb->Run(GenericVector<T*>::data_[old_index++]))
484  ++new_size;
485  // Now just copy anything else that gets false from delete_cb.
486  for (; old_index < GenericVector<T*>::size_used_; ++old_index) {
487  if (!delete_cb->Run(GenericVector<T*>::data_[old_index])) {
488  GenericVector<T*>::data_[new_size++] =
489  GenericVector<T*>::data_[old_index];
490  } else {
491  delete GenericVector<T*>::data_[old_index];
492  }
493  }
495  delete delete_cb;
496  }
497 
498  // Clear the array, calling the clear callback function if any.
499  // All the owned callbacks are also deleted.
500  // If you don't want the callbacks to be deleted, before calling clear, set
501  // the callback to NULL.
502  void clear() {
505  }
506 
507  // Writes a vector of (pointers to) classes to the given file. Assumes the
508  // existence of bool T::Serialize(FILE*) const that returns false in case of
509  // error. There is no Serialize for simple types, as you would have a
510  // normal GenericVector of those.
511  // Returns false in case of error.
512  bool Serialize(FILE* fp) const {
514  if (fwrite(&used, sizeof(used), 1, fp) != 1) return false;
515  for (int i = 0; i < used; ++i) {
516  inT8 non_null = GenericVector<T*>::data_[i] != NULL;
517  if (fwrite(&non_null, sizeof(non_null), 1, fp) != 1) return false;
518  if (non_null && !GenericVector<T*>::data_[i]->Serialize(fp)) return false;
519  }
520  return true;
521  }
522  bool Serialize(TFile* fp) const {
524  if (fp->FWrite(&used, sizeof(used), 1) != 1) return false;
525  for (int i = 0; i < used; ++i) {
526  inT8 non_null = GenericVector<T*>::data_[i] != NULL;
527  if (fp->FWrite(&non_null, sizeof(non_null), 1) != 1) return false;
528  if (non_null && !GenericVector<T*>::data_[i]->Serialize(fp)) return false;
529  }
530  return true;
531  }
532  // Reads a vector of (pointers to) classes to the given file. Assumes the
533  // existence of bool T::DeSerialize(bool, Tfile*) const that returns false in
534  // case of error. There is no Serialize for simple types, as you would have a
535  // normal GenericVector of those.
536  // If swap is true, assumes a big/little-endian swap is needed.
537  // Also needs T::T(), as new T is used in this function.
538  // Returns false in case of error.
539  bool DeSerialize(bool swap, FILE* fp) {
540  inT32 reserved;
541  if (fread(&reserved, sizeof(reserved), 1, fp) != 1) return false;
542  if (swap) Reverse32(&reserved);
543  GenericVector<T*>::reserve(reserved);
544  truncate(0);
545  for (int i = 0; i < reserved; ++i) {
546  inT8 non_null;
547  if (fread(&non_null, sizeof(non_null), 1, fp) != 1) return false;
548  T* item = NULL;
549  if (non_null) {
550  item = new T;
551  if (!item->DeSerialize(swap, fp)) {
552  delete item;
553  return false;
554  }
555  this->push_back(item);
556  } else {
557  // Null elements should keep their place in the vector.
558  this->push_back(NULL);
559  }
560  }
561  return true;
562  }
563  bool DeSerialize(bool swap, TFile* fp) {
564  inT32 reserved;
565  if (!DeSerializeSize(swap, fp, &reserved)) return false;
566  GenericVector<T*>::reserve(reserved);
567  truncate(0);
568  for (int i = 0; i < reserved; ++i) {
569  if (!DeSerializeElement(swap, fp)) return false;
570  }
571  return true;
572  }
573  // Enables deserialization of a selection of elements. Note that in order to
574  // retain the integrity of the stream, the caller must call some combination
575  // of DeSerializeElement and DeSerializeSkip of the exact number returned in
576  // *size, assuming a true return.
577  static bool DeSerializeSize(bool swap, TFile* fp, inT32* size) {
578  if (fp->FRead(size, sizeof(*size), 1) != 1) return false;
579  if (swap) Reverse32(size);
580  return true;
581  }
582  // Reads and appends to the vector the next element of the serialization.
583  bool DeSerializeElement(bool swap, TFile* fp) {
584  inT8 non_null;
585  if (fp->FRead(&non_null, sizeof(non_null), 1) != 1) return false;
586  T* item = NULL;
587  if (non_null) {
588  item = new T;
589  if (!item->DeSerialize(swap, fp)) {
590  delete item;
591  return false;
592  }
593  this->push_back(item);
594  } else {
595  // Null elements should keep their place in the vector.
596  this->push_back(NULL);
597  }
598  return true;
599  }
600  // Skips the next element of the serialization.
601  static bool DeSerializeSkip(bool swap, TFile* fp) {
602  inT8 non_null;
603  if (fp->FRead(&non_null, sizeof(non_null), 1) != 1) return false;
604  if (non_null) {
605  if (!T::SkipDeSerialize(swap, fp)) return false;
606  }
607  return true;
608  }
609 
610  // Sorts the items pointed to by the members of this vector using
611  // t::operator<().
612  void sort() { this->GenericVector<T*>::sort(&sort_ptr_cmp<T>); }
613 };
614 
615 } // namespace tesseract
616 
617 // A useful vector that uses operator== to do comparisons.
618 template <typename T>
619 class GenericVectorEqEq : public GenericVector<T> {
620  public:
623  NewPermanentTessCallback(tesseract::cmp_eq<T>));
624  }
627  NewPermanentTessCallback(tesseract::cmp_eq<T>));
628  }
629 };
630 
631 template <typename T>
632 void GenericVector<T>::init(int size) {
633  size_used_ = 0;
634  size_reserved_ = 0;
635  data_ = 0;
636  clear_cb_ = 0;
637  compare_cb_ = 0;
638  reserve(size);
639 }
640 
641 template <typename T>
643  clear();
644 }
645 
646 // Reserve some memory. If the internal array contains elements, they are
647 // copied.
648 template <typename T>
650  if (size_reserved_ >= size || size <= 0)
651  return;
652  if (size < kDefaultVectorSize) size = kDefaultVectorSize;
653  T* new_array = new T[size];
654  for (int i = 0; i < size_used_; ++i)
655  new_array[i] = data_[i];
656  delete[] data_;
657  data_ = new_array;
658  size_reserved_ = size;
659 }
660 
661 template <typename T>
663  if (size_reserved_ == 0) {
664  reserve(kDefaultVectorSize);
665  }
666  else {
667  reserve(2 * size_reserved_);
668  }
669 }
670 
671 // Resizes to size and sets all values to t.
672 template <typename T>
673 void GenericVector<T>::init_to_size(int size, T t) {
674  reserve(size);
675  size_used_ = size;
676  for (int i = 0; i < size; ++i)
677  data_[i] = t;
678 }
679 
680 
681 // Return the object from an index.
682 template <typename T>
683 T &GenericVector<T>::get(int index) const {
684  ASSERT_HOST(index >= 0 && index < size_used_);
685  return data_[index];
686 }
687 
688 template <typename T>
689 T &GenericVector<T>::operator[](int index) const {
690  assert(index >= 0 && index < size_used_);
691  return data_[index];
692 }
693 
694 template <typename T>
696  ASSERT_HOST(size_used_ > 0);
697  return data_[size_used_ - 1];
698 }
699 // Returns the last object and removes it.
700 template <typename T>
702  ASSERT_HOST(size_used_ > 0);
703  return data_[--size_used_];
704 }
705 
706 // Return the object from an index.
707 template <typename T>
708 void GenericVector<T>::set(T t, int index) {
709  ASSERT_HOST(index >= 0 && index < size_used_);
710  data_[index] = t;
711 }
712 
713 // Shifts the rest of the elements to the right to make
714 // space for the new elements and inserts the given element
715 // at the specified index.
716 template <typename T>
717 void GenericVector<T>::insert(T t, int index) {
718  ASSERT_HOST(index >= 0 && index <= size_used_);
719  if (size_reserved_ == size_used_)
720  double_the_size();
721  for (int i = size_used_; i > index; --i) {
722  data_[i] = data_[i-1];
723  }
724  data_[index] = t;
725  size_used_++;
726 }
727 
728 // Removes an element at the given index and
729 // shifts the remaining elements to the left.
730 template <typename T>
731 void GenericVector<T>::remove(int index) {
732  ASSERT_HOST(index >= 0 && index < size_used_);
733  for (int i = index; i < size_used_ - 1; ++i) {
734  data_[i] = data_[i+1];
735  }
736  size_used_--;
737 }
738 
739 // Return true if the index is valindex
740 template <typename T>
742  return index >= 0 && index < size_used_;
743 }
744 
745 // Return the index of the T object.
746 template <typename T>
747 int GenericVector<T>::get_index(T object) const {
748  for (int i = 0; i < size_used_; ++i) {
749  ASSERT_HOST(compare_cb_ != NULL);
750  if (compare_cb_->Run(object, data_[i]))
751  return i;
752  }
753  return -1;
754 }
755 
756 // Return true if T is in the array
757 template <typename T>
758 bool GenericVector<T>::contains(T object) const {
759  return get_index(object) != -1;
760 }
761 
762 // Add an element in the array
763 template <typename T>
765  int index = 0;
766  if (size_used_ == size_reserved_)
767  double_the_size();
768  index = size_used_++;
769  data_[index] = object;
770  return index;
771 }
772 
773 template <typename T>
775  int index = get_index(object);
776  if (index >= 0)
777  return index;
778  return push_back(object);
779 }
780 
781 // Add an element in the array (front)
782 template <typename T>
784  if (size_used_ == size_reserved_)
785  double_the_size();
786  for (int i = size_used_; i > 0; --i)
787  data_[i] = data_[i-1];
788  data_[0] = object;
789  ++size_used_;
790  return 0;
791 }
792 
793 template <typename T>
795  push_back(t);
796 }
797 
798 template <typename T>
800  this->reserve(size_used_ + other.size_used_);
801  for (int i = 0; i < other.size(); ++i) {
802  this->operator+=(other.data_[i]);
803  }
804  return *this;
805 }
806 
807 template <typename T>
809  if (&other != this) {
810  this->truncate(0);
811  this->operator+=(other);
812  }
813  return *this;
814 }
815 
816 // Add a callback to be called to delete the elements when the array took
817 // their ownership.
818 template <typename T>
820  clear_cb_ = cb;
821 }
822 
823 // Add a callback to be called to delete the elements when the array took
824 // their ownership.
825 template <typename T>
828  compare_cb_ = cb;
829 }
830 
831 // Clear the array, calling the callback function if any.
832 template <typename T>
834  if (size_reserved_ > 0) {
835  if (clear_cb_ != NULL)
836  for (int i = 0; i < size_used_; ++i)
837  clear_cb_->Run(data_[i]);
838  delete[] data_;
839  data_ = NULL;
840  size_used_ = 0;
841  size_reserved_ = 0;
842  }
843  if (clear_cb_ != NULL) {
844  delete clear_cb_;
845  clear_cb_ = NULL;
846  }
847  if (compare_cb_ != NULL) {
848  delete compare_cb_;
849  compare_cb_ = NULL;
850  }
851 }
852 
853 template <typename T>
855  for (int i = 0; i < size_used_; ++i)
856  if (data_[i]) {
857  delete data_[i];
858  }
859 }
860 
861 
862 template <typename T>
864  FILE* f, TessResultCallback2<bool, FILE*, T const &>* cb) const {
865  if (fwrite(&size_reserved_, sizeof(size_reserved_), 1, f) != 1) return false;
866  if (fwrite(&size_used_, sizeof(size_used_), 1, f) != 1) return false;
867  if (cb != NULL) {
868  for (int i = 0; i < size_used_; ++i) {
869  if (!cb->Run(f, data_[i])) {
870  delete cb;
871  return false;
872  }
873  }
874  delete cb;
875  } else {
876  if (fwrite(data_, sizeof(T), size_used_, f) != size_used_) return false;
877  }
878  return true;
879 }
880 
881 template <typename T>
884  bool swap) {
885  inT32 reserved;
886  if (fread(&reserved, sizeof(reserved), 1, f) != 1) return false;
887  if (swap) Reverse32(&reserved);
888  reserve(reserved);
889  if (fread(&size_used_, sizeof(size_used_), 1, f) != 1) return false;
890  if (swap) Reverse32(&size_used_);
891  if (cb != NULL) {
892  for (int i = 0; i < size_used_; ++i) {
893  if (!cb->Run(f, data_ + i, swap)) {
894  delete cb;
895  return false;
896  }
897  }
898  delete cb;
899  } else {
900  if (fread(data_, sizeof(T), size_used_, f) != size_used_) return false;
901  if (swap) {
902  for (int i = 0; i < size_used_; ++i)
903  ReverseN(&data_[i], sizeof(T));
904  }
905  }
906  return true;
907 }
908 
909 // Writes a vector of simple types to the given file. Assumes that bitwise
910 // read/write of T will work. Returns false in case of error.
911 template <typename T>
912 bool GenericVector<T>::Serialize(FILE* fp) const {
913  if (fwrite(&size_used_, sizeof(size_used_), 1, fp) != 1) return false;
914  if (fwrite(data_, sizeof(*data_), size_used_, fp) != size_used_) return false;
915  return true;
916 }
917 template <typename T>
919  if (fp->FWrite(&size_used_, sizeof(size_used_), 1) != 1) return false;
920  if (fp->FWrite(data_, sizeof(*data_), size_used_) != size_used_) return false;
921  return true;
922 }
923 
924 // Reads a vector of simple types from the given file. Assumes that bitwise
925 // read/write will work with ReverseN according to sizeof(T).
926 // Returns false in case of error.
927 // If swap is true, assumes a big/little-endian swap is needed.
928 template <typename T>
929 bool GenericVector<T>::DeSerialize(bool swap, FILE* fp) {
930  inT32 reserved;
931  if (fread(&reserved, sizeof(reserved), 1, fp) != 1) return false;
932  if (swap) Reverse32(&reserved);
933  reserve(reserved);
934  size_used_ = reserved;
935  if (fread(data_, sizeof(T), size_used_, fp) != size_used_) return false;
936  if (swap) {
937  for (int i = 0; i < size_used_; ++i)
938  ReverseN(&data_[i], sizeof(data_[i]));
939  }
940  return true;
941 }
942 template <typename T>
944  inT32 reserved;
945  if (fp->FRead(&reserved, sizeof(reserved), 1) != 1) return false;
946  if (swap) Reverse32(&reserved);
947  reserve(reserved);
948  size_used_ = reserved;
949  if (fp->FRead(data_, sizeof(T), size_used_) != size_used_) return false;
950  if (swap) {
951  for (int i = 0; i < size_used_; ++i)
952  ReverseN(&data_[i], sizeof(data_[i]));
953  }
954  return true;
955 }
956 template <typename T>
958  inT32 reserved;
959  if (fp->FRead(&reserved, sizeof(reserved), 1) != 1) return false;
960  if (swap) Reverse32(&reserved);
961  return fp->FRead(NULL, sizeof(T), reserved) == reserved;
962 }
963 
964 // Writes a vector of classes to the given file. Assumes the existence of
965 // bool T::Serialize(FILE* fp) const that returns false in case of error.
966 // Returns false in case of error.
967 template <typename T>
969  if (fwrite(&size_used_, sizeof(size_used_), 1, fp) != 1) return false;
970  for (int i = 0; i < size_used_; ++i) {
971  if (!data_[i].Serialize(fp)) return false;
972  }
973  return true;
974 }
975 template <typename T>
977  if (fp->FWrite(&size_used_, sizeof(size_used_), 1) != 1) return false;
978  for (int i = 0; i < size_used_; ++i) {
979  if (!data_[i].Serialize(fp)) return false;
980  }
981  return true;
982 }
983 
984 // Reads a vector of classes from the given file. Assumes the existence of
985 // bool T::Deserialize(bool swap, FILE* fp) that returns false in case of
986 // error. Also needs T::T() and T::T(constT&), as init_to_size is used in
987 // this function. Returns false in case of error.
988 // If swap is true, assumes a big/little-endian swap is needed.
989 template <typename T>
990 bool GenericVector<T>::DeSerializeClasses(bool swap, FILE* fp) {
991  uinT32 reserved;
992  if (fread(&reserved, sizeof(reserved), 1, fp) != 1) return false;
993  if (swap) Reverse32(&reserved);
994  T empty;
995  init_to_size(reserved, empty);
996  for (int i = 0; i < reserved; ++i) {
997  if (!data_[i].DeSerialize(swap, fp)) return false;
998  }
999  return true;
1000 }
1001 template <typename T>
1003  uinT32 reserved;
1004  if (fp->FRead(&reserved, sizeof(reserved), 1) != 1) return false;
1005  if (swap) Reverse32(&reserved);
1006  T empty;
1007  init_to_size(reserved, empty);
1008  for (int i = 0; i < reserved; ++i) {
1009  if (!data_[i].DeSerialize(swap, fp)) return false;
1010  }
1011  return true;
1012 }
1013 template <typename T>
1015  uinT32 reserved;
1016  if (fp->FRead(&reserved, sizeof(reserved), 1) != 1) return false;
1017  if (swap) Reverse32(&reserved);
1018  for (int i = 0; i < reserved; ++i) {
1019  if (!T::SkipDeSerialize(swap, fp)) return false;
1020  }
1021  return true;
1022 }
1023 
1024 // This method clear the current object, then, does a shallow copy of
1025 // its argument, and finally invalidates its argument.
1026 template <typename T>
1028  this->clear();
1029  this->data_ = from->data_;
1030  this->size_reserved_ = from->size_reserved_;
1031  this->size_used_ = from->size_used_;
1032  this->compare_cb_ = from->compare_cb_;
1033  this->clear_cb_ = from->clear_cb_;
1034  from->data_ = NULL;
1035  from->clear_cb_ = NULL;
1036  from->compare_cb_ = NULL;
1037  from->size_used_ = 0;
1038  from->size_reserved_ = 0;
1039 }
1040 
1041 template <typename T>
1043  sort(&tesseract::sort_cmp<T>);
1044 }
1045 
1046 // Internal recursive version of choose_nth_item.
1047 // The algorithm used comes from "Algorithms" by Sedgewick:
1048 // http://books.google.com/books/about/Algorithms.html?id=idUdqdDXqnAC
1049 // The principle is to choose a random pivot, and move everything less than
1050 // the pivot to its left, and everything greater than the pivot to the end
1051 // of the array, then recurse on the part that contains the desired index, or
1052 // just return the answer if it is in the equal section in the middle.
1053 // The random pivot guarantees average linear time for the same reason that
1054 // n times vector::push_back takes linear time on average.
1055 // target_index, start and and end are all indices into the full array.
1056 // Seed is a seed for rand_r for thread safety purposes. Its value is
1057 // unimportant as the random numbers do not affect the result except
1058 // between equal answers.
1059 template <typename T>
1060 int GenericVector<T>::choose_nth_item(int target_index, int start, int end,
1061  unsigned int* seed) {
1062  // Number of elements to process.
1063  int num_elements = end - start;
1064  // Trivial cases.
1065  if (num_elements <= 1)
1066  return start;
1067  if (num_elements == 2) {
1068  if (data_[start] < data_[start + 1]) {
1069  return target_index > start ? start + 1 : start;
1070  } else {
1071  return target_index > start ? start : start + 1;
1072  }
1073  }
1074  // Place the pivot at start.
1075  #ifndef rand_r // _MSC_VER, ANDROID
1076  srand(*seed);
1077  #define rand_r(seed) rand()
1078  #endif // _MSC_VER
1079  int pivot = rand_r(seed) % num_elements + start;
1080  swap(pivot, start);
1081  // The invariant condition here is that items [start, next_lesser) are less
1082  // than the pivot (which is at index next_lesser) and items
1083  // [prev_greater, end) are greater than the pivot, with items
1084  // [next_lesser, prev_greater) being equal to the pivot.
1085  int next_lesser = start;
1086  int prev_greater = end;
1087  for (int next_sample = start + 1; next_sample < prev_greater;) {
1088  if (data_[next_sample] < data_[next_lesser]) {
1089  swap(next_lesser++, next_sample++);
1090  } else if (data_[next_sample] == data_[next_lesser]) {
1091  ++next_sample;
1092  } else {
1093  swap(--prev_greater, next_sample);
1094  }
1095  }
1096  // Now the invariant is set up, we recurse on just the section that contains
1097  // the desired index.
1098  if (target_index < next_lesser)
1099  return choose_nth_item(target_index, start, next_lesser, seed);
1100  else if (target_index < prev_greater)
1101  return next_lesser; // In equal bracket.
1102  else
1103  return choose_nth_item(target_index, prev_greater, end, seed);
1104 }
1105 
1106 
1107 #endif // TESSERACT_CCUTIL_GENERICVECTOR_H_
int sort_ptr_cmp(const void *t1, const void *t2)
TessResultCallback2< bool, T const &, T const & > * compare_cb_
bool DeSerializeElement(bool swap, TFile *fp)
PointerVector< T > & operator+=(const PointerVector &other)
void init(int size)
int size_reserved() const
Definition: genericvector.h:75
bool DeSerialize(bool swap, TFile *fp)
void compact(TessResultCallback1< bool, const T *> *delete_cb)
GenericVectorEqEq(int size)
void compact_sorted()
void resize_no_init(int size)
Definition: genericvector.h:66
T & get(int index) const
static const int kDefaultVectorSize
static bool DeSerializeSkip(bool swap, TFile *fp)
virtual R Run(A1)=0
_ConstTessMemberResultCallback_0_0< false, R, T1 >::base * NewPermanentTessCallback(const T1 *obj, R(T2::*member)() const)
Definition: tesscallback.h:116
int FWrite(const void *buffer, int size, int count)
Definition: serialis.cpp:131
void Reverse32(void *ptr)
Definition: helpers.h:193
void insert(T t, int index)
GenericVector< T > & operator+=(const GenericVector &other)
static T * double_the_size_memcpy(int current_size, T *data)
void swap(int index1, int index2)
ICOORD & operator+=(ICOORD &op1, const ICOORD &op2)
Definition: ipoints.h:86
#define MIN(x, y)
Definition: ndminx.h:28
PointerVector< T > & operator=(const PointerVector &other)
bool contains(T object) const
void remove(int index)
bool Serialize(TFile *fp) const
GenericVector(int size, T init_val)
Definition: genericvector.h:43
void move(GenericVector< T > *from)
GenericVector(const GenericVector &other)
Definition: genericvector.h:49
int get_index(T object) const
int push_back_new(T object)
T & back() const
bool DeSerializeClasses(bool swap, FILE *fp)
static bool SkipDeSerialize(bool swap, tesseract::TFile *fp)
bool Serialize(FILE *fp) const
void set_compare_callback(TessResultCallback2< bool, T const &, T const &> *cb)
T dot_product(const GenericVector< T > &other) const
void double_the_size()
int push_back(T object)
inT32 choose_nth_item(inT32 index, float *array, inT32 count)
Definition: statistc.cpp:638
#define rand_r(seed)
virtual R Run(A1, A2, A3)=0
bool LoadDataFromFile(const STRING &filename, GenericVector< char > *data)
T & operator[](int index) const
void set_clear_callback(TessCallback1< T > *cb)
PointerVector(const PointerVector &other)
int FRead(void *buffer, int size, int count)
Definition: serialis.cpp:91
virtual R Run(A1, A2)=0
SIGNED char inT8
Definition: host.h:98
int push_front(T object)
TessCallback1< T > * clear_cb_
bool read(FILE *f, TessResultCallback3< bool, FILE *, T *, bool > *cb, bool swap)
void truncate(int size)
void delete_data_pointers()
bool write(FILE *f, TessResultCallback2< bool, FILE *, T const &> *cb) const
static bool SkipDeSerializeClasses(bool swap, tesseract::TFile *fp)
int inT32
Definition: host.h:102
bool SaveDataToFile(const GenericVector< char > &data, const STRING &filename)
Definition: strngs.h:44
int size() const
Definition: genericvector.h:72
bool WithinBounds(const T &rangemin, const T &rangemax) const
int length() const
Definition: genericvector.h:79
void set(T t, int index)
unsigned int uinT32
Definition: host.h:103
int binary_search(const T &target) const
static bool DeSerializeSize(bool swap, TFile *fp, inT32 *size)
bool SerializeClasses(FILE *fp) const
int choose_nth_item(int target_index)
T contains_index(int index) const
GenericVector< T > & operator=(const GenericVector &other)
void reserve(int size)
bool(* FileReader)(const STRING &filename, GenericVector< char > *data)
bool cmp_eq(T const &t1, T const &t2)
void sort(int(*comparator)(const void *, const void *))
int sort_cmp(const void *t1, const void *t2)
bool DeSerialize(bool swap, FILE *fp)
bool empty() const
Definition: genericvector.h:84
void ReverseN(void *ptr, int num_bytes)
Definition: helpers.h:177
void init_to_size(int size, T t)
#define ASSERT_HOST(x)
Definition: errcode.h:84
inT32 size_reserved_
bool(* FileWriter)(const GenericVector< char > &data, const STRING &filename)
void compact(TessResultCallback1< bool, int > *delete_cb)
bool bool_binary_search(const T &target) const
bool Serialize(FILE *fp) const
bool DeSerialize(bool swap, FILE *fp)
void Swap(T *p1, T *p2)
Definition: helpers.h:90