home *** CD-ROM | disk | FTP | other *** search
/ ARM Club 3 / TheARMClub_PDCD3.iso / hensa / programming / libg_ / libgpp / !libgpp / gen / hp / SkipSet < prev    next >
Text File  |  1995-06-16  |  4KB  |  188 lines
  1. // This may look like C code, but it is really -*- C++ -*-
  2. /* 
  3. Copyright (C) 1991 Free Software Foundation
  4.  
  5. This file is part of the GNU C++ Library.  This library is free
  6. software; you can redistribute it and/or modify it under the terms of
  7. the GNU Library General Public License as published by the Free
  8. Software Foundation; either version 2 of the License, or (at your
  9. option) any later version.  This library is distributed in the hope
  10. that it will be useful, but WITHOUT ANY WARRANTY; without even the
  11. implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
  12. PURPOSE.  See the GNU Library General Public License for more details.
  13. You should have received a copy of the GNU Library General Public
  14. License along with this library; if not, write to the Free Software
  15. Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  16. */
  17.  
  18. /*
  19.  * Sets implemented via William Pugh SkipList algorithms.
  20.  * CACM, June 1990, p 668-676.
  21.  *
  22.  */
  23.  
  24. #ifndef _<T>SkipSet_h
  25. #ifdef __GNUG__
  26. #pragma interface
  27. #endif
  28. #define _<T>SkipSet_h 1
  29.  
  30. #include "<T>.Set.h"
  31.  
  32. #include <limits.h>
  33. #include <MLCG.h>
  34.  
  35. class <T>SkipSet;
  36. class <T>RealSkipSetNode;
  37.  
  38. class <T>SkipSetNode
  39. {
  40. friend class <T>SkipSet;
  41.   private:
  42.     <T>RealSkipSetNode * * forward;
  43.     <T>SkipSetNode(int size);
  44. };
  45.  
  46. class <T>RealSkipSetNode : public <T>SkipSetNode
  47. {
  48. friend class <T>SkipSet;
  49.   private:
  50.     <T>             item;
  51.     <T>RealSkipSetNode(<T&> h, int size);
  52. };
  53.  
  54. typedef <T>RealSkipSetNode* <T>SkipSetNodePtr;
  55.  
  56. inline <T>SkipSetNode::<T>SkipSetNode(int size)
  57. : forward(new <T>SkipSetNodePtr[size+1])
  58. {
  59. }
  60.  
  61. inline <T>RealSkipSetNode::<T>RealSkipSetNode(<T&> h, int size)
  62. : item(h),
  63.   <T>SkipSetNode(size)
  64. {
  65. }
  66.  
  67. class <T>SkipSet : public <T>Set
  68. {
  69. friend class <T>SkipSetinit;
  70.   protected:
  71.     <T>SkipSetNode*   header;
  72.     int               level;
  73.     int               max_levels;
  74.     int               randoms_left;
  75.     long              random_bits;
  76.     
  77.     static MLCG*      gen;
  78.     int               random_level(void);
  79.     
  80.     <T>SkipSetNodePtr leftmost(void);
  81.     <T>SkipSetNodePtr rightmost(void);
  82.     <T>SkipSetNodePtr pred(<T>SkipSetNodePtr t);
  83.     <T>SkipSetNodePtr succ(<T>SkipSetNodePtr t);
  84.     void              _kill(void);
  85.     
  86.   private:
  87.     enum { BITS_IN_RANDOM = LONGBITS-1 };
  88.   public:
  89.     <T>SkipSet(long size=DEFAULT_INITIAL_CAPACITY);
  90.     <T>SkipSet(<T>SkipSet& a);
  91.     ~<T>SkipSet();
  92.     
  93.     Pix             add(<T&> i);
  94.     void            del(<T&> i);
  95.     int             contains(<T&> i);
  96.     
  97.     void            clear(void);
  98.     
  99.     Pix             first(void);
  100.     void            next(Pix& i);
  101.     <T>&            operator () (Pix i);
  102.     Pix             seek(<T&> i);
  103.     
  104.     Pix             last(void);
  105.     void            prev(Pix& i);
  106.     
  107.     void            operator |= (<T>SkipSet& b);
  108.     void            operator -= (<T>SkipSet& b);
  109.     void            operator &= (<T>SkipSet& b);
  110.     
  111.     int             operator == (<T>SkipSet& b);
  112.     int             operator != (<T>SkipSet& b);
  113.     int             operator <= (<T>SkipSet& b); 
  114.     
  115.     int             OK(void);
  116. };
  117.  
  118. /*
  119.  *  A little overkill on the inlines.
  120.  *
  121.  */
  122.  
  123. inline <T>SkipSet::~<T>SkipSet(void)
  124. {
  125.   _kill();
  126.   delete header;
  127. }
  128.  
  129. inline int <T>SkipSet::operator != (<T>SkipSet& b)
  130. {
  131.   return ! (*this == b);
  132. }
  133.  
  134. inline <T>SkipSetNodePtr <T>SkipSet::leftmost(void)
  135. {
  136.   return header->forward[0];
  137. }
  138.  
  139. inline <T>SkipSetNodePtr <T>SkipSet::succ(<T>SkipSetNodePtr t)
  140. {
  141.   <T>SkipSetNodePtr result = 0;
  142.   if (t->forward[0]!=header) result = t->forward[0];
  143.   return result;
  144. }
  145.  
  146. inline Pix <T>SkipSet::first(void)
  147. {
  148.   return Pix(leftmost());
  149. }
  150.  
  151. inline Pix <T>SkipSet::last(void)
  152. {
  153.   return Pix(rightmost());
  154. }
  155.  
  156. inline void <T>SkipSet::next(Pix& i)
  157. {
  158.   if (i != 0) i = Pix(succ((<T>SkipSetNodePtr)i));
  159. }
  160.  
  161. inline void <T>SkipSet::prev(Pix& i)
  162. {
  163.   if (i != 0) i = Pix(pred((<T>SkipSetNodePtr)i));
  164. }
  165.  
  166. inline <T>& <T>SkipSet::operator () (Pix i)
  167. {
  168.   if (i == 0) error("null Pix");
  169.   return ((<T>SkipSetNodePtr)i)->item;
  170. }
  171.  
  172.  
  173. inline int <T>SkipSet::contains(<T&> key)
  174. {
  175.   return seek(key) != 0;
  176. }
  177.  
  178. static class <T>SkipSetinit
  179. {
  180.   public:
  181.     <T>SkipSetinit();
  182.     ~<T>SkipSetinit();
  183.   private:
  184.     static int count;
  185. } <T>skipSetinit;
  186.  
  187. #endif
  188.