SortedBuffer.h

#ifndef theplu_yat_utility_sorted_buffer_
#define theplu_yat_utility_sorted_buffer_

// $Id: SortedBuffer.h 4057 2021-03-31 05:46:00Z peter $

/*
  Copyright (C) 2021 Peter Johansson

  This file is part of the yat library, http://dev.thep.lu.se/yat

  The yat library is free software; you can redistribute it and/or
  modify it under the terms of the GNU General Public License as
  published by the Free Software Foundation; either version 3 of the
  License, or (at your option) any later version.

  The yat library is distributed in the hope that it will be useful,
  but WITHOUT ANY WARRANTY; without even the implied warranty of
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  General Public License for more details.

  You should have received a copy of the GNU General Public License
  along with yat. If not, see <http://www.gnu.org/licenses/>.
*/

#include <deque>
#include <memory>
#include <queue>

#include <iostream>
namespace theplu {
namespace yat {
namespace utility {

  template<typename T, typename OutputIterator,
           typename Comp = typename std::less<T>>
  class SortedBuffer
  {
  public:
    SortedBuffer(OutputIterator out)
      : out_(out) {}

    SortedBuffer(OutputIterator out, const Comp& comp)
      : out_(out), compare_(comp) {}

    virtual ~SortedBuffer(void)
    {
      flush_all();
    }


    void flush(void)
    {
      std::pop_heap(buffer_.begin(), buffer_.end(), compare_);
      *out_ = std::move(buffer_.back());
      buffer_.pop_back();
      YAT_ASSERT(buffer_.size()<2 || !compare_(buffer_[0], buffer_[1]));
    }


    void flush_all(void)
    {
      std::sort_heap(buffer_.begin(), buffer_.end(), compare_);
      std::copy(buffer_.rbegin(), buffer_.rend(), out_);
      buffer_.clear();
    }


    void flush(const T& t)
    {
      while (!buffer_.empty() && compare_(t, top()))
        flush();
    }


    void push(const T& t)
    {
      buffer_.push_back(t);
      std::push_heap(buffer_.begin(), buffer_.end(), compare_);
      YAT_ASSERT(!buffer_.empty());
      YAT_ASSERT(buffer_.size()<2 || !compare_(buffer_[0], buffer_[1]));
    }


    void push(T&& t)
    {
      buffer_.push_back(std::move(t));
      std::push_heap(buffer_.begin(), buffer_.end(), compare_);
      YAT_ASSERT(!buffer_.empty());
      YAT_ASSERT(buffer_.size()<2 || !compare_(buffer_[0], buffer_[1]));
    }


    const T& top(void) const
    {
      YAT_ASSERT(buffer_.size());
      return buffer_.front();
    }

  private:
    OutputIterator out_;

    // heap is sorted such that the greatest value is available, but
    // we want the smallest, so let's turn things upside-down.
    struct Compare
    {
      Compare(void) = default;
      Compare(const Comp& comp)
        : comp_(comp) {}
      bool operator()(const T& lhs, const T& rhs) const
      { return comp_(rhs, lhs); }
    private:
      Comp comp_;
    };

    Compare compare_;
    std::vector<T> buffer_;
  };

}}}
#endif