cde/programs/dtinfo/DtMmdb/dstr/bset.C

   1 /*
   2  * CDE - Common Desktop Environment
   3  *
   4  * Copyright (c) 1993-2012, The Open Group. All rights reserved.
   5  *
   6  * These libraries and programs are free software; you can
   7  * redistribute them and/or modify them under the terms of the GNU
   8  * Lesser General Public License as published by the Free Software
   9  * Foundation; either version 2 of the License, or (at your option)
  10  * any later version.
  11  *
  12  * These libraries and programs are distributed in the hope that
  13  * they will be useful, but WITHOUT ANY WARRANTY; without even the
  14  * implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
  15  * PURPOSE. See the GNU Lesser General Public License for more
  16  * details.
  17  *
  18  * You should have received a copy of the GNU Lesser General Public
  19  * License along with these librararies and programs; if not, write
  20  * to the Free Software Foundation, Inc., 51 Franklin Street, Fifth
  21  * Floor, Boston, MA 02110-1301 USA
  22  */
  23 /*
  24  * $XConsortium: bset.cc /main/5 1996/07/18 14:28:37 drk $
  25  *
  26  * Copyv_right (c) 1993 HAL Computer Systems International, Ltd.
  27  * All v_rights reserved.  Unpublished -- v_rights reserved under
  28  * the Copyv_right Laws of the United States.  USE OF A COPYRIGHT
  29  * NOTICE IS PRECAUTIONARY ONLY AND DOES NOT IMPLY PUBLICATION
  30  * OR DISCLOSURE.
  31  *
  32  * THIS SOFTWARE CONTAINS CONFIDENTIAL INFORMATION AND TRADE
  33  * SECRETS OF HAL COMPUTER SYSTEMS INTERNATIONAL, LTD.  USE,
  34  * DISCLOSURE, OR REPRODUCTION IS PROHIBITED WITHOUT THE
  35  * PRIOR EXPRESS WRITTEN PERMISSION OF HAL COMPUTER SYSTEMS
  36  * INTERNATIONAL, LTD.
  37  *
  38  *                         RESTRICTED RIGHTS LEGEND
  39  * Use, duplication, or disclosure by the Government is subject
  40  * to the restrictions as set forth in subparagraph (c)(l)(ii)
  41  * of the Rights in Technical Data and Computer Software clause
  42  * at DFARS 252.227-7013.
  43  *
  44  *          HAL COMPUTER SYSTEMS INTERNATIONAL, LTD.
  45  *                  1315 Dell Avenue
  46  *                  Campbell, CA  95008
  47  *
  48  */
  49
  50
  51 #include  "dstr/bset.h"
  52
  53 Boolean void_ls(const void* o1, const void* o2)
  54 {
  55    return (long(o1) < long(o2) ) ? true : false;
  56 }
  57
  58 Boolean void_eq(const void* o1, const void* o2)
  59 {
  60    return (long(o1) == long(o2) ) ? true : false;
  61 }
  62
  63 //**************************************************************
  64 //
  65 // a set implemented based on binary search tree data structure.
  66 //
  67 //**************************************************************
  68
  69
  70 bset::bset(cmp_func_ptr_t eq, cmp_func_ptr_t ls): v_setroot(0), set(eq, ls)
  71 {
  72    //assert ( eq && ls );
  73 }
  74
  75 bset::~bset()
  76 {
  77    delete v_setroot;
  78 }
  79
  80 Boolean bset::_insert(void* x, bsetnode *rt)
  81 {
  82 /*
  83 debug(cerr, "in bsert _insert");
  84 debug(cerr, int(x));
  85 debug(cerr, int(rt));
  86 */
  87
  88 /*
  89 debug(cerr, int(f_cmp_func_eq));
  90 debug(cerr, int(f_cmp_func_ls));
  91 */
  92
  93    if ( (*f_cmp_func_eq)(x, rt -> v_element) == true )
  94       return false;
  95
  96    if ( (*f_cmp_func_ls)(x, rt -> v_element) == true )
  97       if ( rt -> v_left == 0 ) {
  98          rt -> v_left = new bsetnode(x);
  99          return true;
 100       } else
 101          return _insert(x, rt -> v_left);
 102    else
 103       if ( rt -> v_right == 0 ) {
 104          rt -> v_right = new bsetnode(x);
 105          return true;
 106       } else
 107          return _insert(x, rt -> v_right);
 108 }
 109
 110 Boolean bset::insert(void* x)
 111 {
 112 /*
 113 debug(cerr, "in bsert insert");
 114 debug(cerr, int(f_cmp_func_eq));
 115 debug(cerr, int(f_cmp_func_ls));
 116 debug(cerr, int(this));
 117 debug(cerr, int(x));
 118 debug(cerr, int(v_setroot));
 119 */
 120
 121    if ( v_setroot == 0 ) {
 122      v_setroot = new bsetnode(x);
 123      return true;
 124    } else {
 125
 126 //debug(cerr, "to bsert _insert");
 127
 128      return _insert(x, v_setroot);
 129    }
 130 }
 131
 132 /////////////////////////////////////////////////////////////
 133 // delete the min node from true rooted at rt and return its
 134 // v_element pointer
 135 /////////////////////////////////////////////////////////////
 136 void* bset::_remove_min(void* x, bsetnode*& rt)
 137 {
 138    if ( rt -> v_left == 0 ) {
 139       if ( rt -> v_right )
 140          return _move(rt, rt -> v_right);
 141       else {
 142          void* y = rt -> v_element;
 143          delete rt;
 144          rt = 0;
 145          return y;
 146       }
 147    } else
 148       return _remove_min(x, rt -> v_left);
 149 }
 150
 151 //**********************************************************************
 152 // move the content and pointers of node2 to node1 and remove node2
 153 //**********************************************************************
 154 void* bset::_move(bsetnode* node1, bsetnode* node2)
 155 {
 156    void* y = node1 -> v_element ;
 157
 158    node1 -> v_element = node2 -> v_element ;
 159    node2 -> v_element = 0;
 160    node1 -> v_left = node2 -> v_left ;
 161    node2 -> v_left = 0;
 162    node1 -> v_right = node2 -> v_right ;
 163    node2 -> v_right = 0;
 164    delete node2 ;
 165
 166    return y;
 167 }
 168
 169 void* bset::_remove(void* x, bsetnode*& rt)
 170 {
 171    if ( (*f_cmp_func_ls)(x, rt -> v_element) == true )  // v_left branch
 172       return _remove(x, rt -> v_left);
 173    else
 174    if ( !((*f_cmp_func_eq)(x, rt -> v_element) == true ) ) // v_right branch
 175       return _remove(x, rt -> v_right);
 176    else
 177    if ( rt -> v_left == 0 && rt -> v_right == 0 )  { // find the node.
 178       void* y = rt -> v_element ;
 179       delete rt;
 180       rt = 0;
 181       return y;
 182    } else
 183    if ( rt -> v_left == 0 ) {
 184       return _move(rt, rt -> v_right);
 185    } else
 186    if ( rt -> v_right == 0 ) {
 187       return _move(rt, rt -> v_left);
 188    } else {
 189       void* y = rt -> v_element ;
 190       rt -> v_element = _remove_min(x, rt -> v_right );
 191       return y;
 192    }
 193 }
 194
 195 void* bset::remove(void* x)
 196 {
 197    if ( v_setroot == 0 )
 198       return 0;
 199    else
 200       return _remove(x, v_setroot);
 201 }
 202
 203 void* bset::_member(const void* x, bsetnode *rt)
 204 {
 205    if ( rt == 0 ) {
 206 //debug(cerr, "member void zeor");
 207       return 0;
 208    } else if ( (*f_cmp_func_eq)(x, rt -> v_element) == true )
 209       return rt -> v_element;
 210    else if ( (*f_cmp_func_ls)(x, rt -> v_element) == true )
 211       return _member(x, rt -> v_left);
 212    else
 213       return _member(x, rt -> v_right);
 214 }
 215
 216 void* bset::member(const void* x)
 217 {
 218 /*
 219 debug(cerr, "member");
 220 debug(cerr, int(f_cmp_func_eq));
 221 debug(cerr, int(f_cmp_func_ls));
 222 debug(cerr, int(this));
 223 */
 224    return _member(x, v_setroot);
 225 }
 226
 227 void bset::apply(app_func_ptr_t f)
 228 {
 229    _apply(v_setroot, f);
 230 }
 231
 232 void bset::_apply(bsetnode* rt, app_func_ptr_t f)
 233 {
 234    if ( rt ) {
 235
 236       f(rt -> v_element);
 237
 238       _apply( rt -> v_left, f );
 239       _apply( rt -> v_right, f );
 240
 241    }
 242 }
 243
 244 void bset::del_elements(app_func_ptr_t func)
 245 {
 246    _del_elements(v_setroot, func);
 247    v_setroot = 0;
 248 }
 249
 250 void bset::_del_elements(bsetnode* rt, app_func_ptr_t func)
 251 {
 252    if ( rt ) {
 253
 254       bsetnode *lt = rt -> v_left;
 255       bsetnode *rg = rt -> v_right;
 256
 257       rt -> v_left = 0;
 258       rt -> v_right = 0;
 259
 260       func(rt -> v_element);
 261       delete rt;
 262
 263       _del_elements( lt, func );
 264       _del_elements( rg, func );
 265    }
 266 }
 267
 268 void bset::unlink_elements()
 269 {
 270    _unlink_elements(v_setroot);
 271    v_setroot = 0;
 272 }
 273
 274 void bset::_unlink_elements(bsetnode* rt)
 275 {
 276    if ( rt ) {
 277
 278       bsetnode *lt = rt -> v_left;
 279       bsetnode *rg = rt -> v_right;
 280
 281       rt -> v_left = 0;
 282       rt -> v_right = 0;
 283       delete rt;
 284
 285       _unlink_elements( lt );
 286       _unlink_elements( rg );
 287    }
 288 }
 289
 290 void bset::_smaller_member(const void* x, bsetnode* rt, void*& answer)
 291 {
 292    if ( rt == 0 ) return;
 293
 294    if ( (*f_cmp_func_eq)(x, rt -> v_element) == true ) {
 295       answer = rt -> v_element;
 296       return;
 297    }
 298
 299    if ( (*f_cmp_func_ls)(rt -> v_element, x) == true ) {
 300       answer = rt -> v_element;
 301       _smaller_member(x, rt -> v_right, answer);
 302       return;
 303    } else {
 304       _smaller_member(x, rt -> v_left, answer);
 305       return;
 306    }
 307
 308 /*
 309    if ( (*f_cmp_func_ls)(x, rt -> v_element) == true ) {
 310       if ( rt -> v_left )
 311          return _smaller_member(x, rt -> v_left);
 312       else
 313          return 0;
 314    }
 315
 316    if ( (*f_cmp_func_eq)(x, rt -> v_element) == true ||
 317         rt -> v_right == 0
 318       )
 319       return rt -> v_element;
 320
 321    return _smaller_member(x, rt -> v_right);
 322 */
 323 }
 324
 325 void* bset::_larger_member(const void* x, bsetnode* rt)
 326 {
 327    if ( gt(x, rt -> v_element) == true ) {
 328       if ( rt -> v_right )
 329          return _larger_member(x, rt -> v_right);
 330       else
 331          return 0;
 332    }
 333
 334    if ( (*f_cmp_func_eq)(x, rt -> v_element) == true ||
 335         rt -> v_left == 0
 336       )
 337       return rt -> v_element;
 338
 339    return _larger_member(x, rt -> v_left);
 340 }
 341
 342
 343 void* bset::smaller_member(const void* x)
 344 {
 345    void* answer = 0;
 346    _smaller_member(x, v_setroot, answer);
 347    return answer;
 348 }
 349
 350 void* bset::larger_member(const void* x)
 351 {
 352    return _larger_member(x, v_setroot);
 353 }
 354
 355 Boolean bset::gt(const void* x, const void* y)
 356 {
 357    if ( (*f_cmp_func_eq)(x, y) == false &&
 358         (*f_cmp_func_ls)(x, y) == false
 359       )
 360      return true;
 361    else
 362      return false;
 363 }
 364
 365 ostream& bset::asciiOut(ostream& out)
 366 {
 367    _asciiOut(out, v_setroot);
 368    return out;
 369 }
 370
 371 void bset::_asciiOut(ostream& out, bsetnode* rt)
 372 {
 373    if ( rt ) {
 374       out << long(rt -> v_element);
 375       out << "\n";
 376       _asciiOut( out, rt -> v_left );
 377       _asciiOut( out, rt -> v_right );
 378    }
 379 }
 380
 381 #ifdef REGRESSION_TEST
 382
 383 #include <sys/time.h>
 384 #include "utility/pm_random.h"
 385
 386 int
 387 in_bset_test(bset& bst, int* ins, unsigned int& in_cts, int* outs, unsigned int& out_cts, pm_random& rand_gen)
 388 {
 389    if ( in_cts == 0 ) return 0;
 390
 391    int k = rand_gen.rand() % in_cts;
 392
 393    int_swap(ins[k], ins[in_cts-1]);
 394
 395 //cerr << "<-------------- removing " << ins[in_cts-1] << "\n";
 396    long j = (long)bst.remove((void*)ins[in_cts-1]);
 397
 398    if ( j != ins[in_cts-1] ) {
 399       cerr << "can't correctly remove " << ins[in_cts-1] << "\n";
 400       return -1;
 401    }
 402
 403    if ( bst.member((void*)ins[in_cts-1]) != 0 ) {
 404       cerr << "element " << ins[in_cts-1] << " still in the set\n";
 405       return -1;
 406    }
 407
 408    outs[out_cts++] = ins[in_cts-1];
 409    in_cts--;
 410
 411    return 0;
 412 }
 413
 414 int
 415 out_bset_test(bset& bst, int* ins, unsigned int& in_cts, int* outs, unsigned int& out_cts,
 416               pm_random& rand_gen)
 417 {
 418    if ( out_cts == 0 ) return 0;
 419
 420    int k = rand_gen.rand() % out_cts;
 421
 422    int_swap(outs[k], outs[out_cts-1]);
 423
 424    if ( bst.member((void*)outs[out_cts-1]) != 0 ) {
 425       cerr << "can still find " << outs[out_cts-1] << "\n";
 426       return -1;
 427    }
 428
 429 //cerr << "--------------> inserting " << outs[out_cts-1] << "\n";
 430
 431    bst.insert((void*)outs[out_cts-1]);
 432
 433    if ( bst.member((void*)outs[out_cts-1]) == 0 ) {
 434       cerr << "can't find " << outs[out_cts-1] << "\n";
 435       return -1;
 436    }
 437
 438    ins[in_cts++] = outs[out_cts-1];
 439    out_cts--;
 440
 441    return 0;
 442 }
 443
 444
 445 int
 446 bset_test(unsigned int in_cts, unsigned int out_cts, pm_random& rand_gen, unsigned int cycles)
 447 {
 448    int ok = 0;
 449
 450    int* ins = new int[in_cts+out_cts];
 451    int* outs = new int[in_cts+out_cts];
 452
 453    bset bst(void_eq, void_ls);
 454
 455    for ( int i=0; i<in_cts; i++ ) {
 456       ins[i] = i + 1;
 457       bst.insert((void*)ins[i]);
 458    }
 459
 460    for ( i=0; i<out_cts; i++ ) {
 461       outs[i] = i + in_cts + 1;
 462    }
 463
 464    for ( i=0; i<cycles; i++ ) {
 465       if ( rand_gen.rand_01() > 0.5 )
 466          ok |= in_bset_test(bst, ins, in_cts, outs, out_cts, rand_gen);
 467       else
 468          ok |= out_bset_test(bst, ins, in_cts, outs, out_cts, rand_gen);
 469    }
 470
 471    delete ins;
 472    delete outs;
 473
 474    return ok;
 475 }
 476
 477 #endif