list.ccp

早期freebsd实现

    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 (!(<T>EQ(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 (!<T>EQ(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;
}