home *** CD-ROM | disk | FTP | other *** search
/ ARM Club 3 / TheARMClub_PDCD3.iso / hensa / programming / libg_ / libgpp / !libgpp / gen / ccp / OSLBag < prev    next >
Text File  |  1995-06-16  |  4KB  |  197 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. #ifdef __GNUG__
  20. #pragma implementation
  21. #endif
  22. #include "<T>.OSLBag.h"
  23.  
  24.  
  25. Pix <T>OSLBag::seek(<T&> item, Pix i)
  26. {
  27.   if (i == 0) i = p.first(); else next(i);
  28.   for (; i != 0; p.next(i))
  29.   {
  30.     int cmp = <T>CMP(item, p(i));
  31.     if (cmp == 0)
  32.       return i;
  33.     else if (cmp < 0)
  34.       return 0;
  35.   }
  36.   return 0;
  37. }
  38.  
  39. int <T>OSLBag::nof(<T&> item)
  40. {
  41.   int n = 0;
  42.   for (Pix i = p.first(); i != 0; p.next(i))
  43.   {
  44.     int cmp = <T>CMP(item, p(i));
  45.     if (cmp == 0)
  46.       ++n;
  47.     else if (cmp < 0)
  48.       break;
  49.   }
  50.   return n;
  51. }
  52.  
  53. Pix <T>OSLBag::add(<T&> item)
  54. {
  55.   Pix i = p.first();
  56.   if (i == 0) 
  57.   {
  58.     ++count;
  59.     return p.prepend(item);
  60.   }
  61.   int cmp = <T>CMP(item, p(i));
  62.   if (cmp <= 0)
  63.   {
  64.     ++count;
  65.     return p.prepend(item);
  66.   }
  67.   else
  68.   {
  69.     Pix trail = i;
  70.     p.next(i);
  71.     for (;;)
  72.     {
  73.       if (i == 0)
  74.       {
  75.         ++count;
  76.         return p.append(item);
  77.       }
  78.       cmp = <T>CMP(item, p(i));
  79.       if (cmp <= 0)
  80.       {
  81.         ++count;
  82.         return p.ins_after(trail, item);
  83.       }
  84.       else
  85.       {
  86.         trail = i;
  87.         p.next(i);
  88.       }
  89.     }
  90.   }
  91. }
  92.  
  93. void <T>OSLBag::del(<T&> item)
  94. {
  95.   Pix i = p.first();
  96.   if (i == 0)
  97.     return;
  98.   int cmp = <T>CMP(item, p(i));
  99.   if (cmp < 0)
  100.     return;
  101.   else if (cmp == 0)
  102.   {
  103.     --count;
  104.     p.del_front();
  105.   }
  106.   else
  107.   {
  108.     Pix trail = i;
  109.     p.next(i);
  110.     while (i != 0)
  111.     {
  112.       cmp = <T>CMP(item, p(i));
  113.       if (cmp < 0)
  114.         return;
  115.       else if (cmp == 0)
  116.       {
  117.         --count;
  118.         p.del_after(trail);
  119.         return;
  120.       }
  121.       else
  122.       {
  123.         trail = i;
  124.         p.next(i);
  125.       }
  126.     }
  127.   }
  128. }
  129.  
  130. void <T>OSLBag::remove(<T&> item)
  131. {
  132.   Pix i = p.first();
  133.   if (i == 0)
  134.     return;
  135.   int cmp = <T>CMP(item, p(i));
  136.   if (cmp < 0)
  137.     return;
  138.   else if (cmp == 0)
  139.   {
  140.     do
  141.     {
  142.       --count;
  143.       p.del_front();
  144.       i = p.first();
  145.     } while (i != 0 && <T>EQ(item, p(i)));
  146.   }
  147.   else
  148.   {
  149.     Pix trail = i;
  150.     p.next(i);
  151.     while (i != 0)
  152.     {
  153.       cmp = <T>CMP(item, p(i));
  154.       if (cmp < 0)
  155.         return;
  156.       else if (cmp == 0)
  157.       {
  158.         do
  159.         {
  160.           --count;
  161.           p.del_after(trail);
  162.           i = trail;
  163.           next(i);
  164.         } while (i != 0 && <T>EQ(item, p(i)));
  165.         return;
  166.       }
  167.       else
  168.       {
  169.         trail = i;
  170.         p.next(i);
  171.       }
  172.     }
  173.   }
  174. }
  175.         
  176. int <T>OSLBag::OK()
  177. {
  178.   int v = p.OK();
  179.   v &= count == p.length();
  180.   Pix trail = p.first();
  181.   if (trail == 0)
  182.     v &= count == 0;
  183.   else
  184.   {
  185.     Pix i = trail; next(i);
  186.     while (i != 0)
  187.     {
  188.       v &= <T>CMP(p(trail), p(i)) <= 0;
  189.       trail = i;
  190.       next(i);
  191.     }
  192.   }
  193.   if (!v) error("invariant failure");
  194.   return v;
  195. }
  196.  
  197.