home *** CD-ROM | disk | FTP | other *** search
/ Geek Gadgets 1 / ADE-1.bin / ade-dist / libg++-2.7.1-bin.lha / lib / g++-include / gen / List.ccP < prev    next >
Text File  |  1996-10-12  |  18KB  |  973 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  17. */
  18.  
  19. #ifdef __GNUG__
  20. #pragma implementation
  21. #endif
  22. #include <builtin.h>
  23. #include "<T>.List.h"
  24.  
  25. <T>ListNode Nil<T>ListNode;
  26.  
  27. class init_Nil<T>ListNode
  28. {
  29. public:
  30.   init_Nil<T>ListNode() 
  31.   {
  32.     Nil<T>ListNode.tl = &Nil<T>ListNode;
  33.     Nil<T>ListNode.ref = -1;
  34.   }
  35. };
  36.  
  37. static init_Nil<T>ListNode Nil<T>ListNode_initializer;
  38.  
  39. <T>List& <T>List::operator = (const <T>List& a)
  40. {
  41.   reference(a.P);
  42.   dereference(P);
  43.   P = a.P;
  44.   return *this;
  45. }
  46.  
  47. <T> <T>List::pop()
  48. {
  49.   <T> res = P->hd;
  50.   <T>ListNode* tail = P->tl;
  51.   reference(tail);
  52.   dereference(P);
  53.   P = tail;
  54.   return res;
  55. }
  56.  
  57. void <T>List::set_tail(<T>List& a)
  58. {
  59.   reference(a.P);
  60.   dereference(P->tl);
  61.   P->tl = a.P;
  62. }
  63.  
  64. <T>List <T>List::nth(int n)
  65. {
  66.   <T>ListNode* p;
  67.   for ( p = P; n-- > 0; p = p->tl);
  68.   reference(p);
  69.   return <T>List(p);
  70. }
  71.  
  72. <T>List <T>List::last()
  73. {
  74.   <T>ListNode* p = P;
  75.   if (p != &Nil<T>ListNode) while (p->tl != &Nil<T>ListNode) p = p->tl;
  76.   reference(p);
  77.   return <T>List(p);
  78. }
  79.  
  80. void <T>List::append(<T>List& l)
  81. {
  82.   <T>ListNode* p = P;
  83.   <T>ListNode* a = l.P;
  84.   reference(a);
  85.   if (p != &Nil<T>ListNode)
  86.   {
  87.     while (p->tl != &Nil<T>ListNode) p = p->tl;
  88.     p->tl = a;
  89.   }
  90.   else
  91.     P = a;
  92. }
  93.  
  94. int <T>List::length()
  95. {
  96.   int l = 0;
  97.   for (<T>ListNode* p = P; p != &Nil<T>ListNode; p = p->tl) ++l;
  98.   return l;
  99. }
  100.  
  101. <T>&  <T>List::operator [] (int n)
  102. {
  103.   <T>ListNode* p;
  104.   for ( p = P; n-- > 0; p = p->tl);
  105.   return (p->hd);
  106. }
  107.  
  108. int operator == (const <T>List& x, const <T>List& y)
  109. {
  110.   <T>ListNode* a = x.P;
  111.   <T>ListNode* b = y.P;
  112.   
  113.   for (;;)
  114.   {
  115.     if (a == &Nil<T>ListNode)
  116.       return b == &Nil<T>ListNode;
  117.     else if (b == &Nil<T>ListNode)
  118.       return 0;
  119.     else if (<T>EQ(a->hd, b->hd))
  120.     {
  121.       a = a->tl;
  122.       b = b->tl;
  123.     }
  124.     else
  125.       return 0;
  126.   }
  127. }
  128.  
  129.  
  130. void <T>List::apply(<T>Procedure f)
  131. {
  132.   for(<T>ListNode* p = P; p != &Nil<T>ListNode; p = p->tl)
  133.     (*f)((p->hd));
  134. }
  135.  
  136. void <T>List::subst(<T&> old, <T&> repl)
  137. {
  138.   for(<T>ListNode* p = P; p != &Nil<T>ListNode; p = p->tl)
  139.     if (<T>EQ(p->hd, old))
  140.       p->hd = repl;
  141. }
  142.  
  143. <T> <T>List::reduce(<T>Combiner f, <T&> base)
  144. {
  145.   <T> r = base;
  146.   for(<T>ListNode* p = P; p != &Nil<T>ListNode; p = p->tl)
  147.     r = (*f)(r, (p->hd));
  148.   return r;
  149. }
  150.  
  151. int <T>List::position(<T&> targ)
  152. {
  153.   int l = 0;
  154.   <T>ListNode* p = P;
  155.   for (;;)
  156.   {
  157.     if (p == &Nil<T>ListNode)
  158.       return -1;
  159.     else if (<T>EQ(p->hd, targ))
  160.       return l;
  161.     else
  162.     {
  163.       ++l;
  164.       p = p->tl;
  165.     }
  166.   }
  167. }
  168.  
  169. int <T>List::contains(<T&> targ)
  170. {
  171.   <T>ListNode* p = P;
  172.   for (;;)
  173.   {
  174.     if (p == &Nil<T>ListNode)
  175.       return 0;
  176.     else if (<T>EQ(p->hd, targ))
  177.       return 1;
  178.     else
  179.       p = p->tl;
  180.   }
  181. }
  182.  
  183. <T>List <T>List::find(<T&> targ)
  184. {
  185.   <T>ListNode* p = P;
  186.   while (p != &Nil<T>ListNode && !<T>EQ(p->hd, targ))
  187.     p=p->tl;
  188.   reference(p);
  189.   return <T>List(p);
  190. }
  191.  
  192. Pix <T>List::seek(<T&> targ) const
  193. {
  194.   const <T>ListNode* p = P; 
  195.   for (;;)
  196.   {
  197.     if (p == &Nil<T>ListNode)
  198.       return 0;
  199.     else if (<T>EQ(p->hd, targ))
  200.       return Pix(p);
  201.     else
  202.       p = p->tl;
  203.   }
  204. }
  205.  
  206. int <T>List::owns(Pix i)
  207. {
  208.   <T>ListNode* p = P; 
  209.   for (;;)
  210.   {
  211.     if (p == &Nil<T>ListNode)
  212.       return 0;
  213.     else if (Pix(p) == i)
  214.       return 1;
  215.     else
  216.       p = p->tl;
  217.   }
  218. }
  219.  
  220. <T>List <T>List::find(<T>List& target)
  221. {
  222.   <T>ListNode* targ = target.P;
  223.   if (targ == &Nil<T>ListNode)
  224.     return <T>List(targ);
  225.  
  226.   <T>ListNode* p = P;
  227.   while (p != &Nil<T>ListNode)
  228.   {
  229.     if (<T>EQ(p->hd, targ->hd))
  230.     {
  231.       <T>ListNode* a = p->tl;
  232.       <T>ListNode* t = targ->tl;
  233.       for(;;)
  234.       {
  235.         if (t == &Nil<T>ListNode)
  236.         {
  237.           reference(p);
  238.           return <T>List(p);
  239.         }
  240.         else if (a == &Nil<T>ListNode || !<T>EQ(a->hd, t->hd))
  241.           break;
  242.         else
  243.         {
  244.           a = a->tl;
  245.           t = t->tl;
  246.         }
  247.       }
  248.     }
  249.     p = p->tl;
  250.   }
  251.   return <T>List(&Nil<T>ListNode);
  252. }
  253.  
  254. int <T>List::contains(<T>List& target)
  255. {
  256.   <T>ListNode* targ = target.P;
  257.   if (targ == &Nil<T>ListNode)
  258.     return 0;
  259.  
  260.   <T>ListNode* p = P;
  261.   while (p != &Nil<T>ListNode)
  262.   {
  263.     if (<T>EQ(p->hd, targ->hd))
  264.     {
  265.       <T>ListNode* a = p->tl;
  266.       <T>ListNode* t = targ->tl;
  267.       for(;;)
  268.       {
  269.         if (t == &Nil<T>ListNode)
  270.           return 1;
  271.         else if (a == &Nil<T>ListNode || !<T>EQ(a->hd, t->hd))
  272.           break;
  273.         else
  274.         {
  275.           a = a->tl;
  276.           t = t->tl;
  277.         }
  278.       }
  279.     }
  280.     p = p->tl;
  281.   }
  282.   return 0;
  283. }
  284.  
  285. void <T>List::del(<T&> targ)
  286. {
  287.   <T>ListNode* h = P;
  288.   // Former bug: targ can be a reference to a element in this list
  289.   // So do not dereference a element if targ is the element,
  290.   // until targ is no longer needed, as dereferencing it may destroy it.
  291.   <T>ListNode* to_be_dereferenced = 0;
  292.  
  293.   for (;;)
  294.   {
  295.     if (h == &Nil<T>ListNode)
  296.     {
  297.       P = h;
  298.       if (to_be_dereferenced)
  299.     dereference(to_be_dereferenced);
  300.       return;
  301.     }
  302.     else if (<T>EQ(h->hd, targ))
  303.     {
  304.       <T>ListNode* nxt = h->tl;
  305.       reference(nxt);
  306.       if ((&targ == &h->hd) && (to_be_dereferenced == 0))
  307.     to_be_dereferenced = h;
  308.       else
  309.         dereference(h);
  310.       h = nxt;
  311.     }
  312.     else
  313.       break;
  314.   }
  315.  
  316.   <T>ListNode* trail = h;
  317.   <T>ListNode* p = h->tl;
  318.   while (p != &Nil<T>ListNode)
  319.   {
  320.     if (<T>EQ(p->hd, targ))
  321.     {
  322.       <T>ListNode* nxt = p->tl;
  323.       reference(nxt);
  324.       if ((&targ == &p->hd) && (to_be_dereferenced == 0))
  325.     to_be_dereferenced = p;
  326.       else
  327.         dereference(p);
  328.       trail->tl = nxt;
  329.       p = nxt;
  330.     }
  331.     else
  332.     {
  333.       trail = p;
  334.       p = p->tl;
  335.     }
  336.   }
  337.   P = h;
  338.   if (to_be_dereferenced)
  339.     dereference(to_be_dereferenced);
  340. }
  341.  
  342. void <T>List::del(<T>Predicate f)
  343. {
  344.   <T>ListNode* h = P;
  345.   for (;;)
  346.   {
  347.     if (h == &Nil<T>ListNode)
  348.     {
  349.       P = h;
  350.       return;
  351.     }
  352.     else if ((*f)(h->hd))
  353.     {
  354.       <T>ListNode* nxt = h->tl;
  355.       reference(nxt);
  356.       dereference(h);
  357.       h = nxt;
  358.     }
  359.     else
  360.       break;
  361.   }
  362.  
  363.   <T>ListNode* trail = h;
  364.   <T>ListNode* p = h->tl;
  365.   while (p != &Nil<T>ListNode)
  366.   {
  367.     if ((*f)(p->hd))
  368.     {
  369.       <T>ListNode* nxt = p->tl;
  370.       reference(nxt);
  371.       dereference(p);
  372.       trail->tl = nxt;
  373.       p = nxt;
  374.     }
  375.     else
  376.     {
  377.       trail = p;
  378.       p = p->tl;
  379.     }
  380.   }
  381.   P = h;
  382. }
  383.  
  384. void <T>List::select(<T>Predicate f)
  385. {
  386.   <T>ListNode* h = P;
  387.   for (;;)
  388.   {
  389.     if (h == &Nil<T>ListNode)
  390.     {
  391.       P = h;
  392.       return;
  393.     }
  394.     else if (!(*f)(h->hd))
  395.     {
  396.       <T>ListNode* nxt = h->tl;
  397.       reference(nxt);
  398.       dereference(h);
  399.       h = nxt;
  400.     }
  401.     else
  402.       break;
  403.   }
  404.   <T>ListNode* trail = h;
  405.   <T>ListNode* p = h->tl;
  406.   while (p != &Nil<T>ListNode)
  407.   {
  408.     if (!(*f)(p->hd))
  409.     {
  410.       <T>ListNode* nxt = p->tl;
  411.       reference(nxt);
  412.       dereference(p);
  413.       trail->tl = nxt;
  414.       p = nxt;
  415.     }
  416.     else
  417.     {
  418.       trail = p;
  419.       p = p->tl;
  420.     }
  421.   }
  422.   P = h;
  423. }
  424.  
  425. void <T>List::reverse()
  426. {
  427.   <T>ListNode* l = &Nil<T>ListNode;
  428.   <T>ListNode* p = P; 
  429.   while (p != &Nil<T>ListNode)
  430.   {
  431.     <T>ListNode* nxt = p->tl;
  432.     p->tl = l;
  433.     l = p;
  434.     p = nxt;
  435.   }
  436.   P = l;
  437. }
  438.  
  439.  
  440. <T>List copy(const <T>List& x)
  441. {
  442.   const <T>ListNode* a = x.P;
  443.   if (a == &Nil<T>ListNode)
  444.     return <T>List(&Nil<T>ListNode);
  445.   else
  446.   {
  447.     <T>ListNode* h = new<T>ListNode(a->hd);
  448.     <T>ListNode* trail = h;
  449.     for(a = a->tl; a != &Nil<T>ListNode; a = a->tl)
  450.     {
  451.       <T>ListNode* n = new<T>ListNode(a->hd);
  452.       trail->tl = n;
  453.       trail = n;
  454.     }
  455.     trail->tl = &Nil<T>ListNode;
  456.     return <T>List(h);
  457.   }
  458. }
  459.  
  460.  
  461. <T>List subst(<T&> old, <T&> repl, <T>List& x)
  462. {
  463.   <T>ListNode* a = x.P;
  464.   if (a == &Nil<T>ListNode)
  465.     return <T>List(a);
  466.   else
  467.   {
  468.     <T>ListNode* h = new <T>ListNode;
  469.     h->ref = 1;
  470.     if (<T>EQ(a->hd, old))
  471.       h->hd = repl;
  472.     else
  473.       h->hd = a->hd;
  474.     <T>ListNode* trail = h;
  475.     for(a = a->tl; a != &Nil<T>ListNode; a = a->tl)
  476.     {
  477.       <T>ListNode* n = new <T>ListNode;
  478.       n->ref = 1;
  479.       if (<T>EQ(a->hd, old))
  480.         n->hd = repl;
  481.       else
  482.         n->hd = a->hd;
  483.       trail->tl = n;
  484.       trail = n;
  485.     }
  486.     trail->tl = &Nil<T>ListNode;
  487.     return <T>List(h);
  488.   }
  489. }
  490.  
  491. <T>List combine(<T>Combiner f, <T>List& x, <T>List& y)
  492. {
  493.   <T>ListNode* a = x.P;
  494.   <T>ListNode* b = y.P;
  495.   if (a == &Nil<T>ListNode || b == &Nil<T>ListNode)
  496.     return <T>List(&Nil<T>ListNode);
  497.   else
  498.   {
  499.     <T>ListNode* h = new<T>ListNode((*f)(a->hd, b->hd));
  500.     <T>ListNode* trail = h;
  501.     a = a->tl;
  502.     b = b->tl;
  503.     while (a != &Nil<T>ListNode && b != &Nil<T>ListNode)
  504.     {
  505.       <T>ListNode* n = new<T>ListNode((*f)(a->hd, b->hd));
  506.       trail->tl = n;
  507.       trail = n;
  508.       a = a->tl;
  509.       b = b->tl;
  510.     }
  511.     trail->tl = &Nil<T>ListNode;
  512.     return <T>List(h);
  513.   }
  514. }
  515.  
  516. <T>List reverse(<T>List& x)
  517. {
  518.   <T>ListNode* a = x.P;
  519.   if (a == &Nil<T>ListNode)
  520.     return <T>List(a);
  521.   else
  522.   {
  523.     <T>ListNode* l = new<T>ListNode(a->hd);
  524.     l->tl = &Nil<T>ListNode;
  525.     for(a = a->tl; a != &Nil<T>ListNode; a = a->tl)
  526.     {
  527.       <T>ListNode* n = new<T>ListNode(a->hd);
  528.       n->tl = l;
  529.       l = n;
  530.     }
  531.     return <T>List(l);
  532.   }
  533. }
  534.  
  535. <T>List append(<T>List& x, <T>List& y)
  536. {
  537.   <T>ListNode* a = x.P;
  538.   <T>ListNode* b = y.P;
  539.   reference(b);
  540.   if (a != &Nil<T>ListNode)
  541.   {
  542.     <T>ListNode* h = new<T>ListNode(a->hd);
  543.     <T>ListNode* trail = h;
  544.     for(a = a->tl; a != &Nil<T>ListNode; a = a->tl)
  545.     {
  546.       <T>ListNode* n = new<T>ListNode(a->hd);
  547.       trail->tl = n;
  548.       trail = n;
  549.     }
  550.     trail->tl = b;
  551.     return <T>List(h);
  552.   }
  553.   else
  554.     return <T>List(b);
  555. }
  556.  
  557. void <T>List::prepend(<T>List& y)
  558. {
  559.   <T>ListNode* b = y.P;
  560.   if (b != &Nil<T>ListNode)
  561.   {
  562.     <T>ListNode* h = new<T>ListNode(b->hd);
  563.     <T>ListNode* trail = h;
  564.     for(b = b->tl; b != &Nil<T>ListNode; b = b->tl)
  565.     {
  566.       <T>ListNode* n = new<T>ListNode(b->hd);
  567.       trail->tl = n;
  568.       trail = n;
  569.     }
  570.     trail->tl = P;
  571.     P = h;
  572.   }
  573. }
  574.  
  575. <T>List concat(<T>List& x, <T>List& y)
  576. {
  577.   <T>ListNode* a = x.P;
  578.   <T>ListNode* b = y.P;
  579.   if (a != &Nil<T>ListNode)
  580.   {
  581.     <T>ListNode* h = new<T>ListNode(a->hd);
  582.     <T>ListNode* trail = h;
  583.     for(a = a->tl; a != &Nil<T>ListNode; a = a->tl)
  584.     {
  585.       <T>ListNode* n = new<T>ListNode(a->hd);
  586.       trail->tl = n;
  587.       trail = n;
  588.     };
  589.     for(;b != &Nil<T>ListNode; b = b->tl)
  590.     {
  591.       <T>ListNode* n = new<T>ListNode(b->hd);
  592.       trail->tl = n;
  593.       trail = n;
  594.     }
  595.     trail->tl = &Nil<T>ListNode;
  596.     return <T>List(h);
  597.   }
  598.   else if (b != &Nil<T>ListNode)
  599.   {
  600.     <T>ListNode* h = new<T>ListNode(b->hd);
  601.     <T>ListNode* trail = h;
  602.     for(b = b->tl; b != &Nil<T>ListNode; b = b->tl)
  603.     {
  604.       <T>ListNode* n = new<T>ListNode(b->hd);
  605.       trail->tl = n;
  606.       trail = n;
  607.     }
  608.     trail->tl = &Nil<T>ListNode;
  609.     return <T>List(h);
  610.   }
  611.   else
  612.     return <T>List(&Nil<T>ListNode);
  613. }
  614.  
  615. <T>List select(<T>Predicate f, <T>List& x)
  616. {
  617.   <T>ListNode* a = x.P;
  618.   <T>ListNode* h = &Nil<T>ListNode;
  619.   while (a != &Nil<T>ListNode)
  620.   {
  621.     if ((*f)(a->hd))
  622.     {
  623.       h = new<T>ListNode(a->hd);
  624.       <T>ListNode* trail = h;
  625.       for(a = a->tl; a != &Nil<T>ListNode; a = a->tl)
  626.       {
  627.         if ((*f)(a->hd))
  628.         {
  629.           <T>ListNode* n = new<T>ListNode(a->hd);
  630.           trail->tl = n;
  631.           trail = n;
  632.         }
  633.       }
  634.       trail->tl = &Nil<T>ListNode;
  635.       break;
  636.     }
  637.     else
  638.       a = a->tl;
  639.   }
  640.   return <T>List(h);
  641. }
  642.  
  643. <T>List remove(<T>Predicate f, <T>List& x)
  644. {
  645.   <T>ListNode* a = x.P;
  646.   <T>ListNode* h = &Nil<T>ListNode;
  647.   while (a != &Nil<T>ListNode)
  648.   {
  649.     if (!(*f)(a->hd))
  650.     {
  651.       h = new<T>ListNode(a->hd);
  652.       <T>ListNode* trail = h;
  653.       for(a = a->tl; a != &Nil<T>ListNode; a = a->tl)
  654.       {
  655.         if (!(*f)(a->hd))
  656.         {
  657.           <T>ListNode* n = new<T>ListNode(a->hd);
  658.           trail->tl = n;
  659.           trail = n;
  660.         }
  661.       }
  662.       trail->tl = &Nil<T>ListNode;
  663.       break;
  664.     }
  665.     else
  666.       a = a->tl;
  667.   }
  668.   return <T>List(h);
  669. }
  670.  
  671. <T>List remove(<T&> targ, <T>List& x)
  672. {
  673.   <T>ListNode* a = x.P;
  674.   <T>ListNode* h = &Nil<T>ListNode;
  675.   while (a != &Nil<T>ListNode)
  676.   {
  677.     if (!(<T>EQ(a->hd, targ)))
  678.     {
  679.       h = new<T>ListNode(a->hd);
  680.       <T>ListNode* trail = h;
  681.       for(a = a->tl; a != &Nil<T>ListNode; a = a->tl)
  682.       {
  683.         if (!<T>EQ(a->hd, targ))
  684.         {
  685.           <T>ListNode* n = new<T>ListNode(a->hd);
  686.           trail->tl = n;
  687.           trail = n;
  688.         }
  689.       }
  690.       trail->tl = &Nil<T>ListNode;
  691.       break;
  692.     }
  693.     else
  694.       a = a->tl;
  695.   }
  696.   return <T>List(h);
  697. }
  698.  
  699. <T>List map(<T>Mapper f, <T>List& x)
  700. {
  701.   <T>ListNode* a = x.P;
  702.   <T>ListNode* h = &Nil<T>ListNode;
  703.   if (a != &Nil<T>ListNode)
  704.   {
  705.     h = new<T>ListNode((*f)(a->hd));
  706.     <T>ListNode* trail = h;
  707.     for(a = a->tl; a != &Nil<T>ListNode; a = a->tl)
  708.     {
  709.       <T>ListNode* n = new<T>ListNode((*f)(a->hd));
  710.       trail->tl = n;
  711.       trail = n;
  712.     }
  713.     trail->tl = &Nil<T>ListNode;
  714.   }
  715.   return <T>List(h);
  716. }
  717.  
  718.  
  719. <T>List merge(<T>List& x, <T>List& y, <T>Comparator f)
  720. {
  721.   <T>ListNode* a = x.P;
  722.   <T>ListNode* b = y.P;
  723.  
  724.   if (a == &Nil<T>ListNode)
  725.   {
  726.     if (b == &Nil<T>ListNode)
  727.       return <T>List(&Nil<T>ListNode);
  728.     else
  729.       return copy(y);
  730.   }
  731.   else if (b == &Nil<T>ListNode)
  732.     return copy(x);
  733.  
  734.   <T>ListNode* h = new <T>ListNode;
  735.   h->ref = 1;
  736.   if ((*f)(a->hd, b->hd) <= 0)
  737.   {
  738.     h->hd = a->hd;
  739.     a = a->tl;
  740.   }
  741.   else
  742.   {
  743.     h->hd = b->hd;
  744.     b = b->tl;
  745.   }
  746.  
  747.   <T>ListNode* r = h;
  748.  
  749.   for(;;)
  750.   {
  751.     if (a == &Nil<T>ListNode)
  752.     {
  753.       while (b != &Nil<T>ListNode)
  754.       {
  755.         <T>ListNode* n = new <T>ListNode;
  756.         n->ref = 1;
  757.         n->hd = b->hd;
  758.         r->tl = n;
  759.         r = n;
  760.         b = b->tl;
  761.       }
  762.       r->tl = &Nil<T>ListNode;
  763.       return <T>List(h);
  764.     }
  765.     else if (b == &Nil<T>ListNode)
  766.     {
  767.       while (a != &Nil<T>ListNode)
  768.       {
  769.         <T>ListNode* n = new <T>ListNode;
  770.         n->ref = 1;
  771.         n->hd = a->hd;
  772.         r->tl = n;
  773.         r = n;
  774.         a = a->tl;
  775.       }
  776.       r->tl = &Nil<T>ListNode;
  777.       return <T>List(h);
  778.     }
  779.     else if ((*f)(a->hd, b->hd) <= 0)
  780.     {
  781.       <T>ListNode* n = new <T>ListNode;
  782.       n->ref = 1;
  783.       n->hd = a->hd;
  784.       r->tl = n;
  785.       r = n;
  786.       a = a->tl;
  787.     }
  788.     else
  789.     {
  790.       <T>ListNode* n = new <T>ListNode;
  791.       n->ref = 1;
  792.       n->hd = b->hd;
  793.       r->tl = n;
  794.       r = n;
  795.       b = b->tl;
  796.     }
  797.   }
  798. }
  799.  
  800. void <T>List::sort(<T>Comparator f)
  801. {
  802.   // strategy: place runs in queue, merge runs until done
  803.   // This is often very fast
  804.  
  805.   if (P == &Nil<T>ListNode || P->tl == &Nil<T>ListNode)
  806.     return;
  807.  
  808.   int qlen = 250;   // guess a good queue size, realloc if necessary
  809.  
  810.   <T>ListNode** queue = (<T>ListNode**)malloc(qlen * sizeof(<T>ListNode*));
  811.  
  812.   <T>ListNode* h = P;
  813.   <T>ListNode* a = h;
  814.   <T>ListNode* b = a->tl;
  815.   int qin = 0;
  816.  
  817.   while (b != &Nil<T>ListNode)
  818.   {
  819.     if ((*f)(a->hd, b->hd) > 0)
  820.     {
  821.       if (h == a)               // minor optimization: ensure runlen >= 2
  822.       {
  823.         h = b;
  824.         a->tl = b->tl;
  825.         b->tl = a;
  826.         b = a->tl;
  827.       }
  828.       else
  829.       {
  830.         if (qin >= qlen)
  831.         {
  832.           qlen *= 2;
  833.           queue = (<T>ListNode**)realloc(queue, qlen * sizeof(<T>ListNode*));
  834.         }
  835.         queue[qin++] = h;
  836.         a->tl = &Nil<T>ListNode;
  837.         h = a = b;
  838.         b = b->tl;
  839.       }
  840.     }
  841.     else
  842.     {
  843.       a = b;
  844.       b = b->tl;
  845.     }
  846.   }
  847.  
  848.   int count = qin;
  849.   queue[qin] = h;
  850.   if (++qin >= qlen) qin = 0;
  851.   int qout = 0;
  852.  
  853.   while (count-- > 0)
  854.   {
  855.     a = queue[qout];
  856.     if (++qout >= qlen) qout = 0;
  857.     b = queue[qout];
  858.     if (++qout >= qlen) qout = 0;
  859.  
  860.     if ((*f)(a->hd, b->hd) <= 0)
  861.     {
  862.       h = a;
  863.       a = a->tl;
  864.     }
  865.     else
  866.     {
  867.       h = b;
  868.       b = b->tl;
  869.     }
  870.     queue[qin] = h;
  871.     if (++qin >= qlen) qin = 0;
  872.  
  873.     for (;;)
  874.     {
  875.       if (a == &Nil<T>ListNode)
  876.       {
  877.         h->tl = b;
  878.         break;
  879.       }
  880.       else if (b == &Nil<T>ListNode)
  881.       {
  882.         h->tl = a;
  883.         break;
  884.       }
  885.       else if ((*f)(a->hd, b->hd) <= 0)
  886.       {
  887.         h->tl = a;
  888.         h = a;
  889.         a = a->tl;
  890.       }
  891.       else
  892.       {
  893.         h->tl = b;
  894.         h = b;
  895.         b = b->tl;
  896.       }
  897.     }
  898.   }
  899.   P = queue[qout];
  900.   free(queue);
  901. }
  902.     
  903. int <T>List::list_length()
  904. {
  905.   <T>ListNode* fast = P;
  906.   if (fast == &Nil<T>ListNode)
  907.     return 0;
  908.  
  909.   <T>ListNode* slow = fast->tl;
  910.   if (slow == &Nil<T>ListNode)
  911.     return 1;
  912.  
  913.   fast = slow->tl;
  914.   int n = 2;
  915.  
  916.   for (;;)
  917.   {
  918.     if (fast == &Nil<T>ListNode)
  919.       return n;
  920.     else if (fast->tl == &Nil<T>ListNode)
  921.       return n+1;
  922.     else if (fast == slow)
  923.       return -1;
  924.     else
  925.     {
  926.       n += 2;
  927.       fast = fast->tl->tl;
  928.       slow = slow->tl;
  929.     }
  930.   }
  931. }
  932.  
  933. void <T>List::error(const char* msg)
  934. {
  935.   (*lib_error_handler)("List", msg);
  936. }
  937.  
  938. int <T>List::OK()
  939. {
  940.   int v = P != 0;               // have a node
  941.   // check that all nodes OK, even if circular:
  942.  
  943.   <T>ListNode* fast = P;
  944.   if (fast != &Nil<T>ListNode)
  945.   {
  946.     v &= fast->ref != 0;
  947.     <T>ListNode* slow = fast->tl;
  948.     v &= slow->ref != 0;
  949.     if (v && slow != &Nil<T>ListNode)
  950.     {
  951.       fast = slow->tl;
  952.       v &= fast->ref != 0;
  953.       while (v)
  954.       {
  955.         if (fast == &Nil<T>ListNode)
  956.           break;
  957.         else if (fast->tl == &Nil<T>ListNode)
  958.           break;
  959.         else if (fast == slow)
  960.           break;
  961.         else
  962.         {
  963.           v &= fast->ref != 0 && slow->ref != 0;
  964.           fast = fast->tl->tl;
  965.           slow = slow->tl;
  966.         }
  967.       }
  968.     }
  969.   }
  970.   if (!v) error ("invariant failure");
  971.   return v;
  972. }
  973.