source: trunk/yat/utility/Segment.h @ 3451

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

add relates dox tag

  • Property svn:eol-style set to native
  • Property svn:keywords set to Id
File size: 6.1 KB
Line 
1#ifndef theplu_yat_utility_segment
2#define theplu_yat_utility_segment
3
4// $Id: Segment.h 3451 2015-12-07 07:15:09Z peter $
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 "yat_assert.h"
26
27#include <algorithm>
28#include <functional>
29
30namespace theplu {
31namespace yat {
32namespace utility {
33
34  /**
35     \brief a class for a Segment or Interval
36
37     A Segment is defined by its \a begin and \a end. The end is not
38     included in the Segment, i.e., you could write the Segment as
39     [begin, end). Type T must be comparable, optionally with a
40     comparator Compare, which should implement <a
41     href="http://www.sgi.com/tech/stl/StrictWeakOrdering.html">
42     Strict Weak Ordering.</a>.
43
44     \since new in yat 0.7
45   */
46  template<typename T, class Compare = std::less<T> >
47  class Segment
48  {
49  public:
50    /**
51       type the Segment holds
52     */
53    typedef T value_type;
54
55    /**
56       \brief default constructor
57     */
58    Segment(void) {}
59
60    /**
61       \brief Constructor
62
63       Creates a segment [begin, end)
64     */
65    Segment(const T& begin, const T& end)
66      : begin_(begin), end_(end) {}
67
68    /**
69       \return reference to first element in Segment
70     */
71    T& begin(void) { return begin_; }
72
73    /**
74       \return const reference to first element in Segment
75     */
76    const T& begin(void) const { return begin_; }
77
78    /**
79       \return reference to first element greater than Segment
80     */
81    T& end(void) { return end_; }
82
83    /**
84       \return const reference to first element greater than Segment
85     */
86    const T& end(void) const { return end_; }
87
88  private:
89    T begin_;
90    T end_;
91
92    // using compiler generated copying
93    //Segment(const Segment&);
94    //Segment& operator=(const Segment&);
95  };
96
97
98  /**
99     \brief Inequality operator
100
101     Inequality operator is defined via the operator< of T or in the
102     general case Compare.
103
104     \return true if Compare returns true for either when comparing
105     lhs.begin() and rhs.begin() or when comparing lhs.end() and
106     rhs.end().
107
108     \relates Segment
109
110     \since New in yat 0.14
111  */
112  template<typename T, class Compare>
113  bool operator!=(const Segment<T, Compare>& lhs,
114                  const Segment<T, Compare>& rhs)
115  {
116    Compare comp;
117    return comp(lhs.begin(), rhs.begin()) ||  comp(rhs.begin(), lhs.begin())
118      || comp(lhs.end(), rhs.end()) || comp(rhs.end(), lhs.end());
119  }
120
121
122  /**
123     \return true if Compare returns false when comparing lhs.begin()
124     and rhs.begin() as well as when comparing lhs.end() and
125     rhs.end().
126
127     \relates Segment
128
129     \since New in yat 0.14
130  */
131  template<typename T, class Compare>
132  bool operator==(const Segment<T, Compare>& lhs,
133                  const Segment<T, Compare>& rhs)
134  {
135    return !(lhs!=rhs);
136  }
137
138
139  /**
140     This function takes two Segment and compare them with comparator
141     Compare. If all elements in \a lhs is less than all elements in
142     \a rhs, \c true is returned. In other words, \c false is returned
143     if \a rhs.begin() is less than \a lhs.end().
144
145     The exception is if both \a lhs and \a rhs are empty Segment
146     (i.e. begin equals end) and their begins and ends are equal, in
147     which case \c false is returned. This exception implies that
148     compare(x,x) always returns false.
149
150     \relates Segment
151
152     \since new in yat 0.7
153   */
154  template<typename T, class Compare>
155  bool compare(const Segment<T, Compare>& lhs, const Segment<T, Compare>& rhs)
156  {
157    Compare c;
158    // begin <= end
159    YAT_ASSERT(!c(lhs.end(), lhs.begin()));
160    YAT_ASSERT(!c(rhs.end(), rhs.begin()));
161    // take care of case when both sides are zero segments
162    if (!c(lhs.begin(), lhs.end()) && !c(rhs.begin(), rhs.end())) {
163      return c(lhs.begin(), rhs.begin());
164    }
165
166    return ! c(rhs.begin(), lhs.end());
167  }
168
169  /**
170     \return -1 if compare(lhs, rhs) is \c true, +1 if compare(rhs,
171     lhs) is \c true, and 0 otherwise
172
173     \relates Segment
174
175     \see compare(const Segment<T, Compare>&, const Segment<T, Compare>&)
176
177     \since new in yat 0.7
178   */
179  template<typename T, class Compare>
180  int compare_3way(const Segment<T, Compare>& lhs,
181                   const Segment<T, Compare>& rhs)
182  {
183    if (compare(lhs, rhs))
184      return -1;
185    if (compare(rhs, lhs))
186      return 1;
187    return 0;
188  }
189
190  /**
191     \return -1 if \a element is less than all elements in \a segment,
192     0 if \a element overlaps with \a segment, and 1 otherwise.
193
194     \relates Segment
195
196     \since new in yat 0.7
197   */
198  template<typename T, class Compare>
199  int compare_3way(const T& element,
200                   const Segment<T, Compare>& segment)
201  {
202    Compare comp;
203    if (comp(element, segment.begin()))
204      return -1;
205    if (comp(element, segment.end()))
206      return 0;
207    return 1;
208  }
209
210  /**
211     \return intersection of \a a and \a b. If \a a and \a b do not
212     overlap an empty Section is returned (begin==end), but the exact
213     value of begin is undefined.
214
215     \relates Segment
216
217     \since new in yat 0.7
218   */
219  template<typename T, class Compare>
220  Segment<T, Compare> intersection(const Segment<T, Compare>& a,
221                                   const Segment<T, Compare>& b)
222  {
223    Compare comp;
224    Segment<T, Compare> result;
225
226    result.begin() = std::max(a.begin(), b.begin(), comp);
227    // the first max is needed in case a and b don't overlap
228    result.end() = std::max(result.begin(),
229                            std::min(a.end(), b.end(), comp),
230                            comp);
231    return result;
232  }
233
234  /**
235     \brief functor using compare
236   */
237  template<typename T, class Compare>
238  struct SegmentCompare :
239    public std::binary_function<Segment<T,Compare>, Segment<T,Compare>, bool>
240  {
241    /**
242       \see compare(const Segment<T,Compare>&, const Segment<T,Compare>&)
243     */
244    bool operator()(const Segment<T, Compare>& lhs,
245                    const Segment<T, Compare>& rhs) const
246    { return compare(lhs, rhs); }
247  };
248
249}}}
250#endif
Note: See TracBrowser for help on using the repository browser.