yat
0.8.3pre
|
00001 #ifndef theplu_yat_utility_segment 00002 #define theplu_yat_utility_segment 00003 00004 // $Id: Segment.h 2358 2010-12-02 06:58:40Z peter $ 00005 00006 /* 00007 Copyright (C) 2010 Peter Johansson 00008 00009 This file is part of the yat library, http://dev.thep.lu.se/yat 00010 00011 The yat library is free software; you can redistribute it and/or 00012 modify it under the terms of the GNU General Public License as 00013 published by the Free Software Foundation; either version 3 of the 00014 License, or (at your option) any later version. 00015 00016 The yat library is distributed in the hope that it will be useful, 00017 but WITHOUT ANY WARRANTY; without even the implied warranty of 00018 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 00019 General Public License for more details. 00020 00021 You should have received a copy of the GNU General Public License 00022 along with yat. If not, see <http://www.gnu.org/licenses/>. 00023 */ 00024 00025 #include "yat_assert.h" 00026 00027 #include <algorithm> 00028 #include <functional> 00029 00030 namespace theplu { 00031 namespace yat { 00032 namespace utility { 00033 00046 template<typename T, class Compare = std::less<T> > 00047 class Segment 00048 { 00049 public: 00053 typedef T value_type; 00054 00058 Segment(void) {} 00059 00065 Segment(const T& begin, const T& end) 00066 : begin_(begin), end_(end) {} 00067 00071 T& begin(void) { return begin_; } 00072 00076 const T& begin(void) const { return begin_; } 00077 00081 T& end(void) { return end_; } 00082 00086 const T& end(void) const { return end_; } 00087 00088 private: 00089 T begin_; 00090 T end_; 00091 00092 // using compiler generated copying 00093 //Segment(const Segment&); 00094 //Segment& operator=(const Segment&); 00095 }; 00096 00112 template<typename T, class Compare> 00113 bool compare(const Segment<T, Compare>& lhs, const Segment<T, Compare>& rhs) 00114 { 00115 Compare c; 00116 // begin <= end 00117 YAT_ASSERT(!c(lhs.end(), lhs.begin())); 00118 YAT_ASSERT(!c(rhs.end(), rhs.begin())); 00119 // take care of case when both sides are zero segments 00120 if (!c(lhs.begin(), lhs.end()) && !c(rhs.begin(), rhs.end())) { 00121 return c(lhs.begin(), rhs.begin()); 00122 } 00123 00124 return ! c(rhs.begin(), lhs.end()); 00125 } 00126 00137 template<typename T, class Compare> 00138 int compare_3way(const Segment<T, Compare>& lhs, 00139 const Segment<T, Compare>& rhs) 00140 { 00141 if (compare(lhs, rhs)) 00142 return -1; 00143 if (compare(rhs, lhs)) 00144 return 1; 00145 return 0; 00146 } 00147 00156 template<typename T, class Compare> 00157 int compare_3way(const T& element, 00158 const Segment<T, Compare>& segment) 00159 { 00160 Compare comp; 00161 if (comp(element, segment.begin())) 00162 return -1; 00163 if (comp(element, segment.end())) 00164 return 0; 00165 return 1; 00166 } 00167 00177 template<typename T, class Compare> 00178 Segment<T, Compare> intersection(const Segment<T, Compare>& a, 00179 const Segment<T, Compare>& b) 00180 { 00181 Compare comp; 00182 Segment<T, Compare> result; 00183 00184 result.begin() = std::max(a.begin(), b.begin(), comp); 00185 // the first max is needed in case a and b don't overlap 00186 result.end() = std::max(result.begin(), 00187 std::min(a.end(), b.end(), comp), 00188 comp); 00189 return result; 00190 } 00191 00195 template<typename T, class Compare> 00196 struct SegmentCompare : 00197 public std::binary_function<Segment<T,Compare>, Segment<T,Compare>, bool> 00198 { 00202 bool operator()(const Segment<T, Compare>& lhs, 00203 const Segment<T, Compare>& rhs) const 00204 { return compare(lhs, rhs); } 00205 }; 00206 00207 }}} 00208 #endif