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

Last change on this file since 2357 was 2357, checked in by Peter, 12 years ago

use compare(Segment, Segment) as comparator in SegmentSet? which allows simplifications in SegmentSet? code. Add some tests and docs.

  • Property svn:eol-style set to native
  • Property svn:keywords set to Id
File size: 4.8 KB
Line 
1#ifndef theplu_yat_utility_segment
2#define theplu_yat_utility_segment
3
4// $Id: Segment.h 2357 2010-12-01 21:08:29Z 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     This function takes two Segment and compare them with comparator
99     Compare. If all elements in \a lhs is less than all elements in
100     \a rhs, \c true is returned. In other words, \c false is returned
101     if \a rhs.begin() is less than \a lhs.end().
102
103     The exception is if both \a lhs and \a rhs are empty Segment
104     (i.e. begin equals end) and their begins and ends are equal, in
105     which case \c false is returned. This exception implies that
106     compare(x,x) always returns false.
107
108     \relates Segment
109
110     \since new in yat 0.7
111   */
112  template<typename T, class Compare>
113  bool compare(const Segment<T, Compare>& lhs, const Segment<T, Compare>& rhs)
114  {
115    Compare c;
116    // begin <= end
117    YAT_ASSERT(!c(lhs.end(), lhs.begin()));
118    YAT_ASSERT(!c(rhs.end(), rhs.begin()));
119    // take care of case when both sides are zero segments
120    if (!c(lhs.begin(), lhs.end()) && !c(rhs.begin(), rhs.end())) {
121      return c(lhs.begin(), rhs.begin());
122    }
123
124    return ! c(rhs.begin(), lhs.end());
125  }
126
127  /**
128     \return -1 if compare(lhs, rhs) is \c true, +1 if compare(rhs,
129     lhs) is \c true, and 0 otherwise
130
131     \relates Segment
132
133     \see compare(const Segment<T, Compare>&, const Segment<T, Compare>&)
134
135     \since new in yat 0.7
136   */
137  template<typename T, class Compare>
138  int compare_3way(const Segment<T, Compare>& lhs, 
139                   const Segment<T, Compare>& rhs)
140  {
141    if (compare(lhs, rhs))
142      return -1;
143    if (compare(rhs, lhs))
144      return 1;
145    return 0;
146  }
147
148  /**
149     \return -1 if \a element is less than all elements in \a segment,
150     0 if \a element overlaps with \a segment, and 1 otherwise.
151
152     \relates Segment
153
154     \since new in yat 0.7
155   */
156  template<typename T, class Compare>
157  int compare_3way(const T& element, 
158                   const Segment<T, Compare>& segment)
159  {
160    Compare comp;
161    if (comp(element, segment.begin()))
162      return -1;
163    if (comp(element, segment.end()))
164      return 0;
165    return 1;
166  }
167
168  /**
169     \return intersection of \a a and \a b. If \a a and \a b do not
170     overlap an empty Section is returned (begin==end), but the exact
171     value of begin is undefined.
172
173     \relates Segment
174
175     \since new in yat 0.7
176   */
177  template<typename T, class Compare>
178  Segment<T, Compare> intersection(const Segment<T, Compare>& a, 
179                                   const Segment<T, Compare>& b)
180  {
181    Compare comp;
182    Segment<T, Compare> result;
183
184    result.begin() = std::max(a.begin(), b.begin(), comp);
185    // the first max is needed in case a and b don't overlap
186    result.end() = std::max(result.begin(), 
187                            std::min(a.end(), b.end(), comp),
188                            comp);
189    return result;
190  }
191
192}}}
193#endif
Note: See TracBrowser for help on using the repository browser.