home *** CD-ROM | disk | FTP | other *** search
/ NeXTSTEP 3.2 (Developer) / NS_dev_3.2.iso / NextDeveloper / Headers / g++ / gen / SplayMap.hP < prev    next >
Text File  |  1993-06-29  |  4KB  |  155 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><C>SplayMap_h
  21. #ifdef __GNUG__
  22. #pragma interface
  23. #endif
  24. #define _<T><C>SplayMap_h 1
  25.  
  26. #include "<T>.<C>.Map.h"
  27.  
  28. #ifndef _<T><C>SplayNode
  29. #define _<T><C>SplayNode 1
  30.  
  31. struct <T><C>SplayNode
  32. {
  33.   <T><C>SplayNode*   lt;
  34.   <T><C>SplayNode*   rt;
  35.   <T><C>SplayNode*   par;
  36.   <T>                item;
  37.   <C>                cont;
  38.                      <T><C>SplayNode(<T&> h, <C&> c, 
  39.                                      <T><C>SplayNode* l=0, 
  40.                                      <T><C>SplayNode* r=0);
  41.                   ~<T><C>SplayNode();
  42. };
  43.  
  44.  
  45. inline <T><C>SplayNode::<T><C>SplayNode(<T&> h, <C&> c, 
  46.                                         <T><C>SplayNode* l, 
  47.                                         <T><C>SplayNode* r)
  48.      :item(h), cont(c), lt(l), rt(r), par(0) {}
  49.  
  50. inline <T><C>SplayNode::~<T><C>SplayNode() {}
  51.  
  52. typedef <T><C>SplayNode* <T><C>SplayNodePtr;
  53.  
  54. #endif
  55.  
  56. class <T><C>SplayMap : public <T><C>Map
  57. {
  58. protected:
  59.   <T><C>SplayNode*   root;
  60.  
  61.   <T><C>SplayNode*   leftmost();
  62.   <T><C>SplayNode*   rightmost();
  63.   <T><C>SplayNode*   pred(<T><C>SplayNode* t);
  64.   <T><C>SplayNode*   succ(<T><C>SplayNode* t);
  65.   void               _kill(<T><C>SplayNode* t);
  66.   <T><C>SplayNode*   _copy(<T><C>SplayNode* t);
  67.  
  68. public:
  69.                <T><C>SplayMap(<C&> dflt);
  70.                <T><C>SplayMap(<T><C>SplayMap& a);
  71.                ~<T><C>SplayMap();
  72.  
  73.   <C>&          operator [] (<T&> key);
  74.  
  75.   void          del(<T&> key);
  76.  
  77.   Pix           first();
  78.   void          next(Pix& i);
  79.   <T>&          key(Pix i);
  80.   <C>&          contents(Pix i);
  81.  
  82.   Pix           seek(<T&> key);
  83.   int           contains(<T&> key);
  84.  
  85.   void          clear(); 
  86.  
  87.   Pix           last();
  88.   void          prev(Pix& i);
  89.  
  90.   int           OK();
  91. };
  92.  
  93.  
  94. inline <T><C>SplayMap::~<T><C>SplayMap()
  95. {
  96.   _kill(root);
  97. }
  98.  
  99. inline <T><C>SplayMap::<T><C>SplayMap(<C&> dflt) :<T><C>Map(dflt)
  100. {
  101.   root = 0;
  102. }
  103.  
  104. inline <T><C>SplayMap::<T><C>SplayMap(<T><C>SplayMap& b) :<T><C>Map(b.def)
  105. {
  106.   count = b.count;
  107.   root = _copy(b.root);
  108. }
  109.  
  110. inline Pix <T><C>SplayMap::first()
  111. {
  112.   return Pix(leftmost());
  113. }
  114.  
  115. inline Pix <T><C>SplayMap::last()
  116. {
  117.   return Pix(rightmost());
  118. }
  119.  
  120. inline void <T><C>SplayMap::next(Pix& i)
  121. {
  122.   if (i != 0) i = Pix(succ((<T><C>SplayNode*)i));
  123. }
  124.  
  125. inline void <T><C>SplayMap::prev(Pix& i)
  126. {
  127.   if (i != 0) i = Pix(pred((<T><C>SplayNode*)i));
  128. }
  129.  
  130. inline <T>& <T><C>SplayMap::key (Pix i)
  131. {
  132.   if (i == 0) error("null Pix");
  133.   return ((<T><C>SplayNode*)i)->item;
  134. }
  135.  
  136. inline <C>& <T><C>SplayMap::contents (Pix i)
  137. {
  138.   if (i == 0) error("null Pix");
  139.   return ((<T><C>SplayNode*)i)->cont;
  140. }
  141.  
  142. inline void <T><C>SplayMap::clear()
  143. {
  144.   _kill(root);
  145.   count = 0;
  146.   root = 0;
  147. }
  148.  
  149. inline int <T><C>SplayMap::contains(<T&> key)
  150. {
  151.   return seek(key) != 0;
  152. }
  153.  
  154. #endif
  155.