include/nilorea/n_trees.h

trees module headers More...

Structures

	Name
struct	TREE_NODE structure of a n-ary TREE node
struct	TREE structure of a TREE
struct	QUADTREE_NODE structure of a quad tree node
struct	QUADTREE structure of a quad tree
struct	POINT3D Structure for a POINT3D in the 3D space.
struct	POINT2D Structure for a POINT2D in the 2D space.
struct	OCTREE_NODE structure of an OCTREE node
struct	OCTREE structure of an OCTREE
union	NODE_DATA_TYPES union of the possibles data values of a TREE node
struct	NODE_DATA structure of a TREE node data
union	COORD_VALUE Union to store the coordinate values.

Detailed Description

trees module headers

Author: Castagnier Mickael

Version: 1.0

Date: 07/08/2024

Source code

/*
 * Nilorea Library
 * Copyright (C) 2005-2026 Castagnier Mickael
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
 * implied. See the License for the specific language governing
 * permissions and limitations under the License.
 *
 * SPDX-License-Identifier: Apache-2.0
 */


#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;

TREE* new_tree();
TREE_NODE* tree_create_node(NODE_DATA value, void (*destroy_func)(void* ptr));
int tree_insert_child(TREE_NODE* parent, TREE_NODE* child);
int tree_delete_node(TREE* tree, TREE_NODE* node);
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;

QUADTREE* create_quadtree(int coord_type);
QUADTREE_NODE* create_node(COORD_VALUE x, COORD_VALUE y, void* data_ptr);
QUADTREE_NODE* search(QUADTREE* qt, QUADTREE_NODE* root, COORD_VALUE x, COORD_VALUE y);
void insert(QUADTREE* qt, QUADTREE_NODE** root, COORD_VALUE x, COORD_VALUE y, void* data_ptr);
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;

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