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

Last change on this file since 90 was 56, checked in by Sam Hocevar, 12 years ago
  • Add licensing terms to most C / C++ files (Ref #5).
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// unlink take a node out of the linked list, but does not dispose of the memory
19int linked_list::unlink(linked_node *p)
20{
21  linked_node *q;
22  if (first())        // if there are any nodes..
23  {
24    if (first()==p)  // if they want to unlinkt the first node
25    {
26      fn->last()->set_next(fn->next());   // set the first's last's next to the first's next
27      fn->next()->set_last(fn->last());    // set the first next's last to the first last
28      if (fn->next()==fn)                   // if there is ony one node
29      { fn=NULL; cn=NULL; }                   // clear the list
30      else fn=p->next();                  // else point the first pointer to the next node
31      nn--;                              // decrement the number of nodes in the list
32      return 1;
33    }
34    else
35    {
36      q=first()->next();
37      while (q!=p && q!=first())    // find the node in the list
38        q=q->next();
39      if (q!=first())                  // is it in the list at all?
40      {  q->last()->set_next(q->next());   // yes unlink the pointers
41         q->next()->set_last(q->last());
42         nn--;
43         return 1;
44      }                                    // decrement the number of nodes
45    }
46  }
47  return 0;
48}
49
50
51// this function clears all the nodes in a linked list and dispose of the
52// memory for each one by calling is't destructor
53linked_list::~linked_list()
54{
55  if (fn)
56    fn->last()->set_next(NULL);  // set the last nodes next to NULL
57                                 // so we can go until we hit NULL
58  while (fn != NULL)          // repeat until we get to that node
59  {
60    cn=fn->next();
61    delete fn;                // delete the old node
62    fn=cn;
63  }
64  cn=NULL;                   // clear the list
65  nn=0;                     // set the number of nodes to 0
66}
67
68// this function returns the node number a node is in a linked list
69// it start at the node and goes backwards until it reaches the first
70// node
71int linked_list::node_number(linked_node *p)
72{
73  int x;
74  x=1;
75  while (p!=first())
76  { x++; p=p->last(); }
77  return x;
78}
79
80
81// this function returns a pointer to the xth node
82class linked_node *linked_list::get_node(int x)
83{
84  class linked_node *p;
85  p=fn;             // start tat the first node
86  while (x--!=1) p=p->next();  // go forward X-1 nodes
87  return p;
88}
89
90
91// this function adds a node to the end of a linked_list
92void linked_list::add_end(class linked_node *p)
93{
94  nn++;
95  if (fn==NULL)        // if there are no nodes, then this one becomes the first
96  { fn=p;
97    fn->set_next(fn);  // and it poits to itself for first and last
98    fn->set_last(fn);
99  }
100  else
101  {
102    p->set_last(fn->last());  // otherwise add it in at the end
103    p->set_next(fn);
104    fn->last()->set_next(p);
105    fn->set_last(p);          // the first's last pointer points to the node we just added
106  }
107}
108
109
110// to add a node at the fron of the list, just add it at the end and set
111// the first pointer to it
112void linked_list::add_front(class linked_node *p)
113{
114  add_end(p);
115  fn=p;
116}
117
118
119// insert adds a node in the list according to is sort value
120void linked_list::insert(class linked_node *p)
121{
122  class linked_node *q;
123
124  // if there are nodes, or it belongs at the beginin call add front
125  if ((fn==NULL) || (p->compare(fn,sortby)>0))
126    add_front(p);
127  // else if it goes at the ned call add_end
128  else if (p->compare(fn->last(),sortby)<=0)
129    add_end(p);
130  else      // otherwise we have to find the right spot for it.
131  {
132    nn++;
133    q=fn;
134    while (q!=fn->last())  // q starts at the front
135    { q=q->next();
136      if (p->compare(q,sortby)>0)  // repeat until we find a value greater than the one we are inserting
137      { p->set_next(q);
138        p->set_last(q->last());     // insert it with pointers here
139        q->last()->set_next(p);
140        q->set_last(p);
141        q=fn->last();         // set q to the last node so we exit the loop
142      }
143    }
144  }
145}
146
147linked_list::linked_list(linked_node *first)
148{ linked_node *prev;
149  fn=first; cn=first; sortby=1; nn=0;
150  if (first)
151  { cn=first;
152    do
153    {
154      nn++;
155      prev=cn;
156      cn=cn->next();
157    } while (cn && cn!=first);
158    if (cn==NULL)
159    {
160      fn->set_last(prev);
161      prev->set_next(fn);
162    }
163    cn=first;
164
165  }
166}
Note: See TracBrowser for help on using the repository browser.