source: trunk/yat/SegmentSet.h @ 1512

#ifndef theplu_yat_utility_segment_set
#define theplu_yat_utility_segment_set

// $Id: SegmentSet.h 2820 2012-08-30 00:47:58Z 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);
      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); 
      // FIXME: use a better hint than end()
      return this->container_.insert(this->end(), segment2);
    }

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

}}}
#endif