merge.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_SORT_MERGE_HXX
#define MODULE_SORT_MERGE_HXX

// STD includes
#include <iterator>

namespace SHA_Sort
{
  template <typename IT>
  class MergeInPlace
  {
  public:
    void operator()(IT begin, IT middle, IT end)
    {
      if (std::distance(begin, middle) < 1 || std::distance(middle, end) < 1)
        return;

      // Use first half as receiver
      for(; begin < middle; ++begin)
      {
        if (*middle >= *begin)
          continue;

        typename std::iterator_traits<IT>::value_type value;
        std::swap(value, *begin);    // keep the higher value
        std::swap(*begin, *middle);  // Place it at the beginning of the second list

        // Displace the higher value in the right place of the second list by swapping
        auto it = middle;
        for (; it != end - 1; ++it)
        {
          if (*(it + 1) >= value)
            break;

          std::swap(*it, *(it + 1));
        }

        // Restore the value at his right place
        std::swap(*it, value);
      }
    }
  };


  template <typename Container, typename IT>
  class MergeWithBuffer
  {
  public:
    void operator()(IT begin, IT middle, IT end)
    {
      if (std::distance(begin, middle) < 1 || std::distance(middle, end) < 1)
        return;

      Container buffer;
      buffer.resize(std::distance(begin, end)); // Reserve right space (e.g. string container)
      auto buffIt = buffer.begin();
      auto tmpBegin = begin;

      // Merge into the buffer array taking one by one the lowest sequence element
      const auto curMiddle(middle);
      while (begin != curMiddle && middle != end)
      {
        if (*begin <= *middle)
          *buffIt++ = *begin++;
        else
          *buffIt++ = *middle++;
      }

      // Finish remaining list into the buffer
      for (; begin != curMiddle; ++buffIt, ++begin)
        *buffIt = *begin;
      for (; middle != end; ++buffIt, ++middle)
        *buffIt = *middle;

      // Refill array given the right position
      for (buffIt = buffer.begin(); buffIt != buffer.end(); ++buffIt, ++tmpBegin)
        *tmpBegin = *buffIt;
    }
  };

  template <typename Container, typename IT, typename Aggregator = MergeWithBuffer<Container, IT>>
  void MergeSort(const IT& begin, const IT& end)
  {
    const auto ksize = static_cast<const int>(std::distance(begin, end));
    if (ksize < 2)
      return;

    auto middle = begin + ksize / 2;

    // Recursively break the vector into two pieces
    MergeSort<Container, IT, Aggregator>(begin, middle);
    MergeSort<Container, IT, Aggregator>(middle, end);

    // Merge the two pieces
    Aggregator()(begin, middle, end);
  }
}

#endif // MODULE_SORT_MERGE_HXX