home *** CD-ROM | disk | FTP | other *** search
/ ARM Club 3 / TheARMClub_PDCD3.iso / hensa / programming / libg_ / libgpp / !libgpp / gen / hp / SplayPQ < prev    next >
Text File  |  1995-06-21  |  3KB  |  124 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>SplayPQ_h
  21. #ifdef __GNUG__
  22. #pragma interface
  23. #endif
  24. #define _<T>SplayPQ_h 1
  25.  
  26. #include "<T>.PQ.h"
  27. #include "<T>.SplayNode.h"
  28.  
  29. class <T>SplayPQ : public <T>PQ
  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>SplayPQ();
  43.                   <T>SplayPQ(<T>SplayPQ& a);
  44.   inline virtual       ~<T>SplayPQ();
  45.  
  46.   Pix           enq(<T&> item);
  47.   <T>           deq(); 
  48.  
  49.   <T>&          front();
  50.   void          del_front();
  51.  
  52.   inline int           contains(<T&> item);
  53.  
  54.   inline void          clear(); 
  55.  
  56.   inline Pix           first(); 
  57.   Pix           last(); 
  58.   inline void          next(Pix& i);
  59.   void          prev(Pix& i);
  60.   inline <T>&          operator () (Pix i);
  61.   void          del(Pix i);
  62.   Pix           seek(<T&> item);
  63.  
  64.   int           OK();                    // rep invariant
  65. };
  66.  
  67.  
  68. inline <T>SplayPQ::~<T>SplayPQ()
  69. {
  70.   _kill(root);
  71. }
  72.  
  73. inline <T>SplayPQ::<T>SplayPQ()
  74. {
  75.   root = 0;
  76.   count = 0;
  77. }
  78.  
  79. inline <T>SplayPQ::<T>SplayPQ(<T>SplayPQ& b)
  80. {
  81.   count = b.count;
  82.   root = _copy(b.root);
  83. }
  84.  
  85. inline Pix <T>SplayPQ::first()
  86. {
  87.   return Pix(leftmost());
  88. }
  89.  
  90. inline Pix <T>SplayPQ::last()
  91. {
  92.   return Pix(rightmost());
  93. }
  94.  
  95. inline void <T>SplayPQ::next(Pix& i)
  96. {
  97.   if (i != 0) i = Pix(succ((<T>SplayNode*)i));
  98. }
  99.  
  100. inline void <T>SplayPQ::prev(Pix& i)
  101. {
  102.   if (i != 0) i = Pix(pred((<T>SplayNode*)i));
  103. }
  104.  
  105. inline <T>& <T>SplayPQ::operator () (Pix i)
  106. {
  107.   if (i == 0) error("null Pix");
  108.   return ((<T>SplayNode*)i)->item;
  109. }
  110.  
  111. inline void <T>SplayPQ::clear()
  112. {
  113.   _kill(root);
  114.   count = 0;
  115.   root = 0;
  116. }
  117.  
  118. inline int <T>SplayPQ::contains(<T&> key)
  119. {
  120.   return seek(key) != 0;
  121. }
  122.  
  123. #endif
  124.