source: trunk/yat/SegmentSet.h @ 1512

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

fetch latest yat sources

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