CObject
Public Member Functions | Data Fields
CCBinaryTree Struct Reference
Trees

Implements the CITree interface with a binary tree/heap. More...

#include <CCBinaryTree.h>

+ Inheritance diagram for CCBinaryTree:

Public Member Functions

const struct CCBinaryTree_VTable * CCBinaryTree_GetVTable ()
 
CError CCBinaryTree (struct CCBinaryTree *self, size_t element_size, size_t max_size, signed char(*compare)(const void *, const void *), size_t key_size)
 
CITreeError CITree_Push (struct CITree *self, const void *element, const void *key)
 
CITreeError CITree_Pop (struct CITree *self, void *element)
 
CITreeError CITree_DeleteElement (struct CITree *self, void *element)
 
CITreeError CITree_Peek (struct CITree *self, void *element)
 
CITreeError CITree_Get (struct CITree *self, void *element, size_t index)
 
CITreeError CITree_Delete (struct CITree *self, void *element, size_t index)
 
size_t CITree_Size (struct CITree *self)
 
size_t CITree_MaxSize (struct CITree *self)
 
void CITree_Clear (struct CITree *self)
 

Data Fields

struct CObject cobject
 
struct CITree citree
 
struct CCArrayList tree_backend
 
unsigned char * swap_space_1
 
unsigned char * key_space_1
 
unsigned char * key_space_2
 
signed char(* compare )(const void *, const void *)
 
size_t index
 
size_t element_size
 
size_t key_size
 
size_t max_size
 
struct CInterface interface
 

Detailed Description

Implements the CITree interface with a binaray tree/heap. Data and keys put into the tree are copied by value. This implementation allows arbitrary keys to be used when inserting into the tree. The root of the tree is always the node with the key that evaluates to be smaller than all other keys. The evaluation function for keys is passed into the constructor as a function argument. For example, the tree below uses integers for keys, can have a maximum of 8 nodes, and will save integers in each of its nodes. The code puts an item in with value 0 and key 0, then an item with value 5 and key -3. This will put the -3:5 key:value pair at the root of tree. Next time CITree_Pop() is called, that is the item that gets removed, since its key will evaluate as being the smallest.

static signed char compare_function( const void* key1_p, const void* key2_p )
{
int key1 = *((int*) key1_p);
int key2 = *((int*) key2_p);
if( key1 < key2 ) {
return -1;
}
else if( key1 > key2 ) {
return 1;
}
else {
return 0;
}
}
int main( int argc, char** argv )
{
struct CCBinaryTree tree;
CCBinaryTree(&tree
sizeof(int),
8,
compare_function,
sizeof(int));
int item = 0, key = 0;
CITree_Push(&tree.cITree, &item, &key);
item = 5; key = -3;
CITree_Push(&tree.cITree, &item, &key);
CDestroy(&tree);
}

Constructor & Destructor Documentation

CError CCBinaryTree ( struct CCBinaryTree *  self,
size_t  element_size,
size_t  max_size,
signed char(*)(const void *, const void *)  compare,
size_t  key_size 
)
Class Constructor

Construct a binary tree. The tree's memory is allocated using CMalloc defined in Class.h. When the tree is no longer needed, CDestroy() must be called on it.

Parameters
selfThe tree.
element_sizeThe number of bytes of data per node. This is how many bytes are copied into a node when CITree_Push() is called. This must be greater than or equal to one.
max_sizeThe maximum number of nodes in the tree. This must be greater than or equal to 2.
compareA function pointer used for comparing keys. The prototype of the function is
signed char compare( const void* key1, const void* key2 );
The inputs point to the location of two keys in memory. This method must be return:
  • -1 if key1 evaluates to be less than key2.
  • +1 if key1 evaluates to be greater than key2.
  • 0 if key1 and key2 evalute to be equal. Keeping in mind, that keys which evaluate to be of lower value are moved closer to the root of the tree. An example implementation is given in the description of struct CCBinaryTree.
key_sizeThe size of keys in bytes. Keys are copied into the tree when CITree_Push() is called. This must be greater than or equal to 1.
Returns
  • COBJ_OK: construction successfull.
  • COBJ_INV_PARAM: Input parameters are not valid.
  • COBJ_ALLOC_FAIL: Failed to allocate memory for the tree using CMalloc.

Member Function Documentation

void CITree_Clear ( struct CITree *  self)
inherited

Reset the tree to have zero ndoes in it. All data in the tree is lost.

Parameters
selfThe tree.
CITreeError CITree_Delete ( struct CITree *  self,
void *  element,
size_t  index 
)
inherited

Delete at an arbitrary index in the tree. Indexing is done such that at any index i, left_child(i) = 2i and right_child(i) = 2i + 1.

Parameters
elementPointer to location where data at the index will be copied to. Use NULL to ignore and simply delete from the tree.
indexLocation in the tree to delete data from
Returns
  • CITREE_ERR_EMPTY: Nothing at given index to delete.
  • CITREE_OK: Success.
CITreeError CITree_DeleteElement ( struct CITree *  self,
void *  element 
)
inherited

Delete the node in the three who's element matches the input parameter element. This function has O(n) execution time.

Parameters
selfThe tree.
elementThe data pointed to by this is the search critera. The function will search for a node whos element matches the data pointed to by this and remove it.
Returns
  • CITREE_ERR_EMPTY: Nothing in the tree to delete or no matching element.
  • CITREE_OK: Root of the tree successfully popped.
CITreeError CITree_Get ( struct CITree *  self,
void *  element,
size_t  index 
)
inherited

Look at an arbitrary index in the tree. Indexing is done such that at any index i, left_child(i) = 2i + 1 and right_child(i) = 2i + 2.

Parameters
elementPointer to location where data at the index will be copied to.
indexLocation in the tree to copy data from
Returns
  • CITREE_ERR_EMPTY: Nothing at given index to copy.
  • CITREE_OK: Success.
size_t CITree_MaxSize ( struct CITree *  self)
inherited

The maximum number of nodes which can be added to the tree.

Parameters
selfThe tree.
Returns
The maximum number of nodes which can be added to the tree.
CITreeError CITree_Peek ( struct CITree *  self,
void *  element 
)
inherited

Get the element at the root of the tree without removing it.

Parameters
selfThe tree.
elementA pointer to the location where data will be copied out of the tree.
Returns
  • CITREE_ERR_EMPTY: Nothing in the tree to peek at.
  • CITREE_OK: Root of the tree successfully looked at.
CITreeError CITree_Pop ( struct CITree *  self,
void *  element 
)
inherited

Get the root of the tree and remove it. The tree will then have its nodes adjusted such that the heap property is maintained.

Parameters
selfThe tree.
elementPointer to location where that data at the root of the tree will be copied too. Use NULL to safely ignore.
Returns
  • CITREE_ERR_EMPTY: Nothing in the tree to pop.
  • CITREE_OK: Root of the tree successfully popped.
CITreeError CITree_Push ( struct CITree *  self,
const void *  element,
const void *  key 
)
inherited

Put an element into the tree by copy and move it up the tree such that the heap property is not violated using the input param key to evaluate the heap property. The heap property requires the root of the tree has the key which evaluates to be less than all other keys in the tree.

Parameters
selfThe tree.
elementPointer to data that will be copied into the three.
keyPointer to the key for the data added to the tree.
Returns
  • CITREE_ERR_FULL: No room in tree to insert the element.
  • CITREE_OK: Element successfully inserted.
size_t CITree_Size ( struct CITree *  self)
inherited

Get the current size of tree, ie, how many nodes have been added to the tree.

Parameters
selfThe tree.
Returns
The current size of the tree.
The documentation for this struct was generated from the following file: