/*
 * 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_FAVLTREE_H_
#define KERN_FAVLTREE_H_ 

#include <arch/types.h>

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


typedef struct favltree_node favltree_node_t;
typedef struct favltree favltree_t;


/** FAVL tree node structure. */
struct favltree_node
{
	/** 
	 * Pointer to left descendand of this node.
	 *
	 * All keys of nodes in the left subtree are less then key of this node.
	 */
	struct favltree_node *lft;
	
	/** 
	 * Pointer to right descendand of this node.
	 *
	 * All keys of nodes in the right subtree are greater then key of this node.
	 */
	struct favltree_node *rgt;
	
	/** Pointer to parent node. Root node has NULL parent. */
	struct favltree_node *par;
	
	/** Nodes key. */
	uint64_t key; 
	
	/** Difference between heights of left and right subtree of this node.*/
	int8_t balance;
};

/** FAVL tree structure. */
struct favltree
{
	/** FAVL root node pointer */
	struct favltree_node *root;
	
	/** Pointer to node with minimal key. */
	struct favltree_node *first;
	
	/** 
	 * Base of tree is value that is smaller or equal then every value in tree 
	 * (valid for positive keys otherwise ignore this atribute).
	 *  
	 * Base is added to current key when new node is inserted into tree.
	 * Base is changed to the key of node which is deleted with function
	 *      avltree_delete_min.
	 */
	uint64_t base;
};


/** Create empty FAVL tree.
 *
 * @param t FAVL tree.
 */
static inline void favltree_create (favltree_t *t)
{
	t->root = NULL;
	t->first = NULL;
	t->base = 0;
}

/** Initialize node.
 *
 * @param Node which is initialized.
 */
static inline void favltree_node_initialize(favltree_node_t *node)
{
	node->key = 0;
	node->lft = NULL;
	node->rgt = NULL;
	node->par = NULL;
	node->balance = 0;
}

/** Find node with smallest key in tree.
 *
 * @param t FAVL tree.
 * @return Pointer to node with smallest key or if tree is empty then returns NULL.
 */
static inline favltree_node_t *favltree_find_min(favltree_t *t)
{
	return t->first;
}

favltree_node_t *favltree_search(favltree_t *t, uint64_t key);
void favltree_insert(favltree_t *t, favltree_node_t *newnode);
void favltree_delete(favltree_t *t, favltree_node_t *node);
bool favltree_delete_min(favltree_t *t);

#endif

/** @}
 */