yat/utility/Segment.h

Code
Comments
Other
Rev Date Author Line
2291 07 Jul 10 peter 1 #ifndef theplu_yat_utility_segment
2291 07 Jul 10 peter 2 #define theplu_yat_utility_segment
2291 07 Jul 10 peter 3
2291 07 Jul 10 peter 4 // $Id$
2291 07 Jul 10 peter 5
2291 07 Jul 10 peter 6 /*
4359 23 Aug 23 peter 7   Copyright (C) 2010, 2015, 2016, 2017, 2021, 2023 Peter Johansson
2291 07 Jul 10 peter 8
2291 07 Jul 10 peter 9   This file is part of the yat library, http://dev.thep.lu.se/yat
2291 07 Jul 10 peter 10
2291 07 Jul 10 peter 11   The yat library is free software; you can redistribute it and/or
2291 07 Jul 10 peter 12   modify it under the terms of the GNU General Public License as
2291 07 Jul 10 peter 13   published by the Free Software Foundation; either version 3 of the
2291 07 Jul 10 peter 14   License, or (at your option) any later version.
2291 07 Jul 10 peter 15
2291 07 Jul 10 peter 16   The yat library is distributed in the hope that it will be useful,
2291 07 Jul 10 peter 17   but WITHOUT ANY WARRANTY; without even the implied warranty of
2291 07 Jul 10 peter 18   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
2291 07 Jul 10 peter 19   General Public License for more details.
2291 07 Jul 10 peter 20
2291 07 Jul 10 peter 21   You should have received a copy of the GNU General Public License
2291 07 Jul 10 peter 22   along with yat. If not, see <http://www.gnu.org/licenses/>.
2291 07 Jul 10 peter 23 */
2291 07 Jul 10 peter 24
2357 01 Dec 10 peter 25 #include "yat_assert.h"
2357 01 Dec 10 peter 26
2321 02 Sep 10 peter 27 #include <algorithm>
2291 07 Jul 10 peter 28 #include <functional>
2291 07 Jul 10 peter 29
2291 07 Jul 10 peter 30 namespace theplu {
2291 07 Jul 10 peter 31 namespace yat {
2291 07 Jul 10 peter 32 namespace utility {
2291 07 Jul 10 peter 33
2291 07 Jul 10 peter 34   /**
2291 07 Jul 10 peter 35      \brief a class for a Segment or Interval
2291 07 Jul 10 peter 36
2357 01 Dec 10 peter 37      A Segment is defined by its \a begin and \a end. The end is not
2357 01 Dec 10 peter 38      included in the Segment, i.e., you could write the Segment as
2357 01 Dec 10 peter 39      [begin, end). Type T must be comparable, optionally with a
2357 01 Dec 10 peter 40      comparator Compare, which should implement <a
2357 01 Dec 10 peter 41      href="http://www.sgi.com/tech/stl/StrictWeakOrdering.html">
3449 07 Dec 15 peter 42      Strict Weak Ordering.</a>.
2291 07 Jul 10 peter 43
2291 07 Jul 10 peter 44      \since new in yat 0.7
2291 07 Jul 10 peter 45    */
2291 07 Jul 10 peter 46   template<typename T, class Compare = std::less<T> >
2291 07 Jul 10 peter 47   class Segment
2291 07 Jul 10 peter 48   {
2291 07 Jul 10 peter 49   public:
2291 07 Jul 10 peter 50     /**
2291 07 Jul 10 peter 51        type the Segment holds
2291 07 Jul 10 peter 52      */
2291 07 Jul 10 peter 53     typedef T value_type;
2291 07 Jul 10 peter 54
2291 07 Jul 10 peter 55     /**
2291 07 Jul 10 peter 56        \brief default constructor
2291 07 Jul 10 peter 57      */
2291 07 Jul 10 peter 58     Segment(void) {}
2291 07 Jul 10 peter 59
2291 07 Jul 10 peter 60     /**
2291 07 Jul 10 peter 61        \brief Constructor
2291 07 Jul 10 peter 62
2291 07 Jul 10 peter 63        Creates a segment [begin, end)
2291 07 Jul 10 peter 64      */
2291 07 Jul 10 peter 65     Segment(const T& begin, const T& end)
2291 07 Jul 10 peter 66       : begin_(begin), end_(end) {}
2291 07 Jul 10 peter 67
2291 07 Jul 10 peter 68     /**
4023 04 Jan 21 peter 69        \brief Constructor
4023 04 Jan 21 peter 70
4023 04 Jan 21 peter 71        Creates a segment [begin, end)
4023 04 Jan 21 peter 72
4023 04 Jan 21 peter 73        \since New in yat 0.19
4023 04 Jan 21 peter 74      */
4023 04 Jan 21 peter 75     Segment(T&& begin, T&& end)
4023 04 Jan 21 peter 76       : begin_(std::move(begin)), end_(std::move(end)) {}
4023 04 Jan 21 peter 77
4023 04 Jan 21 peter 78     /**
2291 07 Jul 10 peter 79        \return reference to first element in Segment
2291 07 Jul 10 peter 80      */
2291 07 Jul 10 peter 81     T& begin(void) { return begin_; }
2291 07 Jul 10 peter 82
2291 07 Jul 10 peter 83     /**
2291 07 Jul 10 peter 84        \return const reference to first element in Segment
2291 07 Jul 10 peter 85      */
2291 07 Jul 10 peter 86     const T& begin(void) const { return begin_; }
2291 07 Jul 10 peter 87
2291 07 Jul 10 peter 88     /**
2291 07 Jul 10 peter 89        \return reference to first element greater than Segment
2291 07 Jul 10 peter 90      */
2291 07 Jul 10 peter 91     T& end(void) { return end_; }
2291 07 Jul 10 peter 92
2291 07 Jul 10 peter 93     /**
2291 07 Jul 10 peter 94        \return const reference to first element greater than Segment
2291 07 Jul 10 peter 95      */
2291 07 Jul 10 peter 96     const T& end(void) const { return end_; }
3449 07 Dec 15 peter 97
2291 07 Jul 10 peter 98   private:
2291 07 Jul 10 peter 99     T begin_;
2291 07 Jul 10 peter 100     T end_;
3449 07 Dec 15 peter 101
2291 07 Jul 10 peter 102     // using compiler generated copying
2291 07 Jul 10 peter 103     //Segment(const Segment&);
2291 07 Jul 10 peter 104     //Segment& operator=(const Segment&);
2291 07 Jul 10 peter 105   };
2291 07 Jul 10 peter 106
3450 07 Dec 15 peter 107
2291 07 Jul 10 peter 108   /**
3598 22 Jan 17 peter 109      \return Segment<T>
3598 22 Jan 17 peter 110
3598 22 Jan 17 peter 111      \since ney in yat 0.15
3598 22 Jan 17 peter 112    */
3598 22 Jan 17 peter 113   template<typename T>
3598 22 Jan 17 peter 114   Segment<T> make_segment(T first, T last)
3598 22 Jan 17 peter 115   {
3598 22 Jan 17 peter 116     return Segment<T>(first, last);
3598 22 Jan 17 peter 117   }
3598 22 Jan 17 peter 118
3598 22 Jan 17 peter 119
3598 22 Jan 17 peter 120   /**
3450 07 Dec 15 peter 121      \brief Inequality operator
3450 07 Dec 15 peter 122
3450 07 Dec 15 peter 123      Inequality operator is defined via the operator< of T or in the
3450 07 Dec 15 peter 124      general case Compare.
3450 07 Dec 15 peter 125
3450 07 Dec 15 peter 126      \return true if Compare returns true for either when comparing
3450 07 Dec 15 peter 127      lhs.begin() and rhs.begin() or when comparing lhs.end() and
3450 07 Dec 15 peter 128      rhs.end().
3450 07 Dec 15 peter 129
3451 07 Dec 15 peter 130      \relates Segment
3451 07 Dec 15 peter 131
3450 07 Dec 15 peter 132      \since New in yat 0.14
3450 07 Dec 15 peter 133   */
3450 07 Dec 15 peter 134   template<typename T, class Compare>
3450 07 Dec 15 peter 135   bool operator!=(const Segment<T, Compare>& lhs,
3450 07 Dec 15 peter 136                   const Segment<T, Compare>& rhs)
3450 07 Dec 15 peter 137   {
3450 07 Dec 15 peter 138     Compare comp;
3450 07 Dec 15 peter 139     return comp(lhs.begin(), rhs.begin()) ||  comp(rhs.begin(), lhs.begin())
3450 07 Dec 15 peter 140       || comp(lhs.end(), rhs.end()) || comp(rhs.end(), lhs.end());
3450 07 Dec 15 peter 141   }
3450 07 Dec 15 peter 142
3450 07 Dec 15 peter 143
3450 07 Dec 15 peter 144   /**
3450 07 Dec 15 peter 145      \return true if Compare returns false when comparing lhs.begin()
3450 07 Dec 15 peter 146      and rhs.begin() as well as when comparing lhs.end() and
3450 07 Dec 15 peter 147      rhs.end().
3450 07 Dec 15 peter 148
3451 07 Dec 15 peter 149      \relates Segment
3451 07 Dec 15 peter 150
3450 07 Dec 15 peter 151      \since New in yat 0.14
3450 07 Dec 15 peter 152   */
3450 07 Dec 15 peter 153   template<typename T, class Compare>
3450 07 Dec 15 peter 154   bool operator==(const Segment<T, Compare>& lhs,
3450 07 Dec 15 peter 155                   const Segment<T, Compare>& rhs)
3450 07 Dec 15 peter 156   {
3450 07 Dec 15 peter 157     return !(lhs!=rhs);
3450 07 Dec 15 peter 158   }
3450 07 Dec 15 peter 159
3450 07 Dec 15 peter 160
3450 07 Dec 15 peter 161   /**
2357 01 Dec 10 peter 162      This function takes two Segment and compare them with comparator
2357 01 Dec 10 peter 163      Compare. If all elements in \a lhs is less than all elements in
2357 01 Dec 10 peter 164      \a rhs, \c true is returned. In other words, \c false is returned
2357 01 Dec 10 peter 165      if \a rhs.begin() is less than \a lhs.end().
2291 07 Jul 10 peter 166
2357 01 Dec 10 peter 167      The exception is if both \a lhs and \a rhs are empty Segment
2357 01 Dec 10 peter 168      (i.e. begin equals end) and their begins and ends are equal, in
2357 01 Dec 10 peter 169      which case \c false is returned. This exception implies that
2357 01 Dec 10 peter 170      compare(x,x) always returns false.
2357 01 Dec 10 peter 171
2291 07 Jul 10 peter 172      \relates Segment
2291 07 Jul 10 peter 173
2291 07 Jul 10 peter 174      \since new in yat 0.7
2291 07 Jul 10 peter 175    */
2291 07 Jul 10 peter 176   template<typename T, class Compare>
2291 07 Jul 10 peter 177   bool compare(const Segment<T, Compare>& lhs, const Segment<T, Compare>& rhs)
2291 07 Jul 10 peter 178   {
2291 07 Jul 10 peter 179     Compare c;
2357 01 Dec 10 peter 180     // begin <= end
2357 01 Dec 10 peter 181     YAT_ASSERT(!c(lhs.end(), lhs.begin()));
2357 01 Dec 10 peter 182     YAT_ASSERT(!c(rhs.end(), rhs.begin()));
2357 01 Dec 10 peter 183     // take care of case when both sides are zero segments
2357 01 Dec 10 peter 184     if (!c(lhs.begin(), lhs.end()) && !c(rhs.begin(), rhs.end())) {
2357 01 Dec 10 peter 185       return c(lhs.begin(), rhs.begin());
2357 01 Dec 10 peter 186     }
2357 01 Dec 10 peter 187
2291 07 Jul 10 peter 188     return ! c(rhs.begin(), lhs.end());
2291 07 Jul 10 peter 189   }
2291 07 Jul 10 peter 190
2291 07 Jul 10 peter 191   /**
2357 01 Dec 10 peter 192      \return -1 if compare(lhs, rhs) is \c true, +1 if compare(rhs,
2357 01 Dec 10 peter 193      lhs) is \c true, and 0 otherwise
2291 07 Jul 10 peter 194
2291 07 Jul 10 peter 195      \relates Segment
2291 07 Jul 10 peter 196
2357 01 Dec 10 peter 197      \see compare(const Segment<T, Compare>&, const Segment<T, Compare>&)
2357 01 Dec 10 peter 198
2291 07 Jul 10 peter 199      \since new in yat 0.7
2291 07 Jul 10 peter 200    */
2291 07 Jul 10 peter 201   template<typename T, class Compare>
3449 07 Dec 15 peter 202   int compare_3way(const Segment<T, Compare>& lhs,
2357 01 Dec 10 peter 203                    const Segment<T, Compare>& rhs)
2291 07 Jul 10 peter 204   {
2291 07 Jul 10 peter 205     if (compare(lhs, rhs))
2291 07 Jul 10 peter 206       return -1;
2291 07 Jul 10 peter 207     if (compare(rhs, lhs))
2291 07 Jul 10 peter 208       return 1;
2291 07 Jul 10 peter 209     return 0;
2291 07 Jul 10 peter 210   }
2291 07 Jul 10 peter 211
2291 07 Jul 10 peter 212   /**
2357 01 Dec 10 peter 213      \return -1 if \a element is less than all elements in \a segment,
2357 01 Dec 10 peter 214      0 if \a element overlaps with \a segment, and 1 otherwise.
2291 07 Jul 10 peter 215
2291 07 Jul 10 peter 216      \relates Segment
2291 07 Jul 10 peter 217
2291 07 Jul 10 peter 218      \since new in yat 0.7
2291 07 Jul 10 peter 219    */
2291 07 Jul 10 peter 220   template<typename T, class Compare>
3449 07 Dec 15 peter 221   int compare_3way(const T& element,
2357 01 Dec 10 peter 222                    const Segment<T, Compare>& segment)
2291 07 Jul 10 peter 223   {
2291 07 Jul 10 peter 224     Compare comp;
2357 01 Dec 10 peter 225     if (comp(element, segment.begin()))
2291 07 Jul 10 peter 226       return -1;
2357 01 Dec 10 peter 227     if (comp(element, segment.end()))
2291 07 Jul 10 peter 228       return 0;
2291 07 Jul 10 peter 229     return 1;
2291 07 Jul 10 peter 230   }
2291 07 Jul 10 peter 231
2293 07 Jul 10 peter 232   /**
3488 01 Apr 16 peter 233      \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.
3488 01 Apr 16 peter 234
3488 01 Apr 16 peter 235      \relates Segment
3488 01 Apr 16 peter 236
3488 01 Apr 16 peter 237      \since new in yat 0.14
3488 01 Apr 16 peter 238    */
3488 01 Apr 16 peter 239   template<typename T, class Compare>
3488 01 Apr 16 peter 240   int compare_3way(const Segment<T, Compare>& segment,
3488 01 Apr 16 peter 241                    const T& element)
3488 01 Apr 16 peter 242   {
3488 01 Apr 16 peter 243     return -compare_3way(element, segment);
3488 01 Apr 16 peter 244   }
3488 01 Apr 16 peter 245
3488 01 Apr 16 peter 246   /**
2357 01 Dec 10 peter 247      \return intersection of \a a and \a b. If \a a and \a b do not
2293 07 Jul 10 peter 248      overlap an empty Section is returned (begin==end), but the exact
2293 07 Jul 10 peter 249      value of begin is undefined.
2293 07 Jul 10 peter 250
2293 07 Jul 10 peter 251      \relates Segment
2293 07 Jul 10 peter 252
2293 07 Jul 10 peter 253      \since new in yat 0.7
2293 07 Jul 10 peter 254    */
2293 07 Jul 10 peter 255   template<typename T, class Compare>
3449 07 Dec 15 peter 256   Segment<T, Compare> intersection(const Segment<T, Compare>& a,
2293 07 Jul 10 peter 257                                    const Segment<T, Compare>& b)
2293 07 Jul 10 peter 258   {
2293 07 Jul 10 peter 259     Compare comp;
2293 07 Jul 10 peter 260     Segment<T, Compare> result;
2293 07 Jul 10 peter 261
2293 07 Jul 10 peter 262     result.begin() = std::max(a.begin(), b.begin(), comp);
2357 01 Dec 10 peter 263     // the first max is needed in case a and b don't overlap
3449 07 Dec 15 peter 264     result.end() = std::max(result.begin(),
2293 07 Jul 10 peter 265                             std::min(a.end(), b.end(), comp),
2293 07 Jul 10 peter 266                             comp);
2293 07 Jul 10 peter 267     return result;
2293 07 Jul 10 peter 268   }
2293 07 Jul 10 peter 269
3649 15 Jun 17 peter 270
2358 02 Dec 10 peter 271   /**
3650 18 Jun 17 peter 272      \brief union of two segments
3650 18 Jun 17 peter 273
3650 18 Jun 17 peter 274      \return union of \a a and \a b. If the union of \a a and \a b is
3650 18 Jun 17 peter 275      not a single segment, i.e., a.end() < b.begin() and b.end() <
3650 18 Jun 17 peter 276      a.begin(), the result is undefined.
3650 18 Jun 17 peter 277
3650 18 Jun 17 peter 278      \relates Segment
3650 18 Jun 17 peter 279
3650 18 Jun 17 peter 280      \see SegmentSet
3650 18 Jun 17 peter 281
3650 18 Jun 17 peter 282      \since new in yat 0.15
3650 18 Jun 17 peter 283    */
3650 18 Jun 17 peter 284   template<typename T, class Compare>
3650 18 Jun 17 peter 285   Segment<T, Compare> set_union(const Segment<T, Compare>& a,
3650 18 Jun 17 peter 286                                 const Segment<T, Compare>& b)
3650 18 Jun 17 peter 287   {
3650 18 Jun 17 peter 288     Compare comp;
3650 18 Jun 17 peter 289     return Segment<T, Compare>(std::min(a.begin(), b.begin(), comp),
3650 18 Jun 17 peter 290                                std::max(a.end(), b.end(), comp));
3650 18 Jun 17 peter 291   }
3650 18 Jun 17 peter 292
3650 18 Jun 17 peter 293
3650 18 Jun 17 peter 294   /**
3649 15 Jun 17 peter 295      Return true if (and only if) lhs.begin is not less than rhs.begin
3649 15 Jun 17 peter 296      and rhs.begin is not less than lhs.end
3649 15 Jun 17 peter 297
3813 10 Jul 19 jari 298      \return true if \a lhs is inluded in \a rhs
3649 15 Jun 17 peter 299
3649 15 Jun 17 peter 300      \since New in yat 0.15
3649 15 Jun 17 peter 301    */
3649 15 Jun 17 peter 302   template<typename T, class Compare>
4338 14 Apr 23 peter 303   bool includes(const Segment<T, Compare>& lhs,
4338 14 Apr 23 peter 304                 const Segment<T, Compare>& rhs)
3649 15 Jun 17 peter 305   {
3649 15 Jun 17 peter 306     Compare comp;
3649 15 Jun 17 peter 307     return !(comp(lhs.begin(), rhs.begin()) || comp(rhs.end(), lhs.end()));
3649 15 Jun 17 peter 308   }
3649 15 Jun 17 peter 309
3649 15 Jun 17 peter 310
3649 15 Jun 17 peter 311   /**
3649 15 Jun 17 peter 312      Return true if \a lhs is not less than \a rhs and \a rhs is not
3649 15 Jun 17 peter 313      less than \a lhs
3649 15 Jun 17 peter 314
3813 10 Jul 19 jari 315      \return true if \a lhs and \a rhs overlap
3649 15 Jun 17 peter 316
3649 15 Jun 17 peter 317      \since New in yat 0.15
3649 15 Jun 17 peter 318   */
3649 15 Jun 17 peter 319   template<typename T, class Compare>
4338 14 Apr 23 peter 320   bool overlap(const Segment<T, Compare>& lhs, const Segment<T, Compare>& rhs)
3649 15 Jun 17 peter 321   {
3649 15 Jun 17 peter 322     return !compare(lhs, rhs) && !compare(rhs, lhs);
3649 15 Jun 17 peter 323   }
3649 15 Jun 17 peter 324
3649 15 Jun 17 peter 325
3649 15 Jun 17 peter 326   /**
2358 02 Dec 10 peter 327      \brief functor using compare
2358 02 Dec 10 peter 328    */
2358 02 Dec 10 peter 329   template<typename T, class Compare>
4339 15 Apr 23 peter 330   struct SegmentCompare
2358 02 Dec 10 peter 331   {
4339 15 Apr 23 peter 332     /// \c first_argument_type is \c Segment<T,Compare>
4339 15 Apr 23 peter 333     typedef Segment<T,Compare> first_argument_type;
4339 15 Apr 23 peter 334     /// \c second_argument_type is \c Segment<T,Compare>
4339 15 Apr 23 peter 335     typedef Segment<T,Compare> second_argument_type;
4339 15 Apr 23 peter 336     /// \c result_type is \c bool
4339 15 Apr 23 peter 337     typedef bool result_type;
4339 15 Apr 23 peter 338
2358 02 Dec 10 peter 339     /**
2358 02 Dec 10 peter 340        \see compare(const Segment<T,Compare>&, const Segment<T,Compare>&)
2358 02 Dec 10 peter 341      */
3449 07 Dec 15 peter 342     bool operator()(const Segment<T, Compare>& lhs,
2358 02 Dec 10 peter 343                     const Segment<T, Compare>& rhs) const
2358 02 Dec 10 peter 344     { return compare(lhs, rhs); }
2358 02 Dec 10 peter 345   };
2358 02 Dec 10 peter 346
2291 07 Jul 10 peter 347 }}}
2291 07 Jul 10 peter 348 #endif

Generated on Sat Oct 14 02:25:17 2023 (UTC) by svndigest 0.11.2pre (dev build 1672)