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

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

new function SegmentSet::insert_merge with hint. refs #818

  • Property svn:eol-style set to native
  • Property svn:keywords set to Id
File size: 4.7 KB
Line 
1#ifndef theplu_yat_utility_segment_set
2#define theplu_yat_utility_segment_set
3
4// $Id: SegmentSet.h 3344 2014-11-06 12:09:32Z 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  private:
116    // used by public functions insert_merge.
117    //
118    // p.first points to the first segment that overlaps with \a segment or
119    // is greater than segment.
120    // p.second points to the first segment that is greater than \a segment
121    typename me::const_iterator
122    insert_merge(const std::pair<typename me::iterator,
123                                 typename me::iterator>& p,
124                 const typename me::value_type& segment)
125    {
126      YAT_ASSERT(p.first==this->end() || !compare(*p.first, segment));
127      YAT_ASSERT(p.second==this->end() || compare(segment, *p.second));
128      if (p.first==p.second) { // no overlap between set and segment
129        return this->container_.insert(p.first, segment);
130      }
131      /*
132        p.first           last         p.second
133        --->    --->      --->         --->
134
135        ----------------------->
136        segment
137      */
138      Compare comp;
139      typename me::iterator last=p.second;
140      YAT_ASSERT(last==this->end() || compare(segment, *last));
141      YAT_ASSERT(last!=this->begin()); // last!=p.first
142      --last;
143      YAT_ASSERT(compare_3way(segment, *last)==0);
144
145      Segment<T, Compare>
146        segment2(std::min(p.first->begin(), segment.begin(), comp),
147                 std::max(last->end(), segment.end(), comp));
148
149      this->container_.erase(p.first, p.second);
150      return this->container_.insert(p.second, segment2);
151    }
152
153    // using compiler generated copying
154    //SegmentSet(const SegmentSet&);
155    //SegmentSet& operator=(const SegmentSet&);
156  };
157
158}}}
159#endif
Note: See TracBrowser for help on using the repository browser.