source: trunk/yat/utility/SegmentSet.h @ 3345

#ifndef theplu_yat_utility_segment_set
#define theplu_yat_utility_segment_set

// $Id: SegmentSet.h 3345 2014-11-06 12:30:45Z peter $

/*
  Copyright (C) 2010 Peter Johansson
  Copyright (C) 2012 Jari Häkkinen

  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 {

  /**
     \brief a set of Segments

     A container that holds a set of Segment. The Segments cannot overlap.

     \since new in yat 0.7
   */
  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:
    /**
       \brief creates a set with no segments
     */
    SegmentSet(void) {}

    /**
       insert \a segment into set. If there is no gap between \a
       segment and neighboring segments the segments are merged.
     */
    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);
    }

    /**
       \brief insert with a hint

       Similar to insert_merge(1) but \a hint help to find where to
       insert \a segment. For the \a hint to be useful, \a segment
       should not be greater than element hint points to and not
       smaller than element --hint points to.

       \since New in yat 0.13
     */
    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);
    }

    /**
       Insert range [first, last). Same result as inserting them
       individually, but inserting a range is potentially faster,
       especially if range is sorted and set is sparse compared to
       range.

      \since new in yat 0.13
     */
    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