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

   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.h /main/4 1996/06/11 17:16:30 cde-hal $
  25  *
  26  * Copyright (c) 1993 HAL Computer Systems International, Ltd.
  27  * All rights reserved.  Unpublished -- rights reserved under
  28  * the Copyright 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 #ifndef _bset_h
  52 #define _bset_h 1
  53
  54 #include  "dstr/set.h"
  55 //#include  "storage/page_storage.h"
  56
  57 //**************************************************************
  58 //
  59 // a set implemented based on binary search tree data structure.
  60 //
  61 //**************************************************************
  62
  63 Boolean void_ls(const void* o1, const void* o2);
  64 Boolean void_eq(const void* o1, const void* o2);
  65
  66 class bset;
  67
  68 struct bsetnode
  69 {
  70    void* v_element;
  71    bsetnode* v_left;
  72    bsetnode* v_right;
  73
  74    bsetnode(void* x) : v_element(x), v_left(0), v_right(0)
  75    {};
  76    virtual ~bsetnode() { delete v_left; delete v_right; };
  77 };
  78
  79 class bset : public set {
  80
  81 public:
  82    bset(cmp_func_ptr_t eq = void_eq, cmp_func_ptr_t ls = void_ls);
  83    virtual ~bset();
  84
  85    virtual Boolean insert(void* element); // return false if element
  86                                           // is already there
  87    virtual void* remove(void* element);
  88    virtual void* member(const void* element);
  89
  90    virtual void* smaller_member(const void* element);
  91    virtual void* larger_member(const void* element);
  92
  93 // print elements as int.
  94    virtual ostream& asciiOut(ostream&);
  95
  96    virtual void unlink_elements(); // unlink those v_elments
  97    virtual void del_elements(app_func_ptr_t func);
  98    virtual void apply(app_func_ptr_t);
  99
 100 protected:
 101
 102    virtual void* _member(const void* element, bsetnode* rt);
 103    virtual Boolean _insert(void* element, bsetnode* rt);
 104    virtual void* _move(bsetnode* target, bsetnode* source);
 105    virtual void* _remove_min(void* element, bsetnode*& rt);
 106    virtual void*_remove(void* element, bsetnode*& rt);
 107    virtual void _del_elements(bsetnode* rt, app_func_ptr_t func);
 108    virtual void _apply(bsetnode* rt, app_func_ptr_t f);
 109    virtual void _unlink_elements(bsetnode* rt);
 110
 111    virtual void _smaller_member(const void* element, bsetnode* rt, void*& answer);
 112    virtual void* _larger_member(const void* element, bsetnode* rt);
 113    Boolean gt(const void* x, const void* y);
 114
 115    virtual void _asciiOut(ostream&, bsetnode* rt);
 116
 117 protected:
 118    bsetnode* v_setroot;
 119
 120 };
 121
 122 typedef bset* bsetPtr;
 123
 124 #endif