yat/utility/SortedBuffer.h

Code
Comments
Other
Rev Date Author Line
4057 31 Mar 21 peter 1 #ifndef theplu_yat_utility_sorted_buffer_
4057 31 Mar 21 peter 2 #define theplu_yat_utility_sorted_buffer_
4057 31 Mar 21 peter 3
4057 31 Mar 21 peter 4 // $Id$
4057 31 Mar 21 peter 5
4057 31 Mar 21 peter 6 /*
4057 31 Mar 21 peter 7   Copyright (C) 2021 Peter Johansson
4057 31 Mar 21 peter 8
4057 31 Mar 21 peter 9   This file is part of the yat library, http://dev.thep.lu.se/yat
4057 31 Mar 21 peter 10
4057 31 Mar 21 peter 11   The yat library is free software; you can redistribute it and/or
4057 31 Mar 21 peter 12   modify it under the terms of the GNU General Public License as
4057 31 Mar 21 peter 13   published by the Free Software Foundation; either version 3 of the
4057 31 Mar 21 peter 14   License, or (at your option) any later version.
4057 31 Mar 21 peter 15
4057 31 Mar 21 peter 16   The yat library is distributed in the hope that it will be useful,
4057 31 Mar 21 peter 17   but WITHOUT ANY WARRANTY; without even the implied warranty of
4057 31 Mar 21 peter 18   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
4057 31 Mar 21 peter 19   General Public License for more details.
4057 31 Mar 21 peter 20
4057 31 Mar 21 peter 21   You should have received a copy of the GNU General Public License
4057 31 Mar 21 peter 22   along with yat. If not, see <http://www.gnu.org/licenses/>.
4057 31 Mar 21 peter 23 */
4057 31 Mar 21 peter 24
4057 31 Mar 21 peter 25 #include <deque>
4057 31 Mar 21 peter 26 #include <memory>
4057 31 Mar 21 peter 27 #include <queue>
4057 31 Mar 21 peter 28
4057 31 Mar 21 peter 29 #include <iostream>
4057 31 Mar 21 peter 30 namespace theplu {
4057 31 Mar 21 peter 31 namespace yat {
4057 31 Mar 21 peter 32 namespace utility {
4057 31 Mar 21 peter 33
4057 31 Mar 21 peter 34   /**
4057 31 Mar 21 peter 35      SortedBuffer is similar to a priority queue. Elements are pushed
4057 31 Mar 21 peter 36      into the container and flushed to an output iterator in a sorted
4057 31 Mar 21 peter 37      manner. Ny default elements are sorted using std::less such that
4057 31 Mar 21 peter 38      the smallest element is flushed first, but this can be modified
4057 31 Mar 21 peter 39      using a different functor.
4057 31 Mar 21 peter 40
4057 31 Mar 21 peter 41      \since new in yat 0.19
4057 31 Mar 21 peter 42    */
4057 31 Mar 21 peter 43   template<typename T, typename OutputIterator,
4057 31 Mar 21 peter 44            typename Comp = typename std::less<T>>
4057 31 Mar 21 peter 45   class SortedBuffer
4057 31 Mar 21 peter 46   {
4057 31 Mar 21 peter 47   public:
4057 31 Mar 21 peter 48     /**
4057 31 Mar 21 peter 49        \param out iterator that elements are copied to
4057 31 Mar 21 peter 50      */
4057 31 Mar 21 peter 51     SortedBuffer(OutputIterator out)
4057 31 Mar 21 peter 52       : out_(out) {}
4057 31 Mar 21 peter 53
4057 31 Mar 21 peter 54     /**
4057 31 Mar 21 peter 55        \param out Iterator that elements are copied to
4057 31 Mar 21 peter 56        \param comp Comparator used to sort elements
4057 31 Mar 21 peter 57      */
4057 31 Mar 21 peter 58     SortedBuffer(OutputIterator out, const Comp& comp)
4057 31 Mar 21 peter 59       : out_(out), compare_(comp) {}
4057 31 Mar 21 peter 60
4057 31 Mar 21 peter 61     /**
4057 31 Mar 21 peter 62        \brief Destructor
4057 31 Mar 21 peter 63
4057 31 Mar 21 peter 64        Flush all elements to output iterator
4057 31 Mar 21 peter 65      */
4057 31 Mar 21 peter 66     virtual ~SortedBuffer(void)
4057 31 Mar 21 peter 67     {
4057 31 Mar 21 peter 68       flush_all();
4057 31 Mar 21 peter 69     }
4057 31 Mar 21 peter 70
4057 31 Mar 21 peter 71
4057 31 Mar 21 peter 72     /**
4057 31 Mar 21 peter 73        Flush one element to output iterator
4057 31 Mar 21 peter 74      */
4057 31 Mar 21 peter 75     void flush(void)
4057 31 Mar 21 peter 76     {
4057 31 Mar 21 peter 77       std::pop_heap(buffer_.begin(), buffer_.end(), compare_);
4057 31 Mar 21 peter 78       *out_ = std::move(buffer_.back());
4057 31 Mar 21 peter 79       buffer_.pop_back();
4057 31 Mar 21 peter 80       YAT_ASSERT(buffer_.size()<2 || !compare_(buffer_[0], buffer_[1]));
4057 31 Mar 21 peter 81     }
4057 31 Mar 21 peter 82
4057 31 Mar 21 peter 83
4057 31 Mar 21 peter 84     /**
4057 31 Mar 21 peter 85        Copy elements in a sorted fashion to the output iterator.
4057 31 Mar 21 peter 86      */
4057 31 Mar 21 peter 87     void flush_all(void)
4057 31 Mar 21 peter 88     {
4057 31 Mar 21 peter 89       std::sort_heap(buffer_.begin(), buffer_.end(), compare_);
4057 31 Mar 21 peter 90       std::copy(buffer_.rbegin(), buffer_.rend(), out_);
4057 31 Mar 21 peter 91       buffer_.clear();
4057 31 Mar 21 peter 92     }
4057 31 Mar 21 peter 93
4057 31 Mar 21 peter 94
4057 31 Mar 21 peter 95     /**
4057 31 Mar 21 peter 96        Flush all elements that are less than \c t.
4057 31 Mar 21 peter 97      */
4057 31 Mar 21 peter 98     void flush(const T& t)
4057 31 Mar 21 peter 99     {
4057 31 Mar 21 peter 100       while (!buffer_.empty() && compare_(t, top()))
4057 31 Mar 21 peter 101         flush();
4057 31 Mar 21 peter 102     }
4057 31 Mar 21 peter 103
4057 31 Mar 21 peter 104
4057 31 Mar 21 peter 105     /**
4057 31 Mar 21 peter 106        Insert an element to the buffer
4057 31 Mar 21 peter 107      */
4057 31 Mar 21 peter 108     void push(const T& t)
4057 31 Mar 21 peter 109     {
4057 31 Mar 21 peter 110       buffer_.push_back(t);
4057 31 Mar 21 peter 111       std::push_heap(buffer_.begin(), buffer_.end(), compare_);
4057 31 Mar 21 peter 112       YAT_ASSERT(!buffer_.empty());
4057 31 Mar 21 peter 113       YAT_ASSERT(buffer_.size()<2 || !compare_(buffer_[0], buffer_[1]));
4057 31 Mar 21 peter 114     }
4057 31 Mar 21 peter 115
4057 31 Mar 21 peter 116
4057 31 Mar 21 peter 117     /**
4057 31 Mar 21 peter 118        Move an element into the buffer
4057 31 Mar 21 peter 119      */
4057 31 Mar 21 peter 120     void push(T&& t)
4057 31 Mar 21 peter 121     {
4057 31 Mar 21 peter 122       buffer_.push_back(std::move(t));
4057 31 Mar 21 peter 123       std::push_heap(buffer_.begin(), buffer_.end(), compare_);
4057 31 Mar 21 peter 124       YAT_ASSERT(!buffer_.empty());
4057 31 Mar 21 peter 125       YAT_ASSERT(buffer_.size()<2 || !compare_(buffer_[0], buffer_[1]));
4057 31 Mar 21 peter 126     }
4057 31 Mar 21 peter 127
4057 31 Mar 21 peter 128
4057 31 Mar 21 peter 129     /**
4057 31 Mar 21 peter 130        \return the smallest element
4057 31 Mar 21 peter 131      */
4057 31 Mar 21 peter 132     const T& top(void) const
4057 31 Mar 21 peter 133     {
4057 31 Mar 21 peter 134       YAT_ASSERT(buffer_.size());
4057 31 Mar 21 peter 135       return buffer_.front();
4057 31 Mar 21 peter 136     }
4057 31 Mar 21 peter 137
4057 31 Mar 21 peter 138   private:
4057 31 Mar 21 peter 139     OutputIterator out_;
4057 31 Mar 21 peter 140
4057 31 Mar 21 peter 141     // heap is sorted such that the greatest value is available, but
4057 31 Mar 21 peter 142     // we want the smallest, so let's turn things upside-down.
4057 31 Mar 21 peter 143     struct Compare
4057 31 Mar 21 peter 144     {
4057 31 Mar 21 peter 145       Compare(void) = default;
4057 31 Mar 21 peter 146       Compare(const Comp& comp)
4057 31 Mar 21 peter 147         : comp_(comp) {}
4057 31 Mar 21 peter 148       bool operator()(const T& lhs, const T& rhs) const
4057 31 Mar 21 peter 149       { return comp_(rhs, lhs); }
4057 31 Mar 21 peter 150     private:
4057 31 Mar 21 peter 151       Comp comp_;
4057 31 Mar 21 peter 152     };
4057 31 Mar 21 peter 153
4057 31 Mar 21 peter 154     Compare compare_;
4057 31 Mar 21 peter 155     std::vector<T> buffer_;
4057 31 Mar 21 peter 156   };
4057 31 Mar 21 peter 157
4057 31 Mar 21 peter 158 }}}
4057 31 Mar 21 peter 159 #endif

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