yat/utility/SegmentSet.h

Code
Comments
Other
Rev Date Author Line
2291 07 Jul 10 peter 1 #ifndef theplu_yat_utility_segment_set
2291 07 Jul 10 peter 2 #define theplu_yat_utility_segment_set
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 /*
2291 07 Jul 10 peter 7   Copyright (C) 2010 Peter Johansson
2820 30 Aug 12 peter 8   Copyright (C) 2012 Jari Häkkinen
4359 23 Aug 23 peter 9   Copyright (C) 2014, 2021 Peter Johansson
2291 07 Jul 10 peter 10
2291 07 Jul 10 peter 11   This file is part of the yat library, http://dev.thep.lu.se/yat
2291 07 Jul 10 peter 12
2291 07 Jul 10 peter 13   The yat library is free software; you can redistribute it and/or
2291 07 Jul 10 peter 14   modify it under the terms of the GNU General Public License as
2291 07 Jul 10 peter 15   published by the Free Software Foundation; either version 3 of the
2291 07 Jul 10 peter 16   License, or (at your option) any later version.
2291 07 Jul 10 peter 17
2291 07 Jul 10 peter 18   The yat library is distributed in the hope that it will be useful,
2291 07 Jul 10 peter 19   but WITHOUT ANY WARRANTY; without even the implied warranty of
2291 07 Jul 10 peter 20   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
2291 07 Jul 10 peter 21   General Public License for more details.
2291 07 Jul 10 peter 22
2291 07 Jul 10 peter 23   You should have received a copy of the GNU General Public License
2291 07 Jul 10 peter 24   along with yat. If not, see <http://www.gnu.org/licenses/>.
2291 07 Jul 10 peter 25 */
2291 07 Jul 10 peter 26
2291 07 Jul 10 peter 27 #include "Segment.h"
2358 02 Dec 10 peter 28 #include "SegmentTree.h"
2360 04 Dec 10 peter 29 #include "stl_utility.h"
2291 07 Jul 10 peter 30 #include "yat_assert.h"
2291 07 Jul 10 peter 31
2291 07 Jul 10 peter 32 #include <set>
2358 02 Dec 10 peter 33 #include <utility>
2291 07 Jul 10 peter 34
2291 07 Jul 10 peter 35 namespace theplu {
2291 07 Jul 10 peter 36 namespace yat {
2291 07 Jul 10 peter 37 namespace utility {
2291 07 Jul 10 peter 38
2291 07 Jul 10 peter 39   /**
2291 07 Jul 10 peter 40      \brief a set of Segments
2291 07 Jul 10 peter 41
2355 30 Nov 10 peter 42      A container that holds a set of Segment. The Segments cannot overlap.
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> >
4026 16 Jan 21 peter 47   class SegmentSet
4026 16 Jan 21 peter 48     : public SegmentTree<std::set<Segment<T, Compare>,
2358 02 Dec 10 peter 49                                   SegmentCompare<T, Compare> >,
2360 04 Dec 10 peter 50                          Compare,
2360 04 Dec 10 peter 51                          Identity<const Segment<T, Compare>&> >
2291 07 Jul 10 peter 52   {
2358 02 Dec 10 peter 53     typedef SegmentSet<T, Compare> me;
2291 07 Jul 10 peter 54   public:
2291 07 Jul 10 peter 55     /**
2357 01 Dec 10 peter 56        \brief creates a set with no segments
2291 07 Jul 10 peter 57      */
2291 07 Jul 10 peter 58     SegmentSet(void) {}
2291 07 Jul 10 peter 59
2291 07 Jul 10 peter 60     /**
2291 07 Jul 10 peter 61        insert \a segment into set. If there is no gap between \a
2357 01 Dec 10 peter 62        segment and neighboring segments the segments are merged.
2291 07 Jul 10 peter 63      */
3337 27 Oct 14 peter 64     typename me::const_iterator
4039 11 Feb 21 peter 65     insert_merge(const Segment<T, Compare>& segment)
2291 07 Jul 10 peter 66     {
3337 27 Oct 14 peter 67       std::pair<typename me::iterator, typename me::iterator> p =
2819 29 Aug 12 jari 68         this->overlap_range(segment);
4027 17 Jan 21 peter 69       Segment<T> tmp(segment);
4027 17 Jan 21 peter 70       return move_insert_merge(p, std::move(tmp));
3344 06 Nov 14 peter 71     }
3344 06 Nov 14 peter 72
3344 06 Nov 14 peter 73     /**
4026 16 Jan 21 peter 74        insert \a segment into set. If there is no gap between \a
4026 16 Jan 21 peter 75        segment and neighboring segments the segments are merged.
4026 16 Jan 21 peter 76
4026 16 Jan 21 peter 77        \since New in yat 0.19
4026 16 Jan 21 peter 78      */
4026 16 Jan 21 peter 79     typename me::const_iterator
4039 11 Feb 21 peter 80     insert_merge(Segment<T, Compare>&& segment)
4026 16 Jan 21 peter 81     {
4026 16 Jan 21 peter 82       std::pair<typename me::iterator, typename me::iterator> p =
4026 16 Jan 21 peter 83         this->overlap_range(segment);
4026 16 Jan 21 peter 84       return move_insert_merge(p, std::move(segment));
4026 16 Jan 21 peter 85     }
4026 16 Jan 21 peter 86
4026 16 Jan 21 peter 87     /**
3344 06 Nov 14 peter 88        \brief insert with a hint
3344 06 Nov 14 peter 89
3344 06 Nov 14 peter 90        Similar to insert_merge(1) but \a hint help to find where to
3344 06 Nov 14 peter 91        insert \a segment. For the \a hint to be useful, \a segment
3344 06 Nov 14 peter 92        should not be greater than element hint points to and not
3344 06 Nov 14 peter 93        smaller than element --hint points to.
3344 06 Nov 14 peter 94
3344 06 Nov 14 peter 95        \since New in yat 0.13
3344 06 Nov 14 peter 96      */
3344 06 Nov 14 peter 97     typename me::iterator insert_merge(typename me::iterator hint,
4039 11 Feb 21 peter 98                                        const Segment<T, Compare>& segment)
3344 06 Nov 14 peter 99     {
4039 11 Feb 21 peter 100       Segment<T, Compare> tmp(segment);
4026 16 Jan 21 peter 101       return insert_merge(hint, std::move(tmp));
4026 16 Jan 21 peter 102     }
4026 16 Jan 21 peter 103
4026 16 Jan 21 peter 104
4026 16 Jan 21 peter 105     /**
4026 16 Jan 21 peter 106        \since New in yat 0.19
4026 16 Jan 21 peter 107      */
4026 16 Jan 21 peter 108     typename me::iterator
4026 16 Jan 21 peter 109     insert_merge(typename me::iterator hint,
4039 11 Feb 21 peter 110                  Segment<T, Compare>&& segment)
4026 16 Jan 21 peter 111     {
3344 06 Nov 14 peter 112       std::pair<typename me::iterator, typename me::iterator> p(hint, hint);
3344 06 Nov 14 peter 113       if (this->container_.empty())
4026 16 Jan 21 peter 114         return move_insert_merge(p, std::move(segment));
3344 06 Nov 14 peter 115
3488 01 Apr 16 peter 116       // If hint points to an element that is less than segment, hint
3488 01 Apr 16 peter 117       // is no good and we ignore the hint.
3344 06 Nov 14 peter 118       if (hint!=this->end() && compare(*hint, segment))
4026 16 Jan 21 peter 119         return insert_merge(std::move(segment));
3344 06 Nov 14 peter 120
3344 06 Nov 14 peter 121       if (p.first!=this->begin()) {
3344 06 Nov 14 peter 122         --p.first;
3344 06 Nov 14 peter 123         // If --hint point to an element greater than segment, hint is
3344 06 Nov 14 peter 124         // no good.
3344 06 Nov 14 peter 125         if (compare(segment, *p.first))
4026 16 Jan 21 peter 126           return insert_merge(std::move(segment));
3344 06 Nov 14 peter 127         // find first element that is smaller than segment
3344 06 Nov 14 peter 128         while (p.first!=this->begin() && !compare(*p.first, segment))
3344 06 Nov 14 peter 129           --p.first;
3344 06 Nov 14 peter 130         YAT_ASSERT(p.first==this->begin() || compare(*p.first, segment));
3344 06 Nov 14 peter 131         YAT_ASSERT(p.first!=this->end());
3344 06 Nov 14 peter 132         if (compare(*p.first, segment))
3344 06 Nov 14 peter 133           ++p.first;
3344 06 Nov 14 peter 134       }
3344 06 Nov 14 peter 135
3344 06 Nov 14 peter 136       // find first element greater than segment
3344 06 Nov 14 peter 137       while (p.second!=this->end() && !compare(segment, *p.second))
3344 06 Nov 14 peter 138         ++p.second;
3344 06 Nov 14 peter 139
4026 16 Jan 21 peter 140       return move_insert_merge(p, std::move(segment));
3344 06 Nov 14 peter 141     }
3344 06 Nov 14 peter 142
4026 16 Jan 21 peter 143
3345 06 Nov 14 peter 144     /**
3345 06 Nov 14 peter 145        Insert range [first, last). Same result as inserting them
3345 06 Nov 14 peter 146        individually, but inserting a range is potentially faster,
3345 06 Nov 14 peter 147        especially if range is sorted and set is sparse compared to
3345 06 Nov 14 peter 148        range.
3345 06 Nov 14 peter 149
3345 06 Nov 14 peter 150       \since new in yat 0.13
3345 06 Nov 14 peter 151      */
3345 06 Nov 14 peter 152     template<typename Iterator>
3345 06 Nov 14 peter 153     void insert_merge(Iterator first, Iterator last)
3345 06 Nov 14 peter 154     {
3345 06 Nov 14 peter 155       typename me::iterator it = this->end();
3345 06 Nov 14 peter 156       for ( ; first!=last; ++first) {
3345 06 Nov 14 peter 157         it = insert_merge(it, *first);
3345 06 Nov 14 peter 158         ++it;
3345 06 Nov 14 peter 159       }
3345 06 Nov 14 peter 160     }
3344 06 Nov 14 peter 161   private:
4026 16 Jan 21 peter 162     // used by functions merge_basic. This function does the actual
4026 16 Jan 21 peter 163     // work. Note that it takes an rvalue; functions that only have
4026 16 Jan 21 peter 164     // access to an lvalue const& need to create a (temporary) copy
4026 16 Jan 21 peter 165     // that can be moved in.
3344 06 Nov 14 peter 166     //
3344 06 Nov 14 peter 167     // p.first points to the first segment that overlaps with \a segment or
3344 06 Nov 14 peter 168     // is greater than segment.
3344 06 Nov 14 peter 169     // p.second points to the first segment that is greater than \a segment
3344 06 Nov 14 peter 170     typename me::const_iterator
4026 16 Jan 21 peter 171     move_insert_merge(const std::pair<typename me::iterator,
4026 16 Jan 21 peter 172                                       typename me::iterator>& p,
4039 11 Feb 21 peter 173                       Segment<T, Compare>&& segment)
3344 06 Nov 14 peter 174     {
3344 06 Nov 14 peter 175       YAT_ASSERT(p.first==this->end() || !compare(*p.first, segment));
3344 06 Nov 14 peter 176       YAT_ASSERT(p.second==this->end() || compare(segment, *p.second));
2358 02 Dec 10 peter 177       if (p.first==p.second) { // no overlap between set and segment
4026 16 Jan 21 peter 178         return this->container_.insert(p.first, std::move(segment));
2291 07 Jul 10 peter 179       }
2358 02 Dec 10 peter 180       /*
2358 02 Dec 10 peter 181         p.first           last         p.second
2358 02 Dec 10 peter 182         --->    --->      --->         --->
3337 27 Oct 14 peter 183
2358 02 Dec 10 peter 184         ----------------------->
2358 02 Dec 10 peter 185         segment
2358 02 Dec 10 peter 186       */
2358 02 Dec 10 peter 187       Compare comp;
2358 02 Dec 10 peter 188       typename me::iterator last=p.second;
2358 02 Dec 10 peter 189       YAT_ASSERT(last==this->end() || compare(segment, *last));
2358 02 Dec 10 peter 190       YAT_ASSERT(last!=this->begin()); // last!=p.first
2358 02 Dec 10 peter 191       --last;
2358 02 Dec 10 peter 192       YAT_ASSERT(compare_3way(segment, *last)==0);
3337 27 Oct 14 peter 193
3337 27 Oct 14 peter 194       Segment<T, Compare>
3337 27 Oct 14 peter 195         segment2(std::min(p.first->begin(), segment.begin(), comp),
3337 27 Oct 14 peter 196                  std::max(last->end(), segment.end(), comp));
3337 27 Oct 14 peter 197
3337 27 Oct 14 peter 198       this->container_.erase(p.first, p.second);
4026 16 Jan 21 peter 199       return this->container_.insert(p.second, std::move(segment2));
2291 07 Jul 10 peter 200     }
2291 07 Jul 10 peter 201
2291 07 Jul 10 peter 202     // using compiler generated copying
2291 07 Jul 10 peter 203     //SegmentSet(const SegmentSet&);
2291 07 Jul 10 peter 204     //SegmentSet& operator=(const SegmentSet&);
2291 07 Jul 10 peter 205   };
2291 07 Jul 10 peter 206
2291 07 Jul 10 peter 207 }}}
2291 07 Jul 10 peter 208 #endif

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