source: trunk/yat/utility/SortedBuffer.h @ 4057

Last change on this file since 4057 was 4057, checked in by Peter, 7 months ago

closes #798; new classes BamPairBuffer? and a more general SortedBuffer?.

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