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

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