include/gsl/gsl_bst.h

0001 /* bst/gsl_bst.h
0002  *
0003  * Copyright (C) 2018, 2019 Patrick Alken
0004  *
0005  * This program is free software; you can redistribute it and/or modify
0006  * it under the terms of the GNU General Public License as published by
0007  * the Free Software Foundation; either version 3 of the License, or (at
0008  * your option) any later version.
0009  *
0010  * This program is distributed in the hope that it will be useful, but
0011  * WITHOUT ANY WARRANTY; without even the implied warranty of
0012  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
0013  * General Public License for more details.
0014  *
0015  * You should have received a copy of the GNU General Public License
0016  * along with this program; if not, write to the Free Software
0017  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
0018  */
0019
0020 #ifndef __GSL_BST_H__
0021 #define __GSL_BST_H__
0022
0023 #include <stdlib.h>
0024 #include <gsl/gsl_math.h>
0025 #include <gsl/gsl_bst_avl.h>
0026 #include <gsl/gsl_bst_rb.h>
0027 #include <gsl/gsl_bst_types.h>
0028
0029 #undef __BEGIN_DECLS
0030 #undef __END_DECLS
0031 #ifdef __cplusplus
0032 # define __BEGIN_DECLS extern "C" {
0033 # define __END_DECLS }
0034 #else
0035 # define __BEGIN_DECLS /* empty */
0036 # define __END_DECLS /* empty */
0037 #endif
0038
0039 __BEGIN_DECLS
0040
0041 /* type of binary search tree */
0042 typedef struct
0043 {
0044   const char *name;
0045   const size_t node_size;
0046   int    (*init)(const gsl_bst_allocator * allocator,
0047                  gsl_bst_cmp_function * compare, void * params, void * vtable);
0048   size_t (*nodes) (const void * vtable);
0049   void * (*insert) (void * item, void * vtable);
0050   void * (*find) (const void *item, const void * vtable);
0051   void * (*remove) (const void *item, void * vtable);
0052   int    (*empty) (void * vtable);
0053   int    (*trav_init) (void * vtrav, const void * vtable);
0054   void * (*trav_first) (void * vtrav, const void * vtable);
0055   void * (*trav_last) (void * vtrav, const void * vtable);
0056   void * (*trav_find) (const void * item, void * vtrav, const void * vtable);
0057   void * (*trav_insert) (void * item, void * vtrav, void * vtable);
0058   void * (*trav_copy) (void * vtrav, const void * vsrc);
0059   void * (*trav_next) (void * vtrav);
0060   void * (*trav_prev) (void * vtrav);
0061   void * (*trav_cur) (const void * vtrav);
0062   void * (*trav_replace) (void * vtrav, void * new_item);
0063 } gsl_bst_type;
0064
0065 typedef struct
0066 {
0067   const gsl_bst_type * type;    /* binary search tree type */
0068   union
0069     {
0070       gsl_bst_avl_table avl_table;
0071       gsl_bst_rb_table rb_table;
0072     } table;
0073 } gsl_bst_workspace;
0074
0075 typedef struct
0076 {
0077   const gsl_bst_type * type;    /* binary search tree type */
0078   union
0079     {
0080       gsl_bst_avl_traverser avl_trav;
0081       gsl_bst_rb_traverser rb_trav;
0082     } trav_data;
0083 } gsl_bst_trav;
0084
0085 /* tree types */
0086 GSL_VAR const gsl_bst_type * gsl_bst_avl;
0087 GSL_VAR const gsl_bst_type * gsl_bst_rb;
0088
0089 /*
0090  * Prototypes
0091  */
0092
0093 gsl_bst_workspace * gsl_bst_alloc(const gsl_bst_type * T, const gsl_bst_allocator * allocator,
0094                                   gsl_bst_cmp_function * compare, void * params);
0095 void gsl_bst_free(gsl_bst_workspace * w);
0096 int gsl_bst_empty(gsl_bst_workspace * w);
0097 void * gsl_bst_insert(void * item, gsl_bst_workspace * w);
0098 void * gsl_bst_find(const void * item, const gsl_bst_workspace * w);
0099 void * gsl_bst_remove(const void * item, gsl_bst_workspace * w);
0100 size_t gsl_bst_nodes(const gsl_bst_workspace * w);
0101 size_t gsl_bst_node_size(const gsl_bst_workspace * w);
0102 const char * gsl_bst_name(const gsl_bst_workspace * w);
0103
0104 int gsl_bst_trav_init(gsl_bst_trav * trav, const gsl_bst_workspace * w);
0105 void * gsl_bst_trav_first(gsl_bst_trav * trav, const gsl_bst_workspace * w);
0106 void * gsl_bst_trav_last (gsl_bst_trav * trav, const gsl_bst_workspace * w);
0107 void * gsl_bst_trav_find (const void * item, gsl_bst_trav * trav, const gsl_bst_workspace * w);
0108 void * gsl_bst_trav_insert (void * item, gsl_bst_trav * trav, gsl_bst_workspace * w);
0109 void * gsl_bst_trav_copy(gsl_bst_trav * dest, const gsl_bst_trav * src);
0110 void * gsl_bst_trav_next(gsl_bst_trav * trav);
0111 void * gsl_bst_trav_prev(gsl_bst_trav * trav);
0112 void * gsl_bst_trav_cur(const gsl_bst_trav * trav);
0113 void * gsl_bst_trav_replace (gsl_bst_trav * trav, void * new_item);
0114
0115 __END_DECLS
0116
0117 #endif /* __GSL_BST_H__ */