diff options
Diffstat (limited to 'libparc/parc/algol/parc_TreeRedBlack.h')
| -rwxr-xr-x | libparc/parc/algol/parc_TreeRedBlack.h | 384 |
1 files changed, 0 insertions, 384 deletions
diff --git a/libparc/parc/algol/parc_TreeRedBlack.h b/libparc/parc/algol/parc_TreeRedBlack.h deleted file mode 100755 index 52d4af36..00000000 --- a/libparc/parc/algol/parc_TreeRedBlack.h +++ /dev/null @@ -1,384 +0,0 @@ -/* - * Copyright (c) 2017 Cisco and/or its affiliates. - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at: - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -/** - * @file parc_TreeRedBlack.h - * @ingroup datastructures - * @brief A red-black tree is a type of self-balancing binary search tree, - * a data structure used in computer science, typically used to implement associative arrays. - * - */ -#ifndef libparc_parc_TreeRedBlack_h -#define libparc_parc_TreeRedBlack_h - -#include <stdlib.h> -#include <parc/algol/parc_ArrayList.h> - -struct parc_tree_redblack; -typedef struct parc_tree_redblack PARCTreeRedBlack; - -/** - * Compare two keys (signum) - * - * This is the definition of a function that takes two keys and compares them. - * It is a signum function. A user of the RedBlack tree will provide this function on creation - * so the tree can perform it's operations. - * - * @param [in] key1 The first key to compare - * @param [in] key2 The second key to compare - * @return A signum comparison. negative if key 1 is smaller, 0 if key1 == key2, greater than 0 if key1 is bigger. - * - * Example: - * @code - * <#example#> - * @endcode - */ -typedef int (PARCTreeRedBlack_KeyCompare)(const void *key1, const void *key2); - -/** - * Compare two values for equality - * - * This is a function definiton for a function that compares two values in a `PARCTreeRedBlack`. - * If the values are equal it will return true. If they are not it will return false. - * A function of this type will be given on the creation of the `PARCTreeRedBlack`. It will be used by the tree - * to test equality. - * - * @param [in] value1 The first value to compare - * @param [in] value2 The second value to compare - * @return TRUE if the values are considered equal, FALSE if they are not - * - * Example: - * @code - * <#example#> - * @endcode - */ -typedef bool (PARCTreeRedBlack_ValueEquals)(const void *value1, const void *value2); - -/** - * A function to free a value pointer - * - * This is a function definition for a function to free a value in the `PARCTreeRedBlack`. The function should - * free/destroy the value when called. A function of this type will be passed to the `PARCTreeRedBlack` on - * creation. It will be used to destroy values when needed. - * - * @param [in,out] value A pointer to a pointer to a value to be freed. - * - * Example: - * @code - * <#example#> - * @endcode - */ -typedef void (PARCTreeRedBlack_ValueFree)(void **value); - -/** - * A function to free a key pointer - * - * This is a function definition for a function to free a key in the `PARCTreeRedBlack`. The function should - * free/destroy the key when called. A function of this type will be passed to the `PARCTreeRedBlack` on - * creation. It will be used to destroy keys when needed. - * - * @param [in,out] key A pointer to a pointer to a key to be freed. - * - * Example: - * @code - * <#example#> - * @endcode - */ -typedef void (PARCTreeRedBlack_KeyFree)(void **key); - -/** - * Create a copy of a key. - * - * This must be a real copy! (allocating new memory) - * - * This function should create a copy of the key. The copy must pass an equality test to the original key. - * If this function retuns NULL, the tree copy will fail (and return NULL) - * - * @param [in] key A pointer to the key to be copied - * - * @return NULL Memory could not be allocated. - * @return non-NULL A pointer to a new key instance - * - */ -typedef void * (PARCTreeRedBlack_KeyCopy)(const void *key); - -/** - * Create a copy of a value - * - * This must be a real copy! (new memory allocated) - * - * This function should create a copy of the value. The copy must pass an equality test to the original value. - * If this function retuns NULL, the tree copy will fail (and return NULL) - * - * @param [in] value A pointer to the value to be copied - * - * @return NULL Memory could not be allocated. - * @return non-NULL A pointer to a new value instance - * - */ -typedef void * (PARCTreeRedBlack_ValueCopy)(const void *value); - -/** - * Create a `PARCTreeRedBlack` - * - * Create a RedBlack Tree. You must provide a key compare function. - * The valueEquals function will be used to compare 2 trees. If you do not provide such a function - * the values will be compared directly. - * The keyFree and valueFree functions are optional but highly encouraged. They will be used on - * destruction of the tree on any remaining elements. They are also used on deletion of elements. - * - * @param [in] keyCompare A function to compare keys (required) - * @param [in] keyFree A function to free Keys (may be NULL) - * @param [in] keyCopy A function to copy Keys (may be NULL) - * @param [in] valueEquals A function to test value equality (may be NULL) - * @param [in] valueFree A function to free Values (may be NULL) - * @param [in] valueCopy A function to free Keys (may be NULL) - * @return NULL Error allocating memory - * @return Non-NULL An initialized RedBlack tree - * - * Example: - * @code - * <#example#> - * @endcode - */ -PARCTreeRedBlack *parcTreeRedBlack_Create(PARCTreeRedBlack_KeyCompare *keyCompare, - PARCTreeRedBlack_KeyFree *keyFree, - PARCTreeRedBlack_KeyCopy *keyCopy, - PARCTreeRedBlack_ValueEquals *valueEquals, - PARCTreeRedBlack_ValueFree *valueFree, - PARCTreeRedBlack_ValueCopy *valueCopy); - -/** - * Destroy a `PARCTreeRedBlack` - * - * Destroy a `PARCTreeRedBlack`, free all the memory. - * All remaining keys and values will be freed with the respective free functions. - * - * @param [in,out] treePointer A pointer to a pointer to the `PARCTreeRedBlack` to be destroyed. - * - * Example: - * @code - * <#example#> - * @endcode - */ -void parcTreeRedBlack_Destroy(PARCTreeRedBlack **treePointer); - -/** - * Insert a value into the `PARCTreeRedBlack`. - * - * Insert a value into the `PARCTreeRedBlack`. - * If the key exists in the tree then the new value will replace the old value. - * The old key and value will be freed using the provided free functions. - * The tree will take ownership of the key and value. They can't be NULL. - * - * @param [in,out] tree A pointer to an initialized `PARCTreeRedBlack`. - * @param [in] key A pointer to a key - This may not be NULL. - * @param [in] value A pointer to a value - This may not be NULL. - * - * Example: - * @code - * <#example#> - * @endcode - */ -void parcTreeRedBlack_Insert(PARCTreeRedBlack *tree, void *key, void *value); - -/** - * Get a value into the `PARCTreeRedBlack`. - * - * Get a value from a `PARCTreeRedBlack`. - * If the key is not found in the tree NULL is returned. - * The returned value will still be owned by the tree. - * - * @param [in] tree A pointer to an initialized `PARCTreeRedBlack`. - * @param [in] key A pointer to a key (The tree will not own this). - * @return A pointer to a value. You do not own this value (it's still in the tree). - * - * Example: - * @code - * <#example#> - * @endcode - */ -void *parcTreeRedBlack_Get(PARCTreeRedBlack *tree, const void *key); - -/** - * Get the first (smallest) key from a `PARCTreeRedBlack`. - * - * Get the first (smallest) key from a `PARCTreeRedBlack`. - * The returned key will still be owned by the tree. - * If the tree is empty the function will return NULL. - * - * @param [in] tree A pointer to an initialized `PARCTreeRedBlack`. - * @return A pointer to the smallest key. You do not own this value (it's still in the tree). - * - * Example: - * @code - * <#example#> - * @endcode - */ -void *parcTreeRedBlack_FirstKey(const PARCTreeRedBlack *tree); - -/** - * Get the last (largest) key from a `PARCTreeRedBlack`. - * - * Get the last (largest) key from a `PARCTreeRedBlack`. - * The returned key will still be owned by the tree. - * If the tree is empty the function will return NULL - * - * @param [in] tree A pointer to an initialized `PARCTreeRedBlack`. - * @return A pointer to the smallest key. You do not own this value (it's still in the tree). - * - * Example: - * @code - * <#example#> - * @endcode - */ -void *parcTreeRedBlack_LastKey(const PARCTreeRedBlack *tree); - -/** - * Remove a value (and key) from a `PARCTreeRedBlack`. - * - * Remove a value from a `PARCTreeRedBlack`. The value (and key) will no longer be in the tree. - * The (internal) key will be freed. The provided key will not be modified. - * The value associated with the key will be returned. You will own this value. - * If the key is not found in the tree NULL is returned. - * - * @param [in,out] tree A pointer to an initialized `PARCTreeRedBlack`. - * @param [in] key A pointer to a key (The tree will not own this). - * @return A pointer to a value. You will now own this value. - * - * Example: - * @code - * <#example#> - * @endcode - */ -void *parcTreeRedBlack_Remove(PARCTreeRedBlack *tree, const void *key); - -/** - * Remove and destroy a value (and key) from a `PARCTreeRedBlack`. - * - * Delete a value from a `PARCTreeRedBlack`. The value (and key) will no longer be in the tree. - * The value and key will be freed by the tree. The provided key will not be modified. - * - * @param [in,out] tree A pointer to an initialized `PARCTreeRedBlack`. - * @param [in] key A pointer to a key (The tree will not own this). - * - * Example: - * @code - * <#example#> - * @endcode - */ -void parcTreeRedBlack_RemoveAndDestroy(PARCTreeRedBlack *tree, const void *key); - -/** - * Get the size of a `PARCTreeRedBlack`. - * - * Return the size of the tree (number of elements). - * - * @param [in] tree A pointer to an initialized `PARCTreeRedBlack`. - * @return size of the tree (number of elements). - * - * Example: - * @code - * <#example#> - * @endcode - */ -size_t parcTreeRedBlack_Size(const PARCTreeRedBlack *tree); - -/** - * Get an ArrayList of the keys in this tree - * - * Get a list of the keys from this `PARCTreeRedBlack`. All of these keys will be valid keys in the `PARCTreeRedBlack`. - * The caller will own the list of keys and should destroy it when done. The caller will not own - * the keys themselves. Destroying the {@link PARCArrayList} should be enough. - * Note that if the tree is modified or destroyed the key pointers might no longer point to valid keys. - * The list of keys will be sorted (as defined by the key compare function, smallest first) - * - * @param [in] tree A pointer to a `PARCTreeRedBlack`. - * @return A list of (pointers to) keys. - * - * Example: - * @code - * <#example#> - * @endcode - */ -PARCArrayList *parcTreeRedBlack_Keys(const PARCTreeRedBlack *tree); - -/** - * Get an ArrayList of the values in this `PARCTreeRedBlack`. - * - * Get a list of the values from this tree. All of these values will be valid in the `PARCTreeRedBlack`. - * The caller will own the list of values and should destroy it when done. The caller will not own - * the values themselves. Destroying the {@link PARCArrayList} should be enough. - * Note that if the tree is modified or destroyed the value pointers might no longer point to valid values. - * The list of values will be sorted by key (as defined by the key compare function, smallest first). - * - * @param [in] tree A pointer to a `PARCTreeRedBlack`. - * @return A list of (pointers to) values. - * - * Example: - * @code - * <#example#> - * @endcode - */ -PARCArrayList *parcTreeRedBlack_Values(const PARCTreeRedBlack *tree); - -/** - * Calculate if two `PARCTreeRedBlack`s are equal - * - * Compare 2 `PARCTreeRedBlack` for equality. - * Two trees are equal if they have the same keys associated with the same values. The values - * will be compared using the valueEquals function provided on create. If this function was not - * provided it will compare the actual values. - * - * @param [in] tree1 A pointer to a `PARCTreeRedBlack`. - * @param [in] tree2 A pointer to another `PARCTreeRedBlack`. - * @return true if the trees are equal, zero otherwise - * - * Example: - * @code - * <#example#> - * @endcode - */ -int parcTreeRedBlack_Equals(const PARCTreeRedBlack *tree1, const PARCTreeRedBlack *tree2); - -/** - * Copy a RedBlack Tree - * - * Crete a copy of a RedBlack Tree. - * This will create a completely new tree. It will copy every key and every value using the Copy functions - * provided at tree creation. If these functions are NULL then the numeric values will be copied directly. - * - * @param [in] source_tree A pointer to a `PARCTreeRedBlack` to be copied - * @return NULL Error copying the tree. - * @return Non-NULL A copy of the `PARCTreeRedBlack`. - * - * Example: - * @code - * { - * PARCTreeRedBlack * source_tree = parcTreeRedBlack_Create(.....); - * - * ... operations on tree ... - * - * PARCTreeRedBlack * tree_copy = parcTreeRedBlack_Copy(source_tree); - * - * ... operations on tree ... - * - * parcTreeRedBlack_Destroy(&source_tree); - * parcTreeRedBlack_Destroy(&tree_copy); - * } - * @endcode - */ -PARCTreeRedBlack *parcTreeRedBlack_Copy(const PARCTreeRedBlack *source_tree); -#endif // libparc_parc_TreeRedBlack_h |