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

Last change on this file since 481 was 481, checked in by Sam Hocevar, 11 years ago

Fuck the history, I'm renaming all .hpp files to .h for my own sanity.

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.h"
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.