greedy_activity_selector

 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

namespace CLRS
{
  template <std::size_t j>
  void recursive_activity_selector(unsigned (&s)[j],
				   unsigned (&f)[j],
				   unsigned k,
				   unsigned n,
				   std::vector<unsigned> &r)
  {
  std:size_t m = k + 1;
    while(m <= n && s[m] < f[k])
      ++m;
    if(m <= n)
      {
	r.push_back(m);
	recursive_activity_selector(s, f, m, n, r);
      }
  }

  template <std::size_t n>
  std::vector<unsigned> greedy_activity_selector(unsigned (&s)[n],
						 unsigned (&f)[n])
  {
    std::size_t length = n - 1;
    std::vector<unsigned> a = {1};
    std::size_t k = 1;
    for(std::size_t m = 2; m <= length; ++m)
      {
	if(s[m] >= f[k])
	  {
	    a.push_back(m);
	    k = m;
	  }
      }
    return a;
  }
}

huffman

 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

#include "chapter-6/build_max_min_heap/build_max_min_heap.h"
#include "chapter-6/heap_priority_queue/heap_priority_queue.h"
namespace CLRS
{
  template <typename T>
  class HuffmanCodingNode
  {
    char c;
    T freq;
    std::shared_ptr<HuffmanCodingNode> left;
    std::shared_ptr<HuffmanCodingNode> right;
    bool leaf = true;
  public:
    HuffmanCodingNode(const char &x, const T &f):
      c(x), freq(f) {}
    HuffmanCodingNode(): leaf(false) {}
    T get_freq() const {return freq;}
    char get_char() const {return c;}
    std::shared_ptr<HuffmanCodingNode> get_left() const {return left;}
    std::shared_ptr<HuffmanCodingNode> get_right() const {return right;}
    void set_left(const std::shared_ptr<HuffmanCodingNode> &l) {left = l;}
    void set_right(const std::shared_ptr<HuffmanCodingNode> &r) {right = r;}
    void set_freq(T f) {freq = f;};
  };

  template <typename T>
  bool operator<(const std::shared_ptr<HuffmanCodingNode<T>> &h1,
		 const std::shared_ptr<HuffmanCodingNode<T>> &h2)
  {return h1->get_freq() < h2->get_freq();}

  template <typename T>
  bool operator>(const std::shared_ptr<HuffmanCodingNode<T>> &h1,
		 const std::shared_ptr<HuffmanCodingNode<T>> &h2)
  {return h1->get_freq() > h2->get_freq();}

  template <typename T>
  HuffmanCodingNode<T> huffman(std::vector
			       <std::shared_ptr<HuffmanCodingNode<T>>> &c)
  {
    std::size_t n = c.size();
    build_min_heap(c);
    for(std::size_t i = 1; i != n; ++i)
      {
	auto z = std::make_shared<HuffmanCodingNode<T>>();
	auto x = heap_extract_min(c);
	auto y = heap_extract_min(c);
	z->set_left(x);
	z->set_right(y);
	z->set_freq(x->get_freq() + y->get_freq());
	min_heap_insert(c, z);
      }
    return *heap_extract_min(c);
  }

  template <typename T, std::size_t n>
  char huffman_decode(const std::bitset<n> &b, const HuffmanCodingNode<T> &q)
  {
    HuffmanCodingNode<T> node = q;
    for(long long i = n - 1; i >= 0; --i)
      {
	bool direction = b[i];
	// direction 0: left, 1: right;
	if(!direction)
	  node = *node.get_left();
	else
	  node = *node.get_right();
      }
    return node.get_char();
  }
}