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 #include "tree_p.h"
00031 #include <gwenhywfar/misc.h>
00032 #include <gwenhywfar/debug.h>
00033 
00034 
00035 
00036 
00037 GWEN_TREE *GWEN_Tree_new() {
00038   GWEN_TREE *l;
00039 
00040   GWEN_NEW_OBJECT(GWEN_TREE, l);
00041   return l;
00042 }
00043 
00044 
00045 void GWEN_Tree_free(GWEN_TREE *l) {
00046   if (l) {
00047     GWEN_FREE_OBJECT(l);
00048   }
00049 }
00050 
00051 
00052 
00053 int GWEN_Tree_GetCount(const GWEN_TREE *l) {
00054   assert(l);
00055   return l->count;
00056 }
00057 
00058 
00059 
00060 void GWEN_Tree_Add(GWEN_TREE *l, GWEN_TREE_ELEMENT *el) {
00061   assert(l);
00062   assert(el);
00063   if (el->treePtr) {
00064     /* element is already part of another list */
00065     DBG_ERROR(GWEN_LOGDOMAIN, "Element is already part of a list");
00066     assert(0);
00067   }
00068   else {
00069     if (l->firstElement==0)
00070       l->firstElement=el;
00071 
00072     el->prevElement=l->lastElement;
00073     if (l->lastElement)
00074       l->lastElement->nextElement=el;
00075     l->lastElement=el;
00076 
00077     el->treePtr=l;
00078     el->parent=NULL;
00079     l->count++;
00080   }
00081 }
00082 
00083 
00084 
00085 void GWEN_Tree_AddList(GWEN_TREE *dest, GWEN_TREE *l) {
00086   GWEN_TREE_ELEMENT *el;
00087 
00088   assert(dest);
00089   assert(l);
00090 
00091   while((el=l->firstElement)) {
00092     GWEN_Tree_Del(el);
00093     GWEN_Tree_Add(dest, el);
00094   }
00095 }
00096 
00097 
00098 
00099 void GWEN_Tree_Insert(GWEN_TREE *l, GWEN_TREE_ELEMENT *el) {
00100   assert(l);
00101   assert(el);
00102   if (el->treePtr) {
00103     /* element is already part of another list */
00104     DBG_ERROR(GWEN_LOGDOMAIN, "Element is already part of a list");
00105   }
00106   else {
00107     el->nextElement=l->firstElement;
00108     l->firstElement=el;
00109 
00110     if (l->lastElement==0)
00111       l->lastElement=el;
00112 
00113     el->treePtr=l;
00114     el->parent=NULL;
00115     l->count++;
00116   }
00117 }
00118 
00119 
00120 
00121 void GWEN_Tree_Del(GWEN_TREE_ELEMENT *el) {
00122   GWEN_TREE *l;
00123 
00124   l=el->treePtr;
00125 
00126   if (l==0) {
00127     /* not part of any list */
00128     DBG_ERROR(GWEN_LOGDOMAIN, "Element is not part of any list");
00129   }
00130   else {
00131     /* unlink from previous */
00132     if (el->prevElement)
00133       el->prevElement->nextElement=el->nextElement;
00134 
00135     /* unlink from next */
00136     if (el->nextElement)
00137       el->nextElement->prevElement=el->prevElement;
00138 
00139     /* unlink from list */
00140     if (l->firstElement==el)
00141       l->firstElement=el->nextElement;
00142     if (l->lastElement==el)
00143       l->lastElement=el->prevElement;
00144     l->count--;
00145 
00146     /* unlink from parent */
00147     if (el->parent) {
00148       if (el->parent->firstChild==el)
00149         el->parent->firstChild=el->nextElement;
00150       if (el->parent->lastChild==el)
00151         el->parent->lastChild=el->prevElement;
00152       el->parent->count--;
00153     }
00154 
00155     el->nextElement=NULL;
00156     el->prevElement=NULL;
00157     el->parent=NULL;
00158     el->treePtr=NULL;
00159   }
00160 }
00161 
00162 
00163 
00164 void GWEN_Tree_AddChild(GWEN_TREE_ELEMENT *where, GWEN_TREE_ELEMENT *el) {
00165   if (el->treePtr) {
00166     /* element is already part of another tree */
00167     DBG_ERROR(GWEN_LOGDOMAIN, "Element is already part of a tree");
00168     assert(0);
00169   }
00170   else {
00171     if (where->firstChild==0)
00172       where->firstChild=el;
00173 
00174     el->prevElement=where->lastChild;
00175     if (where->lastChild)
00176       where->lastChild->nextElement=el;
00177     where->lastChild=el;
00178 
00179     el->parent=where;
00180 
00181     el->treePtr=where->treePtr;
00182     el->treePtr->count++;
00183     where->count++;
00184   }
00185 }
00186 
00187 
00188 
00189 void GWEN_Tree_InsertChild(GWEN_TREE_ELEMENT *where, GWEN_TREE_ELEMENT *el) {
00190   if (el->treePtr) {
00191     /* element is already part of another list */
00192     DBG_ERROR(GWEN_LOGDOMAIN, "Element is already part of a tree");
00193     assert(0);
00194   }
00195   else {
00196     el->nextElement=where->firstChild;
00197     where->firstChild=el;
00198 
00199     if (where->lastChild==NULL)
00200       where->lastChild=el;
00201 
00202     el->parent=where;
00203 
00204     el->treePtr=where->treePtr;
00205     el->treePtr->count++;
00206     where->count++;
00207   }
00208 }
00209 
00210 
00211 
00212 void *GWEN_Tree_GetFirst(const GWEN_TREE *l) {
00213   if (l->firstElement)
00214     return l->firstElement->data;
00215   return 0;
00216 }
00217 
00218 
00219 
00220 void *GWEN_Tree_GetLast(const GWEN_TREE *l) {
00221   if (l->lastElement)
00222     return l->lastElement->data;
00223   return 0;
00224 }
00225 
00226 
00227 
00228 
00229 
00230 GWEN_TREE_ELEMENT *GWEN_TreeElement_new(void *d) {
00231   GWEN_TREE_ELEMENT *el;
00232 
00233   GWEN_NEW_OBJECT(GWEN_TREE_ELEMENT, el);
00234   el->data=d;
00235 
00236   return el;
00237 }
00238 
00239 
00240 
00241 void GWEN_TreeElement_free(GWEN_TREE_ELEMENT *el) {
00242   if (el) {
00243     if (el->treePtr)
00244       GWEN_Tree_Del(el);
00245     if (el->firstChild) {
00246       DBG_ERROR(GWEN_LOGDOMAIN, "Tree element still has children");
00247       assert(0);
00248     }
00249     GWEN_FREE_OBJECT(el);
00250   }
00251 }
00252 
00253 
00254 
00255 void *GWEN_TreeElement_GetPrevious(const GWEN_TREE_ELEMENT *el){
00256   if (el->prevElement)
00257     return el->prevElement->data;
00258   return 0;
00259 }
00260 
00261 
00262 
00263 void *GWEN_TreeElement_GetNext(const GWEN_TREE_ELEMENT *el){
00264   if (el->nextElement)
00265     return el->nextElement->data;
00266   return 0;
00267 }
00268 
00269 
00270 
00271 void *GWEN_TreeElement_GetBelow(const GWEN_TREE_ELEMENT *el) {
00272   if (el->firstChild)                               /* look down */
00273     return el->firstChild->data;
00274   else if (el->nextElement)                         /* look right */
00275     return el->nextElement->data;
00276   else {
00277     /* look for a parent which has a right neighbour */
00278     while(el && el->parent) {
00279       if (el->parent->nextElement)                  /* look right of parent */
00280         return el->parent->nextElement->data;
00281       /* parent has no right neighbour, consult its parent */
00282       el=el->parent;
00283     }
00284   }
00285 
00286   return NULL;
00287 }
00288 
00289 
00290 
00291 void *GWEN_TreeElement_GetFirstChild(const GWEN_TREE_ELEMENT *el){
00292   if (el->firstChild)
00293     return el->firstChild->data;
00294   return NULL;
00295 }
00296 
00297 
00298 
00299 void *GWEN_TreeElement_GetLastChild(const GWEN_TREE_ELEMENT *el){
00300   if (el->lastChild)
00301     return el->lastChild->data;
00302   return NULL;
00303 }
00304 
00305 
00306 
00307 void *GWEN_TreeElement_GetParent(const GWEN_TREE_ELEMENT *el) {
00308   if (el->parent)
00309     return el->parent->data;
00310   return NULL;
00311 }
00312 
00313 
00314 
00315 uint32_t GWEN_TreeElement_GetChildrenCount(const GWEN_TREE_ELEMENT *el){
00316   assert(el);
00317   return el->count;
00318 }
00319 
00320 
00321 
00322 
00323 
00324 
00325 
00326 

Generated on Sat Jan 2 09:32:36 2010 for gwenhywfar by  doxygen 1.6.1