home *** CD-ROM | disk | FTP | other *** search
/ NeXTSTEP 3.3 (Developer) / NeXT_Developer-3.3.iso / NextDeveloper / Headers / g++ / gen / OXPBag.ccP < prev    next >
Encoding:
Text File  |  1995-02-06  |  4.6 KB  |  222 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. #ifdef __GNUG__
  20. #pragma implementation
  21. #endif
  22. #include "<T>.OXPBag.h"
  23.  
  24.  
  25. Pix <T>OXPBag::seek(<T&> item, Pix i)
  26. {
  27.   if (i == 0)
  28.   {
  29.     int l = p.low();
  30.     int h = p.high();
  31.     while (l <= h)
  32.     {
  33.       int mid = (l + h) / 2;
  34.       int cmp = <T>CMP(item, p[mid]);
  35.       if (cmp == 0)
  36.       {
  37.         while (mid > p.low() && <T>EQ(item, p[mid - 1])) --mid;
  38.         return p.index_to_Pix(mid);
  39.       }
  40.       else if (cmp < 0)
  41.         h = mid - 1;
  42.       else
  43.         l = mid + 1;
  44.     }
  45.     return 0;
  46.   }
  47.   int cmp = <T>CMP(item, p(i));
  48.   if (cmp == 0)
  49.   {
  50.     next(i);
  51.     return (<T>EQ(item, p(i)))? i : 0;
  52.   }
  53.   else if (cmp < 0)
  54.   {
  55.     int ind = p.Pix_to_index(i);
  56.     int l = ind;
  57.     int h = p.high();
  58.     while (l <= h)
  59.     {
  60.       int mid = (l + h) / 2;
  61.       cmp = <T>CMP(item, p[mid]);
  62.       if (cmp == 0)
  63.       {
  64.         while (mid > ind && <T>EQ(item, p[mid - 1])) --mid;
  65.         return p.index_to_Pix(mid);
  66.       }
  67.       else if (cmp < 0)
  68.         h = mid - 1;
  69.       else
  70.         l = mid + 1;
  71.     }
  72.     return 0;
  73.   }
  74.   else
  75.     return 0;
  76. }
  77.  
  78. int <T>OXPBag::nof(<T&> item)
  79. {
  80.   int l = p.low();
  81.   int h = p.high();
  82.   while (l <= h)
  83.   {
  84.     int mid = (l + h) / 2;
  85.     int cmp = <T>CMP(item, p[mid]);
  86.     if (cmp == 0)
  87.     {
  88.       l = h = mid;
  89.       while (l > p.low() && <T>EQ(item, p[l - 1])) --l;
  90.       while (h < p.high() && <T>EQ(item, p[h + 1])) ++h;
  91.       return h - l + 1;
  92.     }
  93.     else if (cmp < 0)
  94.       h = mid - 1;
  95.     else
  96.       l = mid + 1;
  97.   }
  98.   return 0;
  99. }
  100.  
  101. Pix <T>OXPBag::add(<T&> item)
  102. {
  103.   if (count == 0) 
  104.   {
  105.     ++count;
  106.     return p.index_to_Pix(p.add_high(item));
  107.   }
  108.   int l = p.low();
  109.   int h = p.high();
  110.   while (l <= h)
  111.   {
  112.     int mid = (l + h) / 2;
  113.     int cmp = <T>CMP(item, p[mid]);
  114.     if (cmp == 0)
  115.     {
  116.       l = mid;
  117.       break;
  118.     }
  119.     else if (cmp < 0)
  120.       h = mid - 1;
  121.     else
  122.       l = mid + 1;
  123.   }
  124.   // add on whichever side is shortest
  125.   ++count;
  126.   if (l == p.fence())
  127.     return p.index_to_Pix(p.add_high(item));
  128.   else if (l == p.low())
  129.     return p.index_to_Pix(p.add_low(item));
  130.   else 
  131.   {
  132.     if (p.high() - l < l - p.low())
  133.     {
  134.       h = p.add_high(p.high_element());
  135.       for (int i = h - 1; i > l; --i) p[i] = p[i-1];
  136.     }
  137.     else
  138.     {
  139.       --l;
  140.       h = p.add_low(p.low_element());
  141.       for (int i = h + 1; i < l; ++i) p[i] = p[i+1];
  142.     }
  143.     p[l] = item;
  144.     return p.index_to_Pix(l);
  145.   }
  146. }
  147.  
  148. void <T>OXPBag::del(<T&> item)
  149. {
  150.   int l = p.low();
  151.   int h = p.high();
  152.   while (l <= h)
  153.   {
  154.     int mid = (l + h) / 2;
  155.     int cmp = <T>CMP(item, p[mid]);
  156.     if (cmp == 0)
  157.     {
  158.       --count;
  159.       if (p.high() - mid < mid - p.low())
  160.       {
  161.         for (int i = mid; i < p.high(); ++i) p[i] = p[i+1];
  162.         p.del_high();
  163.       }
  164.       else
  165.       {
  166.         for (int i = mid; i > p.low(); --i) p[i] = p[i-1];
  167.         p.del_low();
  168.       }
  169.       return;
  170.     }
  171.     else if (cmp < 0)
  172.       h = mid - 1;
  173.     else
  174.       l = mid + 1;
  175.   }
  176. }
  177.  
  178. void <T>OXPBag::remove(<T&> item)
  179. {
  180.   int l = p.low();
  181.   int h = p.high();
  182.   while (l <= h)
  183.   {
  184.     int mid = (l + h) / 2;
  185.     int cmp = <T>CMP(item, p[mid]);
  186.     if (cmp == 0)
  187.     {
  188.       l = h = mid;
  189.       while (l > p.low() && <T>EQ(item, p[l - 1])) --l;
  190.       while (h < p.high() && <T>EQ(item, p[h + 1])) ++h;
  191.       int n = h - l + 1;
  192.       count -= n;
  193.       if (p.high() - h < l - p.low())
  194.       {
  195.         h = p.high() - n;
  196.         for (int i = l; i <= h; ++i) p[i] = p[i+n];
  197.         while (n-- > 0) p.del_high();
  198.       }
  199.       else
  200.       {
  201.         l = p.low() + n;
  202.         for (int i = h; i >= l; --i) p[i] = p[i-n];
  203.         while (n-- > 0) p.del_low();
  204.       }
  205.       return;
  206.     }
  207.     else if (cmp < 0)
  208.       h = mid - 1;
  209.     else
  210.       l = mid + 1;
  211.   }
  212. }
  213.  
  214. int <T>OXPBag::OK()
  215. {
  216.   int v = p.OK();
  217.   v &= count == p.length();
  218.   for (int i = p.low(); i < p.high(); ++i) v &= <T>CMP(p[i], p[i+1]) <= 0;
  219.   if (!v) error("invariant failure");
  220.   return v;
  221. }
  222.