source: abuse/tags/pd/macabuse/imlib/linked.c

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