home *** CD-ROM | disk | FTP | other *** search
/ ARM Club 3 / TheARMClub_PDCD3.iso / hensa / programming / libg_ / libgpp / !libgpp / gen / ccp / OXPSet < prev    next >
Text File  |  1995-06-16  |  6KB  |  281 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>.OXPSet.h"
  23.  
  24.  
  25. Pix <T>OXPSet::seek(<T&> item)
  26. {
  27.   int l = p.low();
  28.   int h = p.high();
  29.   while (l <= h)
  30.   {
  31.     int mid = (l + h) / 2;
  32.     int cmp = <T>CMP(item, p[mid]);
  33.     if (cmp == 0)
  34.       return p.index_to_Pix(mid);
  35.     else if (cmp < 0)
  36.       h = mid - 1;
  37.     else
  38.       l = mid + 1;
  39.   }
  40.   return 0;
  41. }
  42.  
  43. Pix <T>OXPSet::add(<T&> item)
  44. {
  45.   if (count == 0) 
  46.   {
  47.     ++count;
  48.     return p.index_to_Pix(p.add_high(item));
  49.   }
  50.   int l = p.low();
  51.   int h = p.high();
  52.   while (l <= h)
  53.   {
  54.     int mid = (l + h) / 2;
  55.     int cmp = <T>CMP(item, p[mid]);
  56.     if (cmp == 0)
  57.       return p.index_to_Pix(mid);
  58.     else if (cmp < 0)
  59.         h = mid - 1;
  60.     else
  61.       l = mid + 1;
  62.   }
  63.   // add on whichever side is shortest
  64.   ++count;
  65.   if (l == p.fence())
  66.     return p.index_to_Pix(p.add_high(item));
  67.   else if (l == p.low())
  68.     return p.index_to_Pix(p.add_low(item));
  69.   else 
  70.   {
  71.     if (p.fence() - l < l - p.low())
  72.     {
  73.       h = p.add_high(p.high_element());
  74.       for (int i = h - 1; i > l; --i) p[i] = p[i-1];
  75.     }
  76.     else
  77.     {
  78.       --l;
  79.       h = p.add_low(p.low_element());
  80.       for (int i = h + 1; i < l; ++i) p[i] = p[i+1];
  81.     }
  82.     p[l] = item;
  83.     return p.index_to_Pix(l);
  84.   }
  85. }
  86.  
  87. void <T>OXPSet::del(<T&> item)
  88. {
  89.   int l = p.low();
  90.   int h = p.high();
  91.   while (l <= h)
  92.   {
  93.     int mid = (l + h) / 2;
  94.     int cmp = <T>CMP(item, p[mid]);
  95.     if (cmp == 0)
  96.     {
  97.       --count;
  98.       if (p.high() - mid < mid - p.low())
  99.       {
  100.         for (int i = mid; i < p.high(); ++i) p[i] = p[i+1];
  101.         p.del_high();
  102.       }
  103.       else
  104.       {
  105.         for (int i = mid; i > p.low(); --i) p[i] = p[i-1];
  106.         p.del_low();
  107.       }
  108.       return;
  109.     }
  110.     else if (cmp < 0)
  111.       h = mid - 1;
  112.     else
  113.       l = mid + 1;
  114.   }
  115. }
  116.  
  117. int <T>OXPSet::operator <= (<T>OXPSet& b)
  118. {
  119.   if (count > b.count) return 0;
  120.   int i = p.low();
  121.   int j = b.p.low();
  122.   for (;;)
  123.   {
  124.     if (i >= p.fence())
  125.       return 1;
  126.     else if (j >= b.p.fence()) 
  127.       return 0;
  128.     int cmp = <T>CMP(p[i], b.p[j]);
  129.     if (cmp == 0)
  130.     {
  131.       ++i; ++j;
  132.     }
  133.     else if (cmp < 0)
  134.       return 0;
  135.     else
  136.       ++j;
  137.   }
  138. }
  139.  
  140. int <T>OXPSet::operator == (<T>OXPSet& b)
  141. {
  142.   int n = count;
  143.   if (n != b.count) return 0;
  144.   if (n == 0) return 1;
  145.   int i = p.low();
  146.   int j = b.p.low();
  147.   while (n-- > 0) if (!<T>EQ(p[i++], b.p[j++])) return 0;
  148.   return 1;
  149. }
  150.  
  151.  
  152. void <T>OXPSet::operator |= (<T>OXPSet& b)
  153. {
  154.   if (&b == this || b.count == 0)
  155.     return;
  156.   else if (b.count <= 2) // small b -- just add
  157.     for (Pix i = b.first(); i; b.next(i)) add(b(i));
  158.   else
  159.   {
  160.     // strategy: merge into top of p, simultaneously killing old bottom
  161.     int oldfence = p.fence();
  162.     int i = p.low();
  163.     int j = b.p.low();
  164.     for (;;)
  165.     {
  166.       if (i == oldfence)
  167.       {
  168.         while (j < b.p.fence()) p.add_high(b.p[j++]);
  169.         break;
  170.       }
  171.       else if (j == b.p.fence())
  172.       {
  173.         while (i++ < oldfence) 
  174.         {
  175.           p.add_high(p.low_element());
  176.           p.del_low();
  177.         }
  178.         break;
  179.       }
  180.       int cmp = <T>CMP(p[i], b.p[j]);
  181.       if (cmp <= 0)
  182.       {
  183.         ++i;
  184.         if (cmp == 0)  ++j;
  185.         p.add_high(p.low_element());
  186.         p.del_low();
  187.       }
  188.       else
  189.         p.add_high(b.p[j++]);
  190.     }
  191.     count = p.length();
  192.   }
  193. }
  194.  
  195.  
  196.  
  197. void <T>OXPSet::operator -= (<T>OXPSet& b)
  198. {
  199.   if (&b == this)
  200.     clear();
  201.   else if (count != 0 && b.count != 0)
  202.   {
  203.     int i = p.low();
  204.     int k = i;
  205.     int j = b.p.low();
  206.     int oldfence = p.fence();
  207.     for (;;)
  208.     {
  209.       if (i >= oldfence)
  210.         break;
  211.       else if (j >= b.p.fence())
  212.       {
  213.         if (k != i)
  214.           while (i < oldfence) p[k++] = p[i++];
  215.         else
  216.           k = oldfence;
  217.         break;
  218.       }
  219.       int cmp = <T>CMP(p[i], b.p[j]);
  220.       if (cmp == 0)
  221.       {
  222.         ++i; ++j;
  223.       }
  224.       else if (cmp < 0)
  225.       {
  226.         if (k != i) p[k] = p[i];
  227.         ++i; ++k;
  228.       }
  229.       else
  230.         j++;
  231.     }
  232.     while (k++ < oldfence)
  233.     {
  234.       --count;
  235.       p.del_high();
  236.     }
  237.   }
  238. }
  239.  
  240. void <T>OXPSet::operator &= (<T>OXPSet& b)
  241. {
  242.   if (b.count == 0)
  243.     clear();
  244.   else if (&b != this && count != 0)
  245.   {
  246.     int i = p.low();
  247.     int k = i;
  248.     int j = b.p.low();
  249.     int oldfence = p.fence();
  250.     for (;;)
  251.     {
  252.       if (i >= oldfence || j >= b.p.fence())
  253.         break;
  254.       int cmp = <T>CMP(p[i], b.p[j]);
  255.       if (cmp == 0)
  256.       {
  257.         if (k != i) p[k] = p[i];
  258.         ++i; ++k; ++j;
  259.       }
  260.       else if (cmp < 0)
  261.         ++i;
  262.       else
  263.         ++j;
  264.     }
  265.     while (k++ < oldfence)
  266.     {
  267.       --count;
  268.       p.del_high();
  269.     }
  270.   }
  271. }
  272.  
  273. int <T>OXPSet::OK()
  274. {
  275.   int v = p.OK();
  276.   v &= count == p.length();
  277.   for (int i = p.low(); i < p.high(); ++i) v &= <T>CMP(p[i], p[i+1]) < 0;
  278.   if (!v) error("invariant failure");
  279.   return v;
  280. }
  281.