home *** CD-ROM | disk | FTP | other *** search
/ NeXTSTEP 3.2 (Developer) / NS_dev_3.2.iso / NextDeveloper / Headers / g++ / gen / Plex.hP < prev    next >
Text File  |  1993-06-29  |  13KB  |  495 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. #ifndef _<T>Plex_h
  21. #ifdef __GNUG__
  22. #pragma interface
  23. #endif
  24. #define _<T>Plex_h 1
  25.  
  26. #include <std.h>
  27. #include <Pix.h>
  28. #include "<T>.defs.h"
  29.  
  30. // Plexes are made out of <T>IChunks
  31.  
  32. #include <stddef.h>
  33.  
  34. class <T>IChunk
  35. {
  36. //public: // kludge until C++ `protected' policies settled
  37. protected:      
  38.  
  39.   <T>*           data;           // data, from client
  40.  
  41.   int            base;           // lowest possible index
  42.   int            low;            // lowest valid index
  43.   int            fence;          // highest valid index + 1
  44.   int            top;            // highest possible index + 1
  45.  
  46.   <T>IChunk*     nxt;            // circular links
  47.   <T>IChunk*     prv;
  48.  
  49. public:
  50.  
  51. // constructors
  52.  
  53.                  <T>IChunk(<T>*     d,       // ptr to array of elements
  54.                         int      base_idx, // initial indices
  55.                         int      low_idx,  
  56.                         int      fence_idx,
  57.                         int      top_idx);
  58.  
  59.   virtual       ~<T>IChunk();
  60.  
  61. // status reports
  62.  
  63.   int            size() const;    // number of slots
  64.  
  65.   virtual int    empty() const ;
  66.   virtual int    full() const ; 
  67.  
  68.   int            can_grow_high () const ;  // there is space to add data
  69.   int            can_grow_low () const;        
  70.   
  71.   int            base_index() const;   // lowest possible index;
  72.   int            low_index() const;    // lowest actual index;
  73.   virtual int    first_index() const;  // lowest valid index or fence if none
  74.   virtual int    last_index() const;   // highest valid index or low-1 if none
  75.   int            fence_index() const;  // highest actual index + 1
  76.   int            top_index() const;    // highest possible index + 1
  77.  
  78. // indexing conversion
  79.  
  80.   int            possible_index(int i) const; // i between base and top
  81.   int            actual_index(int i) const;   // i between low and fence
  82.   virtual int    valid_index(int i) const;    // i not deleted (mainly for mchunks)
  83.  
  84.   int            possible_pointer(const <T>* p) const; // same for ptr
  85.   int            actual_pointer(const <T>* p) const; 
  86.   virtual int    valid_pointer(const <T>* p) const; 
  87.  
  88.   <T>*           pointer_to(int i) const ;   // pointer to data indexed by i
  89.                                       // caution: i is not checked for validity
  90.   int            index_of(const <T>* p) const; // index of data pointed to by p
  91.                                       // caution: p is not checked for validity
  92.  
  93.   virtual int    succ(int idx) const;     // next valid index or fence if none
  94.   virtual int    pred(int idx) const;     // previous index or low - 1 if none
  95.  
  96.   virtual <T>*   first_pointer() const;   // pointer to first valid pos or 0
  97.   virtual <T>*   last_pointer() const;    // pointer to first valid pos or 0
  98.   virtual <T>*   succ(<T>*  p) const;     // next pointer or 0
  99.   virtual <T>*   pred(<T>* p) const;     // previous pointer or 0
  100.  
  101. // modification
  102.  
  103.   virtual <T>*   grow_high ();      // return spot to add an element
  104.   virtual <T>*   grow_low ();  
  105.  
  106.   virtual void   shrink_high ();    // logically delete top index
  107.   virtual void   shrink_low ();     
  108.  
  109.   virtual void   clear(int lo);     // reset to empty ch with base = lo
  110.   virtual void   cleardown(int hi); // reset to empty ch with top = hi
  111.   void           re_index(int lo);  // re-index so lo is new low
  112.  
  113. // chunk traversal
  114.  
  115.   <T>IChunk*     next() const;
  116.   <T>IChunk*     prev() const;
  117.  
  118.   void           link_to_prev(<T>IChunk* prev);
  119.   void           link_to_next(<T>IChunk* next);
  120.   void           unlink();
  121.  
  122. // state checks
  123.  
  124.   <T>*           invalidate();     // mark self as invalid; return data
  125.                                    // for possible deletion
  126.  
  127.   virtual int    OK() const;             // representation invariant
  128.  
  129.   void   error(const char*) const;
  130.   void   empty_error() const;
  131.   void   full_error() const;
  132.   void   index_error() const;
  133. };
  134.  
  135. // <T>Plex is a partly `abstract' class: few of the virtuals
  136. // are implemented at the Plex level, only in the subclasses
  137.  
  138. class <T>Plex
  139. {
  140. protected:      
  141.  
  142.   <T>IChunk*       hd;          // a chunk holding the data
  143.   int              lo;          // lowest  index
  144.   int              fnc;         // highest index + 1
  145.   int              csize;       // size of the chunk
  146.  
  147.   void             invalidate();              // mark so OK() is false
  148.   void             del_chunk(<T>IChunk*);        // delete a chunk
  149.  
  150.   <T>IChunk*       tl() const;                // last chunk;
  151.   int              one_chunk() const;         // true if hd == tl()
  152.  
  153. public:
  154.  
  155. // constructors, etc.
  156.  
  157.                     <T>Plex();                  // no-op
  158.  
  159.   virtual           ~<T>Plex();
  160.  
  161.   
  162. // Access functions 
  163.     
  164.   virtual <T>&      operator [] (int idx) = 0; // access by index;
  165.   virtual <T>&      operator () (Pix p) = 0;   // access by Pix;
  166.  
  167.   virtual <T>&      high_element () = 0;      // access high element
  168.   virtual <T>&      low_element () = 0;       // access low element
  169.  
  170. // read-only versions for const Plexes
  171.  
  172.   virtual const <T>& operator [] (int idx) const = 0; // access by index;
  173.   virtual const <T>& operator () (Pix p) const = 0;   // access by Pix;
  174.  
  175.   virtual const <T>& high_element () const = 0;      // access high element
  176.   virtual const <T>& low_element () const = 0;       // access low element
  177.  
  178.  
  179. // Index functions
  180.  
  181.   virtual int       valid (int idx) const = 0;      // idx is an OK index
  182.  
  183.   virtual int       low() const = 0;         // lowest index or fence if none
  184.   virtual int       high() const = 0;        // highest index or low-1 if none
  185.  
  186.   int               ecnef() const;         // low limit index (low-1)
  187.   int               fence() const;         // high limit index (high+1)
  188.  
  189.   virtual void      prev(int& idx) const= 0; // set idx to preceding index
  190.                                           // caution: pred may be out of bounds
  191.  
  192.   virtual void      next(int& idx) const = 0;       // set to next index
  193.                                           // caution: succ may be out of bounds
  194.  
  195.   virtual Pix       first() const = 0;        // Pix to low element or 0
  196.   virtual Pix       last() const = 0;         // Pix to high element or 0
  197.   virtual void      prev(Pix& pix) const = 0;  // preceding pix or 0
  198.   virtual void      next(Pix& pix) const = 0;  // next pix or 0
  199.   virtual int       owns(Pix p) const = 0;     // p is an OK Pix
  200.  
  201. // index<->Pix 
  202.  
  203.   virtual int       Pix_to_index(Pix p) const = 0;   // get index via Pix
  204.   virtual Pix       index_to_Pix(int idx) const = 0; // Pix via index
  205.  
  206. // Growth
  207.  
  208.   virtual int       add_high(const <T&> elem) =0;// add new element at high end
  209.                                                 // return new high
  210.  
  211.   virtual int       add_low(const <T&> elem) = 0;   // add new low element,
  212.                                                 // return new low
  213.  
  214. // Shrinkage
  215.  
  216.   virtual int       del_high() = 0;           // remove the element at high end
  217.                                           // return new high
  218.   virtual int       del_low() = 0;        // delete low element, return new lo
  219.  
  220.                                           // caution: del_low/high
  221.                                           // does not necessarily 
  222.                                           // immediately call <T>::~<T>
  223.  
  224.  
  225. // operations on multiple elements
  226.  
  227.   virtual void      fill(const <T&> x);          // set all elements = x
  228.   virtual void      fill(const <T&> x, int from, int to); // fill from to to
  229.   virtual void      clear() = 0;                // reset to zero-sized Plex
  230.   virtual int       reset_low(int newlow); // change low index,return old
  231.   virtual void      reverse();                   // reverse in-place
  232.   virtual void      append(const <T>Plex& a);    // concatenate a copy
  233.   virtual void      prepend(const <T>Plex& a);   // prepend a copy
  234.  
  235. // status
  236.  
  237.   virtual int       can_add_high() const = 0;
  238.   virtual int       can_add_low() const = 0;
  239.   
  240.   int               length () const;       // number of slots
  241.  
  242.   int               empty () const;        // is the plex empty?
  243.   virtual int       full() const = 0;      // it it full?
  244.  
  245.   int               chunk_size() const;    // report chunk size;
  246.  
  247.   virtual int       OK() const = 0;        // representation invariant
  248.  
  249.   void            error(const char* msg) const;
  250.   void            index_error() const;
  251.   void            empty_error() const;
  252.   void            full_error() const;
  253. };
  254.  
  255.  
  256. // <T>IChunk ops
  257.  
  258. inline int <T>IChunk:: size() const
  259. {
  260.   return top - base;
  261. }
  262.  
  263.  
  264. inline int <T>IChunk:: base_index() const
  265. {
  266.   return base;
  267. }
  268.  
  269. inline  int <T>IChunk:: low_index() const
  270. {
  271.   return low;
  272. }
  273.  
  274. inline  int  <T>IChunk:: fence_index() const
  275. {
  276.   return fence;
  277. }
  278.  
  279. inline  int  <T>IChunk:: top_index() const
  280. {
  281.   return top;
  282. }
  283.  
  284. inline  <T>* <T>IChunk:: pointer_to(int i) const
  285. {
  286.   return &(data[i-base]);
  287. }
  288.  
  289. inline  int  <T>IChunk:: index_of(const <T>* p) const
  290. {
  291.   return ((int)p - (int)data) / sizeof(<T>) + base;
  292. }
  293.  
  294. inline  int  <T>IChunk:: possible_index(int i) const
  295. {
  296.   return i >= base && i < top;
  297. }
  298.  
  299. inline  int  <T>IChunk:: possible_pointer(const <T>* p) const
  300. {
  301.   return p >= data && p < &(data[top-base]);
  302. }
  303.  
  304. inline  int  <T>IChunk:: actual_index(int i) const
  305. {
  306.   return i >= low && i < fence;
  307. }
  308.  
  309. inline  int  <T>IChunk:: actual_pointer(const <T>* p) const
  310. {
  311.   return p >= data && p < &(data[fence-base]);
  312. }
  313.  
  314. inline  int  <T>IChunk:: can_grow_high () const
  315. {
  316.   return fence < top;
  317. }
  318.  
  319. inline  int  <T>IChunk:: can_grow_low () const
  320. {
  321.   return base < low;
  322. }
  323.  
  324. inline  <T>* <T>IChunk:: invalidate()
  325. {
  326.   <T>* p = data;
  327.   data = 0;
  328.   return p;
  329. }
  330.  
  331.  
  332. inline <T>IChunk* <T>IChunk::prev() const
  333. {
  334.   return prv;
  335. }
  336.  
  337. inline <T>IChunk* <T>IChunk::next() const
  338. {
  339.   return nxt;
  340. }
  341.  
  342. inline void <T>IChunk::link_to_prev(<T>IChunk* prev)
  343. {
  344.   nxt = prev->nxt;
  345.   prv = prev;
  346.   nxt->prv = this;
  347.   prv->nxt = this;
  348. }
  349.  
  350. inline void <T>IChunk::link_to_next(<T>IChunk* next)
  351. {
  352.   prv = next->prv;
  353.   nxt = next;
  354.   nxt->prv = this;
  355.   prv->nxt = this;
  356. }
  357.  
  358. inline void <T>IChunk::unlink()
  359. {
  360.   <T>IChunk* n = nxt;
  361.   <T>IChunk* p = prv;
  362.   n->prv = p;
  363.   p->nxt = n;
  364.   prv = nxt = this;
  365. }
  366.  
  367. inline  int <T>IChunk:: empty() const
  368. {
  369.   return low == fence;
  370. }
  371.  
  372. inline  int  <T>IChunk:: full() const
  373. {
  374.   return top - base == fence - low;
  375. }
  376.  
  377. inline int <T>IChunk:: first_index() const
  378. {
  379.   return (low == fence)? fence : low;
  380. }
  381.  
  382. inline int <T>IChunk:: last_index() const
  383. {
  384.   return (low == fence)? low - 1 : fence - 1;
  385. }
  386.  
  387. inline  int  <T>IChunk:: succ(int i) const
  388. {
  389.   return (i < low) ? low : i + 1;
  390. }
  391.  
  392. inline  int  <T>IChunk:: pred(int i) const
  393. {
  394.   return (i > fence) ? (fence - 1) : i - 1;
  395. }
  396.  
  397. inline  int  <T>IChunk:: valid_index(int i) const
  398. {
  399.   return i >= low && i < fence;
  400. }
  401.  
  402. inline  int  <T>IChunk:: valid_pointer(const <T>* p) const
  403. {
  404.   return p >= &(data[low - base]) && p < &(data[fence - base]);
  405. }
  406.  
  407. inline  <T>* <T>IChunk:: grow_high ()
  408. {
  409.   if (!can_grow_high()) full_error();
  410.   return &(data[fence++ - base]);
  411. }
  412.  
  413. inline  <T>* <T>IChunk:: grow_low ()
  414. {
  415.   if (!can_grow_low()) full_error();
  416.   return &(data[--low - base]);
  417. }
  418.  
  419. inline  void <T>IChunk:: shrink_high ()
  420. {
  421.   if (empty()) empty_error();
  422.   --fence;
  423. }
  424.  
  425. inline  void <T>IChunk:: shrink_low ()
  426. {
  427.   if (empty()) empty_error();
  428.   ++low;
  429. }
  430.  
  431. inline <T>* <T>IChunk::first_pointer() const
  432. {
  433.   return (low == fence)? 0 : &(data[low - base]);
  434. }
  435.  
  436. inline <T>* <T>IChunk::last_pointer() const
  437. {
  438.   return (low == fence)? 0 : &(data[fence - base - 1]);
  439. }
  440.  
  441. inline <T>* <T>IChunk::succ(<T>* p) const
  442. {
  443.   return ((p+1) <  &(data[low - base]) || (p+1) >= &(data[fence - base])) ? 
  444.     0 : (p+1);
  445. }
  446.  
  447. inline <T>* <T>IChunk::pred(<T>* p) const
  448. {
  449.   return ((p-1) <  &(data[low - base]) || (p-1) >= &(data[fence - base])) ? 
  450.     0 : (p-1);
  451. }
  452.  
  453.  
  454. // generic Plex operations
  455.  
  456. inline <T>Plex::<T>Plex() {}
  457.  
  458. inline int <T>Plex::chunk_size() const
  459. {
  460.   return csize;
  461. }
  462.  
  463. inline  int <T>Plex::ecnef () const
  464. {
  465.   return lo - 1;
  466. }
  467.  
  468.  
  469. inline  int <T>Plex::fence () const
  470. {
  471.   return fnc;
  472. }
  473.  
  474. inline int <T>Plex::length () const
  475. {
  476.   return fnc - lo;
  477. }
  478.  
  479. inline  int <T>Plex::empty () const
  480. {
  481.   return fnc == lo;
  482. }
  483.  
  484. inline <T>IChunk* <T>Plex::tl() const
  485. {
  486.   return hd->prev();
  487. }
  488.  
  489. inline int <T>Plex::one_chunk() const
  490. {
  491.   return hd == hd->prev();
  492. }
  493.  
  494. #endif
  495.