home *** CD-ROM | disk | FTP | other *** search
/ Geek Gadgets 1 / ADE-1.bin / ade-bin / lib / g++-include / gen / oslset.ccp < prev    next >
Encoding:
Text File  |  1996-10-12  |  5.5 KB  |  322 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>.OSLSet.h"
  23.  
  24.  
  25. Pix <T>OSLSet::seek(<T&> item)
  26. {
  27.   for (Pix i = p.first(); i != 0; p.next(i))
  28.   {
  29.     int cmp = <T>CMP(item, p(i));
  30.     if (cmp == 0)
  31.       return i;
  32.     else if (cmp < 0)
  33.       return 0;
  34.   }
  35.   return 0;
  36. }
  37.  
  38. Pix <T>OSLSet::add(<T&> item)
  39. {
  40.   Pix i = p.first();
  41.   if (i == 0) 
  42.   {
  43.     ++count;
  44.     return p.prepend(item);
  45.   }
  46.   int cmp = <T>CMP(item, p(i));
  47.   if (cmp == 0)
  48.     return i;
  49.   else if (cmp < 0)
  50.   {
  51.     ++count;
  52.     return p.prepend(item);
  53.   }
  54.   else
  55.   {
  56.     Pix trail = i;
  57.     p.next(i);
  58.     for (;;)
  59.     {
  60.       if (i == 0)
  61.       {
  62.         ++count;
  63.         return p.append(item);
  64.       }
  65.       cmp = <T>CMP(item, p(i));
  66.       if (cmp == 0)
  67.         return i;
  68.       else if (cmp < 0)
  69.       {
  70.         ++count;
  71.         return p.ins_after(trail, item);
  72.       }
  73.       else
  74.       {
  75.         trail = i;
  76.         p.next(i);
  77.       }
  78.     }
  79.   }
  80. }
  81.  
  82. void <T>OSLSet::del(<T&> item)
  83. {
  84.   Pix i = p.first();
  85.   if (i == 0)
  86.     return;
  87.   int cmp = <T>CMP(item, p(i));
  88.   if (cmp < 0)
  89.     return;
  90.   else if (cmp == 0)
  91.   {
  92.     --count;
  93.     p.del_front();
  94.   }
  95.   else
  96.   {
  97.     Pix trail = i;
  98.     p.next(i);
  99.     while (i != 0)
  100.     {
  101.       cmp = <T>CMP(item, p(i));
  102.       if (cmp < 0)
  103.         return;
  104.       else if (cmp == 0)
  105.       {
  106.         --count;
  107.         p.del_after(trail);
  108.         return;
  109.       }
  110.       else
  111.       {
  112.         trail = i;
  113.         p.next(i);
  114.       }
  115.     }
  116.   }
  117. }
  118.         
  119.  
  120. int <T>OSLSet::operator <= (<T>OSLSet& b)
  121. {
  122.   if (count > b.count) return 0;
  123.   Pix i = first();
  124.   Pix j = b.first();
  125.   for (;;)
  126.   {
  127.     if (i == 0)
  128.       return 1;
  129.     else if (j == 0)
  130.       return 0;
  131.     int cmp = <T>CMP(p(i), b.p(j));
  132.     if (cmp == 0)
  133.     {
  134.       next(i); b.next(j);
  135.     }
  136.     else if (cmp < 0)
  137.       return 0;
  138.     else
  139.       b.next(j);
  140.   }
  141. }
  142.  
  143. int <T>OSLSet::operator == (<T>OSLSet& b)
  144. {
  145.   if (count != b.count) return 0;
  146.   if (count == 0) return 1;
  147.   Pix i = p.first();
  148.   Pix j = b.p.first();
  149.   while (i != 0)
  150.   {
  151.     if (!<T>EQ(p(i),b.p(j))) return 0;
  152.     next(i);
  153.     b.next(j);
  154.   }
  155.   return 1;
  156. }
  157.  
  158.  
  159. void <T>OSLSet::operator |= (<T>OSLSet& b)
  160. {
  161.   if (&b == this || b.count == 0)
  162.     return;
  163.   else
  164.   {
  165.     Pix j = b.p.first();
  166.     Pix i = p.first();
  167.     Pix trail = 0;
  168.     for (;;)
  169.     {
  170.       if (j == 0)
  171.         return;
  172.       else if (i == 0)
  173.       {
  174.         for (; j != 0; b.next(j))
  175.         {
  176.           ++count;
  177.           p.append(b.p(j));
  178.         }
  179.         return;
  180.       }
  181.       int cmp = <T>CMP(p(i), b.p(j));
  182.       if (cmp <= 0)
  183.       {
  184.         if (cmp == 0) b.next(j);
  185.         trail = i;
  186.         next(i);
  187.       }
  188.       else
  189.       {
  190.         ++count;
  191.         if (trail == 0)
  192.           trail = p.prepend(b.p(j));
  193.         else
  194.           trail = p.ins_after(trail, b.p(j));
  195.         b.next(j);
  196.       }
  197.     }
  198.   }
  199. }
  200.  
  201.  
  202. void <T>OSLSet::operator -= (<T>OSLSet& b)
  203. {
  204.   if (&b == this)
  205.     clear();
  206.   else if (count != 0 && b.count != 0)
  207.   {
  208.     Pix i = p.first();
  209.     Pix j = b.p.first();
  210.     Pix trail = 0;
  211.     for (;;)
  212.     {
  213.       if (j == 0 || i == 0)
  214.         return;
  215.       int cmp = <T>CMP(p(i), b.p(j));
  216.       if (cmp == 0)
  217.       {
  218.         --count;
  219.         b.next(j);
  220.         if (trail == 0)
  221.         {
  222.           p.del_front();
  223.           i = p.first();
  224.         }
  225.         else
  226.         {
  227.           next(i);
  228.           p.del_after(trail);
  229.         }
  230.       }
  231.       else if (cmp < 0)
  232.       {
  233.         trail = i;
  234.         next(i);
  235.       }
  236.       else
  237.         b.next(j);
  238.     }
  239.   }
  240. }
  241.  
  242. void <T>OSLSet::operator &= (<T>OSLSet& b)
  243. {
  244.   if (b.count == 0)
  245.     clear();
  246.   else if (&b != this && count != 0)
  247.   {
  248.     Pix i = p.first();
  249.     Pix j = b.p.first();
  250.     Pix trail = 0;
  251.     for (;;)
  252.     {
  253.       if (i == 0)
  254.         return;
  255.       else if (j == 0)
  256.       {
  257.         if (trail == 0)
  258.         {
  259.           p.clear();
  260.           count = 0;
  261.         }
  262.         else
  263.         {
  264.           while (i != 0)
  265.           {
  266.             --count;
  267.             next(i);
  268.             p.del_after(trail);
  269.           }
  270.         }
  271.         return;
  272.       }
  273.       int cmp = <T>CMP(p(i), b.p(j));
  274.  
  275.       if (cmp == 0)
  276.       {
  277.         trail = i;
  278.         next(i);
  279.         b.next(j);
  280.       }
  281.       else if (cmp < 0)
  282.       {
  283.         --count;
  284.         if (trail == 0)
  285.         {
  286.           p.del_front();
  287.           i = p.first();
  288.         }
  289.         else
  290.         {
  291.           next(i);
  292.           p.del_after(trail);
  293.         }
  294.       }
  295.       else
  296.         b.next(j);
  297.     }
  298.   }
  299. }
  300.  
  301.  
  302. int <T>OSLSet::OK()
  303. {
  304.   int v = p.OK();
  305.   v &= count == p.length();
  306.   Pix trail = p.first();
  307.   if (trail == 0)
  308.     v &= count == 0;
  309.   else
  310.   {
  311.     Pix i = trail; next(i);
  312.     while (i != 0)
  313.     {
  314.       v &= <T>CMP(p(trail), p(i)) < 0;
  315.       trail = i;
  316.       next(i);
  317.     }
  318.   }
  319.   if (!v) error("invariant failure");
  320.   return v;
  321. }
  322.