Grok  9.7.5
MinHeap.h
Go to the documentation of this file.
1 #pragma once
2 
3 #include <mutex>
4 #include <queue>
5 
6 namespace grk
7 {
9 {
10  public:
11  MinHeapLocker(std::mutex& mut) : lock(mut) {}
12 
13  private:
14  std::lock_guard<std::mutex> lock;
15 };
16 
18 {
19  public:
20  MinHeapFakeLocker(std::mutex& mut)
21  {
22  GRK_UNUSED(mut);
23  }
24 };
25 
26 template<typename T>
28 {
29  bool operator()(const T a, const T b) const
30  {
31  return a.getIndex() > b.getIndex();
32  }
33 };
34 
35 template<typename T, typename IT, typename L>
36 class MinHeap
37 {
38  public:
39  MinHeap() : nextIndex(0) {}
40  void push(T val)
41  {
42  L locker(queue_mutex);
43  queue.push(val);
44  }
45  T pop(void)
46  {
47  L locker(queue_mutex);
48  if(queue.empty())
49  return T();
50  auto val = queue.top();
51  if(val.getIndex() == nextIndex)
52  {
53  queue.pop();
54  nextIndex++;
55  return val;
56  }
57  return T();
58  }
59  size_t size(void)
60  {
61  return queue.size();
62  }
63 
64  private:
65  std::priority_queue<T, std::vector<T>, MinHeapComparator<T>> queue;
66  std::mutex queue_mutex;
68 };
69 
70 template<typename T>
72 {
73  bool operator()(const T* a, const T* b) const
74  {
75  return a->getIndex() > b->getIndex();
76  }
77 };
78 
79 template<typename T, typename IT, typename L>
81 {
82  public:
84  void push(T* val)
85  {
86  L locker(queue_mutex);
87  queue.push(val);
88  }
89  T* pop(void)
90  {
91  L locker(queue_mutex);
92  if(queue.empty())
93  return nullptr;
94  auto val = queue.top();
95  if(val->getIndex() == nextIndex)
96  {
97  queue.pop();
98  nextIndex++;
99  return val;
100  }
101  return nullptr;
102  }
103  size_t size(void)
104  {
105  return queue.size();
106  }
107 
108  private:
109  std::priority_queue<T*, std::vector<T*>, MinHeapPtrComparator<T>> queue;
110  std::mutex queue_mutex;
112 };
113 
114 } // namespace grk
Definition: MinHeap.h:18
MinHeapFakeLocker(std::mutex &mut)
Definition: MinHeap.h:20
Definition: MinHeap.h:37
std::mutex queue_mutex
Definition: MinHeap.h:66
std::priority_queue< T, std::vector< T >, MinHeapComparator< T > > queue
Definition: MinHeap.h:65
IT nextIndex
Definition: MinHeap.h:67
T pop(void)
Definition: MinHeap.h:45
size_t size(void)
Definition: MinHeap.h:59
MinHeap()
Definition: MinHeap.h:39
void push(T val)
Definition: MinHeap.h:40
Definition: MinHeap.h:9
MinHeapLocker(std::mutex &mut)
Definition: MinHeap.h:11
std::lock_guard< std::mutex > lock
Definition: MinHeap.h:14
Definition: MinHeap.h:81
MinHeapPtr()
Definition: MinHeap.h:83
std::priority_queue< T *, std::vector< T * >, MinHeapPtrComparator< T > > queue
Definition: MinHeap.h:109
void push(T *val)
Definition: MinHeap.h:84
std::mutex queue_mutex
Definition: MinHeap.h:110
IT nextIndex
Definition: MinHeap.h:111
T * pop(void)
Definition: MinHeap.h:89
size_t size(void)
Definition: MinHeap.h:103
#define GRK_UNUSED(x)
Definition: grk_includes.h:87
Copyright (C) 2016-2022 Grok Image Compression Inc.
Definition: ICacheable.h:20
Definition: MinHeap.h:28
bool operator()(const T a, const T b) const
Definition: MinHeap.h:29
Definition: MinHeap.h:72
bool operator()(const T *a, const T *b) const
Definition: MinHeap.h:73