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

Last change on this file since 3345 was 3345, checked in by Peter, 8 years ago

new function SegmentSet::insert_merge(first, last). closes #818

  • Property svn:eol-style set to native
  • Property svn:keywords set to Id
File size: 5.1 KB
Line 
1#ifndef theplu_yat_utility_segment_set
2#define theplu_yat_utility_segment_set
3
4// $Id: SegmentSet.h 3345 2014-11-06 12:30:45Z 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      return insert_merge(p, segment);
69    }
70
71    /**
72       \brief insert with a hint
73
74       Similar to insert_merge(1) but \a hint help to find where to
75       insert \a segment. For the \a hint to be useful, \a segment
76       should not be greater than element hint points to and not
77       smaller than element --hint points to.
78
79       \since New in yat 0.13
80     */
81    typename me::iterator insert_merge(typename me::iterator hint,
82                                       const typename me::value_type& segment)
83    {
84      std::pair<typename me::iterator, typename me::iterator> p(hint, hint);
85      if (this->container_.empty())
86        return insert_merge(p, segment);
87
88      //.If hint points to an element that is less than segment, hint
89      //is no good and we ignore the hint.
90      if (hint!=this->end() && compare(*hint, segment))
91        return insert_merge(segment);
92
93      if (p.first!=this->begin()) {
94        --p.first;
95        // If --hint point to an element greater than segment, hint is
96        // no good.
97        if (compare(segment, *p.first))
98          return insert_merge(segment);
99        // find first element that is smaller than segment
100        while (p.first!=this->begin() && !compare(*p.first, segment))
101          --p.first;
102        YAT_ASSERT(p.first==this->begin() || compare(*p.first, segment));
103        YAT_ASSERT(p.first!=this->end());
104        if (compare(*p.first, segment))
105          ++p.first;
106      }
107
108      // find first element greater than segment
109      while (p.second!=this->end() && !compare(segment, *p.second))
110        ++p.second;
111
112      return insert_merge(p, segment);
113    }
114
115    /**
116       Insert range [first, last). Same result as inserting them
117       individually, but inserting a range is potentially faster,
118       especially if range is sorted and set is sparse compared to
119       range.
120
121      \since new in yat 0.13
122     */
123    template<typename Iterator>
124    void insert_merge(Iterator first, Iterator last)
125    {
126      typename me::iterator it = this->end();
127      for ( ; first!=last; ++first) {
128        it = insert_merge(it, *first);
129        ++it;
130      }
131    }
132  private:
133    // used by public functions insert_merge.
134    //
135    // p.first points to the first segment that overlaps with \a segment or
136    // is greater than segment.
137    // p.second points to the first segment that is greater than \a segment
138    typename me::const_iterator
139    insert_merge(const std::pair<typename me::iterator,
140                                 typename me::iterator>& p,
141                 const typename me::value_type& segment)
142    {
143      YAT_ASSERT(p.first==this->end() || !compare(*p.first, segment));
144      YAT_ASSERT(p.second==this->end() || compare(segment, *p.second));
145      if (p.first==p.second) { // no overlap between set and segment
146        return this->container_.insert(p.first, segment);
147      }
148      /*
149        p.first           last         p.second
150        --->    --->      --->         --->
151
152        ----------------------->
153        segment
154      */
155      Compare comp;
156      typename me::iterator last=p.second;
157      YAT_ASSERT(last==this->end() || compare(segment, *last));
158      YAT_ASSERT(last!=this->begin()); // last!=p.first
159      --last;
160      YAT_ASSERT(compare_3way(segment, *last)==0);
161
162      Segment<T, Compare>
163        segment2(std::min(p.first->begin(), segment.begin(), comp),
164                 std::max(last->end(), segment.end(), comp));
165
166      this->container_.erase(p.first, p.second);
167      return this->container_.insert(p.second, segment2);
168    }
169
170    // using compiler generated copying
171    //SegmentSet(const SegmentSet&);
172    //SegmentSet& operator=(const SegmentSet&);
173  };
174
175}}}
176#endif
Note: See TracBrowser for help on using the repository browser.