/*
 * Copyright (C) 2007 Vojtech Mencl 
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * - Redistributions of source code must retain the above copyright
 *   notice, this list of conditions and the following disclaimer.
 * - Redistributions in binary form must reproduce the above copyright
 *   notice, this list of conditions and the following disclaimer in the
 *   documentation and/or other materials provided with the distribution.
 * - The name of the author may not be used to endorse or promote products
 *   derived from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

/** @addtogroup genericadt
 * @{
 */
/** @file
 */


#ifndef KERN_EXTAVLRELTREE_H_
#define KERN_EXTAVLRELTREE_H_

#include <arch/types.h>

typedef struct extavlreltree_node extavlreltree_node_t;
typedef struct extavlreltree extavlreltree_t;


/*
 * Makro for getting pointer to structure which enclosure extavlreltree structure.
 *
 * @param link Pointer to extavlreltree structure.
 * @param type Name of outer structure.
 * @param member Name of extavlreltree atribute in outer structure.
 */
#define extavlreltree_get_instance(link,type,member) \
	((type *)(((uint8_t *)(link)) - ((uint8_t *)&(((type *)NULL)->member))))



/** Relative key Extended AVL tree node structure. */
struct extavlreltree_node
{
	/** 
	 * Pointer to left descendand of this node.
	 *
	 * All keys of nodes in the left subtree are less then key of this node.
	 */
	extavlreltree_node_t *lft; 

	/** 
	 * Pointer to right descendand of this node.
	 *
	 * All keys of nodes in the right subtree are greater then key of this node.
	 */
	extavlreltree_node_t *rgt;  
	
	/** Pointer to parent node. Root node has NULL parent. */
	extavlreltree_node_t *par;  

	/** Pointer to next node which has equal or the closest greater key or head. */
	extavlreltree_node_t *next; 
	
	/** Pointer to previous node which has equal or the closest lesser key or head. */
	extavlreltree_node_t *prev;
	
	/** Height of left subtree. */
	int16_t lft_height;

	/** Height of right subtree. */
	int16_t rgt_height;     

	/** Nodes key. */
	uint64_t key; 

	/** Sum of all keys in the right subtree. */ 
	uint64_t rgt_sum;
};

/** Relative key Extended AVL tree structure (ExtAvlrel). */
struct extavlreltree
{
	/*
	 * ExtAvlrel root node pointer. 
	 *
	 * Important only for recognition of non tree node.
	 */
	extavlreltree_node_t *root;

	/** Head of doubly linked list of nodes. It is entrance point to the tree. */
	extavlreltree_node_t head;
};



/** Create empty Extended AVL tree.
 *
 * @param t Extended AVL tree structure.
 */
static inline void extavlreltree_create (extavlreltree_t *t) 
{
	t->root = NULL;

	t->head.next = &t->head;
	t->head.prev = &t->head;
}

/** Initialize node.
 *
 * @param node Node which is initialized.
 */
static inline void extavlreltree_node_initialize(extavlreltree_node_t *node)
{
	node->lft = NULL;
	node->rgt = NULL;
	node->lft_height = 0;
	node->rgt_height = 0;
	node->par = NULL;
	node->next = node;
	node->prev = node;
	node->rgt_sum = 0;
}

extavlreltree_node_t *extavlreltree_search(extavlreltree_t *t, uint64_t key);
void extavlreltree_insert(extavlreltree_t *t, extavlreltree_node_t *newnode);
void extavlreltree_delete(extavlreltree_t *t, extavlreltree_node_t *node);
bool extavlreltree_delete_min(extavlreltree_t *t);

#endif

/** @}
 */