gwenhywfar  4.3.3
tree.c
Go to the documentation of this file.
00001 /***************************************************************************
00002     begin       : Fri Jan 02 2009
00003     copyright   : (C) 2009 by Martin Preuss
00004     email       : martin@libchipcard.de
00005 
00006  ***************************************************************************
00007  *                                                                         *
00008  *   This library is free software; you can redistribute it and/or         *
00009  *   modify it under the terms of the GNU Lesser General Public            *
00010  *   License as published by the Free Software Foundation; either          *
00011  *   version 2.1 of the License, or (at your option) any later version.    *
00012  *                                                                         *
00013  *   This library is distributed in the hope that it will be useful,       *
00014  *   but WITHOUT ANY WARRANTY; without even the implied warranty of        *
00015  *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU     *
00016  *   Lesser General Public License for more details.                       *
00017  *                                                                         *
00018  *   You should have received a copy of the GNU Lesser General Public      *
00019  *   License along with this library; if not, write to the Free Software   *
00020  *   Foundation, Inc., 59 Temple Place, Suite 330, Boston,                 *
00021  *   MA  02111-1307  USA                                                   *
00022  *                                                                         *
00023  ***************************************************************************/
00024 
00025 
00026 #ifdef HAVE_CONFIG_H
00027 # include <config.h>
00028 #endif
00029 
00030 #define DISABLE_DEBUGLOG
00031 
00032 #include "tree_p.h"
00033 #include <gwenhywfar/misc.h>
00034 #include <gwenhywfar/debug.h>
00035 
00036 
00037 
00038 
00039 GWEN_TREE *GWEN_Tree_new(void) {
00040   GWEN_TREE *l;
00041 
00042   GWEN_NEW_OBJECT(GWEN_TREE, l);
00043   return l;
00044 }
00045 
00046 
00047 void GWEN_Tree_free(GWEN_TREE *l) {
00048   if (l) {
00049     GWEN_FREE_OBJECT(l);
00050   }
00051 }
00052 
00053 
00054 
00055 int GWEN_Tree_GetCount(const GWEN_TREE *l) {
00056   assert(l);
00057   return l->count;
00058 }
00059 
00060 
00061 
00062 void GWEN_Tree_Add(GWEN_TREE *l, GWEN_TREE_ELEMENT *el) {
00063   assert(l);
00064   assert(el);
00065   if (el->treePtr) {
00066     /* element is already part of another list */
00067     DBG_ERROR(GWEN_LOGDOMAIN, "Element is already part of a list");
00068     assert(0);
00069   }
00070   else {
00071     if (l->firstElement==0)
00072       l->firstElement=el;
00073 
00074     el->prevElement=l->lastElement;
00075     if (l->lastElement)
00076       l->lastElement->nextElement=el;
00077     l->lastElement=el;
00078 
00079     el->treePtr=l;
00080     el->parent=NULL;
00081     l->count++;
00082   }
00083 }
00084 
00085 
00086 
00087 void GWEN_Tree_AddList(GWEN_TREE *dest, GWEN_TREE *l) {
00088   GWEN_TREE_ELEMENT *el;
00089 
00090   assert(dest);
00091   assert(l);
00092 
00093   while((el=l->firstElement)) {
00094     GWEN_Tree_Del(el);
00095     GWEN_Tree_Add(dest, el);
00096   }
00097 }
00098 
00099 
00100 
00101 void GWEN_Tree_Insert(GWEN_TREE *l, GWEN_TREE_ELEMENT *el) {
00102   assert(l);
00103   assert(el);
00104   if (el->treePtr) {
00105     /* element is already part of another list */
00106     DBG_ERROR(GWEN_LOGDOMAIN, "Element is already part of a list");
00107   }
00108   else {
00109     el->nextElement=l->firstElement;
00110     l->firstElement=el;
00111 
00112     if (l->lastElement==0)
00113       l->lastElement=el;
00114 
00115     el->treePtr=l;
00116     el->parent=NULL;
00117     l->count++;
00118   }
00119 }
00120 
00121 
00122 
00123 void GWEN_Tree_Del(GWEN_TREE_ELEMENT *el) {
00124   GWEN_TREE *l;
00125 
00126   l=el->treePtr;
00127 
00128   if (l==0) {
00129     /* not part of any list */
00130     DBG_ERROR(GWEN_LOGDOMAIN, "Element is not part of any list");
00131   }
00132   else {
00133     /* unlink from previous */
00134     if (el->prevElement)
00135       el->prevElement->nextElement=el->nextElement;
00136 
00137     /* unlink from next */
00138     if (el->nextElement)
00139       el->nextElement->prevElement=el->prevElement;
00140 
00141     /* unlink from list */
00142     if (l->firstElement==el)
00143       l->firstElement=el->nextElement;
00144     if (l->lastElement==el)
00145       l->lastElement=el->prevElement;
00146     l->count--;
00147 
00148     /* unlink from parent */
00149     if (el->parent) {
00150       if (el->parent->firstChild==el)
00151         el->parent->firstChild=el->nextElement;
00152       if (el->parent->lastChild==el)
00153         el->parent->lastChild=el->prevElement;
00154       el->parent->count--;
00155     }
00156 
00157     el->nextElement=NULL;
00158     el->prevElement=NULL;
00159     el->parent=NULL;
00160     el->treePtr=NULL;
00161   }
00162 }
00163 
00164 
00165 
00166 void GWEN_Tree_AddChild(GWEN_TREE_ELEMENT *where, GWEN_TREE_ELEMENT *el) {
00167   if (el->treePtr) {
00168     /* element is already part of another tree */
00169     DBG_ERROR(GWEN_LOGDOMAIN, "Element is already part of a tree");
00170     assert(0);
00171   }
00172   else {
00173     if (where->firstChild==0)
00174       where->firstChild=el;
00175 
00176     el->prevElement=where->lastChild;
00177     if (where->lastChild)
00178       where->lastChild->nextElement=el;
00179     where->lastChild=el;
00180 
00181     el->parent=where;
00182 
00183     el->treePtr=where->treePtr;
00184     el->treePtr->count++;
00185     where->count++;
00186   }
00187 }
00188 
00189 
00190 
00191 void GWEN_Tree_InsertChild(GWEN_TREE_ELEMENT *where, GWEN_TREE_ELEMENT *el) {
00192   if (el->treePtr) {
00193     /* element is already part of another list */
00194     DBG_ERROR(GWEN_LOGDOMAIN, "Element is already part of a tree");
00195     assert(0);
00196   }
00197   else {
00198     el->nextElement=where->firstChild;
00199     where->firstChild=el;
00200 
00201     if (where->lastChild==NULL)
00202       where->lastChild=el;
00203 
00204     el->parent=where;
00205 
00206     el->treePtr=where->treePtr;
00207     el->treePtr->count++;
00208     where->count++;
00209   }
00210 }
00211 
00212 
00213 
00214 void *GWEN_Tree_GetFirst(const GWEN_TREE *l) {
00215   if (l->firstElement)
00216     return l->firstElement->data;
00217   return 0;
00218 }
00219 
00220 
00221 
00222 void *GWEN_Tree_GetLast(const GWEN_TREE *l) {
00223   if (l->lastElement)
00224     return l->lastElement->data;
00225   return 0;
00226 }
00227 
00228 
00229 
00230 
00231 
00232 GWEN_TREE_ELEMENT *GWEN_TreeElement_new(void *d) {
00233   GWEN_TREE_ELEMENT *el;
00234 
00235   GWEN_NEW_OBJECT(GWEN_TREE_ELEMENT, el);
00236   el->data=d;
00237 
00238   return el;
00239 }
00240 
00241 
00242 
00243 void GWEN_TreeElement_free(GWEN_TREE_ELEMENT *el) {
00244   if (el) {
00245     if (el->treePtr)
00246       GWEN_Tree_Del(el);
00247     if (el->firstChild) {
00248       DBG_ERROR(GWEN_LOGDOMAIN, "Tree element still has children");
00249       assert(0);
00250     }
00251     GWEN_FREE_OBJECT(el);
00252   }
00253 }
00254 
00255 
00256 
00257 void *GWEN_TreeElement_GetPrevious(const GWEN_TREE_ELEMENT *el){
00258   if (el->prevElement)
00259     return el->prevElement->data;
00260   return 0;
00261 }
00262 
00263 
00264 
00265 void *GWEN_TreeElement_GetNext(const GWEN_TREE_ELEMENT *el){
00266   if (el->nextElement)
00267     return el->nextElement->data;
00268   return 0;
00269 }
00270 
00271 
00272 
00273 void *GWEN_TreeElement_GetBelow(const GWEN_TREE_ELEMENT *el) {
00274   if (el->firstChild)                               /* look down */
00275     return el->firstChild->data;
00276   else if (el->nextElement)                         /* look right */
00277     return el->nextElement->data;
00278   else {
00279     /* look for a parent which has a right neighbour */
00280     while(el && el->parent) {
00281       if (el->parent->nextElement)                  /* look right of parent */
00282         return el->parent->nextElement->data;
00283       /* parent has no right neighbour, consult its parent */
00284       el=el->parent;
00285     }
00286   }
00287 
00288   return NULL;
00289 }
00290 
00291 
00292 
00293 void *GWEN_TreeElement_GetFirstChild(const GWEN_TREE_ELEMENT *el){
00294   if (el->firstChild)
00295     return el->firstChild->data;
00296   return NULL;
00297 }
00298 
00299 
00300 
00301 void *GWEN_TreeElement_GetLastChild(const GWEN_TREE_ELEMENT *el){
00302   if (el->lastChild)
00303     return el->lastChild->data;
00304   return NULL;
00305 }
00306 
00307 
00308 
00309 void *GWEN_TreeElement_GetParent(const GWEN_TREE_ELEMENT *el) {
00310   if (el->parent)
00311     return el->parent->data;
00312   return NULL;
00313 }
00314 
00315 
00316 
00317 uint32_t GWEN_TreeElement_GetChildrenCount(const GWEN_TREE_ELEMENT *el){
00318   assert(el);
00319   return el->count;
00320 }
00321 
00322 
00323 
00324 
00325 
00326 
00327 
00328