home *** CD-ROM | disk | FTP | other *** search
/ ARM Club 3 / TheARMClub_PDCD3.iso / hensa / programming / libg_ / libgpp / !libgpp / gen / hp / SplaySet < prev    next >
Text File  |  1995-06-21  |  3KB  |  146 lines
  1. // This may look like C code, but it is really -*- C++ -*-
  2. /* 
  3. Copyright (C) 1988 Free Software Foundation
  4.     written by Doug Lea (dl@rocky.oswego.edu)
  5.  
  6. This file is part of the GNU C++ Library.  This library is free
  7. software; you can redistribute it and/or modify it under the terms of
  8. the GNU Library General Public License as published by the Free
  9. Software Foundation; either version 2 of the License, or (at your
  10. option) any later version.  This library is distributed in the hope
  11. that it will be useful, but WITHOUT ANY WARRANTY; without even the
  12. implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
  13. PURPOSE.  See the GNU Library General Public License for more details.
  14. You should have received a copy of the GNU Library General Public
  15. License along with this library; if not, write to the Free Software
  16. Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  17. */
  18.  
  19.  
  20. #ifndef _<T>SplaySet_h
  21. #ifdef __GNUG__
  22. #pragma interface
  23. #endif
  24. #define _<T>SplaySet_h 1
  25.  
  26. #include "<T>.Set.h"
  27. #include "<T>.SplayNode.h"
  28.  
  29. class <T>SplaySet : public <T>Set
  30. {
  31. protected:
  32.   <T>SplayNode*   root;
  33.  
  34.   <T>SplayNode*   leftmost();
  35.   <T>SplayNode*   rightmost();
  36.   <T>SplayNode*   pred(<T>SplayNode* t);
  37.   <T>SplayNode*   succ(<T>SplayNode* t);
  38.   void            _kill(<T>SplayNode* t);
  39.   <T>SplayNode*   _copy(<T>SplayNode* t);
  40.  
  41. public:
  42.                   <T>SplaySet();
  43.                   <T>SplaySet(<T>SplaySet& a);
  44.   inline                 ~<T>SplaySet();
  45.  
  46.   Pix             add(<T&> item);
  47.   void            del(<T&> item);
  48.   inline int             contains(<T&> item);
  49.  
  50.   inline void            clear();
  51.  
  52.   inline Pix             first();
  53.   inline void            next(Pix& i);
  54.   inline <T>&            operator () (Pix i);
  55.   Pix             seek(<T&> item);
  56.  
  57.   Pix             last();
  58.   void            prev(Pix& i);
  59.  
  60.   <T>SplaySet&    operator =  (const <T>SplaySet& b);
  61.   void            operator |= (<T>SplaySet& b);
  62.   void            operator -= (<T>SplaySet& b);
  63.   void            operator &= (<T>SplaySet& b);
  64.  
  65.   int             operator == (<T>SplaySet& b);
  66.   int             operator != (<T>SplaySet& b);
  67.   int             operator <= (<T>SplaySet& b); 
  68.  
  69.   int             OK();
  70. };
  71.  
  72.  
  73. inline <T>SplaySet::~<T>SplaySet()
  74. {
  75.   _kill(root);
  76. }
  77.  
  78. inline <T>SplaySet::<T>SplaySet()
  79. {
  80.   root = 0;
  81.   count = 0;
  82. }
  83.  
  84. inline <T>SplaySet::<T>SplaySet(<T>SplaySet& b)
  85. {
  86.   count = b.count;
  87.   root = _copy(b.root);
  88. }
  89.  
  90.  
  91. inline <T>SplaySet& <T>SplaySet::operator = (const <T>SplaySet& b)
  92. {
  93.   if (this != &b)
  94.     {
  95.       _kill (root);
  96.       count = b.count;
  97.       root = _copy (b.root);
  98.     }
  99.   return *this;
  100. }
  101.  
  102. inline int <T>SplaySet::operator != (<T>SplaySet& b)
  103. {
  104.   return ! (*this == b);
  105. }
  106.  
  107. inline Pix <T>SplaySet::first()
  108. {
  109.   return Pix(leftmost());
  110. }
  111.  
  112. inline Pix <T>SplaySet::last()
  113. {
  114.   return Pix(rightmost());
  115. }
  116.  
  117. inline void <T>SplaySet::next(Pix& i)
  118. {
  119.   if (i != 0) i = Pix(succ((<T>SplayNode*)i));
  120. }
  121.  
  122. inline void <T>SplaySet::prev(Pix& i)
  123. {
  124.   if (i != 0) i = Pix(pred((<T>SplayNode*)i));
  125. }
  126.  
  127. inline <T>& <T>SplaySet::operator () (Pix i)
  128. {
  129.   if (i == 0) error("null Pix");
  130.   return ((<T>SplayNode*)i)->item;
  131. }
  132.  
  133. inline void <T>SplaySet::clear()
  134. {
  135.   _kill(root);
  136.   count = 0;
  137.   root = 0;
  138. }
  139.  
  140. inline int <T>SplaySet::contains(<T&> key)
  141. {
  142.   return seek(key) != 0;
  143. }
  144.  
  145. #endif
  146.