yat/utility/SegmentTree.h

Code
Comments
Other
Rev Date Author Line
2358 02 Dec 10 peter 1 #ifndef theplu_yat_utility_segment_tree
2358 02 Dec 10 peter 2 #define theplu_yat_utility_segment_tree
2358 02 Dec 10 peter 3
2358 02 Dec 10 peter 4 // $Id$
2358 02 Dec 10 peter 5
2358 02 Dec 10 peter 6 /*
4024 04 Jan 21 peter 7   Copyright (C) 2010, 2011, 2012, 2013, 2021 Peter Johansson
2358 02 Dec 10 peter 8
2358 02 Dec 10 peter 9   This file is part of the yat library, http://dev.thep.lu.se/yat
2358 02 Dec 10 peter 10
2358 02 Dec 10 peter 11   The yat library is free software; you can redistribute it and/or
2358 02 Dec 10 peter 12   modify it under the terms of the GNU General Public License as
2358 02 Dec 10 peter 13   published by the Free Software Foundation; either version 3 of the
2358 02 Dec 10 peter 14   License, or (at your option) any later version.
2358 02 Dec 10 peter 15
2358 02 Dec 10 peter 16   The yat library is distributed in the hope that it will be useful,
2358 02 Dec 10 peter 17   but WITHOUT ANY WARRANTY; without even the implied warranty of
2358 02 Dec 10 peter 18   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
2358 02 Dec 10 peter 19   General Public License for more details.
2358 02 Dec 10 peter 20
2358 02 Dec 10 peter 21   You should have received a copy of the GNU General Public License
2358 02 Dec 10 peter 22   along with yat. If not, see <http://www.gnu.org/licenses/>.
2358 02 Dec 10 peter 23 */
2358 02 Dec 10 peter 24
2358 02 Dec 10 peter 25 #include "Segment.h"
2358 02 Dec 10 peter 26
2358 02 Dec 10 peter 27 #include "yat_assert.h"
2358 02 Dec 10 peter 28
2358 02 Dec 10 peter 29 #include <algorithm>
2358 02 Dec 10 peter 30 #include <functional>
4024 04 Jan 21 peter 31 #include <utility>
2358 02 Dec 10 peter 32
2358 02 Dec 10 peter 33 namespace theplu {
2358 02 Dec 10 peter 34 namespace yat {
2358 02 Dec 10 peter 35 namespace utility {
2358 02 Dec 10 peter 36
2358 02 Dec 10 peter 37   /**
2358 02 Dec 10 peter 38      \brief Base Class for SegmentSet and SegmentMap
2360 04 Dec 10 peter 39
2360 04 Dec 10 peter 40      - Container: underlying container (set or map)
2360 04 Dec 10 peter 41      - Compare: functor comparing elements (same as in Segment)
2360 04 Dec 10 peter 42      - Value2Key: functor translating a \c const_reference to \c
2360 04 Dec 10 peter 43        key_type (or \c const&)
2358 02 Dec 10 peter 44    */
2360 04 Dec 10 peter 45   template<class Container, class Compare, class Value2Key>
2703 12 Mar 12 peter 46   class SegmentTree
2358 02 Dec 10 peter 47   {
2358 02 Dec 10 peter 48   public:
2703 12 Mar 12 peter 49     /**
2703 12 Mar 12 peter 50        \brief key type is same as \c Container 's \c key_type.
2703 12 Mar 12 peter 51
2703 12 Mar 12 peter 52        Typically Segment<element_type>.
2703 12 Mar 12 peter 53     */
2358 02 Dec 10 peter 54     typedef typename Container::key_type key_type;
2703 12 Mar 12 peter 55
2703 12 Mar 12 peter 56     /**
2703 12 Mar 12 peter 57        \brief value type is same as \c Container 's \c value_type.
2703 12 Mar 12 peter 58
2703 12 Mar 12 peter 59        Typically a Segment<element_type> or pair<const
2703 12 Mar 12 peter 60        Segment<element_type>, Data>.
2703 12 Mar 12 peter 61     */
2358 02 Dec 10 peter 62     typedef typename Container::value_type value_type;
2703 12 Mar 12 peter 63
2703 12 Mar 12 peter 64     /**
2703 12 Mar 12 peter 65        \brief element type is same as \c key_type 's value_type.
2703 12 Mar 12 peter 66
2703 12 Mar 12 peter 67        If the key held is \c Segment<T>, \c value_type is \c T.
2703 12 Mar 12 peter 68     */
2358 02 Dec 10 peter 69     typedef typename key_type::value_type element_type;
2358 02 Dec 10 peter 70
2703 12 Mar 12 peter 71     ///  \brief key compare
2358 02 Dec 10 peter 72     typedef typename Container::key_compare key_compare;
2610 03 Nov 11 peter 73     /// \brief value compare
2358 02 Dec 10 peter 74     typedef typename Container::value_compare value_compare;
2358 02 Dec 10 peter 75     /// \brief element compare
2358 02 Dec 10 peter 76     typedef Compare element_compare;
2358 02 Dec 10 peter 77
2358 02 Dec 10 peter 78     /// \brief pointer
2358 02 Dec 10 peter 79     typedef typename Container::pointer pointer;
2358 02 Dec 10 peter 80     /// \brief reference
2358 02 Dec 10 peter 81     typedef typename Container::reference reference;
2358 02 Dec 10 peter 82     /// \brief const reference
2358 02 Dec 10 peter 83     typedef typename Container::const_reference const_reference;
2358 02 Dec 10 peter 84     /// \brief size_type
2358 02 Dec 10 peter 85     typedef typename Container::size_type size_type;
2358 02 Dec 10 peter 86     /// \brief difference_type
2358 02 Dec 10 peter 87     typedef typename Container::difference_type difference_type;
2358 02 Dec 10 peter 88     /// \brief iterator
2358 02 Dec 10 peter 89     typedef typename Container::iterator iterator;
2358 02 Dec 10 peter 90     /// \brief const_iterator
2358 02 Dec 10 peter 91     typedef typename Container::const_iterator const_iterator;
2358 02 Dec 10 peter 92
2358 02 Dec 10 peter 93     /**
2703 12 Mar 12 peter 94        \brief creates a SegmentTree with no segments
2358 02 Dec 10 peter 95      */
2358 02 Dec 10 peter 96     SegmentTree(void) {}
2358 02 Dec 10 peter 97
2358 02 Dec 10 peter 98     /**
2361 04 Dec 10 peter 99        \brief Destructor
2361 04 Dec 10 peter 100     */
2361 04 Dec 10 peter 101     virtual ~SegmentTree(void) {}
2361 04 Dec 10 peter 102
2361 04 Dec 10 peter 103     /**
2703 12 Mar 12 peter 104        \return const iterator pointing to beginning of container
2358 02 Dec 10 peter 105      */
2358 02 Dec 10 peter 106     const_iterator begin(void) const { return container_.begin(); }
2358 02 Dec 10 peter 107
2358 02 Dec 10 peter 108     /**
2703 12 Mar 12 peter 109        \return iterator pointing to beginning of container
2358 02 Dec 10 peter 110      */
2358 02 Dec 10 peter 111     iterator begin(void) { return container_.begin(); }
2358 02 Dec 10 peter 112
2358 02 Dec 10 peter 113     /**
2703 12 Mar 12 peter 114        \brief erases all values
2358 02 Dec 10 peter 115      */
2358 02 Dec 10 peter 116     void clear(void) { container_.clear(); }
2358 02 Dec 10 peter 117
2358 02 Dec 10 peter 118     /**
2703 12 Mar 12 peter 119        \return 1 if there is a Segment that overlaps with \a element
2358 02 Dec 10 peter 120      */
2358 02 Dec 10 peter 121     size_type count(const element_type& element) const;
2358 02 Dec 10 peter 122
2358 02 Dec 10 peter 123     /**
2610 03 Nov 11 peter 124        \return \c true if size is zero
2358 02 Dec 10 peter 125     */
2358 02 Dec 10 peter 126     bool empty(void) const { return container_.empty(); }
2358 02 Dec 10 peter 127
2358 02 Dec 10 peter 128     /**
2703 12 Mar 12 peter 129        \return a const_iterator pointing to the end of container
2358 02 Dec 10 peter 130      */
2358 02 Dec 10 peter 131     const_iterator end(void) const { return container_.end(); }
2358 02 Dec 10 peter 132
2358 02 Dec 10 peter 133     /**
2703 12 Mar 12 peter 134        \return end of container
2358 02 Dec 10 peter 135      */
2358 02 Dec 10 peter 136     iterator end(void) { return container_.end(); }
2358 02 Dec 10 peter 137
2358 02 Dec 10 peter 138     /**
2703 12 Mar 12 peter 139        \brief erase values in range [first, last)
2611 04 Nov 11 peter 140
2611 04 Nov 11 peter 141        \since New in yat 0.8
2611 04 Nov 11 peter 142      */
2611 04 Nov 11 peter 143     void erase(iterator first, iterator last) { container_.erase(first, last);}
2611 04 Nov 11 peter 144
2611 04 Nov 11 peter 145     /**
2703 12 Mar 12 peter 146        erase value pointed to by \a pos
2611 04 Nov 11 peter 147
2611 04 Nov 11 peter 148        \since New in yat 0.8
2611 04 Nov 11 peter 149      */
2611 04 Nov 11 peter 150     void erase(iterator pos) { container_.erase(pos); }
2611 04 Nov 11 peter 151
2611 04 Nov 11 peter 152     /**
2703 12 Mar 12 peter 153        \return iterator pointing to value containing \a element
2611 04 Nov 11 peter 154
2703 12 Mar 12 peter 155        If no value contains \a element, end() is returned.
2358 02 Dec 10 peter 156      */
2703 12 Mar 12 peter 157     iterator find(const element_type& element);
2611 04 Nov 11 peter 158
2611 04 Nov 11 peter 159     /**
2703 12 Mar 12 peter 160        \return const iterator pointing to value containing \a element
2703 12 Mar 12 peter 161
2703 12 Mar 12 peter 162        If no value contains \a element, end() is returned.
2703 12 Mar 12 peter 163
2611 04 Nov 11 peter 164        \return an iterator pointing to the Segment that contains \a
3092 16 Oct 13 peter 165        element. If no Segment contains \a element, end() is returned.
2611 04 Nov 11 peter 166      */
3064 09 Jul 13 peter 167     const_iterator find(const element_type& element) const;
2358 02 Dec 10 peter 168
2358 02 Dec 10 peter 169     /**
2703 12 Mar 12 peter 170        \brief insert value
2358 02 Dec 10 peter 171
2703 12 Mar 12 peter 172        if \a value does not overlap with container, insert
2358 02 Dec 10 peter 173        segment; otherwise do nothing.
2358 02 Dec 10 peter 174
2703 12 Mar 12 peter 175        \return a pair where pair.first points to the inserted \a value
2703 12 Mar 12 peter 176        or if \a value was not inserted it points to a value in
2703 12 Mar 12 peter 177        container that overlaps with \a value; pair.second is true if
2703 12 Mar 12 peter 178        \a value was inserted.
2358 02 Dec 10 peter 179      */
2703 12 Mar 12 peter 180     std::pair<iterator, bool> insert(const value_type& value);
2358 02 Dec 10 peter 181
2358 02 Dec 10 peter 182     /**
4024 04 Jan 21 peter 183        Same as insert(const&) but move \a value rather than copy.
4024 04 Jan 21 peter 184
4024 04 Jan 21 peter 185        \since New in yat 0.19
4024 04 Jan 21 peter 186      */
4024 04 Jan 21 peter 187     std::pair<iterator, bool> insert(value_type&& value);
4024 04 Jan 21 peter 188
4024 04 Jan 21 peter 189     /**
2703 12 Mar 12 peter 190        \return Comparison functor to compare two keys (Segment)
2358 02 Dec 10 peter 191      */
2703 12 Mar 12 peter 192     key_compare key_comp(void) const
2703 12 Mar 12 peter 193     {
4032 21 Jan 21 peter 194       return container_.key_comp();
2358 02 Dec 10 peter 195     }
2358 02 Dec 10 peter 196
2358 02 Dec 10 peter 197     /**
2703 12 Mar 12 peter 198        \brief similar to lower_bound in std::set and std::map
2703 12 Mar 12 peter 199
2703 12 Mar 12 peter 200        \return iterator pointing to first value whose key overlaps
2703 12 Mar 12 peter 201        with \a element or is greater than \a element.
2358 02 Dec 10 peter 202      */
2358 02 Dec 10 peter 203     iterator lower_bound(const element_type& element);
2358 02 Dec 10 peter 204
2358 02 Dec 10 peter 205     /**
2703 12 Mar 12 peter 206        \brief similar to lower_bound in std::set and std::map
2703 12 Mar 12 peter 207
2703 12 Mar 12 peter 208        \return const iterator pointing to first value whose key
2703 12 Mar 12 peter 209        overlaps with \a element or is greater than \a element.
2358 02 Dec 10 peter 210      */
2358 02 Dec 10 peter 211     const_iterator lower_bound(const element_type& element) const;
2358 02 Dec 10 peter 212
2358 02 Dec 10 peter 213     /**
2703 12 Mar 12 peter 214        \return number of values in container
2358 02 Dec 10 peter 215      */
2358 02 Dec 10 peter 216     size_type size(void) const { return container_.size(); }
2358 02 Dec 10 peter 217
2358 02 Dec 10 peter 218     /**
2358 02 Dec 10 peter 219        \return iterator pointing to first segment that is greater than
2358 02 Dec 10 peter 220        \a segment.
2358 02 Dec 10 peter 221      */
2358 02 Dec 10 peter 222     iterator upper_bound(const element_type& element);
2358 02 Dec 10 peter 223
2358 02 Dec 10 peter 224     /**
2703 12 Mar 12 peter 225        \brief similar to upper_bound in std::set and std::map
2703 12 Mar 12 peter 226
2703 12 Mar 12 peter 227        \return iterator pointing to first value whose key is greater
2703 12 Mar 12 peter 228        than \a element.
2358 02 Dec 10 peter 229      */
2358 02 Dec 10 peter 230     const_iterator upper_bound(const element_type& element) const;
2358 02 Dec 10 peter 231
2358 02 Dec 10 peter 232     /**
2788 25 Jul 12 peter 233        \return the \c value_compare object used by the class to sort
2788 25 Jul 12 peter 234        \c values
2358 02 Dec 10 peter 235      */
4032 21 Jan 21 peter 236     value_compare value_comp(void) const { return container_.value_comp(); }
2358 02 Dec 10 peter 237
2358 02 Dec 10 peter 238   protected:
2358 02 Dec 10 peter 239     /// underlying container
2358 02 Dec 10 peter 240     Container container_;
2358 02 Dec 10 peter 241
2358 02 Dec 10 peter 242     /**
2358 02 Dec 10 peter 243        pair.first first (smallest) segment that overlaps with \a
2358 02 Dec 10 peter 244        segment and pair.second first (smallest) segment that does not
2358 02 Dec 10 peter 245        overlap with \a segment.
2358 02 Dec 10 peter 246      */
2703 12 Mar 12 peter 247     std::pair<iterator, iterator> overlap_range(const key_type& segment)
2358 02 Dec 10 peter 248     {
2358 02 Dec 10 peter 249       iterator first = container_.lower_bound(segment);
2358 02 Dec 10 peter 250       if (first!=begin()) {
2358 02 Dec 10 peter 251         --first;
2358 02 Dec 10 peter 252         if (compare(*first, segment))
2358 02 Dec 10 peter 253           ++first;
2358 02 Dec 10 peter 254       }
2358 02 Dec 10 peter 255       iterator last = first;
2358 02 Dec 10 peter 256       while (last!=end() && !compare(segment, *last))
2358 02 Dec 10 peter 257         ++last;
2358 02 Dec 10 peter 258       YAT_ASSERT(last==end() || compare(segment, *last));
2358 02 Dec 10 peter 259       return std::make_pair(first, last);
2358 02 Dec 10 peter 260     }
2358 02 Dec 10 peter 261
2358 02 Dec 10 peter 262     // using compiler generated copying
2358 02 Dec 10 peter 263     //SegmentTree(const SegmentTree&);
2358 02 Dec 10 peter 264     //SegmentTree& operator=(const SegmentTree&);
2358 02 Dec 10 peter 265   };
2358 02 Dec 10 peter 266
2360 04 Dec 10 peter 267   template<class Container, class Compare, class Value2Key>
2703 12 Mar 12 peter 268   typename SegmentTree<Container, Compare, Value2Key>::size_type
2360 04 Dec 10 peter 269   SegmentTree<Container,Compare,Value2Key>::count(const element_type& element) const
2358 02 Dec 10 peter 270   {
2358 02 Dec 10 peter 271     if (find(element)==end())
2358 02 Dec 10 peter 272       return 0;
2358 02 Dec 10 peter 273     return 1;
2358 02 Dec 10 peter 274   }
2358 02 Dec 10 peter 275
2358 02 Dec 10 peter 276
2360 04 Dec 10 peter 277   template<class Container, class Compare, class Value2Key>
2703 12 Mar 12 peter 278   typename SegmentTree<Container, Compare, Value2Key>::const_iterator
2360 04 Dec 10 peter 279   SegmentTree<Container, Compare, Value2Key>::find(const element_type& vt) const
2358 02 Dec 10 peter 280   {
2358 02 Dec 10 peter 281     const_iterator iter = lower_bound(vt);
2358 02 Dec 10 peter 282     element_compare comp;
2360 04 Dec 10 peter 283     //    if (iter==end() || comp(vt, iter->begin()))
2360 04 Dec 10 peter 284     if (iter==end() || comp(vt, Value2Key()(*iter).begin()))
2358 02 Dec 10 peter 285       return end();
2358 02 Dec 10 peter 286     return iter;
2358 02 Dec 10 peter 287   }
2358 02 Dec 10 peter 288
2358 02 Dec 10 peter 289
2611 04 Nov 11 peter 290   template<class Container, class Compare, class Value2Key>
2703 12 Mar 12 peter 291   typename SegmentTree<Container, Compare, Value2Key>::iterator
2611 04 Nov 11 peter 292   SegmentTree<Container, Compare, Value2Key>::find(const element_type& vt)
2611 04 Nov 11 peter 293   {
2611 04 Nov 11 peter 294     iterator iter = lower_bound(vt);
2611 04 Nov 11 peter 295     element_compare comp;
2611 04 Nov 11 peter 296     if (iter==end() || comp(vt, Value2Key()(*iter).begin()))
2611 04 Nov 11 peter 297       return end();
2611 04 Nov 11 peter 298     return iter;
2611 04 Nov 11 peter 299   }
2611 04 Nov 11 peter 300
2611 04 Nov 11 peter 301
2360 04 Dec 10 peter 302   template<typename T, class Compare, class Value2Key>
2703 12 Mar 12 peter 303   std::pair<typename SegmentTree<T, Compare, Value2Key>::iterator, bool>
2360 04 Dec 10 peter 304   SegmentTree<T, Compare,Value2Key>::insert(const value_type& segment)
2358 02 Dec 10 peter 305   {
2358 02 Dec 10 peter 306     return container_.insert(segment);
2358 02 Dec 10 peter 307   }
2358 02 Dec 10 peter 308
2358 02 Dec 10 peter 309
2360 04 Dec 10 peter 310   template<typename T, class Compare, class Value2Key>
4024 04 Jan 21 peter 311   std::pair<typename SegmentTree<T, Compare, Value2Key>::iterator, bool>
4024 04 Jan 21 peter 312   SegmentTree<T, Compare,Value2Key>::insert(value_type&& segment)
4024 04 Jan 21 peter 313   {
4024 04 Jan 21 peter 314     return container_.insert(std::move(segment));
4024 04 Jan 21 peter 315   }
4024 04 Jan 21 peter 316
4024 04 Jan 21 peter 317
4024 04 Jan 21 peter 318   template<typename T, class Compare, class Value2Key>
2360 04 Dec 10 peter 319   typename SegmentTree<T, Compare, Value2Key>::iterator
2360 04 Dec 10 peter 320   SegmentTree<T, Compare,Value2Key>::lower_bound(const element_type& element)
2358 02 Dec 10 peter 321   {
2358 02 Dec 10 peter 322     key_type segment(element, element);
2358 02 Dec 10 peter 323     iterator result = container_.lower_bound(segment);
2358 02 Dec 10 peter 324     // result is larger or overlapping with segment (i.e.! result<segment)
2703 12 Mar 12 peter 325     YAT_ASSERT(result==end()
2360 04 Dec 10 peter 326                || !compare(Value2Key()(*result),segment));
2358 02 Dec 10 peter 327     return result;
2358 02 Dec 10 peter 328   }
2358 02 Dec 10 peter 329
2358 02 Dec 10 peter 330
2360 04 Dec 10 peter 331   template<typename T, class Compare, class Value2Key>
2360 04 Dec 10 peter 332   typename SegmentTree<T, Compare, Value2Key>::const_iterator
2360 04 Dec 10 peter 333   SegmentTree<T, Compare,Value2Key>::lower_bound(const element_type& element) const
2358 02 Dec 10 peter 334   {
2358 02 Dec 10 peter 335     key_type segment(element, element);
2358 02 Dec 10 peter 336     const_iterator result = container_.lower_bound(segment);
2358 02 Dec 10 peter 337     // result is larger or overlapping with segment (i.e.! result<segment)
2703 12 Mar 12 peter 338     YAT_ASSERT(result==end()
2360 04 Dec 10 peter 339                || !compare(Value2Key()(*result),segment));
2358 02 Dec 10 peter 340     return result;
2358 02 Dec 10 peter 341   }
2358 02 Dec 10 peter 342
2358 02 Dec 10 peter 343
2360 04 Dec 10 peter 344   template<typename T, class Compare, class Value2Key>
2360 04 Dec 10 peter 345   typename SegmentTree<T, Compare, Value2Key>::iterator
2360 04 Dec 10 peter 346   SegmentTree<T, Compare,Value2Key>::upper_bound(const element_type& element)
2358 02 Dec 10 peter 347   {
2358 02 Dec 10 peter 348     key_type segment(element, element);
2358 02 Dec 10 peter 349     iterator result = container_.upper_bound(segment);
2358 02 Dec 10 peter 350     Compare comp;
2363 05 Dec 10 peter 351     Value2Key value2key;
2363 05 Dec 10 peter 352     if (result==end() || comp(element, value2key(*result).begin()))
2358 02 Dec 10 peter 353       return result;
2358 02 Dec 10 peter 354     ++result;
2358 02 Dec 10 peter 355     // result is larger than segment
2363 05 Dec 10 peter 356     YAT_ASSERT(result==end() || compare(segment, value2key(*result)));
2358 02 Dec 10 peter 357     return result;
2358 02 Dec 10 peter 358   }
2358 02 Dec 10 peter 359
2358 02 Dec 10 peter 360
2360 04 Dec 10 peter 361   template<typename T, class Compare, class Value2Key>
2360 04 Dec 10 peter 362   typename SegmentTree<T, Compare, Value2Key>::const_iterator
2360 04 Dec 10 peter 363   SegmentTree<T, Compare,Value2Key>::upper_bound(const element_type& element) const
2358 02 Dec 10 peter 364   {
2363 05 Dec 10 peter 365     Segment<element_type, Compare> segment(element, element);
2358 02 Dec 10 peter 366     const_iterator result = container_.upper_bound(segment);
2358 02 Dec 10 peter 367     Compare comp;
2363 05 Dec 10 peter 368     Value2Key value2key;
2363 05 Dec 10 peter 369     if (result==end() || comp(element, value2key(*result).begin()))
2358 02 Dec 10 peter 370       return result;
2358 02 Dec 10 peter 371     ++result;
2358 02 Dec 10 peter 372     // result is larger than segment
2363 05 Dec 10 peter 373     YAT_ASSERT(result==end() || compare(segment, value2key(*result)));
2358 02 Dec 10 peter 374     return result;
2358 02 Dec 10 peter 375   }
2358 02 Dec 10 peter 376
2358 02 Dec 10 peter 377 }}}
2358 02 Dec 10 peter 378 #endif

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