src/coll/treebase.c

   1 /*
   2  * treebase.c
   3  *
   4  * Copyright (c) 2013-2014 project bchan
   5  *
   6  * This software is provided 'as-is', without any express or implied
   7  * warranty. In no event will the authors be held liable for any damages
   8  * arising from the use of this software.
   9  *
  10  * Permission is granted to anyone to use this software for any purpose,
  11  * including commercial applications, and to alter it and redistribute it
  12  * freely, subject to the following restrictions:
  13  *
  14  * 1. The origin of this software must not be misrepresented; you must not
  15  *    claim that you wrote the original software. If you use this software
  16  *    in a product, an acknowledgment in the product documentation would be
  17  *    appreciated but is not required.
  18  *
  19  * 2. Altered source versions must be plainly marked as such, and must not be
  20  *    misrepresented as being the original software.
  21  *
  22  * 3. This notice may not be removed or altered from any source
  23  *    distribution.
  24  *
  25  */
  26
  27 #include "treebase.h"
  28
  29 #include <basic.h>
  30 #include <bstdio.h>
  31 #include <bsys/queue.h>
  32
  33 EXPORT VOID treebase_node_appendchild(treebase_node_t *node, treebase_node_t *child)
  34 {
  35         Bool ok;
  36
  37         ok = treebase_node_haschild(node);
  38         if (ok == False) {
  39                 node->firstchild = child;
  40         } else {
  41                 QueInsert(&child->sibling, &node->firstchild->sibling);
  42         }
  43         child->parent = node;
  44 }
  45
  46 EXPORT W treebase_node_insertbefore(treebase_node_t *node, treebase_node_t *child, treebase_node_t *ref)
  47 {
  48         if (ref == NULL) {
  49                 treebase_node_appendchild(node, child);
  50                 return 0;
  51         }
  52         if (ref->parent != node) {
  53                 return -1; /* TODO */
  54         }
  55
  56         if (node->firstchild == ref) {
  57                 node->firstchild = child;
  58         }
  59         QueInsert(&child->sibling, &ref->sibling);
  60         child->parent = node;
  61
  62         return 0;
  63 }
  64
  65 EXPORT VOID treebase_node_remove(treebase_node_t *node)
  66 {
  67         if (node->parent == NULL) { /* root node */
  68                 return;
  69         }
  70         if (node->parent->firstchild == node) {
  71                 node->parent->firstchild = treebase_node_getnextsibling(node);
  72         }
  73         QueRemove(&node->sibling);
  74         node->parent = NULL;
  75 }
  76
  77 EXPORT treebase_node_t* treebase_node_getparent(treebase_node_t *node)
  78 {
  79         return node->parent;
  80 }
  81
  82 EXPORT treebase_node_t* treebase_node_getnextsibling(treebase_node_t *node)
  83 {
  84         Bool empty;
  85         treebase_node_t *parent, *last;
  86         empty = isQueEmpty(&node->sibling);
  87         if (empty != False) {
  88                 return NULL;
  89         }
  90         parent = treebase_node_getparent(node);
  91         if (parent == NULL) {
  92                 return NULL;
  93         }
  94         last = treebase_node_getlastchild(parent);
  95         if (node == last) {
  96                 return NULL;
  97         }
  98         return (treebase_node_t*)node->sibling.next;
  99 }
 100
 101 EXPORT treebase_node_t* treebase_node_getprevsibling(treebase_node_t *node)
 102 {
 103         Bool empty;
 104         treebase_node_t *parent, *first;
 105         empty = isQueEmpty(&node->sibling);
 106         if (empty != False) {
 107                 return NULL;
 108         }
 109         parent = treebase_node_getparent(node);
 110         if (parent == NULL) {
 111                 return NULL;
 112         }
 113         first = treebase_node_getfirstchild(parent);
 114         if (node == first) {
 115                 return NULL;
 116         }
 117         return (treebase_node_t*)node->sibling.prev;
 118 }
 119
 120 EXPORT treebase_node_t* treebase_node_getfirstchild(treebase_node_t *node)
 121 {
 122         return node->firstchild;
 123 }
 124
 125 EXPORT treebase_node_t* treebase_node_getlastchild(treebase_node_t *node)
 126 {
 127         if (node->firstchild == NULL) {
 128                 return NULL;
 129         }
 130         return (treebase_node_t*)node->firstchild->sibling.prev;
 131 }
 132
 133 EXPORT Bool treebase_node_haschild(treebase_node_t *node)
 134 {
 135         if (node->firstchild == NULL) {
 136                 return False;
 137         }
 138         return True;
 139 }
 140
 141 EXPORT VOID treebase_node_initialize(treebase_node_t *node)
 142 {
 143         QueInit(&node->sibling);
 144         node->firstchild = NULL;
 145         node->parent = NULL;
 146 }
 147
 148 EXPORT VOID treebase_node_finalize(treebase_node_t *node)
 149 {
 150         treebase_node_remove(node);
 151 }
 152
 153
 154 EXPORT Bool treebase_preordertraversal_next(treebase_preordertraversal_t *traversal, treebase_node_t **node, TREEBASE_TRAVERSAL_DIRECTION *dir)
 155 {
 156         treebase_node_t *child, *sibling;
 157
 158         if (traversal->current == NULL) {
 159                 return False;
 160         }
 161
 162         *node = traversal->current;
 163         *dir = traversal->dir;
 164
 165         if (traversal->dir == TREEBASE_TRAVERSAL_DIRECTION_DOWN) {
 166                 child = treebase_node_getfirstchild(traversal->current);
 167                 if (child == NULL) {
 168                         traversal->dir = TREEBASE_TRAVERSAL_DIRECTION_UP;
 169                 } else {
 170                         traversal->current = child;
 171                 }
 172         } else {
 173                 sibling = treebase_node_getnextsibling(traversal->current);
 174                 if (sibling == NULL) {
 175                         if (traversal->current == traversal->root) {
 176                                 traversal->current = NULL;
 177                         } else {
 178                                 traversal->current = treebase_node_getparent(traversal->current);
 179                         }
 180                 } else {
 181                         traversal->current = sibling;
 182                         traversal->dir = TREEBASE_TRAVERSAL_DIRECTION_DOWN;
 183                 }
 184         }
 185
 186         return True;
 187 }
 188
 189 EXPORT VOID treebase_preordertraversal_initialize(treebase_preordertraversal_t *traversal, treebase_node_t *root)
 190 {
 191         traversal->root = root;
 192         traversal->current = root;
 193         traversal->dir = TREEBASE_TRAVERSAL_DIRECTION_DOWN;
 194 }
 195
 196 EXPORT VOID treebase_preordertraversal_finalize(treebase_preordertraversal_t *traversal)
 197 {
 198 }
 199
 200
 201 EXPORT Bool treebase_postordertraversal_next(treebase_postordertraversal_t *traversal, treebase_node_t **node, TREEBASE_TRAVERSAL_DIRECTION *dir)
 202 {
 203         treebase_node_t *child, *sibling;
 204
 205         if (traversal->current == NULL) {
 206                 return False;
 207         }
 208
 209         *node = traversal->current;
 210         *dir = traversal->dir;
 211
 212         if (traversal->dir == TREEBASE_TRAVERSAL_DIRECTION_DOWN) {
 213                 child = treebase_node_getlastchild(traversal->current);
 214                 if (child == NULL) {
 215                         traversal->dir = TREEBASE_TRAVERSAL_DIRECTION_UP;
 216                 } else {
 217                         traversal->current = child;
 218                 }
 219         } else {
 220                 sibling = treebase_node_getprevsibling(traversal->current);
 221                 if (sibling == NULL) {
 222                         if (traversal->current == traversal->root) {
 223                                 traversal->current = NULL;
 224                         } else {
 225                                 traversal->current = treebase_node_getparent(traversal->current);
 226                         }
 227                 } else {
 228                         traversal->current = sibling;
 229                         traversal->dir = TREEBASE_TRAVERSAL_DIRECTION_DOWN;
 230                 }
 231         }
 232
 233         return True;
 234 }
 235
 236 EXPORT VOID treebase_postordertraversal_initialize(treebase_postordertraversal_t *traversal, treebase_node_t *root)
 237 {
 238         traversal->root = root;
 239         traversal->current = root;
 240         traversal->dir = TREEBASE_TRAVERSAL_DIRECTION_DOWN;
 241 }
 242
 243 EXPORT VOID treebase_postordertraversal_finalize(treebase_postordertraversal_t *traversal)
 244 {
 245 }