CLRS-Cpp-Implementations-Chapter-21

  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

namespace CLRS
{
  template <typename T> class LinkedListDisjointSet;
  template <typename T> class LinkedListDisjointSetNode;
  template <typename T>
  std::shared_ptr<LinkedListDisjointSet<T>>
  linked_list_disjoint_make_set(const std::shared_ptr
				<LinkedListDisjointSetNode<T>> &);
  template <typename T>
  void linked_list_disjoint_union(const std::shared_ptr
				  <LinkedListDisjointSetNode<T>> &,
				  const std::shared_ptr
				  <LinkedListDisjointSetNode<T>> &);
  template <typename T>
  std::shared_ptr<LinkedListDisjointSetNode<T>>
  linked_list_disjoint_find_set(const std::shared_ptr
				<LinkedListDisjointSetNode<T>> &);

  template <typename T>
  struct LinkedListDisjointSet
  {
    using LLDSN = LinkedListDisjointSetNode<T>;
    using LLDSN_SHR = std::shared_ptr<LLDSN>;
    LinkedListDisjointSet(const std::shared_ptr
			  <LLDSN> &x):
      head(x), tail(head), length(1) {}
    LLDSN_SHR get_head() const {return head;}
    void set_head(const LLDSN_SHR &p) {head = p;}
    LLDSN_SHR get_tail() const {return tail;}
    void set_tail(const LLDSN_SHR &p) {tail = p;}
    std::size_t get_length() {return length;}
    void add_length(std::size_t l) {length += l;}
  private:
    LLDSN_SHR head;
    LLDSN_SHR tail;
    std::size_t length = 0;
  };

  template <typename T>
  struct LinkedListDisjointSetNode
  {
    using LLDS = LinkedListDisjointSet<T>;
    using LLDSN = LinkedListDisjointSetNode;
    using LLDS_SHR = std::shared_ptr<LLDS>;
    using LLDSN_SHR = std::shared_ptr<LLDSN>;
    LinkedListDisjointSetNode(T x): key(x) {}
    T get_key() const {return key;}
    LLDS_SHR get_set_p() const {return set_p;}
    void set_set_p(const LLDS_SHR &p) {set_p = p;}
    LLDSN_SHR get_next() {return next;}
    void set_next(const LLDSN_SHR &n) {next = n;}
  private:
    T key;
    LLDS_SHR set_p;
    LLDSN_SHR next;
  };

  template <typename T>
  std::shared_ptr<LinkedListDisjointSet<T>>
  linked_list_disjoint_make_set(const std::shared_ptr
				<LinkedListDisjointSetNode<T>> &x)
  {
    auto set = std::make_shared<LinkedListDisjointSet<T>>(x);
    x->set_set_p(set);
    return set;
  }

  template <typename T>
  void linked_list_disjoint_union(const std::shared_ptr
				  <LinkedListDisjointSetNode<T>> &x,
				  const std::shared_ptr
				  <LinkedListDisjointSetNode<T>> &y)
  {
    auto x_set_p = x->get_set_p();
    std::size_t x_set_len = x_set_p->get_length();
    auto y_set_p = y->get_set_p();
    std::size_t y_set_len = y_set_p->get_length();
    if(x_set_len <= y_set_len)
      {
	auto x_head = x_set_p->get_head();
	auto x_tail = x_set_p->get_tail();
	// update the set_p data member of objects in linked list
	for(auto shr = x_head;
	    shr != nullptr;
	    shr = shr->get_next())
	  shr->set_set_p(y_set_p);
	auto y_tail = y_set_p->get_tail();
	y_tail->set_next(x_head);
	y_set_p->set_tail(x_tail);
	y_set_p->add_length(x_set_p->get_length());
	// clear after merge
	x_set_p->set_head(nullptr);
	x_set_p->set_tail(nullptr);
      }
    else
      {
	auto y_head = y_set_p->get_head();
	auto y_tail = y_set_p->get_tail();
	// update the set_p data member of objects in linked list
	for(auto shr = y_head;
	    shr != nullptr;
	    shr = shr->get_next())
	  shr->set_set_p(x_set_p);
	auto x_tail = x_set_p->get_tail();
	x_tail->set_next(y_head);
	x_set_p->set_tail(y_tail);
	x_set_p->add_length(y_set_p->get_length());
	// clear after merge
	y_set_p->set_head(nullptr);
	y_set_p->set_tail(nullptr);
      }
  }

  template <typename T>
  std::shared_ptr<LinkedListDisjointSetNode<T>>
  linked_list_disjoint_find_set
  (const std::shared_ptr<LinkedListDisjointSetNode<T>> &x)
  {
    return x->get_set_p()->get_head();
  }
}

 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

namespace CLRS
{
  template <typename T>
  struct TreeDisjointSetNode;
  template <typename T>
  void tree_disjoint_make_set
  (const std::shared_ptr<TreeDisjointSetNode<T>> &x);
  template <typename T>
  void tree_disjoint_union
  (const std::shared_ptr<TreeDisjointSetNode<T>> &x,
   const std::shared_ptr<TreeDisjointSetNode<T>> &y);
  template <typename T>
  void tree_disjoint_link
  (const std::shared_ptr<TreeDisjointSetNode<T>> &x,
   const std::shared_ptr<TreeDisjointSetNode<T>> &y);
  template <typename T>
  std::shared_ptr<TreeDisjointSetNode<T>>
  tree_disjoint_find_set
  (const std::shared_ptr<TreeDisjointSetNode<T>> &x);

  template <typename T>
  struct TreeDisjointSetNode
  {
    using TDSN_SHR =
      std::shared_ptr<TreeDisjointSetNode<T>>;
    TreeDisjointSetNode(T k): key(k) {}
    T get_key() const {return key;}
    TDSN_SHR get_p() const {return p;}
    void set_p(const TDSN_SHR &P) {p = P;}
    std::size_t get_rank() const {return rank;}
    void incr_rank() {++rank;}
  private:
    T key;
    TDSN_SHR p;
    std::size_t rank = 0;
  };

  template <typename T>
  void tree_disjoint_make_set
  (const std::shared_ptr<TreeDisjointSetNode<T>> &x)
  {
    x->set_p(x);
  }

  template <typename T>
  void tree_disjoint_union
  (const std::shared_ptr<TreeDisjointSetNode<T>> &x,
   const std::shared_ptr<TreeDisjointSetNode<T>> &y)
  {
    tree_disjoint_link(tree_disjoint_find_set(x),
		       tree_disjoint_find_set(y));
  }

  template <typename T>
  void tree_disjoint_link
  (const std::shared_ptr<TreeDisjointSetNode<T>> &x,
   const std::shared_ptr<TreeDisjointSetNode<T>> &y)
  {
    // union by rank
    if(x->get_rank() > y->get_rank())
      y->set_p(x);
    else
      {
	x->set_p(y);
	if(x->get_rank() == y->get_rank())
	  y->incr_rank();
      }
  }

  template <typename T>
  std::shared_ptr<TreeDisjointSetNode<T>>
  tree_disjoint_find_set
  (const std::shared_ptr<TreeDisjointSetNode<T>> &x)
  {
    if(x != x->get_p())
      // path compression
      x->set_p(tree_disjoint_find_set(x->get_p()));
    return x->get_p();
  }
}