SegmentSet.h

#ifndef theplu_yat_utility_segment_set
#define theplu_yat_utility_segment_set

// $Id: SegmentSet.h 3550 2017-01-03 05:41:02Z peter $

/*
  Copyright (C) 2010 Peter Johansson
  Copyright (C) 2012 Jari Häkkinen
  Copyright (C) 2014, 2016 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 typename me::value_type& segment)
    {
      std::pair<typename me::iterator, typename me::iterator> p =
        this->overlap_range(segment);
      return insert_merge(p, segment);
    }

    typename me::iterator insert_merge(typename me::iterator hint,
                                       const typename me::value_type& segment)
    {
      std::pair<typename me::iterator, typename me::iterator> p(hint, hint);
      if (this->container_.empty())
        return insert_merge(p, 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(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(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 insert_merge(p, 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 public functions insert_merge.
    //
    // 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
    insert_merge(const std::pair<typename me::iterator,
                                 typename me::iterator>& p,
                 const typename me::value_type& 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, 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, segment2);
    }

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

}}}
#endif