source: abuse/trunk/src/imlib/linked.cpp @ 518

Last change on this file since 518 was 494, checked in by Sam Hocevar, 12 years ago

style: remove trailing spaces, fix copyright statements.

File size: 4.5 KB
Line 
1/*
2 *  Abuse - dark 2D side-scrolling platform game
3 *  Copyright (c) 1995 Crack dot Com
4 *  Copyright (c) 2005-2011 Sam Hocevar <sam@hocevar.net>
5 *
6 *  This software was released into the Public Domain. As with most public
7 *  domain software, no warranty is made or implied by Crack dot Com or
8 *  Jonathan Clark.
9 */
10
11#include "config.h"
12
13#include <stdio.h>
14#include <stdlib.h>
15#include <string.h>
16
17#include "linked.h"
18
19//
20// take a node out of the linked list, but do not dispose of the memory
21//
22int linked_list::unlink(linked_node *p)
23{
24  linked_node *q;
25  if (first())        // if there are any nodes..
26  {
27    if (first()==p)  // if they want to unlinkt the first node
28    {
29      fn->last()->set_next(fn->next());   // set the first's last's next to the first's next
30      fn->next()->set_last(fn->last());    // set the first next's last to the first last
31      if (fn->next()==fn)                   // if there is ony one node
32      { fn=NULL; cn=NULL; }                   // clear the list
33      else fn=p->next();                  // else point the first pointer to the next node
34      nn--;                              // decrement the number of nodes in the list
35      return 1;
36    }
37    else
38    {
39      q=first()->next();
40      while (q!=p && q!=first())    // find the node in the list
41    q=q->next();
42      if (q!=first())                  // is it in the list at all?
43      {  q->last()->set_next(q->next());   // yes unlink the pointers
44     q->next()->set_last(q->last());
45     nn--;
46      return 1;
47      }                                    // decrement the number of nodes
48    }
49  }
50  return 0;
51}
52
53
54//
55// clear all the nodes in a linked list and dispose of the
56// memory for each one by calling its destructor
57//
58linked_list::~linked_list()
59{
60  if (fn)
61    fn->last()->set_next(NULL);  // set the last nodes next to NULL
62                                 // so we can go until we hit NULL
63  while (fn != NULL)          // repeat until we get to that node
64  {
65    cn=fn->next();
66    delete fn;                // delete the old node
67    fn=cn;
68  }
69  cn=NULL;                   // clear the list
70  nn=0;                     // set the number of nodes to 0
71}
72
73//
74// return the index of a given node in a linked list, by starting at the
75// node and parsing backwards
76//
77int linked_list::node_number(linked_node *p)
78{
79  int x;
80  x=1;
81  while (p!=first())
82  { x++; p=p->last(); }
83  return x;
84}
85
86
87// this function returns a pointer to the xth node
88class linked_node *linked_list::get_node(int x)
89{
90  class linked_node *p;
91  p=fn;             // start tat the first node
92  while (x--!=1) p=p->next();  // go forward X-1 nodes
93  return p;
94}
95
96
97// this function adds a node to the end of a linked_list
98void linked_list::add_end(class linked_node *p)
99{
100  nn++;
101  if (fn==NULL)        // if there are no nodes, then this one becomes the first
102  { fn=p;
103    fn->set_next(fn);  // and it poits to itself for first and last
104    fn->set_last(fn);
105  }
106  else
107  {
108    p->set_last(fn->last());  // otherwise add it in at the end
109    p->set_next(fn);
110    fn->last()->set_next(p);
111    fn->set_last(p);          // the first's last pointer points to the node we just added
112  }
113}
114
115
116// to add a node at the fron of the list, just add it at the end and set
117// the first pointer to it
118void linked_list::add_front(class linked_node *p)
119{
120  add_end(p);
121  fn=p;
122}
123
124
125// insert adds a node in the list according to is sort value
126void linked_list::insert(class linked_node *p)
127{
128  class linked_node *q;
129
130  // if there are nodes, or it belongs at the beginin call add front
131  if ((fn==NULL) || (p->compare(fn,sortby)>0))
132    add_front(p);
133  // else if it goes at the ned call add_end
134  else if (p->compare(fn->last(),sortby)<=0)
135    add_end(p);
136  else      // otherwise we have to find the right spot for it.
137  {
138    nn++;
139    q=fn;
140    while (q!=fn->last())  // q starts at the front
141    { q=q->next();
142      if (p->compare(q,sortby)>0)  // repeat until we find a value greater than the one we are inserting
143      { p->set_next(q);
144    p->set_last(q->last());     // insert it with pointers here
145    q->last()->set_next(p);
146    q->set_last(p);
147    q=fn->last();         // set q to the last node so we finish the loop
148      }
149    }
150  }
151}
152
153linked_list::linked_list(linked_node *first)
154{ linked_node *prev;
155  fn=first; cn=first; sortby=1; nn=0;
156  if (first)
157  { cn=first;
158    do
159    {
160      nn++;
161      prev=cn;
162      cn=cn->next();
163    } while (cn && cn!=first);
164    if (cn==NULL)
165    {
166      fn->set_last(prev);
167      prev->set_next(fn);
168    }
169    cn=first;
170
171  }
172}
Note: See TracBrowser for help on using the repository browser.