Baillehache Pascal's personal website

LibCapy - tree

Generic tree class.

Macros:

#define CAPY_TREE_H

#define CapyDecTreeIterator(name, type_)                     \
typedef struct name name;                                    \
typedef struct name ## IteratorStep name ## IteratorStep;    \
struct name ## IteratorStep {                                \
  name* node;                                                \
  name ## IteratorStep* next;                                \
};                                                           \
typedef struct name ## Iterator {                            \
  size_t idx;                                                \
  name* tree;                                                \
  name ## IteratorStep* curStep;                             \
  type_ datatype;                                            \
  CapyPad(type_, datatype);                                  \
  CapyTreeIteratorType type;                                 \
  CapyPad(CapyTreeIteratorType, 1);                          \
  name ## IteratorStep* steps;                               \
  void (*destruct)(void);                                    \
  type_* (*reset)(void);                                     \
  type_* (*next)(void);                                      \
  bool (*isActive)(void);                                    \
  type_* (*get)(void);                                       \
  void (*setType)(CapyTreeIteratorType type);                \
} name ## Iterator;                                          \
name ## Iterator name ## IteratorCreate(                     \
  name* const arr, CapyTreeIteratorType const type);         \
name ## Iterator* name ## IteratorAlloc(                     \
  name* const arr, CapyTreeIteratorType const type);         \
void name ## IteratorDestruct(void);                         \
void name ## IteratorFree(name ## Iterator** const that);    \
type_* name ## IteratorReset(void);                          \
type_* name ## IteratorNextBreadthFirst(void);               \
type_* name ## IteratorNextDepthFirst(void);                 \
bool name ## IteratorIsActive(void);                         \
void name ## IteratorToLast(void);                           \
type_* name ## IteratorGet(void);                            \
void name ## IteratorSetType(CapyTreeIteratorType type);

Iterator for generic tree structure. Declaration macro for an iterator structure named 'name' ## Iterator, associated to a tree named 'name' containing elements of type 'type'

#define CapyDefTreeIteratorCreate(name, type_)         \
name ## Iterator name ## IteratorCreate(               \
  name* const tree,                                    \
  CapyTreeIteratorType const type) {                   \
  name ## Iterator that = {                            \
    .idx = 0,                                          \
    .tree = tree,                                      \
    .type = type,                                      \
    .steps = NULL,                                     \
    .destruct = name ## IteratorDestruct,              \
    .reset = name ## IteratorReset,                    \
    .isActive = name ## IteratorIsActive,              \
    .get = name ## IteratorGet,                        \
    .setType = name ## IteratorSetType,                \
  };                                                   \
  if(type == capyTreeIteratorType_breadthFirst)        \
    that.next = name ## IteratorNextBreadthFirst;      \
  else if(type == capyTreeIteratorType_depthFirst)     \
    that.next = name ## IteratorNextDepthFirst;        \
  $(&that, reset)();                                   \
  return that;                                         \
}

Create an iterator on a generic tree

Input argument(s):

tree: the generic tree on which to iterate
type: the type of iterator

Output and side effect(s):

Return the iterator

#define CapyDefTreeIteratorAlloc(name, type_)                     \
name ## Iterator* name ## IteratorAlloc(                          \
  name* const tree,                                               \
  CapyTreeIteratorType const type) {                              \
  name ## Iterator* that = NULL;                                  \
  safeMalloc(that, 1);                                            \
  if(!that) return NULL;                                          \
  name ## Iterator i = name ## IteratorCreate(tree, type);        \
  memcpy(that, &i, sizeof(name ## Iterator));                     \
  return that;                                                    \
}

Allocate memory and create an iterator on a generic tree

Input argument(s):

tree: the generic tree on which to iterate
type: the type of iterator

Output and side effect(s):

Return the iterator

#define CapyDefTreeIteratorDestruct(name, type)                \
void name ## IteratorFreeSteps(name ## Iterator* const that) { \
  name ## IteratorStep* step = that->steps;                    \
  while(that->steps != NULL) {                                 \
    step = that->steps->next;                                  \
    free(that->steps);                                         \
    that->steps = step;                                        \
  }                                                            \
}                                                              \
void name ## IteratorDestruct(void) {                          \
  name ## Iterator* that = (name ## Iterator*)capyThat;        \
  name ## IteratorFreeSteps(that);                             \
}

Free the memory used by an iterator.

Input argument(s):

that: the iterator to free

#define CapyDefTreeIteratorFree(name, type)                    \
void name ## IteratorFree(name ## Iterator** const that) {     \
  if(that == NULL || *that == NULL) return;                    \
  $(*that, destruct)();                                        \
  free(*that);                                                 \
  *that = NULL;                                                \
}

Free the memory used by a pointer to an iterator and reset '*that' to NULL

Input argument(s):

that: a pointer to the iterator to free

#define CapyDefTreeIteratorReset(name, type_)           \
type_* name ## IteratorReset(void) {                    \
  name ## Iterator* that = (name ## Iterator*)capyThat; \
  assert(that->tree && "Tree iterator uninitialised");  \
  that->idx = 0;                                        \
  name ## IteratorFreeSteps(that);                      \
  safeMalloc(that->steps, 1);                           \
  that->steps->node = that->tree;                       \
  that->steps->next = NULL;                             \
  if(name ## IteratorIsActive())                        \
    return name ## IteratorGet();                       \
  else                                                  \
    return NULL;                                        \
}

Reset the iterator

Output and side effect(s):

Return the first element of the iteration

#define CapyDefTreeIteratorNextBreadthFirst(name, type_)  \
type_* name ## IteratorNextBreadthFirst(void) {           \
  name ## Iterator* that = (name ## Iterator*)capyThat;   \
  if(name ## IteratorIsActive()) {                        \
    ++(that->idx);                                        \
    name* child = that->steps->node->child;               \
    name ## IteratorStep* first = that->steps;            \
    that->steps = that->steps->next;                      \
    free(first);                                          \
    name ## IteratorStep* last = that->steps;             \
    while(last && last->next) last = last->next;          \
    while(child != NULL) {                                \
      name ## IteratorStep* step = NULL;                  \
      safeMalloc(step, 1);                                \
      step->node = child;                                 \
      step->next = NULL;                                  \
      if(last == NULL) {                                  \
        that->steps = step;                               \
        last = step;                                      \
      } else {                                            \
        last->next = step;                                \
        last = step;                                      \
      }                                                   \
      child = child->brother;                             \
    }                                                     \
    return $(that, get)();                                \
  } else return NULL;                                     \
}

Move the iterator to the next element (breadth first)

Output and side effect(s):

Return the next element of the iteration

#define CapyDefTreeIteratorNextDepthFirst(name, type_)    \
type_* name ## IteratorNextDepthFirst(void) {             \
  name ## Iterator* that = (name ## Iterator*)capyThat;   \
  if(name ## IteratorIsActive()) {                        \
    ++(that->idx);                                        \
    name* child = that->steps->node->child;               \
    name ## IteratorStep* first = that->steps;            \
    that->steps = that->steps->next;                      \
    free(first);                                          \
    first = that->steps;                                  \
    that->steps = NULL;                                   \
    name ## IteratorStep* last = NULL;                    \
    while(child != NULL) {                                \
      name ## IteratorStep* step = NULL;                  \
      safeMalloc(step, 1);                                \
      step->node = child;                                 \
      step->next = NULL;                                  \
      if(last == NULL) {                                  \
        that->steps = step;                               \
        last = step;                                      \
      } else {                                            \
        last->next = step;                                \
        last = step;                                      \
      }                                                   \
      child = child->brother;                             \
    }                                                     \
    if(last != NULL) last->next = first;                  \
    else that->steps = first;                             \
    return $(that, get)();                                \
  } else return NULL;                                     \
}

Move the iterator to the next element (depth first)

Output and side effect(s):

Return the next element of the iteration

#define CapyDefTreeIteratorIsActive(name, type)         \
bool name ## IteratorIsActive(void) {                   \
  name ## Iterator* that = (name ## Iterator*)capyThat; \
  return (that->steps != NULL);                         \
}

Check if the iterator is on a valid element

Output and side effect(s):

Return true if the iterator is on a valid element, else false

#define CapyDefTreeIteratorGet(name, type_)                         \
type_* name ## IteratorGet(void) {                                  \
  name ## Iterator* that = (name ## Iterator*)capyThat;             \
  if(that->steps == NULL) return NULL;                              \
  return &(that->steps->node->data);                                \
}

Get the current element of the iteration

Output and side effect(s):

Return a pointer to the current element

#define CapyDefTreeIteratorSetType(name, type_)            \
void name ## IteratorSetType(CapyTreeIteratorType type) {  \
  name ## Iterator* that = (name ## Iterator*)capyThat;    \
  that->type = type;                                       \
  if(type == capyTreeIteratorType_breadthFirst)            \
    that->next = name ## IteratorNextBreadthFirst;         \
  else if(type == capyTreeIteratorType_depthFirst)         \
    that->next = name ## IteratorNextDepthFirst;           \
  name ## IteratorReset();                                 \
}

Set the type of the iterator and reset it

Input argument(s):

type: the new type of the iterator

#define CapyDefTreeIterator(name, type)           \
  CapyDefTreeIteratorCreate(name, type)           \
  CapyDefTreeIteratorAlloc(name, type)            \
  CapyDefTreeIteratorDestruct(name, type)         \
  CapyDefTreeIteratorFree(name, type)             \
  CapyDefTreeIteratorReset(name, type)            \
  CapyDefTreeIteratorNextBreadthFirst(name, type) \
  CapyDefTreeIteratorNextDepthFirst(name, type)   \
  CapyDefTreeIteratorIsActive(name, type)         \
  CapyDefTreeIteratorGet(name, type)              \
  CapyDefTreeIteratorSetType(name, type)

Definition macro calling all the submacros at once for an iterator on an array structure named 'name', containing elements of type 'type'

#define CapyDecTree(name, type)                            \
CapyDecTreeIterator(name, type)                            \
struct name {                                              \
  type data;                                               \
  CapyPad(type, data);                                     \
  name ## Iterator iter;                                   \
  name* parent;                                            \
  name* brother;                                           \
  name* child;                                             \
  void (*destruct)(void);                                  \
  void (*setData)(type const* const val);                  \
  type (*getData)(void);                                   \
  type* (*getDataPtr)(void);                               \
  name* (*getParent)(void);                                \
  name* (*getNextBrother)(void);                           \
  name* (*getFirstChild)(void);                            \
  name* (*addChild)(type const* const val);                \
  name* (*addBrother)(type const* const val);              \
  void (*initIterator)(void);                              \
};                                                         \
name name ## Create(type const* const val);                \
name* name ## Alloc(type const* const val);                \
void name ## Destruct(void);                               \
void name ## Free(name** const that);                      \
void name ## SetData(type const* const val);               \
type name ## GetData(void);                                \
type* name ## GetDataPtr(void);                            \
name* name ## GetParent(void);                             \
name* name ## GetNextBrother(void);                        \
name* name ## GetFirstChild(void);                         \
name* name ## AddChild(type const* const val);             \
name* name ## AddBrother(type const* const val);           \
void name ## InitIterator(void);

Generic tree structure. Declaration macro for a tree structure named 'name', containing data of type 'type'

#define CapyDefTreeCreate(name, type) \
name name ## Create(type const* const val) {       \
  return (name){                                   \
    .data = *val,                                  \
    .parent = NULL,                                \
    .brother = NULL,                               \
    .child = NULL,                                 \
    .destruct = name ## Destruct,                  \
    .setData = name ## SetData,                    \
    .getData = name ## GetData,                    \
    .initIterator = name ## InitIterator,          \
    .getDataPtr = name ## GetDataPtr,              \
    .getParent = name ## GetParent,                \
    .getNextBrother = name ## GetNextBrother,      \
    .getFirstChild = name ## GetFirstChild,        \
    .addChild = name ## AddChild,                  \
    .addBrother = name ## AddBrother,              \
    .iter = {.tree = NULL},                        \
  };                                               \
}

Generic tree structure. Definition macro and submacros for a tree structure named 'name', containing data of type 'type' Create a tree

Output and side effect(s):

Return a tree containing data of type 'type'

#define CapyDefTreeAlloc(name, type) \
name* name ## Alloc(type const* const val) {      \
  name* that = NULL;                              \
  safeMalloc(that, 1);                            \
  if(!that) return NULL;                          \
  *that = name ## Create(val);                    \
  that->iter = name ## IteratorCreate(            \
    that, capyTreeIteratorType_breadthFirst);     \
  return that;                                    \
}

Allocate memory for a new tree and create it

Output and side effect(s):

Return a tree containing data of type 'type'

Exception(s):

May raise CapyExc_MallocFailed.

#define CapyDefTreeDestruct(name, type)                         \
void name ## Destruct(void) {                                   \
  name* that = (name*)capyThat;                                 \
  if(that->child != NULL) name ## Free(&(that->child));         \
  if(that->brother != NULL) name ## Free(&(that->brother));     \
  if(that->data.destruct != NULL) $(&(that->data), destruct)(); \
  $(&(that->iter), destruct)();                                 \
  *that = (name){0};                                            \
}

Free the memory used by a tree.

Input argument(s):

that: the tree to free

#define CapyDefTreeFree(name, type)              \
void name ## Free(name** const that) {           \
  if(that == NULL || *that == NULL) return;      \
  $(*that, destruct)();                          \
  free(*that);                                   \
  *that = NULL;                                  \
}

Free the memory used by a pointer to a tree and reset '*that' to NULL

Input argument(s):

that: a pointer to the tree to free

#define CapyDefTreeSetData(name, type)        \
void name ## SetData(type const* const val) { \
  assert (val != NULL);                       \
  name* that = (name*)capyThat;               \
  that->data = *val;                          \
}

Set the data of the tree node

Input argument(s):

val: the value to set

#define CapyDefTreeGetData(name, type)  \
type name ## GetData(void) {            \
  name* that = (name*)capyThat;         \
  return that->data;                    \
}

Get the data of the tree node

Output and side effect(s):

Return the data value

#define CapyDefTreeGetDataPtr(name, type) \
type* name ## GetDataPtr(void) {          \
  name* that = (name*)capyThat;           \
  return &(that->data);                   \
}

Get a pointer to the data of the tree node

Output and side effect(s):

Return the pointer to the data

#define CapyDefTreeGetParent(name, type)  \
name* name ## GetParent(void) {           \
  name* that = (name*)capyThat;           \
  return that->parent;                    \
}

Get a pointer to the parent of the tree node

Output and side effect(s):

Return the pointer to the parent node

#define CapyDefTreeGetFirstChild(name, type)  \
name* name ## GetFirstChild(void) {           \
  name* that = (name*)capyThat;               \
  return that->child;                         \
}

Get a pointer to the first child of the tree node

Output and side effect(s):

Return the pointer to the first child node

#define CapyDefTreeGetNextBrother(name, type)  \
name* name ## GetNextBrother(void) {           \
  name* that = (name*)capyThat;                \
  return that->brother;                        \
}

Get a pointer to the next brother of the tree node

Output and side effect(s):

Return the pointer to the next brother node

#define CapyDefTreeInitIterator(name, type)                          \
void name ## InitIterator(void) {                                    \
  name* that = (name*)capyThat;                                      \
  that->iter =                                                       \
    name ## IteratorCreate(that, capyTreeIteratorType_breadthFirst); \
}

Initialise the iterator of the tree, must be called after the creation of the tree when it is created with Create(), Alloc() automatically initialise the iterator.

#define CapyDefTreeAddChild(name, type)                          \
name* name ## AddChild(type const* const val) {                  \
  name* that = (name*)capyThat;                                  \
  if(that->child == NULL) {                                      \
    that->child = name ## Alloc(val);                            \
    that->child->parent = that;                                  \
    return that->child;                                          \
  } else return  $(that->child, addBrother)(val);                \
}

Add a child to the tree node. The child is added to the brothers of the current child, or become the cild if there isn't yet. The new child is returned.

#define CapyDefTreeAddBrother(name, type)                            \
name* name ## AddBrother(type const* const val) {                    \
  name* that = (name*)capyThat;                                      \
  if(that->brother == NULL) {                                        \
    that->brother = name ## Alloc(val);                              \
    that->brother->parent = that;                                    \
    return that->brother;                                            \
  } else {                                                           \
    name* lastBrother = that->brother;                               \
    while(lastBrother->brother) lastBrother = lastBrother->brother;  \
    lastBrother->brother = name ## Alloc(val);                       \
    lastBrother->brother->parent = lastBrother->parent;              \
    return lastBrother->brother;                                     \
  }                                                                  \
}

Add a brother to the tree node. The brother is added to the end of the list. The new brother is returned.

#define CapyDefTree(name, type)         \
  CapyDefTreeCreate(name, type)         \
  CapyDefTreeAlloc(name, type)          \
  CapyDefTreeDestruct(name, type)       \
  CapyDefTreeFree(name, type)           \
  CapyDefTreeSetData(name, type)        \
  CapyDefTreeGetData(name, type)        \
  CapyDefTreeGetDataPtr(name, type)     \
  CapyDefTreeGetParent(name, type)      \
  CapyDefTreeGetFirstChild(name, type)  \
  CapyDefTreeGetNextBrother(name, type) \
  CapyDefTreeAddBrother(name, type)     \
  CapyDefTreeAddChild(name, type)       \
  CapyDefTreeInitIterator(name, type)   \
  CapyDefTreeIterator(name, type)

Definition macro calling all the submacros at once for an array structure named 'name', containing 'size_' elements of type 'type'

Enumerations:

typedef enum CapyTreeIteratorType {
  capyTreeIteratorType_breadthFirst,
  capyTreeIteratorType_depthFirst,
} CapyTreeIteratorType;

Enumeration for the types of iterator on generic tree

Typedefs:

None.

Functions:

None.

2024-03-20
in LibCapy,
21 views