max_m_elements.hxx

Go to the documentation of this file.

/*===========================================================================================================
 *
 * SHA - Simple Hybesis Algorithms
 *
 * Copyright (c) Michael Jeulin-Lagarrigue
 *
 *  Licensed under the MIT License, you may not use this file except in compliance with the License.
 *  You may obtain a copy of the License at
 *
 *         https://github.com/michael-jeulinl/Simple-Hybesis-Algorithms/blob/master/LICENSE
 *
 * 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.
 *
 * The above copyright notice and this permission notice shall be included in all copies or
 * substantial portions of the Software.
 *
 *=========================================================================================================*/
#ifndef MODULE_SEARCH_MAX_M_ELEMENTS_HXX
#define MODULE_SEARCH_MAX_M_ELEMENTS_HXX

// STD includes
#include <functional>
#include <limits>

namespace SHA_Search
{
  template <typename Container,
            typename IT,
            typename Compare = std::greater_equal<typename std::iterator_traits<IT>::value_type>>
  Container MaxMElements(const IT& begin, const IT& end, const int m)
  {
    if (m < 1 || m > std::distance(begin, end))
      return Container();

    // Initiale values depends on the comparator functor
    const auto limitValue = Compare()(0, std::numeric_limits<typename std::iterator_traits<IT>::value_type>::
                                      lowest()) ?
                                         std::numeric_limits<typename std::iterator_traits<IT>::value_type>::
                                      lowest() :
                                         std::numeric_limits<typename std::iterator_traits<IT>::value_type>::
                                      max();

    // Allocate the container final size
    Container maxMElements;
    maxMElements.resize(m, limitValue);
    for (auto it = begin; it != end; ++it)
    {
      // Insert the value at the right place and bubble down replacement value
      int index = 0;
      auto tmpVal = *it;
      for (auto subIt = maxMElements.begin(); index < m; ++subIt, ++index)
        if (Compare()(tmpVal, *subIt))
          std::swap(*subIt, tmpVal);
    }

    return maxMElements;
  }
}

#endif // MODULE_COLLECTIONS_SEARCH_HXX