///////////////////////////////////////////////////////////////////////

// File:        sorthelper.h

// Description: Generic sort and maxfinding class.

// Author:      Ray Smith

//

// (C) Copyright 2010, Google Inc.

// Licensed under the Apache License, Version 2.0 (the "License");

// you may not use this file except in compliance with the License.

// You may obtain a copy of the License at

// http://www.apache.org/licenses/LICENSE-2.0

// Unless required by applicable law or agreed to in writing, software

// distributed under the License is distributed on an "AS IS" BASIS,

// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.

// See the License for the specific language governing permissions and

// limitations under the License.

//

///////////////////////////////////////////////////////////////////////

#ifndef TESSERACT_CCUTIL_SORTHELPER_H_

#define TESSERACT_CCUTIL_SORTHELPER_H_

#include <cstdlib>

#include <vector>

namespace tesseract {

// Generic class to provide functions based on a <value,count> pair.

// T is the value type.

// The class keeps a count of each value and can return the most frequent

// value or a sorted array of the values with counts.

// Note that this class uses linear search for adding. It is better

// to use the STATS class to get the mode of a large number of values

// in a small space. SortHelper is better to get the mode of a small number

// of values from a large space.

// T must have a copy constructor.

template <typename T>

class SortHelper {

public:

  // Simple pair class to hold the values and counts.

  template <typename PairT>

  struct SortPair {

    PairT value;

    int count;

  };

  // qsort function to sort by decreasing count.

  static int SortPairsByCount(const void *v1, const void *v2) {

    const auto *p1 = static_cast<const SortPair<T> *>(v1);

    const auto *p2 = static_cast<const SortPair<T> *>(v2);

    return p2->count - p1->count;

  }

  // qsort function to sort by decreasing value.

  static int SortPairsByValue(const void *v1, const void *v2) {

    const auto *p1 = static_cast<const SortPair<T> *>(v1);

    const auto *p2 = static_cast<const SortPair<T> *>(v2);

    if (p2->value - p1->value < 0) {

      return -1;

    }

    if (p2->value - p1->value > 0) {

      return 1;

    }

    return 0;

  }

  // Constructor takes a hint of the array size, but it need not be accurate.

  explicit SortHelper(int sizehint) {

    counts_.reserve(sizehint);

  }

  // Add a value that may be a duplicate of an existing value.

  // Uses a linear search.

  void Add(T value, int count) {

    // Linear search for value.

    for (auto &it : counts_) {

      if (it.value == value) {

        it.count += count;

        return;

      }

    }

    SortPair<T> new_pair = {value, count};

    counts_.push_back(SortPair<T>(new_pair));

  }

  // Returns the frequency of the most frequent value.

  // If max_value is not nullptr, returns the most frequent value.

  // If the array is empty, returns -INT32_MAX and max_value is unchanged.

  int MaxCount(T *max_value) const {

    int best_count = -INT32_MAX;

    for (auto &it : counts_) {

      if (it.count > best_count) {

        best_count = it.count;

        if (max_value != nullptr) {

          *max_value = it.value;

        }

      }

    }

    return best_count;

  }

  // Returns the data array sorted by decreasing frequency.

  const std::vector<SortPair<T>> &SortByCount() {

    counts_.sort(&SortPairsByCount);

    return counts_;

  }

  // Returns the data array sorted by decreasing value.

  const std::vector<SortPair<T>> &SortByValue() {

    counts_.sort(&SortPairsByValue);

    return counts_;

  }

private:

  std::vector<SortPair<T>> counts_;

};

} // namespace tesseract

#endif // TESSERACT_CCUTIL_SORTHELPER_H_.