source: abuse/trunk/src/imlib/linked.cpp @ 521 Tweet

/*
 *  Abuse - dark 2D side-scrolling platform game
 *  Copyright (c) 1995 Crack dot Com
 *  Copyright (c) 2005-2011 Sam Hocevar <sam@hocevar.net>
 *
 *  This software was released into the Public Domain. As with most public
 *  domain software, no warranty is made or implied by Crack dot Com or
 *  Jonathan Clark.
 */

#include "config.h"

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "linked.h"

//
// take a node out of the linked list, but do not dispose of the memory
//
int linked_list::unlink(linked_node *p)
{
  linked_node *q;
  if (first())        // if there are any nodes..
  {
    if (first()==p)  // if they want to unlinkt the first node
    {
      fn->last()->set_next(fn->next());   // set the first's last's next to the first's next
      fn->next()->set_last(fn->last());    // set the first next's last to the first last
      if (fn->next()==fn)                   // if there is ony one node
      { fn=NULL; cn=NULL; }                   // clear the list
      else fn=p->next();                  // else point the first pointer to the next node
      nn--;                              // decrement the number of nodes in the list
      return 1;
    }
    else
    {
      q=first()->next();
      while (q!=p && q!=first())    // find the node in the list
    q=q->next();
      if (q!=first())                  // is it in the list at all?
      {  q->last()->set_next(q->next());   // yes unlink the pointers
     q->next()->set_last(q->last());
     nn--;
      return 1;
      }                                    // decrement the number of nodes
    }
  }
  return 0;
}


//
// clear all the nodes in a linked list and dispose of the
// memory for each one by calling its destructor
//
linked_list::~linked_list()
{
  if (fn)
    fn->last()->set_next(NULL);  // set the last nodes next to NULL
                                 // so we can go until we hit NULL
  while (fn != NULL)          // repeat until we get to that node
  {
    cn=fn->next();
    delete fn;                // delete the old node
    fn=cn;
  }
  cn=NULL;                   // clear the list
  nn=0;                     // set the number of nodes to 0
}

//
// return the index of a given node in a linked list, by starting at the
// node and parsing backwards
//
int linked_list::node_number(linked_node *p)
{
  int x;
  x=1;
  while (p!=first())
  { x++; p=p->last(); }
  return x;
}


// this function returns a pointer to the xth node
class linked_node *linked_list::get_node(int x)
{
  class linked_node *p;
  p=fn;             // start tat the first node
  while (x--!=1) p=p->next();  // go forward X-1 nodes
  return p;
}


// this function adds a node to the end of a linked_list
void linked_list::add_end(class linked_node *p)
{
  nn++;
  if (fn==NULL)        // if there are no nodes, then this one becomes the first
  { fn=p;
    fn->set_next(fn);  // and it poits to itself for first and last
    fn->set_last(fn);
  }
  else
  {
    p->set_last(fn->last());  // otherwise add it in at the end
    p->set_next(fn);
    fn->last()->set_next(p);
    fn->set_last(p);          // the first's last pointer points to the node we just added
  }
}


// to add a node at the fron of the list, just add it at the end and set
// the first pointer to it
void linked_list::add_front(class linked_node *p)
{
  add_end(p);
  fn=p;
}


// insert adds a node in the list according to is sort value
void linked_list::insert(class linked_node *p)
{
  class linked_node *q;

  // if there are nodes, or it belongs at the beginin call add front
  if ((fn==NULL) || (p->compare(fn,sortby)>0))
    add_front(p);
  // else if it goes at the ned call add_end
  else if (p->compare(fn->last(),sortby)<=0)
    add_end(p);
  else      // otherwise we have to find the right spot for it.
  {
    nn++;
    q=fn;
    while (q!=fn->last())  // q starts at the front
    { q=q->next();
      if (p->compare(q,sortby)>0)  // repeat until we find a value greater than the one we are inserting
      { p->set_next(q);
    p->set_last(q->last());     // insert it with pointers here
    q->last()->set_next(p);
    q->set_last(p);
    q=fn->last();         // set q to the last node so we finish the loop
      }
    }
  }
}

linked_list::linked_list(linked_node *first)
{ linked_node *prev;
  fn=first; cn=first; sortby=1; nn=0;
  if (first)
  { cn=first;
    do
    {
      nn++;
      prev=cn;
      cn=cn->next();
    } while (cn && cn!=first);
    if (cn==NULL)
    {
      fn->set_last(prev);
      prev->set_next(fn);
    }
    cn=first;

  }
}