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

Last change on this file since 3598 was 3598, checked in by Peter, 6 years ago

implement make_segment. closes #834

  • Property svn:eol-style set to native
  • Property svn:keywords set to Id
File size: 6.6 KB
Line 
1#ifndef theplu_yat_utility_segment
2#define theplu_yat_utility_segment
3
4// $Id: Segment.h 3598 2017-01-22 11:17:40Z peter $
5
6/*
7  Copyright (C) 2010, 2015, 2016 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     \return Segment<T>
100
101     \since ney in yat 0.15
102   */
103  template<typename T>
104  Segment<T> make_segment(T first, T last)
105  {
106    return Segment<T>(first, last);
107  }
108
109
110  /**
111     \brief Inequality operator
112
113     Inequality operator is defined via the operator< of T or in the
114     general case Compare.
115
116     \return true if Compare returns true for either when comparing
117     lhs.begin() and rhs.begin() or when comparing lhs.end() and
118     rhs.end().
119
120     \relates Segment
121
122     \since New in yat 0.14
123  */
124  template<typename T, class Compare>
125  bool operator!=(const Segment<T, Compare>& lhs,
126                  const Segment<T, Compare>& rhs)
127  {
128    Compare comp;
129    return comp(lhs.begin(), rhs.begin()) ||  comp(rhs.begin(), lhs.begin())
130      || comp(lhs.end(), rhs.end()) || comp(rhs.end(), lhs.end());
131  }
132
133
134  /**
135     \return true if Compare returns false when comparing lhs.begin()
136     and rhs.begin() as well as when comparing lhs.end() and
137     rhs.end().
138
139     \relates Segment
140
141     \since New in yat 0.14
142  */
143  template<typename T, class Compare>
144  bool operator==(const Segment<T, Compare>& lhs,
145                  const Segment<T, Compare>& rhs)
146  {
147    return !(lhs!=rhs);
148  }
149
150
151  /**
152     This function takes two Segment and compare them with comparator
153     Compare. If all elements in \a lhs is less than all elements in
154     \a rhs, \c true is returned. In other words, \c false is returned
155     if \a rhs.begin() is less than \a lhs.end().
156
157     The exception is if both \a lhs and \a rhs are empty Segment
158     (i.e. begin equals end) and their begins and ends are equal, in
159     which case \c false is returned. This exception implies that
160     compare(x,x) always returns false.
161
162     \relates Segment
163
164     \since new in yat 0.7
165   */
166  template<typename T, class Compare>
167  bool compare(const Segment<T, Compare>& lhs, const Segment<T, Compare>& rhs)
168  {
169    Compare c;
170    // begin <= end
171    YAT_ASSERT(!c(lhs.end(), lhs.begin()));
172    YAT_ASSERT(!c(rhs.end(), rhs.begin()));
173    // take care of case when both sides are zero segments
174    if (!c(lhs.begin(), lhs.end()) && !c(rhs.begin(), rhs.end())) {
175      return c(lhs.begin(), rhs.begin());
176    }
177
178    return ! c(rhs.begin(), lhs.end());
179  }
180
181  /**
182     \return -1 if compare(lhs, rhs) is \c true, +1 if compare(rhs,
183     lhs) is \c true, and 0 otherwise
184
185     \relates Segment
186
187     \see compare(const Segment<T, Compare>&, const Segment<T, Compare>&)
188
189     \since new in yat 0.7
190   */
191  template<typename T, class Compare>
192  int compare_3way(const Segment<T, Compare>& lhs,
193                   const Segment<T, Compare>& rhs)
194  {
195    if (compare(lhs, rhs))
196      return -1;
197    if (compare(rhs, lhs))
198      return 1;
199    return 0;
200  }
201
202  /**
203     \return -1 if \a element is less than all elements in \a segment,
204     0 if \a element overlaps with \a segment, and 1 otherwise.
205
206     \relates Segment
207
208     \since new in yat 0.7
209   */
210  template<typename T, class Compare>
211  int compare_3way(const T& element,
212                   const Segment<T, Compare>& segment)
213  {
214    Compare comp;
215    if (comp(element, segment.begin()))
216      return -1;
217    if (comp(element, segment.end()))
218      return 0;
219    return 1;
220  }
221
222  /**
223     \return -1 if \a all elements in \a segment are less than \a element, 0 if if \a element overlaps with \a segment, and 1 otherwise.
224
225     \relates Segment
226
227     \since new in yat 0.14
228   */
229  template<typename T, class Compare>
230  int compare_3way(const Segment<T, Compare>& segment,
231                   const T& element)
232  {
233    return -compare_3way(element, segment);
234  }
235
236  /**
237     \return intersection of \a a and \a b. If \a a and \a b do not
238     overlap an empty Section is returned (begin==end), but the exact
239     value of begin is undefined.
240
241     \relates Segment
242
243     \since new in yat 0.7
244   */
245  template<typename T, class Compare>
246  Segment<T, Compare> intersection(const Segment<T, Compare>& a,
247                                   const Segment<T, Compare>& b)
248  {
249    Compare comp;
250    Segment<T, Compare> result;
251
252    result.begin() = std::max(a.begin(), b.begin(), comp);
253    // the first max is needed in case a and b don't overlap
254    result.end() = std::max(result.begin(),
255                            std::min(a.end(), b.end(), comp),
256                            comp);
257    return result;
258  }
259
260  /**
261     \brief functor using compare
262   */
263  template<typename T, class Compare>
264  struct SegmentCompare :
265    public std::binary_function<Segment<T,Compare>, Segment<T,Compare>, bool>
266  {
267    /**
268       \see compare(const Segment<T,Compare>&, const Segment<T,Compare>&)
269     */
270    bool operator()(const Segment<T, Compare>& lhs,
271                    const Segment<T, Compare>& rhs) const
272    { return compare(lhs, rhs); }
273  };
274
275}}}
276#endif
Note: See TracBrowser for help on using the repository browser.