text: /* bst/gsl_bst.h
   * 
   * Copyright (C) 2018, 2019 Patrick Alken
   * 
   * This program is free software; you can redistribute it and/or modify
   * it under the terms of the GNU General Public License as published by
   * the Free Software Foundation; either version 3 of the License, or (at
   * your option) any later version.
   * 
   * This program is distributed in the hope that it will be useful, but
   * WITHOUT ANY WARRANTY; without even the implied warranty of
   * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
   * General Public License for more details.
   * 
   * You should have received a copy of the GNU General Public License
   * along with this program; if not, write to the Free Software
   * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
   */
  
  #ifndef __GSL_BST_H__
  #define __GSL_BST_H__
  
  #if !defined( GSL_FUN )
  #  if !defined( GSL_DLL )
  #    define GSL_FUN extern
  #  elif defined( BUILD_GSL_DLL )
  #    define GSL_FUN extern __declspec(dllexport)
  #  else
  #    define GSL_FUN extern __declspec(dllimport)
  #  endif
  #endif
  
  #include <stdlib.h>
  #include <gsl/gsl_math.h>
  #include <gsl/gsl_bst_avl.h>
  #include <gsl/gsl_bst_rb.h>
  #include <gsl/gsl_bst_types.h>
  
  #undef __BEGIN_DECLS
  #undef __END_DECLS
  #ifdef __cplusplus
  # define __BEGIN_DECLS extern "C" {
  # define __END_DECLS }
  #else
  # define __BEGIN_DECLS /* empty */
  # define __END_DECLS /* empty */
  #endif
  
  __BEGIN_DECLS
  
  /* type of binary search tree */
  typedef struct
  {
    const char *name;
    const size_t node_size;
    int    (*init)(const gsl_bst_allocator * allocator,
                   gsl_bst_cmp_function * compare, void * params, void * vtable);
    size_t (*nodes) (const void * vtable);
    void * (*insert) (void * item, void * vtable);
    void * (*find) (const void *item, const void * vtable);
    void * (*remove) (const void *item, void * vtable);
    int    (*empty) (void * vtable);
    int    (*trav_init) (void * vtrav, const void * vtable);
    void * (*trav_first) (void * vtrav, const void * vtable);
    void * (*trav_last) (void * vtrav, const void * vtable);
    void * (*trav_find) (const void * item, void * vtrav, const void * vtable);
    void * (*trav_insert) (void * item, void * vtrav, void * vtable);
    void * (*trav_copy) (void * vtrav, const void * vsrc);
    void * (*trav_next) (void * vtrav);
    void * (*trav_prev) (void * vtrav);
    void * (*trav_cur) (const void * vtrav);
    void * (*trav_replace) (void * vtrav, void * new_item);
  } gsl_bst_type;
  
  typedef struct
  {
    const gsl_bst_type * type;    /* binary search tree type */
    union
      {
        gsl_bst_avl_table avl_table;
        gsl_bst_rb_table rb_table;
      } table;
  } gsl_bst_workspace;
  
  typedef struct
  {
    const gsl_bst_type * type;    /* binary search tree type */
    union
      {
        gsl_bst_avl_traverser avl_trav;
        gsl_bst_rb_traverser rb_trav;
      } trav_data;
  } gsl_bst_trav;
  
  /* tree types */
  GSL_VAR const gsl_bst_type * gsl_bst_avl;
  GSL_VAR const gsl_bst_type * gsl_bst_rb;
  
  /*
   * Prototypes
   */
  
  GSL_FUN gsl_bst_workspace * gsl_bst_alloc(const gsl_bst_type * T, const gsl_bst_allocator * allocator,
                                    gsl_bst_cmp_function * compare, void * params);
  GSL_FUN void gsl_bst_free(gsl_bst_workspace * w);
  GSL_FUN int gsl_bst_empty(gsl_bst_workspace * w);
  GSL_FUN void * gsl_bst_insert(void * item, gsl_bst_workspace * w);
  GSL_FUN void * gsl_bst_find(const void * item, const gsl_bst_workspace * w);
  GSL_FUN void * gsl_bst_remove(const void * item, gsl_bst_workspace * w);
  GSL_FUN size_t gsl_bst_nodes(const gsl_bst_workspace * w);
  GSL_FUN size_t gsl_bst_node_size(const gsl_bst_workspace * w);
  GSL_FUN const char * gsl_bst_name(const gsl_bst_workspace * w);
  
  GSL_FUN int gsl_bst_trav_init(gsl_bst_trav * trav, const gsl_bst_workspace * w);
  GSL_FUN void * gsl_bst_trav_first(gsl_bst_trav * trav, const gsl_bst_workspace * w);
  GSL_FUN void * gsl_bst_trav_last (gsl_bst_trav * trav, const gsl_bst_workspace * w);
  GSL_FUN void * gsl_bst_trav_find (const void * item, gsl_bst_trav * trav, const gsl_bst_workspace * w);
  GSL_FUN void * gsl_bst_trav_insert (void * item, gsl_bst_trav * trav, gsl_bst_workspace * w);
  GSL_FUN void * gsl_bst_trav_copy(gsl_bst_trav * dest, const gsl_bst_trav * src);
  GSL_FUN void * gsl_bst_trav_next(gsl_bst_trav * trav);
  GSL_FUN void * gsl_bst_trav_prev(gsl_bst_trav * trav);
  GSL_FUN void * gsl_bst_trav_cur(const gsl_bst_trav * trav);
  GSL_FUN void * gsl_bst_trav_replace (gsl_bst_trav * trav, void * new_item);
  
  __END_DECLS
  
  #endif /* __GSL_BST_H__ */
  