n_trees.h

Go to the documentation of this file.

 
#ifndef __NILOREA_TREES__
#define __NILOREA_TREES__
 
#ifdef __cplusplus
extern "C"
{
#endif
 
#include "nilorea/n_common.h"
#include "nilorea/n_str.h"
#include "nilorea/n_log.h"
#include "nilorea/n_list.h"
#include "nilorea/n_hash.h"
#include "nilorea/n_3d.h"
 
                union NODE_DATA_TYPES
                {
                                int    ival ;
                                double fval ;
                                void   *ptr ;
                                char   *string ;
                                N_STR *nstr ;
                };
 
    typedef struct NODE_DATA
    {
        union NODE_DATA_TYPES value ;
        int32_t type ;
    } NODE_DATA;
 
                typedef struct TREE_NODE
                {
                                NODE_DATA data ;
                                void (*destroy_func)( void *ptr );
                                struct TREE_NODE *parent;
                                LIST_NODE *parent_list_node ;
                                LIST *children;
                } TREE_NODE ;
 
                typedef struct TREE
                {
                                TREE_NODE *root ;
                                pthread_rwlock_t rwlock;  
                                size_t nb_nodes ;
                                size_t height ;
                } TREE ;
 
                 // create a TREE 
                TREE *new_tree();
                 // create a TREE node
                TREE_NODE* tree_create_node( NODE_DATA value, void (*destroy_func)( void *ptr ));
                 // insert a node in the parent node
                int tree_insert_child(TREE_NODE *parent, TREE_NODE *child);
                 // delete a TREE node
                int tree_delete_node(TREE *tree, TREE_NODE *node);
                 // delete a TREE
                void tree_destroy(TREE **tree);
 
                enum COORD_TYPE {
                                COORD_INT,
                                COORD_FLOAT,
                                COORD_DOUBLE
                };
 
                typedef union {
                                int i;
                                float f;
                                double d;
                } COORD_VALUE;
 
                typedef struct POINT2D {
                                COORD_VALUE 
            x, 
            y;
                } POINT2D;
 
                typedef struct POINT3D {
                                COORD_VALUE 
            x, 
            y, 
            z;
                } POINT3D;
 
                typedef int (*compare_func)(COORD_VALUE a, COORD_VALUE b);
                typedef void (*print_func)(COORD_VALUE val);
 
                typedef struct QUADTREE_NODE {
                                COORD_VALUE x;   
                                COORD_VALUE y;   
                                POINT2D point;  
                                void *data_ptr;  
                                struct QUADTREE_NODE *nw; 
                                struct QUADTREE_NODE *ne; 
                                struct QUADTREE_NODE *sw; 
                                struct QUADTREE_NODE *se; 
                } QUADTREE_NODE;
 
                typedef struct QUADTREE {
                                int coord_type;
                                compare_func compare;
                                print_func print;
                                QUADTREE_NODE *root;
                } QUADTREE;
 
                // Function to create a new quad tree
                QUADTREE* create_quadtree(int coord_type);
                // Function to create a new quad tree node
                QUADTREE_NODE* create_node(COORD_VALUE x, COORD_VALUE y, void *data_ptr);
                // Function to search for a point in the quad tree
                QUADTREE_NODE* search(QUADTREE *qt, QUADTREE_NODE *root, COORD_VALUE x, COORD_VALUE y);
                // Function to insert a point into the quad tree
                void insert(QUADTREE *qt, QUADTREE_NODE **root, COORD_VALUE x, COORD_VALUE y, void *data_ptr);
                // Function to free the quad tree
                void free_quadtree(QUADTREE_NODE *root);
 
                typedef struct OCTREE_NODE {
                                POINT3D point;
                                void *data_ptr;
                                struct OCTREE_NODE *children[8];
                } OCTREE_NODE;
 
                typedef struct {
                                OCTREE_NODE *root;
                                int coord_type;
                } OCTREE;
 
                // Function prototypes
                OCTREE* create_octree(int type);
                OCTREE_NODE* create_octree_node(POINT3D point, void *data_ptr);
                void insert_octree(OCTREE *OCTREE, POINT3D point, void *data_ptr);
                void free_octree_node(OCTREE_NODE *node);
                void free_octree(OCTREE *OCTREE);
 
#ifdef __cplusplus
}
#endif
 
#endif // header guard