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

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

Update copyright years. Happy New Year

  • Property svn:eol-style set to native
  • Property svn:keywords set to Id
File size: 6.4 KB
Line 
1#ifndef theplu_yat_utility_segment
2#define theplu_yat_utility_segment
3
4// $Id: Segment.h 3550 2017-01-03 05:41:02Z 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     \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 -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.
212
213     \relates Segment
214
215     \since new in yat 0.14
216   */
217  template<typename T, class Compare>
218  int compare_3way(const Segment<T, Compare>& segment,
219                   const T& element)
220  {
221    return -compare_3way(element, segment);
222  }
223
224  /**
225     \return intersection of \a a and \a b. If \a a and \a b do not
226     overlap an empty Section is returned (begin==end), but the exact
227     value of begin is undefined.
228
229     \relates Segment
230
231     \since new in yat 0.7
232   */
233  template<typename T, class Compare>
234  Segment<T, Compare> intersection(const Segment<T, Compare>& a,
235                                   const Segment<T, Compare>& b)
236  {
237    Compare comp;
238    Segment<T, Compare> result;
239
240    result.begin() = std::max(a.begin(), b.begin(), comp);
241    // the first max is needed in case a and b don't overlap
242    result.end() = std::max(result.begin(),
243                            std::min(a.end(), b.end(), comp),
244                            comp);
245    return result;
246  }
247
248  /**
249     \brief functor using compare
250   */
251  template<typename T, class Compare>
252  struct SegmentCompare :
253    public std::binary_function<Segment<T,Compare>, Segment<T,Compare>, bool>
254  {
255    /**
256       \see compare(const Segment<T,Compare>&, const Segment<T,Compare>&)
257     */
258    bool operator()(const Segment<T, Compare>& lhs,
259                    const Segment<T, Compare>& rhs) const
260    { return compare(lhs, rhs); }
261  };
262
263}}}
264#endif
Note: See TracBrowser for help on using the repository browser.