home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 22 gnu / 22-gnu.zip / GNU_1OF3.ZIP / HEADERS.ZIP / g++-include / gen / List.hP < prev    next >
Encoding:
Text File  |  1992-03-06  |  5.9 KB  |  272 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.  
  20. #ifndef _<T>List_h
  21. #ifdef __GNUG__
  22. #pragma interface
  23. #endif
  24. #define _<T>List_h 1
  25.  
  26. #ifndef _<T>_typedefs
  27. #define _<T>_typedefs 1
  28. typedef void (*<T>Procedure)(<T&>);
  29. typedef <T>  (*<T>Mapper)(<T&>);
  30. typedef <T>  (*<T>Combiner)(<T&>, <T&>);
  31. typedef int  (*<T>Predicate)(<T&>);
  32. typedef int  (*<T>Comparator)(<T&>, <T&>);
  33. #endif
  34.  
  35. #include <Pix.h>
  36.  
  37. struct <T>ListNode
  38. {
  39.   <T>ListNode*          tl;
  40.   short                 ref;
  41.   <T>                   hd;
  42. };
  43.  
  44. extern <T>ListNode Nil<T>ListNode;
  45.  
  46. class <T>List
  47. {
  48. protected:
  49.   <T>ListNode*          P;
  50.  
  51.                         <T>List(<T>ListNode* p);
  52. public:
  53.                         <T>List();
  54.                         <T>List(<T&> head);
  55.                         <T>List(<T&> head, <T>List& tl);
  56.                         <T>List(<T>List& a);
  57.                         <T>List(Pix p);
  58.                         ~<T>List();
  59.  
  60.   <T>List&              operator = (<T>List& a);
  61.  
  62.   int                   null();
  63.   int                   valid();
  64.                         operator const void* ();
  65.   int                   operator ! ();
  66.  
  67.   int                   length();
  68.   int                   list_length();
  69.  
  70.   <T>&                  get();
  71.   <T>&                  head();
  72.   <T>&                  operator [] (int n);
  73.  
  74.   <T>List               nth(int n);
  75.   <T>List               tail();
  76.   <T>List               last();
  77.  
  78.   <T>List               find(<T&> targ);
  79.   <T>List               find(<T>List& targ);
  80.   int                   contains(<T&> targ);
  81.   int                   contains(<T>List& targ);
  82.   int                   position(<T&> targ);
  83.  
  84.   friend <T>List        copy(<T>List& a);
  85.   friend <T>List        concat(<T>List& a, <T>List& b);
  86.   friend <T>List        append(<T>List& a, <T>List& b);
  87.   friend <T>List        map(<T>Mapper f, <T>List& a);
  88.   friend <T>List        merge(<T>List& a, <T>List& b, <T>Comparator f);
  89.   friend <T>List        combine(<T>Combiner f, <T>List& a, <T>List& b);
  90.   friend <T>List        reverse(<T>List& a);
  91.   friend <T>List        select(<T>Predicate f, <T>List& a);        
  92.   friend <T>List        remove(<T&> targ, <T>List& a);
  93.   friend <T>List        remove(<T>Predicate f, <T>List& a);
  94.   friend <T>List        subst(<T&> old, <T&> repl, <T>List& a);
  95.  
  96.   void                  push(<T&> x);
  97.   <T>                   pop();
  98.  
  99.   void                  set_tail(<T>List& p);
  100.   void                  append(<T>List& p);
  101.   void                  prepend(<T>List& p);
  102.   void                  del(<T&> targ);
  103.   void                  del(<T>Predicate f);
  104.   void                  select(<T>Predicate f);
  105.   void                  subst(<T&> old, <T&> repl);
  106.   void                  reverse();
  107.   void                  sort(<T>Comparator f);
  108.  
  109.   void                  apply(<T>Procedure f);
  110.   <T>                   reduce(<T>Combiner f, <T&> base);
  111.  
  112.   friend int            operator == (<T>List& a, <T>List& b);
  113.   friend int            operator != (<T>List& a, <T>List& b);
  114.  
  115.   Pix                   first();
  116.   void                  next(Pix& p);
  117.   Pix                   seek(<T&> item);
  118.   <T>&                  operator () (Pix p);
  119.   int                   owns(Pix p);
  120.  
  121.   void                  error(const char*);
  122.   int                   OK();
  123. };
  124.  
  125.  
  126. inline void reference(<T>ListNode* p)
  127. {
  128.   if (p->ref >= 0) ++p->ref;
  129. }
  130.  
  131. inline void dereference(<T>ListNode* p)
  132. {
  133.   while (p->ref > 0 && --p->ref == 0)
  134.   {
  135.     <T>ListNode* n = p->tl;
  136.     delete(p);
  137.     p = n;
  138.   }
  139. }
  140.  
  141.  
  142. inline <T>ListNode* new<T>ListNode(<T&> h)
  143. {
  144.   <T>ListNode* p = new <T>ListNode;
  145.   p->ref = 1;
  146.   p->hd = h;
  147.   return p;
  148. }
  149.  
  150. inline <T>ListNode* new<T>ListNode(<T&> h, <T>ListNode* t)
  151. {
  152.   <T>ListNode* p = new <T>ListNode;
  153.   p->ref = 1;
  154.   p->hd = h;
  155.   p->tl = t;
  156.   return p;
  157. }
  158.  
  159.  
  160. inline <T>List::~<T>List()
  161. {
  162.   dereference(P);
  163. }
  164.  
  165. inline <T>List::<T>List()
  166. {
  167.   P = &Nil<T>ListNode;
  168. }
  169.  
  170. inline <T>List::<T>List(<T>ListNode* p)
  171. {
  172.   P = p;
  173. }
  174.  
  175. inline <T>List::<T>List(<T&> head)
  176. {
  177.   P = new<T>ListNode(head);
  178.   P->tl = &Nil<T>ListNode;
  179. }
  180.  
  181. inline <T>List::<T>List(<T&> head, <T>List& tl)
  182. {
  183.   P = new<T>ListNode(head, tl.P);
  184.   reference(P->tl);
  185. }
  186.  
  187. inline <T>List::<T>List(<T>List& a)
  188. {
  189.   reference(a.P);
  190.   P = a.P;
  191. }
  192.  
  193.  
  194. inline <T>& <T>List::get()
  195. {
  196.   return P->hd;
  197. }
  198.  
  199. inline <T>& <T>List::head()
  200. {
  201.   return P->hd;
  202. }
  203.  
  204.  
  205. inline <T>List <T>List::tail()
  206. {
  207.   reference(P->tl);
  208.   return <T>List(P->tl);
  209. }
  210.  
  211.  
  212.  
  213. inline int <T>List::null()
  214. {
  215.   return P == &Nil<T>ListNode;
  216. }
  217.  
  218. inline int <T>List::valid()
  219. {
  220.   return P != &Nil<T>ListNode;
  221. }
  222.  
  223. inline <T>List::operator const void* ()
  224. {
  225.   return (P == &Nil<T>ListNode)? 0 : this;
  226. }
  227.  
  228. inline int <T>List::operator ! ()
  229. {
  230.   return (P == &Nil<T>ListNode);
  231. }
  232.  
  233.  
  234. inline void <T>List::push(<T&> head)
  235. {
  236.   <T>ListNode* oldp = P;
  237.   P = new<T>ListNode(head, oldp);
  238. }
  239.  
  240.  
  241. inline int operator != (<T>List& x, <T>List& y)
  242. {
  243.   return !(x == y);
  244. }
  245.  
  246. inline Pix <T>List::first()
  247. {
  248.   return (P == &Nil<T>ListNode)? 0 : Pix(P);
  249. }
  250.  
  251. inline <T>& <T>List::operator () (Pix p)
  252. {
  253.   return ((<T>ListNode*)p)->hd;
  254. }
  255.  
  256. inline void <T>List::next(Pix& p)
  257. {
  258.   if (p != 0)
  259.   {
  260.     p = Pix(((<T>ListNode*)p)->tl);
  261.     if (p == &Nil<T>ListNode) p = 0;
  262.   }
  263. }
  264.  
  265. inline <T>List::<T>List(Pix p)
  266. {
  267.   P = (<T>ListNode*)p;
  268.   reference(P);
  269. }
  270.  
  271. #endif
  272.