home *** CD-ROM | disk | FTP | other *** search
/ NeXTSTEP 3.2 (Developer) / NS_dev_3.2.iso / NextDeveloper / Headers / g++ / gen / SplaySet.hP < prev    next >
Text File  |  1993-06-29  |  3KB  |  134 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, 675 Mass Ave, Cambridge, MA 02139, 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.                   ~<T>SplaySet();
  45.  
  46.   Pix             add(<T&> item);
  47.   void            del(<T&> item);
  48.   int             contains(<T&> item);
  49.  
  50.   void            clear();
  51.  
  52.   Pix             first();
  53.   void            next(Pix& i);
  54.   <T>&            operator () (Pix i);
  55.   Pix             seek(<T&> item);
  56.  
  57.   Pix             last();
  58.   void            prev(Pix& i);
  59.  
  60.   void            operator |= (<T>SplaySet& b);
  61.   void            operator -= (<T>SplaySet& b);
  62.   void            operator &= (<T>SplaySet& b);
  63.  
  64.   int             operator == (<T>SplaySet& b);
  65.   int             operator != (<T>SplaySet& b);
  66.   int             operator <= (<T>SplaySet& b); 
  67.  
  68.   int             OK();
  69. };
  70.  
  71.  
  72. inline <T>SplaySet::~<T>SplaySet()
  73. {
  74.   _kill(root);
  75. }
  76.  
  77. inline <T>SplaySet::<T>SplaySet()
  78. {
  79.   root = 0;
  80.   count = 0;
  81. }
  82.  
  83. inline <T>SplaySet::<T>SplaySet(<T>SplaySet& b)
  84. {
  85.   count = b.count;
  86.   root = _copy(b.root);
  87. }
  88.  
  89.  
  90. inline int <T>SplaySet::operator != (<T>SplaySet& b)
  91. {
  92.   return ! (*this == b);
  93. }
  94.  
  95. inline Pix <T>SplaySet::first()
  96. {
  97.   return Pix(leftmost());
  98. }
  99.  
  100. inline Pix <T>SplaySet::last()
  101. {
  102.   return Pix(rightmost());
  103. }
  104.  
  105. inline void <T>SplaySet::next(Pix& i)
  106. {
  107.   if (i != 0) i = Pix(succ((<T>SplayNode*)i));
  108. }
  109.  
  110. inline void <T>SplaySet::prev(Pix& i)
  111. {
  112.   if (i != 0) i = Pix(pred((<T>SplayNode*)i));
  113. }
  114.  
  115. inline <T>& <T>SplaySet::operator () (Pix i)
  116. {
  117.   if (i == 0) error("null Pix");
  118.   return ((<T>SplayNode*)i)->item;
  119. }
  120.  
  121. inline void <T>SplaySet::clear()
  122. {
  123.   _kill(root);
  124.   count = 0;
  125.   root = 0;
  126. }
  127.  
  128. inline int <T>SplaySet::contains(<T&> key)
  129. {
  130.   return seek(key) != 0;
  131. }
  132.  
  133. #endif
  134.