cpp-huffman-coding/HeapQueue.hpp at main · therealdaud/cpp-huffman-coding · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
#ifndef HEAPQUEUE_H
#define HEAPQUEUE_H

#include <vector>

template <typename E>
class VectorCompleteTree
{
private:
  std::vector<E> V;
public:
  typedef typename std::vector<E>::iterator Position;
protected:
  Position pos(int i)
  {
    return V.begin() + i;
  }

  int idx(const Position &p) const
  {
    return p - V.begin();
  }

public:
  VectorCompleteTree() : V(1) {}
  int size() const { return V.size() - 1; }
  Position left(const Position &p) { return pos(2 * idx(p)); }
  Position right(const Position &p) { return pos(2 * idx(p) + 1); }
  Position parent(const Position &p) { return pos(idx(p) / 2); }
  bool hasLeft(const Position &p) const { return 2 * idx(p) <= size(); }
  bool hasRight(const Position &p) const { return 2 * idx(p) + 1 <= size(); }
  bool isRoot(const Position &p) const { return idx(p) == 1; }
  Position root() { return pos(1); }
  Position last() { return pos(size()); }
  void addLast(const E &e) { V.push_back(e); }
  void removeLast() { V.pop_back(); }
  void swap(const Position &p, const Position &q)
  {
    E e = *q;
    *q = *p;
    *p = e;
  }
};

template <typename E, typename C>
class HeapQueue
{
public:
  int size() const;
  bool empty() const;
  void insert(const E &e);
  const E &min();
  void removeMin();

private:
  VectorCompleteTree<E> T;
  C isLess;

  typedef typename VectorCompleteTree<E>::Position Position;
};

template <typename E, typename C>
int HeapQueue<E, C>::size() const
{
  return T.size();
}

template <typename E, typename C>
bool HeapQueue<E, C>::empty() const
{
  return size() == 0;
}

template <typename E, typename C>
const E &HeapQueue<E, C>::min()
{
  return *(T.root());
}

template <typename E, typename C>
void HeapQueue<E, C>::removeMin()
{
  if (size() == 1)
  {
    T.removeLast();
  }
  else
  {
    Position u = T.root();
    T.swap(u, T.last());
    T.removeLast();

    while (T.hasLeft(u))
    {
      Position v = T.left(u);
      if (T.hasRight(u) && isLess(*(T.right(u)), *v))
      {
        v = T.right(u);
      }
      if (isLess(*v, *u))
      {
        T.swap(u, v);
        u = v;
      }
      else
      {
        break;
      }
    }
  }
}

template <typename E, typename C>
void HeapQueue<E, C>::insert(const E &e)
{
  T.addLast(e);
  Position v = T.last();
  while (!T.isRoot(v))
  {
    Position u = T.parent(v);
    if (!isLess(*v, *u))
      break;
    T.swap(v, u);
    v = u;
  }
}

#endif