MinHeap.h

Go to the documentation of this file.

/*
 *    Copyright (C) 2016-2026 Grok Image Compression Inc.
 *
 *    This source code is free software: you can redistribute it and/or  modify
 *    it under the terms of the GNU Affero General Public License, version 3,
 *    as published by the Free Software Foundation.
 *
 *    This source code 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 Affero General Public License for more details.
 *
 *    You should have received a copy of the GNU Affero General Public License
 *    along with this program.  If not, see <http://www.gnu.org/licenses/>.
 *
 */
 
#pragma once
 
#include <mutex>
#include <queue>
#include <vector>
#include <concepts>
#include <optional>
 
namespace grk
{

template<typename T>
class SimpleHeap
{
public:
  void push(T index)
  {
    queue.push(index);
  }

  std::optional<T> push_and_pop(T index)
  {
    queue.push(index);
 
    // While the top of the heap matches the expected next index, pop it and extend the sequence
    while(!queue.empty() && queue.top() == start)
    {
      queue.pop();
      start++;
    }
 
    // Return the greatest index in the contiguous sequence
    // If start is still 0, no sequence has been established
    return start > 0 ? std::optional<T>(start - 1) : std::nullopt;
  }

  size_t size() const
  {
    return queue.size();
  }
 
private:
  std::priority_queue<T, std::vector<T>, std::greater<T>> queue; 
  T start = 0; 
};

class MinHeapLocker
{
public:
  explicit MinHeapLocker(std::mutex& mut) : lock(mut) {}
 
private:
  std::lock_guard<std::mutex> lock;
};

class MinHeapFakeLocker
{
public:
  explicit MinHeapFakeLocker([[maybe_unused]] std::mutex& mut) {}
};

template<typename T>
concept HasGetIndex = requires(T t) {
  { t.getIndex() } -> std::integral;
};

template<typename T>
  requires HasGetIndex<T>
struct MinHeapComparator
{
  bool operator()(const T& a, const T& b) const
  {
    return a.getIndex() > b.getIndex();
  }
};

template<typename IT>
class MinHeapBase
{
protected:
  MinHeapBase() : start(0) {}
  mutable std::mutex queue_mutex; 
  IT start; 
};

template<typename T, typename IT, typename L>
  requires HasGetIndex<T> && std::integral<IT>
class MinHeap : protected MinHeapBase<IT>
{
public:
  using MinHeapBase<IT>::queue_mutex;
  using MinHeapBase<IT>::start;

  void push(const T& val)
  {
    L locker(queue_mutex);
    queue.push(val);
  }

  std::vector<T> push_and_pop(const T& val)
  {
    L locker(queue_mutex);
    queue.push(val);
    std::vector<T> inSequence;
    while(!queue.empty() && queue.top().getIndex() == start)
    {
      inSequence.push_back(queue.top());
      queue.pop();
      start++;
    }
    return inSequence;
  }

  size_t size() const
  {
    std::lock_guard<std::mutex> locker(queue_mutex);
    return queue.size();
  }
 
private:
  std::priority_queue<T, std::vector<T>, MinHeapComparator<T>> queue; 
};

template<typename T>
  requires HasGetIndex<T>
struct MinHeapPtrComparator
{
  bool operator()(const T* a, const T* b) const
  {
    return a->getIndex() > b->getIndex();
  }
};

template<typename T, typename IT, typename L>
  requires HasGetIndex<T> && std::integral<IT>
class MinHeapPtr : protected MinHeapBase<IT>
{
public:
  using MinHeapBase<IT>::queue_mutex;
  using MinHeapBase<IT>::start;

  void push(T* val)
  {
    L locker(queue_mutex);
    queue.push(val);
  }

  std::vector<T*> pop(T* val)
  {
    L locker(queue_mutex);
    if(val)
      queue.push(val);
    std::vector<T*> inSequence;
    while(!queue.empty() && queue.top()->getIndex() == start)
    {
      inSequence.push_back(queue.top());
      queue.pop();
      start++;
    }
    return inSequence;
  }

  size_t size() const
  {
    std::lock_guard<std::mutex> locker(queue_mutex);
    return queue.size();
  }
 
private:
  std::priority_queue<T*, std::vector<T*>, MinHeapPtrComparator<T>> queue; 
};
 
} // namespace grk