/*******************************************************************
  uLan Utilities Library - C library of basic reusable constructions

  ul_hptree.h  - heap tree implementation

  (C) Copyright 2003-2004 by Pavel Pisa - Originator

  The uLan utilities library can be used, copied and modified under
  next licenses
    - GPL - GNU General Public License
    - LGPL - GNU Lesser General Public License
    - MPL - Mozilla Public License
    - and other licenses added by project originators
  Code can be modified and re-distributed under any combination
  of the above listed licenses. If contributor does not agree with
  some of the licenses, he/she can delete appropriate line.
  Warning, if you delete all lines, you are not allowed to
  distribute source code and/or binaries utilizing code.
  
  See files COPYING and README for details.

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

#ifndef _UL_HPTREE_H
#define _UL_HPTREE_H

#ifdef __cplusplus
extern "C" {
#endif

typedef struct ul_hpt_node {
  long index;
} ul_hpt_node_t;

typedef struct{
  ul_hpt_node_t **heaparr;
  long count;
  long capacity;
} ul_hpt_root_field_t;

#define ul_hpt_first_i     (1)
#define ul_hpt_parent_i(i) ((i)/2)
#define ul_hpt_left_i(i)   ((i)*2)
#define ul_hpt_right_i(i)  ((i)*2+1)

/* Declaration of heap tree */
#define UL_HPTREE_DEC(cust_prefix, cust_root_t, cust_item_t, cust_key_t,\
		cust_root_field, cust_item_node, cust_item_key, cust_cmp_fnc) \
\
static inline cust_item_t * \
cust_prefix##_node2item(const cust_root_t *root, const ul_hpt_node_t *node) \
  {return (cust_item_t*)((char*)node-(long)&((cust_item_t*)0)->cust_item_node);}\
\
static inline cust_key_t *\
cust_prefix##_node2key(const cust_root_t *root, ul_hpt_node_t *node)\
  { return &(cust_prefix##_node2item(root, node)->cust_item_key);}\
\
int cust_prefix##_init_root_field(cust_root_t *root);\
\
static inline void \
cust_prefix##_init_detached(cust_item_t *item){;}\
\
int cust_prefix##_insert(cust_root_t *root, cust_item_t *item);\
cust_item_t *cust_prefix##_cut_first(cust_root_t *root);\
int cust_prefix##_delete(cust_root_t *root, cust_item_t *item);\
\
static inline cust_item_t *\
cust_prefix##_first(const cust_root_t *root)\
{\
  ul_hpt_node_t *n;\
  if(!root->cust_root_field.count)\
    return NULL;\
  n=root->cust_root_field.heaparr[ul_hpt_first_i];\
  return cust_prefix##_node2item(root,n);\
}\
static inline int \
cust_prefix##_is_empty(const cust_root_t *root)\
{\
  return !root->cust_root_field.count;\
}

#define UL_HPTREE_IMP(cust_prefix, cust_root_t, cust_item_t, cust_key_t,\
		cust_root_field, cust_item_node, cust_item_key, cust_cmp_fnc,\
		cust_ins_fl, cust_first_change, cust_empty_state) \
\
int cust_prefix##_init_root_field(cust_root_t *root)\
  { return ul_hpt_init_root_hpt(&root->cust_root_field, 64);}\
\
static inline int \
cust_prefix##_cmp_hpt_i(cust_root_t *root, ul_hpt_node_t *p, ul_hpt_node_t *r)\
{\
  return cust_cmp_fnc(cust_prefix##_node2key(root,p),\
                      cust_prefix##_node2key(root,r));\
}\
\
int cust_prefix##_insert(cust_root_t *root, cust_item_t *item)\
{\
  long i, j; \
  ul_hpt_node_t *p, *r;\
  i=root->cust_root_field.count+1;\
  if(i>root->cust_root_field.capacity)\
    if(ul_hpt_enlarge_hpt(&root->cust_root_field)<0)\
      return -1;\
  root->cust_root_field.count=i;\
  p=&item->cust_item_node;\
  while(i>ul_hpt_first_i){\
    j=ul_hpt_parent_i(i);\
    r=root->cust_root_field.heaparr[j];\
    if(cust_prefix##_cmp_hpt_i(root,p,r)>=0)\
      break;\
    r->index=i;\
    root->cust_root_field.heaparr[i]=r;\
    i=j;\
  }\
  p->index=i;\
  root->cust_root_field.heaparr[i]=p;\
  if(i<=ul_hpt_first_i){\
    cust_first_change;\
  }\
  return 1;\
}\
\
cust_item_t *cust_prefix##_cut_first(cust_root_t *root)\
{\
  long i, j;\
  ul_hpt_node_t *n, *p, *r;\
  if(!(i=root->cust_root_field.count))\
    return NULL;\
  \
  n=root->cust_root_field.heaparr[ul_hpt_first_i];\
  if((root->cust_root_field.count=i-1)){\
    p=root->cust_root_field.heaparr[i];\
    i=ul_hpt_first_i;\
    while((j=ul_hpt_left_i(i))<=root->cust_root_field.count){\
      r=root->cust_root_field.heaparr[j];\
      if(j!=root->cust_root_field.count)\
        if(cust_prefix##_cmp_hpt_i(root,r,root->cust_root_field.heaparr[j+1])>0)\
          {j++; r=root->cust_root_field.heaparr[j];}\
      if(cust_prefix##_cmp_hpt_i(root,p,r)<=0)\
        break;\
      r->index=i;\
      root->cust_root_field.heaparr[i]=r;\
      i=j;\
    }\
    p->index=i;\
    root->cust_root_field.heaparr[i]=p;\
    cust_first_change;\
  }else{\
    cust_empty_state;\
  }\
  return cust_prefix##_node2item(root,n);\
}\
\
int cust_prefix##_delete(cust_root_t *root, cust_item_t *item)\
{\
  long i, j;\
  ul_hpt_node_t *p, *r;\
  p=&item->cust_item_node;\
  i=p->index;\
  if(i>root->cust_root_field.count) return -1;\
  if(root->cust_root_field.heaparr[i]!=p) return -1;\
  if(i==ul_hpt_first_i){\
    cust_prefix##_cut_first(root);\
    return 1;\
  }\
  if(i==(j=root->cust_root_field.count--))\
    return 0;\
  p=root->cust_root_field.heaparr[j];\
  j=ul_hpt_parent_i(i);\
  r=root->cust_root_field.heaparr[j];\
  if(cust_prefix##_cmp_hpt_i(root,p,r)<0){\
    do{\
      r->index=i;\
      root->cust_root_field.heaparr[i]=r;\
      i=j;\
      j=ul_hpt_parent_i(i);\
      r=root->cust_root_field.heaparr[j];\
      if(cust_prefix##_cmp_hpt_i(root,p,r)>=0)\
	break;\
    }while(1);\
  }else{\
    while((j=ul_hpt_left_i(i))<=root->cust_root_field.count){\
      r=root->cust_root_field.heaparr[j];\
      if(j!=root->cust_root_field.count)\
        if(cust_prefix##_cmp_hpt_i(root,r,root->cust_root_field.heaparr[j+1])>0)\
          {j++; r=root->cust_root_field.heaparr[j];}\
      if(cust_prefix##_cmp_hpt_i(root,p,r)<=0)\
        break;\
      r->index=i;\
      root->cust_root_field.heaparr[i]=r;\
      i=j;\
    }\
  }\
  p->index=i;\
  root->cust_root_field.heaparr[i]=p;\
  return 1;\
}

int ul_hpt_init_root_hpt(ul_hpt_root_field_t *hpt_root, int acapacity);
int ul_hpt_enlarge_hpt(ul_hpt_root_field_t *hpt_root);

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

#endif /* _UL_HPTREE_H */