/**********************************************************************

  Copyright 2019 Andrey V.Kosteltsev

  Licensed under the Radix.pro License, Version 1.0 (the "License");
  you may not use this file  except  in compliance with the License.
  You may obtain a copy of the License at

     https://radix.pro/licenses/LICENSE-1.0-en_US.txt

  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.

 **********************************************************************/

#ifndef _BTREE_H_
#define _BTREE_H_

#ifdef __cplusplus
extern "C" {
#endif


struct btree {
  struct btree *left, *right;
  int           ltag,  rtag;
  int           lprn,  rprn;

  struct btree *parent;

  void   *data;
};

typedef void (*TREE_FUNC)  ( void *data, void *user_data );
typedef int  (*TREE_CMPF)  ( const void *a, const void *b );


extern struct btree *__btree_alloc( void *data );
extern struct btree *btree_insert_left( struct btree *tree, struct btree *node );
extern struct btree *btree_insert_right( struct btree *tree, struct btree *node );

extern void btree_preorder_traversal( struct btree *root, TREE_FUNC func, void *user_data );
extern void btree_postorder_traversal( struct btree *root, TREE_FUNC func, void *user_data );
extern void btree_endorder_traversal( struct btree *root, TREE_FUNC func, void *user_data );

extern int btree_height( struct btree *root );
extern int btree_width( struct btree *root );
extern int btree_left_width( struct btree *root );
extern int btree_right_width( struct btree *root );

extern struct btree *btree_detach( struct btree *node );

extern int btree_compare( struct btree *root_a, struct btree *root_b, TREE_CMPF cmp_func );

void __btree_free( struct btree *root );
void btree_free( struct btree *root, TREE_FUNC free_func );


struct btree_stack {
  void   *__mem;
  void   *__cur_brk;
  size_t  __mem_size;
  size_t  __unit_size;
};

extern struct btree_stack *btree_stack_alloc( const size_t n, const size_t u );
extern void btree_stack_free( struct btree_stack **pstack );
extern int btree_stack_push( struct btree_stack *stack, const void *unit );
extern int btree_stack_pop( struct btree_stack *stack, void *unit );

extern int btree_stack_is_empty( struct btree_stack *stack );
extern int btree_stack_depth( struct btree_stack *stack );


struct _bctx
{
  FILE *output;
  struct btree *node;
  int indent;
};

extern void btree_reduce( struct btree *root, TREE_CMPF cmp_func, TREE_FUNC func );
extern void btree_print_json( FILE *output, struct btree *root, TREE_FUNC func );


#ifdef __cplusplus
}  /* ... extern "C" */
#endif

#endif /* _BTREE_H_ */