gwenhywfar  4.7.0beta
tree.c
Go to the documentation of this file.
1 /***************************************************************************
2  begin : Fri Jan 02 2009
3  copyright : (C) 2009 by Martin Preuss
4  email : martin@libchipcard.de
5 
6  ***************************************************************************
7  * *
8  * This library is free software; you can redistribute it and/or *
9  * modify it under the terms of the GNU Lesser General Public *
10  * License as published by the Free Software Foundation; either *
11  * version 2.1 of the License, or (at your option) any later version. *
12  * *
13  * This library is distributed in the hope that it will be useful, *
14  * but WITHOUT ANY WARRANTY; without even the implied warranty of *
15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU *
16  * Lesser General Public License for more details. *
17  * *
18  * You should have received a copy of the GNU Lesser General Public *
19  * License along with this library; if not, write to the Free Software *
20  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, *
21  * MA 02111-1307 USA *
22  * *
23  ***************************************************************************/
24 
25 
26 #ifdef HAVE_CONFIG_H
27 # include <config.h>
28 #endif
29 
30 #define DISABLE_DEBUGLOG
31 
32 #include "tree_p.h"
33 #include <gwenhywfar/misc.h>
34 #include <gwenhywfar/debug.h>
35 
36 
37 
38 
40  GWEN_TREE *l;
41 
43  return l;
44 }
45 
46 
48  if (l) {
50  }
51 }
52 
53 
54 
56  assert(l);
57  return l->count;
58 }
59 
60 
61 
63  assert(l);
64  assert(el);
65  if (el->treePtr) {
66  /* element is already part of another list */
67  DBG_ERROR(GWEN_LOGDOMAIN, "Element is already part of a list");
68  assert(0);
69  }
70  else {
71  if (l->firstElement==0)
72  l->firstElement=el;
73 
74  el->prevElement=l->lastElement;
75  if (l->lastElement)
76  l->lastElement->nextElement=el;
77  l->lastElement=el;
78 
79  el->treePtr=l;
80  el->parent=NULL;
81  l->count++;
82  }
83 }
84 
85 
86 
89 
90  assert(dest);
91  assert(l);
92 
93  while((el=l->firstElement)) {
94  GWEN_Tree_Del(el);
95  GWEN_Tree_Add(dest, el);
96  }
97 }
98 
99 
100 
102  assert(l);
103  assert(el);
104  if (el->treePtr) {
105  /* element is already part of another list */
106  DBG_ERROR(GWEN_LOGDOMAIN, "Element is already part of a list");
107  }
108  else {
109  el->nextElement=l->firstElement;
110  l->firstElement=el;
111 
112  if (l->lastElement==0)
113  l->lastElement=el;
114 
115  el->treePtr=l;
116  el->parent=NULL;
117  l->count++;
118  }
119 }
120 
121 
122 
124  GWEN_TREE *l;
125 
126  l=el->treePtr;
127 
128  if (l==0) {
129  /* not part of any list */
130  DBG_ERROR(GWEN_LOGDOMAIN, "Element is not part of any list");
131  }
132  else {
133  /* unlink from previous */
134  if (el->prevElement)
135  el->prevElement->nextElement=el->nextElement;
136 
137  /* unlink from next */
138  if (el->nextElement)
139  el->nextElement->prevElement=el->prevElement;
140 
141  /* unlink from list */
142  if (l->firstElement==el)
143  l->firstElement=el->nextElement;
144  if (l->lastElement==el)
145  l->lastElement=el->prevElement;
146  l->count--;
147 
148  /* unlink from parent */
149  if (el->parent) {
150  if (el->parent->firstChild==el)
151  el->parent->firstChild=el->nextElement;
152  if (el->parent->lastChild==el)
153  el->parent->lastChild=el->prevElement;
154  el->parent->count--;
155  }
156 
157  el->nextElement=NULL;
158  el->prevElement=NULL;
159  el->parent=NULL;
160  el->treePtr=NULL;
161  }
162 }
163 
164 
165 
167  if (el->treePtr) {
168  /* element is already part of another tree */
169  DBG_ERROR(GWEN_LOGDOMAIN, "Element is already part of a tree");
170  assert(0);
171  }
172  else {
173  if (where->firstChild==0)
174  where->firstChild=el;
175 
176  el->prevElement=where->lastChild;
177  if (where->lastChild)
178  where->lastChild->nextElement=el;
179  where->lastChild=el;
180 
181  el->parent=where;
182 
183  el->treePtr=where->treePtr;
184  el->treePtr->count++;
185  where->count++;
186  }
187 }
188 
189 
190 
192  if (el->treePtr) {
193  /* element is already part of another list */
194  DBG_ERROR(GWEN_LOGDOMAIN, "Element is already part of a tree");
195  assert(0);
196  }
197  else {
198  el->nextElement=where->firstChild;
199  where->firstChild=el;
200 
201  if (where->lastChild==NULL)
202  where->lastChild=el;
203 
204  el->parent=where;
205 
206  el->treePtr=where->treePtr;
207  el->treePtr->count++;
208  where->count++;
209  }
210 }
211 
212 
213 
214 void *GWEN_Tree_GetFirst(const GWEN_TREE *l) {
215  if (l->firstElement)
216  return l->firstElement->data;
217  return 0;
218 }
219 
220 
221 
222 void *GWEN_Tree_GetLast(const GWEN_TREE *l) {
223  if (l->lastElement)
224  return l->lastElement->data;
225  return 0;
226 }
227 
228 
229 
230 
231 
233  GWEN_TREE_ELEMENT *el;
234 
236  el->data=d;
237 
238  return el;
239 }
240 
241 
242 
244  if (el) {
245  if (el->treePtr)
246  GWEN_Tree_Del(el);
247  if (el->firstChild) {
248  DBG_ERROR(GWEN_LOGDOMAIN, "Tree element still has children");
249  assert(0);
250  }
251  GWEN_FREE_OBJECT(el);
252  }
253 }
254 
255 
256 
258  if (el->prevElement)
259  return el->prevElement->data;
260  return 0;
261 }
262 
263 
264 
266  if (el->nextElement)
267  return el->nextElement->data;
268  return 0;
269 }
270 
271 
272 
274  if (el->firstChild) /* look down */
275  return el->firstChild->data;
276  else if (el->nextElement) /* look right */
277  return el->nextElement->data;
278  else {
279  /* look for a parent which has a right neighbour */
280  while(el && el->parent) {
281  if (el->parent->nextElement) /* look right of parent */
282  return el->parent->nextElement->data;
283  /* parent has no right neighbour, consult its parent */
284  el=el->parent;
285  }
286  }
287 
288  return NULL;
289 }
290 
291 
292 
294  if (el->firstChild)
295  return el->firstChild->data;
296  return NULL;
297 }
298 
299 
300 
302  if (el->lastChild)
303  return el->lastChild->data;
304  return NULL;
305 }
306 
307 
308 
310  if (el->parent)
311  return el->parent->data;
312  return NULL;
313 }
314 
315 
316 
318  assert(el);
319  return el->count;
320 }
321 
322 
323 
324 
325 
326 
327 
328