SegmentSet.h

#ifndef theplu_yat_utility_segment_set
#define theplu_yat_utility_segment_set

// $Id: SegmentSet.h 4039 2021-02-11 07:30:04Z peter $

/*
  Copyright (C) 2010 Peter Johansson
  Copyright (C) 2012 Jari Häkkinen
  Copyright (C) 2014, 2016, 2021 Peter Johansson

  This file is part of the yat library, http://dev.thep.lu.se/yat

  The yat library is free software; you can redistribute it and/or
  modify it under the terms of the GNU General Public License as
  published by the Free Software Foundation; either version 3 of the
  License, or (at your option) any later version.

  The yat library is distributed in the hope that it will be useful,
  but WITHOUT ANY WARRANTY; without even the implied warranty of
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  General Public License for more details.

  You should have received a copy of the GNU General Public License
  along with yat. If not, see <http://www.gnu.org/licenses/>.
*/

#include "Segment.h"
#include "SegmentTree.h"
#include "stl_utility.h"
#include "yat_assert.h"

#include <set>
#include <utility>

namespace theplu {
namespace yat {
namespace utility {

  template<typename T, class Compare = std::less<T> >
  class SegmentSet
    : public SegmentTree<std::set<Segment<T, Compare>,
                                  SegmentCompare<T, Compare> >,
                         Compare,
                         Identity<const Segment<T, Compare>&> >
  {
    typedef SegmentSet<T, Compare> me;
  public:
    SegmentSet(void) {}

    typename me::const_iterator
    insert_merge(const Segment<T, Compare>& segment)
    {
      std::pair<typename me::iterator, typename me::iterator> p =
        this->overlap_range(segment);
      Segment<T> tmp(segment);
      return move_insert_merge(p, std::move(tmp));
    }

    typename me::const_iterator
    insert_merge(Segment<T, Compare>&& segment)
    {
      std::pair<typename me::iterator, typename me::iterator> p =
        this->overlap_range(segment);
      return move_insert_merge(p, std::move(segment));
    }

    typename me::iterator insert_merge(typename me::iterator hint,
                                       const Segment<T, Compare>& segment)
    {
      Segment<T, Compare> tmp(segment);
      return insert_merge(hint, std::move(tmp));
    }


    typename me::iterator
    insert_merge(typename me::iterator hint,
                 Segment<T, Compare>&& segment)
    {
      std::pair<typename me::iterator, typename me::iterator> p(hint, hint);
      if (this->container_.empty())
        return move_insert_merge(p, std::move(segment));

      // If hint points to an element that is less than segment, hint
      // is no good and we ignore the hint.
      if (hint!=this->end() && compare(*hint, segment))
        return insert_merge(std::move(segment));

      if (p.first!=this->begin()) {
        --p.first;
        // If --hint point to an element greater than segment, hint is
        // no good.
        if (compare(segment, *p.first))
          return insert_merge(std::move(segment));
        // find first element that is smaller than segment
        while (p.first!=this->begin() && !compare(*p.first, segment))
          --p.first;
        YAT_ASSERT(p.first==this->begin() || compare(*p.first, segment));
        YAT_ASSERT(p.first!=this->end());
        if (compare(*p.first, segment))
          ++p.first;
      }

      // find first element greater than segment
      while (p.second!=this->end() && !compare(segment, *p.second))
        ++p.second;

      return move_insert_merge(p, std::move(segment));
    }


    template<typename Iterator>
    void insert_merge(Iterator first, Iterator last)
    {
      typename me::iterator it = this->end();
      for ( ; first!=last; ++first) {
        it = insert_merge(it, *first);
        ++it;
      }
    }
  private:
    // used by functions merge_basic. This function does the actual
    // work. Note that it takes an rvalue; functions that only have
    // access to an lvalue const& need to create a (temporary) copy
    // that can be moved in.
    //
    // p.first points to the first segment that overlaps with \a segment or
    // is greater than segment.
    // p.second points to the first segment that is greater than \a segment
    typename me::const_iterator
    move_insert_merge(const std::pair<typename me::iterator,
                                      typename me::iterator>& p,
                      Segment<T, Compare>&& segment)
    {
      YAT_ASSERT(p.first==this->end() || !compare(*p.first, segment));
      YAT_ASSERT(p.second==this->end() || compare(segment, *p.second));
      if (p.first==p.second) { // no overlap between set and segment
        return this->container_.insert(p.first, std::move(segment));
      }
      /*
        p.first           last         p.second
        --->    --->      --->         --->

        ----------------------->
        segment
      */
      Compare comp;
      typename me::iterator last=p.second;
      YAT_ASSERT(last==this->end() || compare(segment, *last));
      YAT_ASSERT(last!=this->begin()); // last!=p.first
      --last;
      YAT_ASSERT(compare_3way(segment, *last)==0);

      Segment<T, Compare>
        segment2(std::min(p.first->begin(), segment.begin(), comp),
                 std::max(last->end(), segment.end(), comp));

      this->container_.erase(p.first, p.second);
      return this->container_.insert(p.second, std::move(segment2));
    }

    // using compiler generated copying
    //SegmentSet(const SegmentSet&);
    //SegmentSet& operator=(const SegmentSet&);
  };

}}}
#endif