home *** CD-ROM | disk | FTP | other *** search
/ NeXTSTEP 3.3 (Developer) / NeXT_Developer-3.3.iso / NextDeveloper / Headers / g++ / gen / XPlex.ccP < prev    next >
Encoding:
Text File  |  1995-02-06  |  8.0 KB  |  398 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>.XPlex.h"
  24.  
  25.  
  26. <T>XPlex:: <T>XPlex()
  27. {
  28.   lo = fnc = 0;
  29.   csize = DEFAULT_INITIAL_CAPACITY;
  30.   <T>* data = new <T>[csize];
  31.   set_cache(new <T>IChunk(data,  lo, lo, fnc, lo+csize));
  32.   hd = ch;
  33. }
  34.  
  35. <T>XPlex:: <T>XPlex(int chunksize)
  36. {
  37.   if (chunksize == 0) error("invalid constructor specification");
  38.   lo = fnc = 0;
  39.   if (chunksize > 0)
  40.   {
  41.     csize = chunksize;
  42.     <T>* data = new <T>[csize];
  43.     set_cache(new <T>IChunk(data,  lo, lo, fnc, csize));
  44.     hd = ch;
  45.   }
  46.   else
  47.   {
  48.     csize = -chunksize;
  49.     <T>* data = new <T>[csize];
  50.     set_cache(new <T>IChunk(data,  chunksize, lo, fnc, fnc));
  51.     hd = ch;
  52.   }
  53. }
  54.  
  55.  
  56. <T>XPlex:: <T>XPlex(int l, int chunksize)
  57. {
  58.   if (chunksize == 0) error("invalid constructor specification");
  59.   lo = fnc = l;
  60.   if (chunksize > 0)
  61.   {
  62.     csize = chunksize;
  63.     <T>* data = new <T>[csize];
  64.     set_cache(new <T>IChunk(data,  lo, lo, fnc, csize+lo));
  65.     hd = ch;
  66.   }
  67.   else
  68.   {
  69.     csize = -chunksize;
  70.     <T>* data = new <T>[csize];
  71.     set_cache(new <T>IChunk(data,  chunksize+lo, lo, fnc, fnc));
  72.     hd = ch;
  73.   }
  74. }
  75.  
  76. void <T>XPlex::make_initial_chunks(int up)
  77. {
  78.   int need = fnc - lo;
  79.   hd = 0;
  80.   if (up)
  81.   {
  82.     int l = lo;
  83.     do
  84.     {
  85.       int sz;
  86.       if (need >= csize)
  87.         sz = csize;
  88.       else
  89.         sz = need;
  90.       <T>* data = new <T> [csize];
  91.       <T>IChunk* h = new <T>IChunk(data,  l, l, l+sz, l+csize);
  92.       if (hd != 0)
  93.         h->link_to_next(hd);
  94.       else
  95.         hd = h;
  96.       l += sz;
  97.       need -= sz;
  98.     } while (need > 0);
  99.   }
  100.   else
  101.   {
  102.     int hi = fnc;
  103.     do
  104.     {
  105.       int sz;
  106.       if (need >= csize)
  107.         sz = csize;
  108.       else
  109.         sz = need;
  110.       <T>* data = new <T> [csize];
  111.       <T>IChunk* h = new <T>IChunk(data,  hi-csize, hi-sz, hi, hi);
  112.       if (hd != 0)
  113.         h->link_to_next(hd);
  114.       hd = h;
  115.       hi -= sz;
  116.       need -= sz;
  117.     } while (need > 0);
  118.   }
  119.   set_cache(hd);
  120. }
  121.  
  122. <T>XPlex:: <T>XPlex(int l, int hi, const <T&> initval, int chunksize)
  123. {
  124.   lo = l;
  125.   fnc = hi + 1;
  126.   if (chunksize == 0)
  127.   {
  128.     csize = fnc - l;
  129.     make_initial_chunks(1);
  130.   }
  131.   else if (chunksize < 0)
  132.   {
  133.     csize = -chunksize;
  134.     make_initial_chunks(0);
  135.   }
  136.   else
  137.   {
  138.     csize = chunksize;
  139.     make_initial_chunks(1);
  140.   }
  141.   fill(initval);
  142. }
  143.  
  144. <T>XPlex::<T>XPlex(const <T>XPlex& a)
  145. {
  146.   lo = a.lo;
  147.   fnc = a.fnc;
  148.   csize = a.csize;
  149.   make_initial_chunks();
  150.   for (int i = a.low(); i < a.fence(); a.next(i)) (*this)[i] = a[i];
  151. }
  152.  
  153. void <T>XPlex::operator= (const <T>XPlex& a)
  154. {
  155.   if (&a != this)
  156.   {
  157.     invalidate();
  158.     lo = a.lo;
  159.     fnc = a.fnc;
  160.     csize = a.csize;
  161.     make_initial_chunks();
  162.     for (int i = a.low(); i < a.fence(); a.next(i)) (*this)[i] = a[i];
  163.   }
  164. }
  165.  
  166.  
  167. void <T>XPlex::cache(int idx) const
  168. {
  169.   const <T>IChunk* tail = tl();
  170.   const <T>IChunk* t = ch;
  171.   while (idx >= t->fence_index())
  172.   {
  173.     if (t == tail) index_error();
  174.     t = (t->next());
  175.   }
  176.   while (idx < t->low_index())
  177.   {
  178.     if (t == hd) index_error();
  179.     t = (t->prev());
  180.   }
  181.   set_cache(t);
  182. }
  183.  
  184.  
  185. void <T>XPlex::cache(const <T>* p) const
  186. {
  187.   const <T>IChunk* old = ch;
  188.   const <T>IChunk* t = ch;
  189.   while (!t->actual_pointer(p))
  190.   {
  191.     t = (t->next());
  192.     if (t == old) index_error();
  193.   }
  194.   set_cache(t);
  195. }
  196.  
  197. int <T>XPlex::owns(Pix px) const
  198. {
  199.   <T>* p = (<T>*)px;
  200.   const <T>IChunk* old = ch;
  201.   const <T>IChunk* t = ch;
  202.   while (!t->actual_pointer(p))
  203.   {
  204.     t = (t->next());
  205.     if (t == old) { set_cache(t); return 0; }
  206.   }
  207.   set_cache(t);
  208.   return 1;
  209. }
  210.  
  211.  
  212. <T>* <T>XPlex::dosucc(const <T>* p) const
  213. {
  214.   if (p == 0) return 0;
  215.   const <T>IChunk* old = ch;
  216.   const <T>IChunk* t = ch;
  217.  
  218.   while (!t->actual_pointer(p))
  219.   {
  220.     t = (t->next());
  221.     if (t == old)  return 0;
  222.   }
  223.   int i = t->index_of(p) + 1;
  224.   if (i >= fnc) return 0;
  225.   if (i >= t->fence_index()) t = (t->next());
  226.   set_cache(t);
  227.   return (t->pointer_to(i));
  228. }
  229.  
  230. <T>* <T>XPlex::dopred(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->prev());
  238.     if (t == old) return 0;
  239.   }
  240.   int i = t->index_of(p) - 1;
  241.   if (i < lo) return 0;
  242.   if (i < t->low_index()) t = (t->prev());
  243.   set_cache(t);
  244.   return (t->pointer_to(i));
  245. }
  246.  
  247.  
  248. int <T>XPlex::add_high(const <T&> elem)
  249. {
  250.   <T>IChunk* t = tl();
  251.   if (!t->can_grow_high())
  252.   {
  253.     if (t-><T>IChunk::empty() && one_chunk())
  254.       t->clear(fnc);
  255.     else
  256.     {
  257.       <T>* data = new <T> [csize];
  258.       t = (new <T>IChunk(data,  fnc, fnc, fnc,fnc+csize));
  259.       t->link_to_prev(tl());
  260.     }
  261.   }
  262.   *((t-><T>IChunk::grow_high())) = elem;
  263.   set_cache(t);
  264.   return fnc++;
  265. }
  266.  
  267. int <T>XPlex::del_high ()
  268. {
  269.   if (empty()) empty_error();
  270.   <T>IChunk* t = tl();
  271.   t-><T>IChunk::shrink_high();
  272.   if (t-><T>IChunk::empty() && !one_chunk())
  273.   {
  274.     <T>IChunk* pred = t->prev();
  275.     del_chunk(t);
  276.     t = pred;
  277.   }
  278.   set_cache(t);
  279.   return --fnc - 1;
  280. }
  281.  
  282. int <T>XPlex::add_low (const <T&> elem)
  283. {
  284.   <T>IChunk* t = hd;
  285.   if (!t->can_grow_low())
  286.   {
  287.     if (t-><T>IChunk::empty() && one_chunk())
  288.       t->cleardown(lo);
  289.     else
  290.     {
  291.       <T>* data = new <T> [csize];
  292.       hd = new <T>IChunk(data,  lo-csize, lo, lo, lo);
  293.       hd->link_to_next(t);
  294.       t = hd;
  295.     }
  296.   }
  297.   *((t-><T>IChunk::grow_low())) = elem;
  298.   set_cache(t);
  299.   return --lo;
  300. }
  301.  
  302.  
  303. int <T>XPlex::del_low ()
  304. {
  305.   if (empty()) empty_error();
  306.   <T>IChunk* t = hd;
  307.   t-><T>IChunk::shrink_low();
  308.   if (t-><T>IChunk::empty() && !one_chunk())
  309.   {
  310.     hd = t->next();
  311.     del_chunk(t);
  312.     t = hd;
  313.   }
  314.   set_cache(t);
  315.   return ++lo;
  316. }
  317.  
  318. void <T>XPlex::reverse()
  319. {
  320.   <T> tmp;
  321.   int l = lo;
  322.   int h = fnc - 1;
  323.   <T>IChunk* loch = hd;
  324.   <T>IChunk* hich = tl();
  325.   while (l < h)
  326.   {
  327.     <T>* lptr = loch->pointer_to(l);
  328.     <T>* hptr = hich->pointer_to(h);
  329.     tmp = *lptr;
  330.     *lptr = *hptr;
  331.     *hptr = tmp;
  332.     if (++l >= loch->fence_index()) loch = loch->next();
  333.     if (--h < hich->low_index()) hich = hich->prev();
  334.   }
  335. }
  336.  
  337. void <T>XPlex::fill(const <T&> x)
  338. {
  339.   for (int i = lo; i < fnc; ++i) (*this)[i] = x;
  340. }
  341.  
  342. void <T>XPlex::fill(const <T&> x, int l, int hi)
  343. {
  344.   for (int i = l; i <= hi; ++i) (*this)[i] = x;
  345. }
  346.  
  347.  
  348. void <T>XPlex::clear()
  349. {
  350.   if (fnc != lo)
  351.   {
  352.     <T>IChunk* t = tl();
  353.     while (t != hd)
  354.     {
  355.       <T>IChunk* prv = t->prev();
  356.       del_chunk(t);
  357.       t = prv;
  358.     }
  359.     t-><T>IChunk::clear(lo);
  360.     set_cache(t);
  361.     fnc = lo;
  362.   }
  363. }
  364.  
  365.  
  366. int <T>XPlex::OK () const
  367. {
  368.   int v = hd != 0 && ch != 0;     // at least one chunk
  369.  
  370.   v &= fnc == tl()->fence_index();// last chunk fence == plex fence
  371.   v &= lo == ((hd))-><T>IChunk::low_index();    // first lo == plex lo
  372.  
  373. // loop for others:
  374.   int found_ch = 0;                   // to make sure ch is in list;
  375.   const <T>IChunk* t = (hd);
  376.   for (;;)
  377.   {
  378.     if (t == ch) ++found_ch;
  379.     v &= t-><T>IChunk::OK();              // each chunk is OK
  380.     if (t == tl())
  381.       break;
  382.     else                              // and has indices contiguous to succ
  383.     {
  384.       v &= t->top_index() == t->next()->base_index();
  385.       if (t != hd)                  // internal chunks full
  386.       {
  387.         v &= !t->empty();
  388.         v &= !t->can_grow_low();
  389.         v &= !t->can_grow_high();
  390.       }
  391.       t = t->next();
  392.     }
  393.   }
  394.   v &= found_ch == 1;
  395.   if (!v) error("invariant failure");
  396.   return v;
  397. }
  398.