home *** CD-ROM | disk | FTP | other *** search
/ NeXTSTEP 3.3 (Developer) / NeXT_Developer-3.3.iso / NextDeveloper / Headers / g++ / gen / RPlex.ccP < prev    next >
Encoding:
Text File  |  1995-02-06  |  9.9 KB  |  478 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.     based on code by Marc Shapiro (shapiro@sor.inria.fr)
  6.  
  7. This file is part of the GNU C++ Library.  This library is free
  8. software; you can redistribute it and/or modify it under the terms of
  9. the GNU Library General Public License as published by the Free
  10. Software Foundation; either version 2 of the License, or (at your
  11. option) any later version.  This library is distributed in the hope
  12. that it will be useful, but WITHOUT ANY WARRANTY; without even the
  13. implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
  14. PURPOSE.  See the GNU Library General Public License for more details.
  15. You should have received a copy of the GNU Library General Public
  16. License along with this library; if not, write to the Free Software
  17. Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
  18. */
  19.  
  20. #ifdef __GNUG__
  21. #pragma implementation
  22. #endif
  23. #include "<T>.RPlex.h"
  24.  
  25. typedef <T>IChunk* _<T>IChunk_ptr;
  26.  
  27. <T>RPlex:: <T>RPlex()
  28. {
  29.   lo = fnc = 0;
  30.   csize = DEFAULT_INITIAL_CAPACITY;
  31.   <T>* data = new <T>[csize];
  32.   set_cache(new <T>IChunk(data,  lo, lo, fnc, lo+csize));
  33.   hd = ch;
  34.   maxch = MIN_NCHUNKS;
  35.   lch = maxch / 2;
  36.   fch = lch + 1;
  37.   base = ch->base_index() - lch * csize;
  38.   chunks = new _<T>IChunk_ptr[maxch];
  39.   chunks[lch] = ch;
  40. }
  41.  
  42. <T>RPlex:: <T>RPlex(int chunksize)
  43. {
  44.   if (chunksize == 0) error("invalid constructor specification");
  45.   lo = fnc = 0;
  46.   if (chunksize > 0)
  47.   {
  48.     csize = chunksize;
  49.     <T>* data = new <T>[csize];
  50.     set_cache(new <T>IChunk(data,  lo, lo, fnc, csize+lo));
  51.     hd = ch;
  52.   }
  53.   else
  54.   {
  55.     csize = -chunksize;
  56.     <T>* data = new <T>[csize];
  57.     set_cache(new <T>IChunk(data,  chunksize+lo, lo, fnc, fnc));
  58.     hd = ch;
  59.   }
  60.   maxch = MIN_NCHUNKS;
  61.   lch = maxch / 2;
  62.   fch = lch + 1;
  63.   base = ch->base_index() - lch * csize;
  64.   chunks = new _<T>IChunk_ptr[maxch];
  65.   chunks[lch] = ch;
  66. }
  67.  
  68.  
  69. <T>RPlex:: <T>RPlex(int l, int chunksize)
  70. {
  71.   if (chunksize == 0) error("invalid constructor specification");
  72.   lo = fnc = l;
  73.   if (chunksize > 0)
  74.   {
  75.     csize = chunksize;
  76.     <T>* data = new <T>[csize];
  77.     set_cache(new <T>IChunk(data,  lo, lo, fnc, lo+csize));
  78.     hd = ch;
  79.   }
  80.   else
  81.   {
  82.     csize = -chunksize;
  83.     <T>* data = new <T>[csize];
  84.     set_cache(new <T>IChunk(data,  chunksize+lo, lo, fnc, fnc));
  85.     hd = ch;
  86.   }
  87.   maxch = MIN_NCHUNKS;
  88.   lch = maxch / 2;
  89.   fch = lch + 1;
  90.   base = ch->base_index() - lch * csize;
  91.   chunks = new _<T>IChunk_ptr[maxch];
  92.   chunks[lch] = ch;
  93. }
  94.  
  95. void <T>RPlex::make_initial_chunks(int up)
  96. {
  97.   int count = 0;
  98.   int need = fnc - lo;
  99.   hd = 0;
  100.   if (up)
  101.   {
  102.     int l = lo;
  103.     do
  104.     {
  105.       ++count;
  106.       int sz;
  107.       if (need >= csize)
  108.         sz = csize;
  109.       else
  110.         sz = need;
  111.       <T>* data = new <T> [csize];
  112.       <T>IChunk* h = new <T>IChunk(data,  l, l, l+sz, l+csize);
  113.       if (hd != 0)
  114.         h->link_to_next(hd);
  115.       else
  116.         hd = h;
  117.       l += sz;
  118.       need -= sz;
  119.     } while (need > 0);
  120.   }
  121.   else
  122.   {
  123.     int hi = fnc;
  124.     do
  125.     {
  126.       ++count;
  127.       int sz;
  128.       if (need >= csize)
  129.         sz = csize;
  130.       else
  131.         sz = need;
  132.       <T>* data = new <T> [csize];
  133.       <T>IChunk* h = new <T>IChunk(data,  hi-csize, hi-sz, hi, hi);
  134.       if (hd != 0)
  135.         h->link_to_next(hd);
  136.       hd = h;
  137.       hi -= sz;
  138.       need -= sz;
  139.     } while (need > 0);
  140.   }
  141.   set_cache((<T>IChunk*)hd);
  142.   
  143.   maxch = MIN_NCHUNKS;
  144.   if (maxch < count * 2)
  145.     maxch = count * 2;
  146.   chunks = new _<T>IChunk_ptr[maxch];
  147.   lch = maxch / 3;
  148.   fch = lch + count;
  149.   base = ch->base_index() - csize * lch;
  150.   int k = lch;
  151.   do
  152.   {
  153.     chunks[k++] = ch;
  154.     set_cache(ch->next());
  155.   } while (ch != hd);
  156. }
  157.  
  158. <T>RPlex:: <T>RPlex(int l, int hi, const <T&> initval, int chunksize)
  159. {
  160.   lo = l;
  161.   fnc = hi + 1;
  162.   if (chunksize == 0)
  163.   {
  164.     csize = fnc - l;
  165.     make_initial_chunks(1);
  166.   }
  167.   else if (chunksize < 0)
  168.   {
  169.     csize = -chunksize;
  170.     make_initial_chunks(0);
  171.   }
  172.   else
  173.   {
  174.     csize = chunksize;
  175.     make_initial_chunks(1);
  176.   }
  177.   fill(initval);
  178. }
  179.  
  180. <T>RPlex::<T>RPlex(const <T>RPlex& a)
  181. {
  182.   lo = a.lo;
  183.   fnc = a.fnc;
  184.   csize = a.csize;
  185.   make_initial_chunks();
  186.   for (int i = a.low(); i < a.fence(); a.next(i)) (*this)[i] = a[i];
  187. }
  188.  
  189. void <T>RPlex::operator= (const <T>RPlex& a)
  190. {
  191.   if (&a != this)
  192.   {
  193.     invalidate();
  194.     lo = a.lo;
  195.     fnc = a.fnc;
  196.     csize = a.csize;
  197.     make_initial_chunks();
  198.     for (int i = a.low(); i < a.fence(); a.next(i)) (*this)[i] = a[i];
  199.   }
  200. }
  201.  
  202.  
  203. void <T>RPlex::cache(const <T>* p) const
  204. {
  205.   const <T>IChunk* old = ch;
  206.   const <T>IChunk* t = ch;
  207.   while (!t->actual_pointer(p))
  208.   {
  209.     t = (t->next());
  210.     if (t == old) index_error();
  211.   }
  212.   set_cache(t);
  213. }
  214.  
  215. int <T>RPlex::owns(Pix px) const
  216. {
  217.   <T>* p = (<T>*)px;
  218.   const <T>IChunk* old = ch;
  219.   const <T>IChunk* t = ch;
  220.   while (!t->actual_pointer(p))
  221.   {
  222.     t = (t->next());
  223.     if (t == old) return 0;
  224.   }
  225.   set_cache(t);
  226.   return 1;
  227. }
  228.  
  229.  
  230. <T>* <T>RPlex::dosucc(const <T>* p) const
  231. {
  232.   if (p == 0) return 0;
  233.   const <T>IChunk* old = ch;
  234.   const <T>IChunk* t = ch;
  235.   while (!t->actual_pointer(p))
  236.   {
  237.     t = (t->next());
  238.     if (t == old) return 0;
  239.   }
  240.   int i = t->index_of(p) + 1;
  241.   if (i >= fnc) return 0;
  242.   if (i >= t->fence_index()) t = (t->next());
  243.   set_cache(t);
  244.   return t->pointer_to(i);
  245. }
  246.  
  247. <T>* <T>RPlex::dopred(const <T>* p) const
  248. {
  249.   if (p == 0) return 0;
  250.   const <T>IChunk* old = ch;
  251.   const <T>IChunk* t = ch;
  252.   while (!t->actual_pointer(p))
  253.   {
  254.     t = (t->prev());
  255.     if (t == old) return 0;
  256.   }
  257.   int i = t->index_of(p) - 1;
  258.   if (i < lo) return 0;
  259.   if (i < t->low_index()) t = (t->prev());
  260.   set_cache(t);
  261.   return (t->pointer_to(i));
  262. }
  263.  
  264. int <T>RPlex::add_high(const <T&> elem)
  265. {
  266.   <T>IChunk* t = tl();
  267.   if (!t->can_grow_high())
  268.   {
  269.     if (t-><T>IChunk::empty() && one_chunk())
  270.     {
  271.       t->clear(fnc);
  272.       base = t->base_index() - lch * csize;
  273.     }
  274.     else
  275.     {
  276.       <T>* data = new <T> [csize];
  277.       t = (new <T>IChunk(data,  fnc, fnc, fnc,fnc+csize));
  278.       t->link_to_prev(tl());
  279.       if (fch == maxch)
  280.       {
  281.         maxch *= 2;
  282.         <T>IChunk** newch = new _<T>IChunk_ptr [maxch];
  283.         memcpy(newch, chunks, fch * sizeof(_<T>IChunk_ptr));
  284.         delete chunks;
  285.         chunks = newch;
  286.       }
  287.       chunks[fch++] = t;
  288.     }
  289.   }
  290.   *((t-><T>IChunk::grow_high())) = elem;
  291.   set_cache(t);
  292.   return fnc++;
  293. }
  294.  
  295. int <T>RPlex::del_high ()
  296. {
  297.   if (empty()) empty_error();
  298.   <T>IChunk* t = tl();
  299.   if (t-><T>IChunk::empty()) // kill straggler first
  300.   {
  301.     <T>IChunk* pred = t->prev();
  302.     del_chunk(t);
  303.     t = (pred);
  304.     --fch;
  305.   }
  306.   t-><T>IChunk::shrink_high();
  307.   if (t-><T>IChunk::empty() && !one_chunk())
  308.   {
  309.     <T>IChunk* pred = t->prev();
  310.     del_chunk(t);
  311.     t = (pred);
  312.     --fch;
  313.   }
  314.   set_cache(t);
  315.   return --fnc - 1;
  316. }
  317.  
  318. int <T>RPlex::add_low (const <T&> elem)
  319. {
  320.   <T>IChunk* t = hd;
  321.   if (!t->can_grow_low())
  322.   {
  323.     if (t-><T>IChunk::empty() && one_chunk())
  324.     {
  325.       t->cleardown(lo);
  326.       base = t->base_index() - lch * csize;
  327.     }
  328.     else
  329.     {
  330.       <T>* data = new <T> [csize];
  331.       hd = new <T>IChunk(data,  lo-csize, lo, lo, lo);
  332.       hd->link_to_next(t);
  333.       t = ( hd);
  334.       if (lch == 0)
  335.       {
  336.         lch = maxch;
  337.         fch += maxch;
  338.         maxch *= 2;
  339.         <T>IChunk** newch = new _<T>IChunk_ptr [maxch];
  340.         memcpy(&(newch[lch]), chunks, lch * sizeof(_<T>IChunk_ptr));
  341.         delete chunks;
  342.         chunks = newch;
  343.         base = t->base_index() - (lch - 1) * csize;
  344.       }
  345.       chunks[--lch] = t;
  346.     }
  347.   }
  348.   *((t-><T>IChunk::grow_low())) = elem;
  349.   set_cache(t);
  350.   return --lo;
  351. }
  352.  
  353.  
  354. int <T>RPlex::del_low ()
  355. {
  356.   if (empty()) empty_error();
  357.   <T>IChunk* t = hd;
  358.   if (t-><T>IChunk::empty())
  359.   {
  360.     hd = t->next();
  361.     del_chunk(t);
  362.     t = hd;
  363.     ++lch;
  364.   }
  365.   t-><T>IChunk::shrink_low();
  366.   if (t-><T>IChunk::empty() && !one_chunk())
  367.   {
  368.     hd = t->next();
  369.     del_chunk(t);
  370.     t = hd;
  371.     ++lch;
  372.   }
  373.   set_cache(t);
  374.   return ++lo;
  375. }
  376.  
  377. void <T>RPlex::reverse()
  378. {
  379.   <T> tmp;
  380.   int l = lo;
  381.   int h = fnc - 1;
  382.   <T>IChunk* loch = hd;
  383.   <T>IChunk* hich = tl();
  384.   while (l < h)
  385.   {
  386.     <T>* lptr = loch->pointer_to(l);
  387.     <T>* hptr = hich->pointer_to(h);
  388.     tmp = *lptr;
  389.     *lptr = *hptr;
  390.     *hptr = tmp;
  391.     if (++l >= loch->fence_index()) loch = loch->next();
  392.     if (--h < hich->low_index()) hich = hich->prev();
  393.   }
  394. }
  395.  
  396. void <T>RPlex::fill(const <T&> x)
  397. {
  398.   for (int i = lo; i < fnc; ++i) (*this)[i] = x;
  399. }
  400.  
  401. void <T>RPlex::fill(const <T&> x, int lo, int hi)
  402. {
  403.   for (int i = lo; i <= hi; ++i) (*this)[i] = x;
  404. }
  405.  
  406.  
  407. void <T>RPlex::clear()
  408. {
  409.   for (int i = lch + 1; i < fch; ++i)
  410.     del_chunk(chunks[i]);
  411.   fch = lch + 1;
  412.   set_cache(chunks[lch]);
  413.   ch-><T>IChunk::clear(lo);
  414.   fnc = lo;
  415. }
  416.  
  417. int <T>RPlex::reset_low(int l)
  418. {
  419.   int old = lo;
  420.   int diff = l - lo;
  421.   if (diff != 0)
  422.   {
  423.     lo += diff;
  424.     fnc += diff;
  425.     <T>IChunk* t = hd;
  426.     do
  427.     {
  428.       t->re_index(t->low_index() + diff);
  429.       t = t->next();
  430.     } while (t != hd);
  431.   }
  432.   base = hd->base_index() - lch * csize;
  433.   return old;
  434. }
  435.  
  436.  
  437. int <T>RPlex::OK () const
  438. {
  439.   int v = hd != 0 && ch != 0;         // at least one chunk
  440.  
  441.   v &= fnc == tl()->fence_index();  // last chunk fnc == plex fnc
  442.   v &= lo == hd-><T>IChunk::low_index();    // first lo == plex lo
  443.  
  444.   v &= base == hd->base_index() - lch * csize; // base is correct;
  445.   v &= lch < fch;
  446.   v &= fch <= maxch;                  // within allocation;
  447.  
  448. // loop for others:
  449.  
  450.   int k = lch;                        // to cross-check nch
  451.  
  452.   int found_ch = 0;                   // to make sure ch is in list;
  453.   const <T>IChunk* t = (hd);
  454.   for (;;)
  455.   {
  456.     v &= chunks[k++] == t;             // each chunk is at proper index
  457.     if (t == ch) ++found_ch;
  458.     v &= t-><T>IChunk::OK();              // each chunk is OK
  459.     if (t == tl())
  460.       break;
  461.     else                              // and has indices contiguous to succ
  462.     {
  463.       v &= t->top_index() == t->next()->base_index();
  464.       if (t != hd)                  // internal chunks full
  465.       {
  466.         v &= !t->empty();
  467.         v &= !t->can_grow_low();
  468.         v &= !t->can_grow_high();
  469.       }
  470.       t = t->next();
  471.     }
  472.   }
  473.   v &= found_ch == 1;
  474.   v &= fch == k;
  475.   if (!v) error("invariant failure");
  476.   return v;
  477. }
  478.