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