source: trunk/yat/SegmentSet.h @ 1505

Last change on this file since 1505 was 1505, checked in by Peter Johansson, 7 years ago

update to latest yat source (including Id strings)

  • Property svn:eol-style set to native
File size: 2.8 KB
Line 
1#ifndef theplu_yat_utility_segment_set
2#define theplu_yat_utility_segment_set
3
4// $Id: SegmentSet.h 2819 2012-08-29 20:56:39Z jari $
5
6/*
7  Copyright (C) 2010 Peter Johansson
8
9  This file is part of the yat library, http://dev.thep.lu.se/yat
10
11  The yat library is free software; you can redistribute it and/or
12  modify it under the terms of the GNU General Public License as
13  published by the Free Software Foundation; either version 3 of the
14  License, or (at your option) any later version.
15
16  The yat library is distributed in the hope that it will be useful,
17  but WITHOUT ANY WARRANTY; without even the implied warranty of
18  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
19  General Public License for more details.
20
21  You should have received a copy of the GNU General Public License
22  along with yat. If not, see <http://www.gnu.org/licenses/>.
23*/
24
25#include "Segment.h"
26#include "SegmentTree.h"
27#include "stl_utility.h"
28#include "yat_assert.h"
29
30#include <set>
31#include <utility>
32
33namespace theplu {
34namespace yat {
35namespace utility {
36
37  /**
38     \brief a set of Segments
39
40     A container that holds a set of Segment. The Segments cannot overlap.
41
42     \since new in yat 0.7
43   */
44  template<typename T, class Compare = std::less<T> >
45  class SegmentSet 
46    : public SegmentTree<std::set<Segment<T, Compare>, 
47                                  SegmentCompare<T, Compare> >,
48                         Compare,
49                         Identity<const Segment<T, Compare>&> >
50  {
51    typedef SegmentSet<T, Compare> me;
52  public:
53    /**
54       \brief creates a set with no segments
55     */
56    SegmentSet(void) {}
57
58    /**
59       insert \a segment into set. If there is no gap between \a
60       segment and neighboring segments the segments are merged.
61     */
62    typename me::const_iterator
63    insert_merge(const typename me::value_type& segment)
64    {
65      std::pair<typename me::iterator, typename me::iterator> p = 
66        this->overlap_range(segment);
67      if (p.first==p.second) { // no overlap between set and segment
68        return this->container_.insert(p.first, segment);
69      }
70      /*
71        p.first           last         p.second
72        --->    --->      --->         --->
73       
74        ----------------------->
75        segment
76      */
77      Compare comp;
78      typename me::iterator last=p.second;
79      YAT_ASSERT(last==this->end() || compare(segment, *last));
80      YAT_ASSERT(last!=this->begin()); // last!=p.first
81      --last;
82      YAT_ASSERT(compare_3way(segment, *last)==0);
83     
84      Segment<T, Compare> segment2(std::min(p.first->begin(),
85                                            segment.begin(), comp),
86                                   std::max(last->end(), segment.end(), comp));
87      this->container_.erase(p.first, p.second); 
88      // FIXME: use a better hint than end()
89      return this->container_.insert(this->end(), segment2);
90    }
91
92  private:
93    // using compiler generated copying
94    //SegmentSet(const SegmentSet&);
95    //SegmentSet& operator=(const SegmentSet&);
96  };
97
98}}}
99#endif
Note: See TracBrowser for help on using the repository browser.