head	1.2;
access;
symbols
	perseant-exfatfs-base-20250801:1.2
	perseant-exfatfs-base-20240630:1.2
	cjep_sun2x:1.2.0.44
	cjep_sun2x-base:1.2
	cjep_staticlib_x-base1:1.2
	cjep_staticlib_x:1.2.0.42
	cjep_staticlib_x-base:1.2
	phil-wifi-20200421:1.2
	phil-wifi-20200411:1.2
	phil-wifi-20200406:1.2
	pgoyette-compat-merge-20190127:1.2
	pgoyette-compat-20190127:1.2
	pgoyette-compat-20190118:1.2
	pgoyette-compat-1226:1.2
	pgoyette-compat-1126:1.2
	pgoyette-compat-1020:1.2
	pgoyette-compat-0930:1.2
	pgoyette-compat-0906:1.2
	pgoyette-compat-0728:1.2
	pgoyette-compat-0625:1.2
	pgoyette-compat-0521:1.2
	pgoyette-compat-0502:1.2
	pgoyette-compat-0422:1.2
	pgoyette-compat-0415:1.2
	pgoyette-compat-0407:1.2
	pgoyette-compat-0330:1.2
	pgoyette-compat-0322:1.2
	pgoyette-compat-0315:1.2
	pgoyette-compat:1.2.0.40
	pgoyette-compat-base:1.2
	perseant-stdc-iso10646:1.2.0.38
	perseant-stdc-iso10646-base:1.2
	prg-localcount2-base3:1.2
	prg-localcount2-base2:1.2
	prg-localcount2-base1:1.2
	prg-localcount2:1.2.0.36
	prg-localcount2-base:1.2
	pgoyette-localcount-20170426:1.2
	bouyer-socketcan-base1:1.2
	pgoyette-localcount-20170320:1.2
	bouyer-socketcan:1.2.0.34
	bouyer-socketcan-base:1.2
	pgoyette-localcount-20170107:1.2
	pgoyette-localcount-20161104:1.2
	localcount-20160914:1.2
	pgoyette-localcount-20160806:1.2
	pgoyette-localcount-20160726:1.2
	pgoyette-localcount:1.2.0.32
	pgoyette-localcount-base:1.2
	netbsd-5-2-3-RELEASE:1.2
	netbsd-5-1-5-RELEASE:1.2
	yamt-pagecache-base9:1.2
	yamt-pagecache-tag8:1.2
	tls-earlyentropy:1.2.0.28
	tls-earlyentropy-base:1.2
	riastradh-xf86-video-intel-2-7-1-pre-2-21-15:1.2
	riastradh-drm2-base3:1.2
	netbsd-5-2-2-RELEASE:1.2
	netbsd-5-1-4-RELEASE:1.2
	netbsd-5-2-1-RELEASE:1.2
	netbsd-5-1-3-RELEASE:1.2
	agc-symver:1.2.0.30
	agc-symver-base:1.2
	tls-maxphys-base:1.2
	yamt-pagecache-base8:1.2
	netbsd-5-2:1.2.0.26
	yamt-pagecache-base7:1.2
	netbsd-5-2-RELEASE:1.2
	netbsd-5-2-RC1:1.2
	yamt-pagecache-base6:1.2
	yamt-pagecache-base5:1.2
	yamt-pagecache-base4:1.2
	netbsd-5-1-2-RELEASE:1.2
	netbsd-5-1-1-RELEASE:1.2
	yamt-pagecache-base3:1.2
	yamt-pagecache-base2:1.2
	yamt-pagecache:1.2.0.24
	yamt-pagecache-base:1.2
	bouyer-quota2-nbase:1.2
	bouyer-quota2:1.2.0.22
	bouyer-quota2-base:1.2
	matt-nb5-pq3:1.2.0.20
	matt-nb5-pq3-base:1.2
	netbsd-5-1:1.2.0.18
	netbsd-5-1-RELEASE:1.2
	netbsd-5-1-RC4:1.2
	netbsd-5-1-RC3:1.2
	netbsd-5-1-RC2:1.2
	netbsd-5-1-RC1:1.2
	netbsd-5-0-2-RELEASE:1.2
	netbsd-5-0-1-RELEASE:1.2
	jym-xensuspend-nbase:1.2
	netbsd-5-0:1.2.0.16
	netbsd-5-0-RELEASE:1.2
	netbsd-5-0-RC4:1.2
	netbsd-5-0-RC3:1.2
	netbsd-5-0-RC2:1.2
	jym-xensuspend:1.2.0.14
	jym-xensuspend-base:1.2
	netbsd-5-0-RC1:1.2
	netbsd-5:1.2.0.12
	netbsd-5-base:1.2
	mjf-devfs2:1.2.0.10
	mjf-devfs2-base:1.2
	yamt-pf42-base4:1.2
	yamt-pf42-base3:1.2
	hpcarm-cleanup-nbase:1.2
	yamt-pf42-base2:1.2
	yamt-pf42:1.2.0.8
	yamt-pf42-base:1.2
	keiichi-mipv6:1.2.0.6
	keiichi-mipv6-base:1.2
	cube-autoconf:1.2.0.4
	cube-autoconf-base:1.2
	hpcarm-cleanup:1.2.0.2
	hpcarm-cleanup-base:1.2
	netbsd-1-1-PATCH001:1.1.1.1
	netbsd-1-1-RELEASE:1.1.1.1
	netbsd-1-1:1.1.1.1.0.4
	netbsd-1-1-base:1.1.1.1
	netbsd-1-0-PATCH06:1.1.1.1
	netbsd-1-0-PATCH05:1.1.1.1
	netbsd-1-0-PATCH04:1.1.1.1
	netbsd-1-0-PATCH03:1.1.1.1
	netbsd-1-0-PATCH02:1.1.1.1
	netbsd-1-0-PATCH1:1.1.1.1
	netbsd-1-0-PATCH0:1.1.1.1
	netbsd-1-0-RELEASE:1.1.1.1
	netbsd-1-0:1.1.1.1.0.2
	netbsd-1-0-base:1.1.1.1
	netbsd-0-8:1.1.1.1
	netbsd-alpha-1:1.1.1.1
	patchkit-0-2-2:1.1.1.1
	WFJ-386bsd-01:1.1.1.1
	WFJ-920714:1.1.1;
locks; strict;
comment	@# @;


1.2
date	96.03.09.00.26.14;	author phil;	state dead;
branches;
next	1.1;

1.1
date	93.03.21.09.45.37;	author cgd;	state Exp;
branches
	1.1.1.1;
next	;

1.1.1.1
date	93.03.21.09.45.37;	author cgd;	state Exp;
branches;
next	;


desc
@@


1.2
log
@Deleting old libg++.
@
text
@// This may look like C code, but it is really -*- C++ -*-
/* 
Copyright (C) 1988 Free Software Foundation
    written by Doug Lea (dl@@rocky.oswego.edu)

This file is part of GNU CC.

GNU CC is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY.  No author or distributor
accepts responsibility to anyone for the consequences of using it
or for whether it serves any particular purpose or works at all,
unless he says so in writing.  Refer to the GNU CC General Public
License for full details.

Everyone is granted permission to copy, modify and redistribute
GNU CC, but only under the conditions described in the
GNU CC General Public License.   A copy of this license is
supposed to have been given to you along with GNU CC so you
can know your rights and responsibilities.  It should be in a
file named COPYING.  Among other things, the copyright notice
and this notice must be preserved on all copies.  
*/

#ifdef __GNUG__
#pragma implementation
#endif
#include <builtin.h>
#include "<T>.List.h"

<T>ListNode Nil<T>ListNode;

class init_Nil<T>ListNode
{
public:
  inline init_Nil<T>ListNode() 
  {
    Nil<T>ListNode.tl = &Nil<T>ListNode;
    Nil<T>ListNode.ref = -1;
  }
};

static init_Nil<T>ListNode Nil<T>ListNode_initializer;

<T>List& <T>List::operator = (<T>List& a)
{
  reference(a.P);
  dereference(P);
  P = a.P;
  return *this;
}

<T> <T>List::pop()
{
  <T> res = P->hd;
  <T>ListNode* tail = P->tl;
  reference(tail);
  dereference(P);
  P = tail;
  return res;
}

void <T>List::set_tail(<T>List& a)
{
  reference(a.P);
  dereference(P->tl);
  P->tl = a.P;
}

<T>List <T>List::nth(int n)
{
  for (<T>ListNode* p = P; n-- > 0; p = p->tl);
  reference(p);
  return <T>List(p);
}

<T>List <T>List::last()
{
  <T>ListNode* p = P;
  if (p != &Nil<T>ListNode) while (p->tl != &Nil<T>ListNode) p = p->tl;
  reference(p);
  return <T>List(p);
}

void <T>List::append(<T>List& l)
{
  <T>ListNode* p = P;
  <T>ListNode* a = l.P;
  reference(a);
  if (p != &Nil<T>ListNode)
  {
    while (p->tl != &Nil<T>ListNode) p = p->tl;
    p->tl = a;
  }
  else
    P = a;
}

int <T>List::length()
{
  int l = 0;
  for (<T>ListNode* p = P; p != &Nil<T>ListNode; p = p->tl) ++l;
  return l;
}

<T>&  <T>List::operator [] (int n)
{
  for (<T>ListNode* p = P; n-- > 0; p = p->tl);
  return (p->hd);
}

int operator == (<T>List& x, <T>List& y)
{
  <T>ListNode* a = x.P;
  <T>ListNode* b = y.P;
  
  for (;;)
  {
    if (a == &Nil<T>ListNode)
      return b == &Nil<T>ListNode;
    else if (b == &Nil<T>ListNode)
      return 0;
    else if (a->hd == b->hd)
    {
      a = a->tl;
      b = b->tl;
    }
    else
      return 0;
  }
}


void <T>List::apply(<T>Procedure f)
{
  for(<T>ListNode* p = P; p != &Nil<T>ListNode; p = p->tl)
    (*f)((p->hd));
}

void <T>List::subst(<T&> old, <T&> repl)
{
  for(<T>ListNode* p = P; p != &Nil<T>ListNode; p = p->tl)
    if (p->hd == old)
      p->hd = repl;
}

<T> <T>List::reduce(<T>Combiner f, <T&> base)
{
  <T> r = base;
  for(<T>ListNode* p = P; p != &Nil<T>ListNode; p = p->tl)
    r = (*f)(r, (p->hd));
  return r;
}

int <T>List::position(<T&> targ)
{
  int l = 0;
  <T>ListNode* p = P;
  for (;;)
  {
    if (p == &Nil<T>ListNode)
      return -1;
    else if (p->hd == targ)
      return l;
    else
    {
      ++l;
      p = p->tl;
    }
  }
}

int <T>List::contains(<T&> targ)
{
  <T>ListNode* p = P;
  for (;;)
  {
    if (p == &Nil<T>ListNode)
      return 0;
    else if (p->hd == targ)
      return 1;
    else
      p = p->tl;
  }
}

<T>List <T>List::find(<T&> targ)
{
  for (<T>ListNode* p = P; p != &Nil<T>ListNode && !(p->hd == targ); p=p->tl);
  reference(p);
  return <T>List(p);
}

Pix <T>List::seek(<T&> targ)
{
  <T>ListNode* p = P; 
  for (;;)
  {
    if (p == &Nil<T>ListNode)
      return 0;
    else if (p->hd == targ)
      return Pix(p);
    else
      p = p->tl;
  }
}

int <T>List::owns(Pix i)
{
  <T>ListNode* p = P; 
  for (;;)
  {
    if (p == &Nil<T>ListNode)
      return 0;
    else if (Pix(p) == i)
      return 1;
    else
      p = p->tl;
  }
}

<T>List <T>List::find(<T>List& target)
{
  <T>ListNode* targ = target.P;
  if (targ == &Nil<T>ListNode)
    return <T>List(targ);

  <T>ListNode* p = P;
  while (p != &Nil<T>ListNode)
  {
    if (p->hd == targ->hd)
    {
      <T>ListNode* a = p->tl;
      <T>ListNode* t = targ->tl;
      for(;;)
      {
        if (t == &Nil<T>ListNode)
        {
          reference(p);
          return <T>List(p);
        }
        else if (a == &Nil<T>ListNode || !(a->hd == t->hd))
          break;
        else
        {
          a = a->tl;
          t = t->tl;
        }
      }
    }
    p = p->tl;
  }
  return <T>List(&Nil<T>ListNode);
}

int <T>List::contains(<T>List& target)
{
  <T>ListNode* targ = target.P;
  if (targ == &Nil<T>ListNode)
    return 0;

  <T>ListNode* p = P;
  while (p != &Nil<T>ListNode)
  {
    if (p->hd == targ->hd)
    {
      <T>ListNode* a = p->tl;
      <T>ListNode* t = targ->tl;
      for(;;)
      {
        if (t == &Nil<T>ListNode)
          return 1;
        else if (a == &Nil<T>ListNode || !(a->hd == t->hd))
          break;
        else
        {
          a = a->tl;
          t = t->tl;
        }
      }
    }
    p = p->tl;
  }
  return 0;
}

void <T>List::del(<T&> targ)
{
  <T>ListNode* h = P;

  for (;;)
  {
    if (h == &Nil<T>ListNode)
    {
      P = h;
      return;
    }
    else if (h->hd == targ)
    {
      <T>ListNode* nxt = h->tl;
      reference(nxt);
      dereference(h);
      h = nxt;
    }
    else
      break;
  }

  <T>ListNode* trail = h;
  <T>ListNode* p = h->tl;
  while (p != &Nil<T>ListNode)
  {
    if (p->hd == targ)
    {
      <T>ListNode* nxt = p->tl;
      reference(nxt);
      dereference(p);
      trail->tl = nxt;
      p = nxt;
    }
    else
    {
      trail = p;
      p = p->tl;
    }
  }
  P = h;
}

void <T>List::del(<T>Predicate f)
{
  <T>ListNode* h = P;
  for (;;)
  {
    if (h == &Nil<T>ListNode)
    {
      P = h;
      return;
    }
    else if ((*f)(h->hd))
    {
      <T>ListNode* nxt = h->tl;
      reference(nxt);
      dereference(h);
      h = nxt;
    }
    else
      break;
  }

  <T>ListNode* trail = h;
  <T>ListNode* p = h->tl;
  while (p != &Nil<T>ListNode)
  {
    if ((*f)(p->hd))
    {
      <T>ListNode* nxt = p->tl;
      reference(nxt);
      dereference(p);
      trail->tl = nxt;
      p = nxt;
    }
    else
    {
      trail = p;
      p = p->tl;
    }
  }
  P = h;
}

void <T>List::select(<T>Predicate f)
{
  <T>ListNode* h = P;
  for (;;)
  {
    if (h == &Nil<T>ListNode)
    {
      P = h;
      return;
    }
    else if (!(*f)(h->hd))
    {
      <T>ListNode* nxt = h->tl;
      reference(nxt);
      dereference(h);
      h = nxt;
    }
    else
      break;
  }
  <T>ListNode* trail = h;
  <T>ListNode* p = h->tl;
  while (p != &Nil<T>ListNode)
  {
    if (!(*f)(p->hd))
    {
      <T>ListNode* nxt = p->tl;
      reference(nxt);
      dereference(p);
      trail->tl = nxt;
      p = nxt;
    }
    else
    {
      trail = p;
      p = p->tl;
    }
  }
  P = h;
}

void <T>List::reverse()
{
  <T>ListNode* l = &Nil<T>ListNode;
  <T>ListNode* p = P; 
  while (p != &Nil<T>ListNode)
  {
    <T>ListNode* nxt = p->tl;
    p->tl = l;
    l = p;
    p = nxt;
  }
  P = l;
}


<T>List copy(<T>List& x)
{
  <T>ListNode* a = x.P;
  if (a == &Nil<T>ListNode)
    return <T>List(a);
  else
  {
    <T>ListNode* h = new<T>ListNode(a->hd);
    <T>ListNode* trail = h;
    for(a = a->tl; a != &Nil<T>ListNode; a = a->tl)
    {
      <T>ListNode* n = new<T>ListNode(a->hd);
      trail->tl = n;
      trail = n;
    }
    trail->tl = &Nil<T>ListNode;
    return <T>List(h);
  }
}


<T>List subst(<T&> old, <T&> repl, <T>List& x)
{
  <T>ListNode* a = x.P;
  if (a == &Nil<T>ListNode)
    return <T>List(a);
  else
  {
    <T>ListNode* h = new <T>ListNode;
    h->ref = 1;
    if (a->hd == old)
      h->hd = repl;
    else
      h->hd = a->hd;
    <T>ListNode* trail = h;
    for(a = a->tl; a != &Nil<T>ListNode; a = a->tl)
    {
      <T>ListNode* n = new <T>ListNode;
      n->ref = 1;
      if (a->hd == old)
        n->hd = repl;
      else
        n->hd = a->hd;
      trail->tl = n;
      trail = n;
    }
    trail->tl = &Nil<T>ListNode;
    return <T>List(h);
  }
}

<T>List combine(<T>Combiner f, <T>List& x, <T>List& y)
{
  <T>ListNode* a = x.P;
  <T>ListNode* b = y.P;
  if (a == &Nil<T>ListNode || b == &Nil<T>ListNode)
    return <T>List(&Nil<T>ListNode);
  else
  {
    <T>ListNode* h = new<T>ListNode((*f)(a->hd, b->hd));
    <T>ListNode* trail = h;
    a = a->tl;
    b = b->tl;
    while (a != &Nil<T>ListNode && b != &Nil<T>ListNode)
    {
      <T>ListNode* n = new<T>ListNode((*f)(a->hd, b->hd));
      trail->tl = n;
      trail = n;
      a = a->tl;
      b = b->tl;
    }
    trail->tl = &Nil<T>ListNode;
    return <T>List(h);
  }
}

<T>List reverse(<T>List& x)
{
  <T>ListNode* a = x.P;
  if (a == &Nil<T>ListNode)
    return <T>List(a);
  else
  {
    <T>ListNode* l = new<T>ListNode(a->hd);
    l->tl = &Nil<T>ListNode;
    for(a = a->tl; a != &Nil<T>ListNode; a = a->tl)
    {
      <T>ListNode* n = new<T>ListNode(a->hd);
      n->tl = l;
      l = n;
    }
    return <T>List(l);
  }
}

<T>List append(<T>List& x, <T>List& y)
{
  <T>ListNode* a = x.P;
  <T>ListNode* b = y.P;
  reference(b);
  if (a != &Nil<T>ListNode)
  {
    <T>ListNode* h = new<T>ListNode(a->hd);
    <T>ListNode* trail = h;
    for(a = a->tl; a != &Nil<T>ListNode; a = a->tl)
    {
      <T>ListNode* n = new<T>ListNode(a->hd);
      trail->tl = n;
      trail = n;
    }
    trail->tl = b;
    return <T>List(h);
  }
  else
    return <T>List(b);
}

void <T>List::prepend(<T>List& y)
{
  <T>ListNode* b = y.P;
  if (b != &Nil<T>ListNode)
  {
    <T>ListNode* h = new<T>ListNode(b->hd);
    <T>ListNode* trail = h;
    for(b = b->tl; b != &Nil<T>ListNode; b = b->tl)
    {
      <T>ListNode* n = new<T>ListNode(b->hd);
      trail->tl = n;
      trail = n;
    }
    trail->tl = P;
    P = h;
  }
}

<T>List concat(<T>List& x, <T>List& y)
{
  <T>ListNode* a = x.P;
  <T>ListNode* b = y.P;
  if (a != &Nil<T>ListNode)
  {
    <T>ListNode* h = new<T>ListNode(a->hd);
    <T>ListNode* trail = h;
    for(a = a->tl; a != &Nil<T>ListNode; a = a->tl)
    {
      <T>ListNode* n = new<T>ListNode(a->hd);
      trail->tl = n;
      trail = n;
    };
    for(;b != &Nil<T>ListNode; b = b->tl)
    {
      <T>ListNode* n = new<T>ListNode(b->hd);
      trail->tl = n;
      trail = n;
    }
    trail->tl = &Nil<T>ListNode;
    return <T>List(h);
  }
  else if (b != &Nil<T>ListNode)
  {
    <T>ListNode* h = new<T>ListNode(b->hd);
    <T>ListNode* trail = h;
    for(b = b->tl; b != &Nil<T>ListNode; b = b->tl)
    {
      <T>ListNode* n = new<T>ListNode(b->hd);
      trail->tl = n;
      trail = n;
    }
    trail->tl = &Nil<T>ListNode;
    return <T>List(h);
  }
  else
    return <T>List(&Nil<T>ListNode);
}

<T>List select(<T>Predicate f, <T>List& x)
{
  <T>ListNode* a = x.P;
  <T>ListNode* h = &Nil<T>ListNode;
  while (a != &Nil<T>ListNode)
  {
    if ((*f)(a->hd))
    {
      h = new<T>ListNode(a->hd);
      <T>ListNode* trail = h;
      for(a = a->tl; a != &Nil<T>ListNode; a = a->tl)
      {
        if ((*f)(a->hd))
        {
          <T>ListNode* n = new<T>ListNode(a->hd);
          trail->tl = n;
          trail = n;
        }
      }
      trail->tl = &Nil<T>ListNode;
      break;
    }
    else
      a = a->tl;
  }
  return <T>List(h);
}

<T>List remove(<T>Predicate f, <T>List& x)
{
  <T>ListNode* a = x.P;
  <T>ListNode* h = &Nil<T>ListNode;
  while (a != &Nil<T>ListNode)
  {
    if (!(*f)(a->hd))
    {
      h = new<T>ListNode(a->hd);
      <T>ListNode* trail = h;
      for(a = a->tl; a != &Nil<T>ListNode; a = a->tl)
      {
        if (!(*f)(a->hd))
        {
          <T>ListNode* n = new<T>ListNode(a->hd);
          trail->tl = n;
          trail = n;
        }
      }
      trail->tl = &Nil<T>ListNode;
      break;
    }
    else
      a = a->tl;
  }
  return <T>List(h);
}

<T>List remove(<T&> targ, <T>List& x)
{
  <T>ListNode* a = x.P;
  <T>ListNode* h = &Nil<T>ListNode;
  while (a != &Nil<T>ListNode)
  {
    if (!(a->hd == targ))
    {
      h = new<T>ListNode(a->hd);
      <T>ListNode* trail = h;
      for(a = a->tl; a != &Nil<T>ListNode; a = a->tl)
      {
        if (!(a->hd == targ))
        {
          <T>ListNode* n = new<T>ListNode(a->hd);
          trail->tl = n;
          trail = n;
        }
      }
      trail->tl = &Nil<T>ListNode;
      break;
    }
    else
      a = a->tl;
  }
  return <T>List(h);
}

<T>List map(<T>Mapper f, <T>List& x)
{
  <T>ListNode* a = x.P;
  <T>ListNode* h = &Nil<T>ListNode;
  if (a != &Nil<T>ListNode)
  {
    h = new<T>ListNode((*f)(a->hd));
    <T>ListNode* trail = h;
    for(a = a->tl; a != &Nil<T>ListNode; a = a->tl)
    {
      <T>ListNode* n = new<T>ListNode((*f)(a->hd));
      trail->tl = n;
      trail = n;
    }
    trail->tl = &Nil<T>ListNode;
  }
  return <T>List(h);
}


<T>List merge(<T>List& x, <T>List& y, <T>Comparator f)
{
  <T>ListNode* a = x.P;
  <T>ListNode* b = y.P;

  if (a == &Nil<T>ListNode)
  {
    if (b == &Nil<T>ListNode)
      return <T>List(&Nil<T>ListNode);
    else
      return copy(y);
  }
  else if (b == &Nil<T>ListNode)
    return copy(x);

  <T>ListNode* h = new <T>ListNode;
  h->ref = 1;
  if ((*f)(a->hd, b->hd) <= 0)
  {
    h->hd = a->hd;
    a = a->tl;
  }
  else
  {
    h->hd = b->hd;
    b = b->tl;
  }

  <T>ListNode* r = h;

  for(;;)
  {
    if (a == &Nil<T>ListNode)
    {
      while (b != &Nil<T>ListNode)
      {
        <T>ListNode* n = new <T>ListNode;
        n->ref = 1;
        n->hd = b->hd;
        r->tl = n;
        r = n;
        b = b->tl;
      }
      r->tl = &Nil<T>ListNode;
      return <T>List(h);
    }
    else if (b == &Nil<T>ListNode)
    {
      while (a != &Nil<T>ListNode)
      {
        <T>ListNode* n = new <T>ListNode;
        n->ref = 1;
        n->hd = a->hd;
        r->tl = n;
        r = n;
        a = a->tl;
      }
      r->tl = &Nil<T>ListNode;
      return <T>List(h);
    }
    else if ((*f)(a->hd, b->hd) <= 0)
    {
      <T>ListNode* n = new <T>ListNode;
      n->ref = 1;
      n->hd = a->hd;
      r->tl = n;
      r = n;
      a = a->tl;
    }
    else
    {
      <T>ListNode* n = new <T>ListNode;
      n->ref = 1;
      n->hd = b->hd;
      r->tl = n;
      r = n;
      b = b->tl;
    }
  }
}

void <T>List::sort(<T>Comparator f)
{
  // strategy: place runs in queue, merge runs until done
  // This is often very fast

  if (P == &Nil<T>ListNode || P->tl == &Nil<T>ListNode)
    return;

  int qlen = 250;   // guess a good queue size, realloc if necessary

  <T>ListNode** queue = (<T>ListNode**)malloc(qlen * sizeof(<T>ListNode*));

  <T>ListNode* h = P;
  <T>ListNode* a = h;
  <T>ListNode* b = a->tl;
  int qin = 0;

  while (b != &Nil<T>ListNode)
  {
    if ((*f)(a->hd, b->hd) > 0)
    {
      if (h == a)               // minor optimization: ensure runlen >= 2
      {
        h = b;
        a->tl = b->tl;
        b->tl = a;
        b = a->tl;
      }
      else
      {
        if (qin >= qlen)
        {
          qlen *= 2;
          queue = (<T>ListNode**)realloc(queue, qlen * sizeof(<T>ListNode*));
        }
        queue[qin++] = h;
        a->tl = &Nil<T>ListNode;
        h = a = b;
        b = b->tl;
      }
    }
    else
    {
      a = b;
      b = b->tl;
    }
  }

  int count = qin;
  queue[qin] = h;
  if (++qin >= qlen) qin = 0;
  int qout = 0;

  while (count-- > 0)
  {
    a = queue[qout];
    if (++qout >= qlen) qout = 0;
    b = queue[qout];
    if (++qout >= qlen) qout = 0;

    if ((*f)(a->hd, b->hd) <= 0)
    {
      h = a;
      a = a->tl;
    }
    else
    {
      h = b;
      b = b->tl;
    }
    queue[qin] = h;
    if (++qin >= qlen) qin = 0;

    for (;;)
    {
      if (a == &Nil<T>ListNode)
      {
        h->tl = b;
        break;
      }
      else if (b == &Nil<T>ListNode)
      {
        h->tl = a;
        break;
      }
      else if ((*f)(a->hd, b->hd) <= 0)
      {
        h->tl = a;
        h = a;
        a = a->tl;
      }
      else
      {
        h->tl = b;
        h = b;
        b = b->tl;
      }
    }
  }
  P = queue[qout];
  free(queue);
}
    
int <T>List::list_length()
{
  <T>ListNode* fast = P;
  if (fast == &Nil<T>ListNode)
    return 0;

  <T>ListNode* slow = fast->tl;
  if (slow == &Nil<T>ListNode)
    return 1;

  fast = slow->tl;
  int n = 2;

  for (;;)
  {
    if (fast == &Nil<T>ListNode)
      return n;
    else if (fast->tl == &Nil<T>ListNode)
      return n+1;
    else if (fast == slow)
      return -1;
    else
    {
      n += 2;
      fast = fast->tl->tl;
      slow = slow->tl;
    }
  }
}

void <T>List::error(const char* msg)
{
  (*lib_error_handler)("List", msg);
}

int <T>List::OK()
{
  int v = P != 0;               // have a node
  // check that all nodes OK, even if circular:

  <T>ListNode* fast = P;
  if (fast != &Nil<T>ListNode)
  {
    v &= fast->ref != 0;
    <T>ListNode* slow = fast->tl;
    v &= slow->ref != 0;
    if (v && slow != &Nil<T>ListNode)
    {
      fast = slow->tl;
      v &= fast->ref != 0;
      while (v)
      {
        if (fast == &Nil<T>ListNode)
          break;
        else if (fast->tl == &Nil<T>ListNode)
          break;
        else if (fast == slow)
          break;
        else
        {
          v &= fast->ref != 0 && slow->ref != 0;
          fast = fast->tl->tl;
          slow = slow->tl;
        }
      }
    }
  }
  if (!v) error ("invariant failure");
  return v;
}
@


1.1
log
@Initial revision
@
text
@@


1.1.1.1
log
@initial import of 386bsd-0.1 sources
@
text
@@