kzc_binary_tree.h File Reference

Binary search tree. More...

#include "kzc_comparator.h"
#include <system/kzs_types.h>
#include <system/debug/kzs_error.h>
#include <system/kzs_header.h>

Classes
struct	KzcBinaryTreeIterator
	Read-only iterator for binary tree. More...

Macros
#define	kzcBinaryTreeIterate(iterator_param)
	Finds the next entry in the attached binary tree. More...
#define	kzcBinaryTreeIteratorGetValue(iterator_param)
	Returns the value of the binary tree entry pointed by the iterator. More...

Functions
kzsError	kzcBinaryTreeCreate (const struct KzcMemoryManager *memoryManager, KzcComparatorFunction comparator, struct KzcBinaryTree **out_binaryTree)
	Creates a new initially empty binary tree. More...
kzsError	kzcBinaryTreeDelete (struct KzcBinaryTree *binaryTree)
	Frees the memory allocated for the binary tree. More...
kzsError	kzcBinaryTreeAdd (struct KzcBinaryTree *binaryTree, void *element)
	Adds the specified element to the binary tree. More...
kzsError	kzcBinaryTreeRemove (struct KzcBinaryTree *binaryTree, const void *element)
	Removes the specified element from the binary tree. More...
kzUint	kzcBinaryTreeGetSize (const struct KzcBinaryTree *binaryTree)
	Returns the number of elements in the binary tree. More...
void *	kzcBinaryTreeGetFirst (const struct KzcBinaryTree *binaryTree)
	Returns the first element in the tree. More...
void *	kzcBinaryTreeGetLast (const struct KzcBinaryTree *binaryTree)
	Returns the last element in the tree. More...
struct KzcBinaryTreeIterator	kzcBinaryTreeGetIterator (const struct KzcBinaryTree *binaryTree)
	Returns an iterator for all elements in the binary tree. More...
kzBool	kzcBinaryTreeIterate_private (struct KzcBinaryTreeIterator *iterator)
void *	kzcBinaryTreeIteratorGetValue_private (const struct KzcBinaryTreeIterator *iterator)
void *	kzcBinaryTreeGetLower (const struct KzcBinaryTree *binaryTree, const void *element)
	Gets the biggest element that is smaller than the given element. More...
void *	kzcBinaryTreeGetLowerOrEqual (const struct KzcBinaryTree *binaryTree, const void *element)
	Gets the biggest element that is smaller or equal than the given element. More...
void *	kzcBinaryTreeGetHigher (const struct KzcBinaryTree *binaryTree, const void *element)
	Gets the smallest element that is bigger than the given element. More...
void *	kzcBinaryTreeGetHigherOrEqual (const struct KzcBinaryTree *binaryTree, const void *element)
	Gets the smallest element that is bigger or equal than the given element. More...
kzsError	kzcBinaryTreeClear (struct KzcBinaryTree *binaryTree)
	Clears the tree by removing all nodes from it. More...

Detailed Description

Binary search tree.

Copyright 2008-2020 by Rightware. All rights reserved.

Macro Definition Documentation

#define kzcBinaryTreeIterate

(

iterator_param

)

Finds the next entry in the attached binary tree.

Returns KZ_TRUE if next entry is found, otherwise KZ_FALSE.

#define kzcBinaryTreeIteratorGetValue

(

iterator_param

)

Returns the value of the binary tree entry pointed by the iterator.

Function Documentation

kzsError kzcBinaryTreeCreate	(	const struct KzcMemoryManager *	memoryManager,
		KzcComparatorFunction	comparator,
		struct KzcBinaryTree **	out_binaryTree
	)

Creates a new initially empty binary tree.

Parameters

memoryManager	The memory manager to use for allocating the tree and any nodes to it.
comparator	A function that is used to compare two elements and specify the order of elements in the tree.
out_binaryTree	A pointer that is set to point to the new binary tree.

Returns

KZS_SUCCESS on success.

kzsError kzcBinaryTreeDelete

(

struct KzcBinaryTree *

binaryTree

)

Frees the memory allocated for the binary tree.

kzsError kzcBinaryTreeAdd	(	struct KzcBinaryTree *	binaryTree,
		void *	element
	)

Adds the specified element to the binary tree.

The element must not already exist in the tree.

Returns

KZC_ERROR_DUPLICATE_ELEMENT if the element already exists in the tree, KZS_SUCCESS on success.

kzsError kzcBinaryTreeRemove	(	struct KzcBinaryTree *	binaryTree,
		const void *	element
	)

Removes the specified element from the binary tree.

Decides equality by using the KzcComparatorFunction previously passed to kzcBinaryTreeCreate().

Returns

KZC_ERROR_ELEMENT_NOT_FOUND if the element is not found, KZS_SUCCESS on success.

kzUint kzcBinaryTreeGetSize

(

const struct KzcBinaryTree *

binaryTree

)

Returns the number of elements in the binary tree.

void* kzcBinaryTreeGetFirst

(

const struct KzcBinaryTree *

binaryTree

)

Returns the first element in the tree.

void* kzcBinaryTreeGetLast

(

const struct KzcBinaryTree *

binaryTree

)

Returns the last element in the tree.

struct KzcBinaryTreeIterator kzcBinaryTreeGetIterator

(

const struct KzcBinaryTree *

binaryTree

)

Returns an iterator for all elements in the binary tree.

kzBool kzcBinaryTreeIterate_private

(

struct KzcBinaryTreeIterator *

iterator

)

See also

kzcBinaryTreeIterate

void* kzcBinaryTreeIteratorGetValue_private

(

const struct KzcBinaryTreeIterator *

iterator

)

See also

kzcBinaryTreeIteratorGetValue

void* kzcBinaryTreeGetLower	(	const struct KzcBinaryTree *	binaryTree,
		const void *	element
	)

Gets the biggest element that is smaller than the given element.

The KzcComparatorFunction previously passed to kzcBinaryTreeCreate() specifies the order.

void* kzcBinaryTreeGetLowerOrEqual	(	const struct KzcBinaryTree *	binaryTree,
		const void *	element
	)

Gets the biggest element that is smaller or equal than the given element.

The KzcComparatorFunction previously passed to kzcBinaryTreeCreate() specifies the order.

void* kzcBinaryTreeGetHigher	(	const struct KzcBinaryTree *	binaryTree,
		const void *	element
	)

Gets the smallest element that is bigger than the given element.

The KzcComparatorFunction previously passed to kzcBinaryTreeCreate() specifies the order.

void* kzcBinaryTreeGetHigherOrEqual	(	const struct KzcBinaryTree *	binaryTree,
		const void *	element
	)

Gets the smallest element that is bigger or equal than the given element.

The KzcComparatorFunction previously passed to kzcBinaryTreeCreate() specifies the order.

kzsError kzcBinaryTreeClear

(

struct KzcBinaryTree *

binaryTree

)

Clears the tree by removing all nodes from it.