max_m_elements.hxx

Go to the documentation of this file.

/*===========================================================================================================
 *
 * HUC - Hurna Core
 *
 * 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/Hurna/Hurna-Core/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 huc
{
  namespace 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