Doxygen Generated Documentation of Ben-Jose Trainable SAT Solver Library
mem_redblack.h
1 
2 
3 /*************************************************************
4 
5 This file is part of ben-jose.
6 
7 ben-jose is free software: you can redistribute it and/or modify
8 it under the terms of the version 3 of the GNU General Public
9 License as published by the Free Software Foundation.
10 
11 ben-jose is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
15 
16 You should have received a copy of the GNU General Public License
17 along with ben-jose. If not, see <http://www.gnu.org/licenses/>.
18 
19 ------------------------------------------------------------
20 
21 Copyright (C) 2007-2012, 2014-2016. QUIROGA BELTRAN, Jose Luis.
22 Id (cedula): 79523732 de Bogota - Colombia.
23 See https://github.com/joseluisquiroga/ben-jose
24 
25 ben-jose is free software thanks to The Glory of Our Lord
26  Yashua Melej Hamashiaj.
27 Our Resurrected and Living, both in Body and Spirit,
28  Prince of Peace.
29 
30 ------------------------------------------------------------
31 
32 mem_redblack.h
33 
34 Red-black trees with mem templates.
35 
36 --------------------------------------------------------------*/
37 
38 
39 #ifndef MEM_REDBLACK_H
40 #define MEM_REDBLACK_H
41 
42 #include "tools.h"
43 #include "redblack.h"
44 
45 template<class obj_t>
46 class rbt_mem_node {
47 public:
48  obj_t obj;
49  rbt_mem_node* left;
50  rbt_mem_node* right;
51  rbt_mem_node* parent;
52  rbt_color_t color;
53 
54  rbt_mem_node(){
55  init_rbt_mem_node();
56  }
57  ~rbt_mem_node(){
58  init_rbt_mem_node();
59  //obj.~obj_t();
60  }
61  void init_rbt_mem_node(){
62  left = NULL_PT;
63  right = NULL_PT;
64  parent = NULL_PT;
65  color = k_invalid_color;
66  }
67 
68  bj_ostream& print(bj_ostream& os){
69  os << obj;
70  return os;
71  }
72 
73  friend bj_ostream& operator << (bj_ostream& os, rbt_mem_node& nod){
74  nod.print(os);
75  return os;
76  }
77 };
78 
79 template<class obj_t>
80 class rbt_mem_node_handler {
81 public:
82  typedef obj_t rbt_obj_t;
83  typedef rbt_mem_node<rbt_obj_t> rbt_node_t;
84  typedef rbt_node_t* rbt_nod_ref_t;
85 
86  typedef comparison (*cmp_func_t)(obj_t const & obj1, obj_t const & obj2);
87 
88  cmp_func_t cmp_func;
89 
90  rbt_mem_node_handler(cmp_func_t cmp_fn) : cmp_func(cmp_fn){
91  REDBLACK_CK(cmp_fn != NULL_PT);
92  }
93 
94  ~rbt_mem_node_handler(){
95  cmp_func = NULL_PT;
96  REDBLACK_CK(cmp_func == NULL_PT);
97  }
98 
99  // Don't allow copying (error prone):
100  // force use of referenced objs
101 
102  rbt_mem_node_handler& operator = (
103  rbt_mem_node_handler& other)
104  {
105  RBT_OBJECT_COPY_ERROR;
106  }
107 
108  rbt_mem_node_handler(rbt_mem_node_handler& other){
109  RBT_OBJECT_COPY_ERROR;
110  }
111 
112  rbt_nod_ref_t create_node(rbt_obj_t const & obj1){
113  rbt_nod_ref_t nd = tpl_malloc<rbt_node_t>();
114  new (nd) rbt_node_t();
115  nd->obj = obj1;
116  return nd;
117  }
118 
119  void destroy_all_nodes(redblack<rbt_mem_node_handler<obj_t> >& rbt);
120 
121  comparison compare_node_objects(rbt_obj_t const & obj1, rbt_obj_t const & obj2){
122  REDBLACK_CK(cmp_func != NULL_PT);
123  comparison cc_val = (*cmp_func)(obj1, obj2);
124  return cc_val;
125  }
126  rbt_nod_ref_t get_null_node_reference(){
127  return NULL_PT;
128  }
129  rbt_nod_ref_t& get_right_node_reference_of(rbt_nod_ref_t const & nd){
130  REDBLACK_CK(nd != NULL_PT);
131  return nd->right;
132  }
133  rbt_nod_ref_t& get_left_node_reference_of(rbt_nod_ref_t const & nd){
134  REDBLACK_CK(nd != NULL_PT);
135  return nd->left;
136  }
137  rbt_nod_ref_t& get_parent_node_reference_of(rbt_nod_ref_t const & nd){
138  REDBLACK_CK(nd != NULL_PT);
139  return nd->parent;
140  }
141  rbt_obj_t& get_object_of(rbt_nod_ref_t const & nd){
142  REDBLACK_CK(nd != NULL_PT);
143  return nd->obj;
144  }
145  rbt_color_t get_color_of(rbt_nod_ref_t const & nd){
146  REDBLACK_CK(nd != NULL_PT);
147  return nd->color;
148  }
149  void set_color_of(rbt_nod_ref_t const & nd, rbt_color_t col){
150  REDBLACK_CK(nd != NULL_PT);
151  nd->color = col;
152  }
153 
154  void free_node(redblack<rbt_mem_node_handler<obj_t> >& rbt,
155  rbt_nod_ref_t nd)
156  {
157  REDBLACK_CK(nd != NULL_PT);
158  REDBLACK_CK(rbt.is_alone(nd));
159  nd->~rbt_node_t();
160  tpl_free<rbt_node_t>(nd);
161  }
162 };
163 
164 template<class obj_t>
165 void
166 rbt_mem_node_handler<obj_t>::destroy_all_nodes(redblack<rbt_mem_node_handler<obj_t> >& rbt){
167  while(! rbt.is_empty()){
168  rbt_nod_ref_t mm = rbt.get_min();
169  REDBLACK_CK(mm != NULL_PT);
170  rbt_nod_ref_t nd = rbt.rbt_remove(mm);
171  free_node(rbt, nd);
172  }
173 }
174 
175 template<class obj_t>
176 class mem_redblack : public redblack<rbt_mem_node_handler<obj_t> > {
177 public:
178  typedef typename rbt_mem_node_handler<obj_t>::rbt_nod_ref_t rbt_nod_ref_t;
179  typedef typename rbt_mem_node_handler<obj_t>::rbt_node_t rbt_node_t;
180  //typedef typename rbt_mem_node_handler<obj_t>::rbt_obj_t rbt_obj_t;
181 
182  rbt_mem_node_handler<obj_t> node_hdlr;
183 
184  typedef redblack<rbt_mem_node_handler<obj_t> > rbt_sup_t;
185  typedef redblack_iter<rbt_mem_node_handler<obj_t> > rbt_iter_t;
186  typedef comparison (*cmp_func_t)(obj_t const & obj1, obj_t const & obj2);
187 
188  mem_redblack(cmp_func_t cmp_fn) : redblack<rbt_mem_node_handler<obj_t> >(node_hdlr),
189  node_hdlr(cmp_fn)
190  {}
191 
192  ~mem_redblack(){
193  // MUST DO THIS so order destruction does not leave cmp in mgr in NULL
194  rbt_sup_t::clear_redblack();
195  }
196 
197  // Don't allow copying (error prone):
198  // force use of referenced objs
199 
200  mem_redblack& operator = (mem_redblack& other)
201  {
202  RBT_OBJECT_COPY_ERROR;
203  }
204 
205  mem_redblack(mem_redblack& other){
206  RBT_OBJECT_COPY_ERROR;
207  }
208 
209  bool push(obj_t obj){
210  bool p_ok = (rbt_insert(obj) != rbt_sup_t::get_null());
211  return p_ok;
212  }
213 
214  bool pop(obj_t obj){
215  rbt_nod_ref_t ref_obj = search(obj);
216  if(ref_obj == rbt_sup_t::get_null()){
217  return false;
218  }
219  cmp_func_t cmp_fn = node_hdlr.cmp_func;
220  MARK_USED(cmp_fn);
221 
222  REDBLACK_CK(cmp_fn(get_obj(ref_obj), obj) == 0);
223  rbt_nod_ref_t ref_pop = rbt_remove(ref_obj);
224 
225  REDBLACK_CK(ref_pop != rbt_sup_t::get_null());
226  node_hdlr.free_node(*this, ref_pop);
227 
228  SLOW_REDBLACK_CK(check_min_max());
229  return true;
230  }
231 
232  bj_ostream& print_row(bj_ostream& os){
233  rbt_iter_t iter1(*this);
234  iter1.go_first_ref();
235  os << "[";
236  while(! iter1.in_null()){
237  os << iter1.get_obj() << " ";
238  iter1++;
239  }
240  os << "]";
241  return os;
242  }
243 
244  bj_ostream& print_tree(bj_ostream& os){
245  return rbt_sup_t::print(os);
246  }
247 
248  friend
249  bj_ostream& operator << (bj_ostream& os, mem_redblack& rbt){
250  rbt.print_row(os);
251  return os;
252  }
253 
254  friend
255  cmp_is_sub cmp_mem_redblack(mem_redblack<obj_t>& rbt1, mem_redblack<obj_t>& rbt2,
256  bool& are_eq)
257  {
258  rbt_iter_t iter1(rbt1);
259  rbt_iter_t iter2(rbt2);
260  cmp_func_t cmp_fn = rbt1.node_hdlr.cmp_func;
261  REDBLACK_CK(cmp_fn == rbt2.node_hdlr.cmp_func);
262 
263  return is_subset_cmp<obj_t, rbt_iter_t>(iter1,
264  iter2, cmp_fn, are_eq);
265  }
266 
267 };
268 
269 
270 #endif // MEM_REDBLACK_H
271 
Generated on Fri Jun 16 2017 16:56:09 for Doxygen-Documentation by   doxygen 1.8.11