list.ccp

早期freebsd实现

// This may look like C code, but it is really -*- C++ -*-
/* 
Copyright (C) 1988 Free Software Foundation
    written by Doug Lea ([e-mail])

This file is part of the GNU C++ Library.  This library is free
software; you can redistribute it and/or modify it under the terms of
the GNU Library General Public License as published by the Free
Software Foundation; either version 2 of the License, or (at your
option) any later version.  This library is distributed in the hope
that it will be useful, but WITHOUT ANY WARRANTY; without even the
implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
PURPOSE.  See the GNU Library General Public License for more details.
You should have received a copy of the GNU Library General Public
License along with this library; if not, write to the Free Software
Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
*/

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

<T>ListNode Nil<T>ListNode;

class init_Nil<T>ListNode
{
public:
  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 (<T>EQ(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 (<T>EQ(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 (<T>EQ(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 (<T>EQ(p->hd, targ))
      return 1;
    else
      p = p->tl;
  }
}

<T>List <T>List::find(<T&> targ)
{
  <T>ListNode* p = P;
  while (p != &Nil<T>ListNode && !<T>EQ(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 (<T>EQ(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 (<T>EQ(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 || !<T>EQ(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 (<T>EQ(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 || !<T>EQ(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 (<T>EQ(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 (<T>EQ(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 (<T>EQ(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 (<T>EQ(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)