/*  BINARY_TREE.H    Copyright (C)  DUL-Soft      16/03/93

    Модуль работы с двоичным деревом
     элементы которого упорядочены.
*/


#ifndef _BINARY_TREE
   #define _BINARY_TREE


/*   Элемент дерева.   */

typedef struct b_tree
{
   struct b_tree  * left ;
   struct b_tree  * right ;
   void           * key ;
   void           * data ;
}  B_TREE ;

/* Где :
   left, right - ссылки, соответственно, на левое
		 или правое поддерево ;
   key         - ключ по которому происходит упорядовачение
		 элементов дерева ;
   data        - ссылка на сохраняемые данные.
*/


/*   Функции, использующиеся при работе с деревом.  */

typedef struct
{
   int       ( * compare_key ) ( void * key, void * tree_key ) ;
   unsigned  ( * key_len )     ( void * key ) ;
   unsigned  ( * data_len )    ( void * data ) ;
   void      ( * move_key )    ( void * dest, void * sourse ) ;
   void      ( * move_data )   ( void * dest, void * sourse ) ;
   void      ( * modify_data ) ( void * data, void * tree_data ) ;
   int       ( * process )     ( B_TREE * current ) ;
}  B_TREE_FUNCTIONS ;

/* Где :
   compare_key - функция, используемая для сравнения
		 передаваемого  ключа key  и  ключа,
		 хранящегося в дереве ( tree_key ) .
      Коды возврата :
	     0 - ключи совпадают ;
	    <0 - ключ key должен быть размещен в памяти
		 раньше ключа tree_key ;
	    >0 - ключ key должен быть размещен в памяти
		 за ключом tree_key .
      Внимание ! Передаваемые параметры могут быть = NULL.

   key_len  - должна  возвращать   объем  памяти,
	      требуемый для размещения ключа key.
   data_len - должна возвращать объем памяти, требуемый
	      для размещения данного data.
      Для этих двух функций гарантируется,
      что передаваемый параметр != NULL.

   move_key  - функция пересылки ключа в дерево.
   move_data - функция пересылки данных в дерево.
      Параметры :
	 dest   - приемник информации.
	 sourse - источник информации.
      Гарантируется :
	 1) Под приемник выделена запрашиваемая память.
	 2) Параметры dest, sourse != NULL.
      Если  эти  функции  не определены,  то будет вызвана
      стандартная процедура пересылки информации - memcpy.

   modify_data - изменить значение данного, хранящегося по
		 адресу tree_data используя передаваемый
		 параметр data.
      Внимание ! Передаваемые параметры могут быть = NULL.

   process - обработать текущий элемент дерева.
	     Параметр current != NULL.
      Коды возврата :
	<0 - прервать обработку дерева.
	     ( Возможно это сигнал ошибки исполнения ).
       >=0 - обработка прошла успешно.

   Замечание ! Первые 3 указателя на функции обязательно
	       должны быть инициализированы.
*/


/*    Двоичное дерево.   */

typedef struct
{
   B_TREE           * root ;
   B_TREE_FUNCTIONS * function ;
   int                unique ;
   unsigned           max_number ;
   unsigned           cur_number ;
}  BINARY_TREE ;

/* Где :
   root       - указатель на корень дерева.
   function   - указатель на функции, применяющиеся при
		работе с деревом.
   unique     - Если unique != 0, то в дереве будут
		храниться только уникальные ключи.
   max_number - Максимальное число элементов в дереве.
   cur_number - Текущее число элементов в дереве.

	     Смысл введения параметра max_number :
      Функции bt1_clear, bt1_process применяют рекурсивную
      обработку дерева. На каждый вызов расходуется, соот-
      ветственно, 8 или 10 байт стека. Если дерево  несба-
      лансировано, то возможна ошибка - stack overflow.
      Как только  cur_number станет равным  max_number, то
      вставка в дерево произведена не будет, и будет возв-
      ращен код = -1 - нет памяти.
*/


/*     Интерфейс класса.   */

void bt1_init    ( BINARY_TREE * bt,
		   B_TREE_FUNCTIONS * function,
		   int unique, unsigned max_number  ) ;
void bt1_clear   ( BINARY_TREE * bt ) ;
int  bt1_look    ( BINARY_TREE * bt, void * key ) ;
int  bt1_insert  ( BINARY_TREE * bt, void * key, void * data ) ;
int  bt1_modify  ( BINARY_TREE * bt, void * key, void * data ) ;
int  bt1_process ( BINARY_TREE * bt ) ;


/*                   Назначение функций.

   bt1_init - корректно инициализирует структуру BINARY_TREE,
	      устанавливая  root = NULL, cur_number = 0.

   bt1_clear - освобождает всю память, используемую деревом.

   bt1_look - проверяет наличие ключа key в дереве.
      Коды возврата :
	  1 - ключ существует.
	  0 - ключ отсутствует.

   bt1_insert - вставить элемент в дерево.
      Коды возврата :
	  1 - ключ уже существует. При установленном
	      флаге unique вставка не производится.
	  0 - вставка произведена.
	 -1 - нет памяти.

   bt1_modify - модифицировать элемент key дерева используя
		data.  Если  ключ  отсутствует в дереве, то
		действие функции эквивалентно bt1_insert.
      Коды возврата :
	  1 - ключ изменен.
       0,-1 - смотри bt1_insert.

   bt1_process - обработать все элементы дерева. Порядок
		 обработки элементов  -   по возрастанию
		 ключей.
      Коды возврата :
	  0 - обработка прошла успешно.
	 <0 - код, возращаемый функцией function -> process -
	      обработка прервана.
*/


/*    Реализация функций класса находится в модуле B_TREE.C
*/


#endif
