diff options
Diffstat (limited to 'libparc/parc/algol/parc_TreeMap.h')
| -rwxr-xr-x | libparc/parc/algol/parc_TreeMap.h | 714 |
1 files changed, 0 insertions, 714 deletions
diff --git a/libparc/parc/algol/parc_TreeMap.h b/libparc/parc/algol/parc_TreeMap.h deleted file mode 100755 index 5f0ed8d8..00000000 --- a/libparc/parc/algol/parc_TreeMap.h +++ /dev/null @@ -1,714 +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_TreeMap.h - * @ingroup datastructures - * @brief A Red-Black tree containing PARCObject keys and values. - * - * The map is sorted according to the natural ordering of its keys, - * or by a comparator function provided at creation time, depending on which constructor is used. - * - */ -#ifndef libparc_parc_TreeMap_h -#define libparc_parc_TreeMap_h - -#include <stdlib.h> - -#include "parc_Object.h" -#include "parc_KeyValue.h" -#include "parc_List.h" -#include "parc_Iterator.h" - -struct parc_treemap; -typedef struct parc_treemap PARCTreeMap; - -/** - * Definition of a custom funcion to compare two keys. A function of - * this signature can be provided to CreateCustom(...) constructor to - * override the default parcObject_Compare(...) for comparing key - * objects. This will be used during all internal comparisons. - * - * @param [in] key1 The first key to compare - * @param [in] key2 The second key to compare - * - * @return A signum comparison. negative if key1 is smaller than key2, - * 0 if equal, positive if key1 is bigger. - * - * Example: - * @code - * { - * int _compareKeys(const PARCObject *key1, const PARCObject *key2) {...} - * - * PARCTreeMap * tree1 = parcTreeMap_CreateCustom(_compareKeys); - * - * ... - * - * parcTreeMap_Release(&tree1); - * } - * @endcode - */ -typedef int (PARCTreeMap_CustomCompare)(const PARCObject *key1, const PARCObject *key2); - -/** - * Create a standard `PARCTreeMap` that uses parcObject_Compare for - * comparisons. - * - * @return NULL Error allocating memory - * @return Non-NULL An initialized TreeMap - * - * Example: - * @code - * { - * PARCTreeMap * tree1 = parcTreeMap_Create(.....); - * - * ... - * - * parcTreeMap_Release(&tree1); - * } - * @endcode - */ -PARCTreeMap *parcTreeMap_Create(void); - -/** - * Create a `PARCTreeMap` that uses the provided custom compare - * function for key comparisons. - * - * @param [in] customCompare A cusom function to compare keys (required) - * @return NULL Error allocating memory - * @return Non-NULL An initialized RedBlack tree - * - * Example: - * @code - * { - * int _compareKeys(const PARCObject *key1, const PARCObject *key2) {...} - * - * PARCTreeMap * tree1 = parcTreeMap_CreateCustom(_compareKeys); - * - * ... - * - * parcTreeMap_Release(&tree1); - * } - * @endcode - */ -PARCTreeMap *parcTreeMap_CreateCustom(PARCTreeMap_CustomCompare *customCompare); - -/** - * Acquire a reference to a `PARCTreeMap`. - * - * @param tree The tree reference to acquire. - * - * @return the acquired reference. - * - */ -PARCTreeMap *parcTreeMap_Acquire(const PARCTreeMap *tree); - -/** - * Release a reference to a `PARCTreeMap` object. If it is the last - * reference, the object itself is freed and the specified free - * function is invoked on the stored keys and values. - * - * @param [in,out] treePointer A pointer to a pointer to the `PARCTreeMap` to be released. - * - * Example: - * @code - * { - * PARCTreeMap * tree1 = parcTreeMap_Create(.....); - * - * ... - * - * parcTreeMap_Release(&tree1); - * } - * @endcode - */ -void parcTreeMap_Release(PARCTreeMap **treePointer); - -/** - * Insert a value into the `PARCTreeMap`. If the key exists in the - * tree then the new value will replace the old value. The old key and - * value will be released by the map and the map will acquire a - * reference to the new key and value. The key must not be NULL. - * - * @param [in, out] tree A pointer to an initialized `PARCTreeMap`. - * @param [in] key A pointer to a key - This may not be NULL. - * @param [in] value A pointer to a value. - * - * Example: - * @code - * { - * PARCTreeMap * tree1 = parcTreeMap_Create(.....); - * - * PARCObject *someKey = ...; - * PARCObject *someValue = ...; - * - * parcTreeMap_Put(tree1, someKey, someValue); - * - * parcObject_Release(&someKey); - * parcObject_Release(&someValue); - * parcTreeMap_Release(&tree1); - * } - * @endcode - */ -void parcTreeMap_Put(PARCTreeMap *tree, const PARCObject *key, const PARCObject *value); - -/** - * Checks to see if a PARCTreeMap already contains a key. - * - * @param [in] tree A pointer to an initialized `PARCTreeMap`. - * @param [in] key A pointer to a key - This may not be NULL. - * - * Example: - * @code - * { - * PARCTreeMap * tree1 = parcTreeMap_Create(.....); - * - * ... - * - * PARCObject *someKey = ...; - * - * if (parcTreeMap_ContainsKey(tree1, someKey) { - * ... - * } - * - * parcObject_Release(&someKey); - * parcTreeMap_Release(&tree1); - * } - * @endcode - */ -bool parcTreeMap_ContainsKey(PARCTreeMap *tree, PARCObject *key); - -/** - * Get a value from a `PARCTreeMap`. 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 `PARCTreeMap`. - * @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 - * { - * PARCTreeMap * tree1 = parcTreeMap_Create(.....); - * - * ... - * - * PARCObject *someKey = ...; - * - * PARCObject *someValue = parcTreeMap_Get(tree1, someKey); - * if (someValue != NULL) { - * ... - * } - * - * parcObject_Release(&someKey); - * parcTreeMap_Release(&tree1); - * } - * @endcode - */ -PARCObject *parcTreeMap_Get(PARCTreeMap *tree, const PARCObject *key); - -/** - * Get the first (smallest) key from a `PARCTreeMap`. 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 `PARCTreeMap`. - * @return A pointer to the smallest key. - * - * Example: - * @code - * { - * PARCTreeMap * tree1 = parcTreeMap_Create(.....); - * - * ... - * - * PARCObject *someKey = parcTreeMap_GetFirstKey(tree1); - * if (someKey != NULL) { - * ... - * } - * - * parcTreeMap_Release(&tree1); - * } - * @endcode - */ -PARCObject *parcTreeMap_GetFirstKey(const PARCTreeMap *tree); - -/** - * Get the first entry (one with the smallest key) from a - * `PARCTreeMap`. The returned PARCKeyValue 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 `PARCTreeMap`. - * @return A pointer to the entry (a PARCKeyValue) with the smallest key. - * - * Example: - * @code - * { - * PARCTreeMap * tree1 = parcTreeMap_Create(.....); - * - * ... - * - * PARCKeyValue *someEntry = parcTreeMap_GetFirstEntry(tree1); - * if (someEntry != NULL) { - * ... - * } - * - * parcTreeMap_Release(&tree1); - * } - * @endcode - */ -PARCKeyValue *parcTreeMap_GetFirstEntry(const PARCTreeMap *tree); - -/** - * Get the last (largest) key from a `PARCTreeMap`. 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 `PARCTreeMap`. - * @return A pointer to the largest key. - * - * Example: - * @code - * { - * PARCTreeMap * tree1 = parcTreeMap_Create(.....); - * - * ... - * - * PARCObject *someKey = parcTreeMap_GetLastKey(tree1); - * if (someKey != NULL) { - * ... - * } - * - * parcTreeMap_Release(&tree1); - * } - * @endcode - */ -PARCObject *parcTreeMap_GetLastKey(const PARCTreeMap *tree); - -/** - * Get the last entry (entry with the largest key) from a - * `PARCTreeMap`. The returned entry 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 `PARCTreeMap`. - * @return A pointer to the entry (a PARCKeyValue) with the largest key. - * - * Example: - * @code - * { - * PARCTreeMap * tree1 = parcTreeMap_Create(.....); - * - * ... - * - * PARCKeyValue *lastEntry = parcTreeMap_GetLastEntry(tree1); - * if (lastEntry != NULL) { - * ... - * } - * - * parcTreeMap_Release(&tree1); - * } - * @endcode - */ -PARCKeyValue *parcTreeMap_GetLastEntry(const PARCTreeMap *tree); - -/** - * Get the next largest key from a `PARCTreeMap`. The returned key - * will still be owned by the tree. If the tree is empty or the - * supplied key is the largest, the function will return NULL - * - * @param [in] tree A pointer to an initialized `PARCTreeMap`. - * @return A pointer to the next key. You do not own this value (it's still in the tree). - * - * Example: - * @code - * { - * PARCTreeMap * tree1 = parcTreeMap_Create(.....); - * - * ... - * - * PARCObject *someKey = ...; - * - * PARCObject *nextKey = parcTreeMap_GetHigherKey(tree1, someKey); - * if (nextKey != NULL) { - * ... - * } - * - * parcObject_Release(&someKey); - * parcTreeMap_Release(&tree1); - * } - * @endcode - */ -PARCObject *parcTreeMap_GetHigherKey(const PARCTreeMap *tree, const PARCObject *key); - -/** - * Get the entry with the next largest key from a `PARCTreeMap`. The - * returned entry will still be owned by the tree. If the tree is - * empty or the supplied key is the largest, the function will return - * NULL. - * - * @param [in] tree A pointer to an initialized `PARCTreeMap`. - * @return A pointer to the next entry (a PARCKeyValue). The caller - * does not own this return. - * - * Example: - * @code - * { - * PARCTreeMap * tree1 = parcTreeMap_Create(.....); - * - * ... - * - * PARCObject *someKey = ...; - * - * PARCKeyValue *nextEntry = parcTreeMap_GetHigherEntry(tree1, someKey); - * if (nextEntry != NULL) { - * ... - * } - * - * parcObject_Release(&someKey); - * parcTreeMap_Release(&tree1); - * } - * @endcode - */ -PARCKeyValue *parcTreeMap_GetHigherEntry(const PARCTreeMap *tree, const PARCObject *key); - -/** - * Get the previous key from a `PARCTreeMap`. The returned key will - * still be owned by the tree. If the tree is empty or the supplied - * key is the smallest in the tree, the function will return NULL. - * - * @param [in] tree A pointer to an initialized `PARCTreeMap`. - * @param [in] key A pointer to an key - * @return A pointer to the previous key. The caller - * does not own this return. - * - * Example: - * @code - * { - * PARCTreeMap * tree1 = parcTreeMap_Create(.....); - * - * ... - * - * PARCObject *someKey = ...; - * - * PARCObject *previousKey = parcTreeMap_GetLowerKey(tree1, someKey); - * if (previousKey != NULL) { - * ... - * } - * - * parcObject_Release(&someKey); - * parcTreeMap_Release(&tree1); - * } - * @endcode - */ -PARCObject *parcTreeMap_GetLowerKey(const PARCTreeMap *tree, const PARCObject *key); - -/** - * Get the entry with the next smallest key from a `PARCTreeMap`. The returned entry (a PARCKeyValue) will - * still be owned by the tree. If the tree is empty or the supplied - * key is the smallest in the tree, the function will return NULL. - * - * @param [in] tree A pointer to an initialized `PARCTreeMap`. - * @param [in] key A pointer to an key - * @return A pointer to the previous entry (a PARCKeyValue). The caller - * does not own this return. - * - * Example: - * @code - * { - * PARCTreeMap * tree1 = parcTreeMap_Create(.....); - * - * ... - * - * PARCObject *someKey = ...; - * - * PARCKeyValue *previousEntry = parcTreeMap_GetLowerKey(tree1, someKey); - * if (previousEntry != NULL) { - * ... - * } - * - * parcObject_Release(&someKey); - * parcTreeMap_Release(&tree1); - * } - * @endcode - */ -PARCKeyValue *parcTreeMap_GetLowerEntry(const PARCTreeMap *tree, const PARCObject *key); - -/** - * Remove an entry from a `PARCTreeMap`. The entry will be removed - * from the tree and the tree's reference to the key will be - * released. The value will be returned and responsibility for - * releasing the reference to the value will transfer to the caller. - * The provided key will not be modified. If the key is not found in - * the tree, NULL is returned. - * - * @param [in,out] tree A pointer to an initialized `PARCTreeMap`. - * @param [in] key A pointer to a key (The tree will not own this). - * @return A pointer to a value or NULL. You will now own this value. - * - * Example: - * @code - * { - * PARCTreeMap * tree1 = parcTreeMap_Create(.....); - * - * ... - * - * PARCObject *someKey = ...; - * - * PARCObject *someValue = parcTreeMap_Remove(tree1, someKey); - * if (someValue != NULL) { - * ... - * parcObject_Release(&someValue); - * } - * - * parcObject_Release(&someKey); - * parcTreeMap_Release(&tree1); - * } - * @endcode - */ -PARCObject *parcTreeMap_Remove(PARCTreeMap *tree, const PARCObject *key); - -/** - * Remove and destroy an entry from a `PARCTreeMap`. The entry along with - * it's key & value will be removed and released. - * - * @param [in,out] tree A pointer to an initialized `PARCTreeMap`. - * @param [in] key A pointer to a key (The tree will not own this). - * - * Example: - * @code - * { - * PARCTreeMap * tree1 = parcTreeMap_Create(.....); - * - * ... - * - * PARCObject *someKey = ...; - * - * parcTreeMap_RemoveAndRelease(tree1, someKey); - * - * parcObject_Release(&someKey); - * parcTreeMap_Release(&tree1); - * } - * @endcode - */ -void parcTreeMap_RemoveAndRelease(PARCTreeMap *tree, const PARCObject *key); - -/** - * Get the size (nuber of elements) of a `PARCTreeMap`. - * - * - * @param [in] tree A pointer to an initialized `PARCTreeMap`. - * @return size of the tree (number of elements). - * - * Example: - * @code - * { - * PARCTreeMap * tree1 = parcTreeMap_Create(.....); - * - * ... - * - * if (parcTreeMap_Size(tree1) > 0) { - * ... - * } - * - * parcTreeMap_Release(&tree1); - * } - * @endcode - */ -size_t parcTreeMap_Size(const PARCTreeMap *tree); - -/** - * Get a PARCList of the keys from a `PARCTreeMap`. All keys will be - * valid keys in the `PARCTreeMap`. The caller will own the list of - * keys and should release it when done. The caller will not own the - * keys themselves. 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 per the provided or key's default compare function. - * - * @param [in] tree A pointer to a `PARCTreeMap`. - * @return A list of (pointers to) keys. - * - * Example: - * @code - * { - * PARCTreeMap * tree1 = parcTreeMap_Create(.....); - * - * ... - * - * PARCList *keys = parcTreeMap_AcquireKeys(tree1); - * for (size_t i=0; i < parcList_Size(keys); ++i) { - * ... - * } - * - * parcList_Release(&keys); - * parcTreeMap_Release(&tree1); - * } - * @endcode - */ -PARCList *parcTreeMap_AcquireKeys(const PARCTreeMap *tree); - -/** - * Get an PARCList of the values in this `PARCTreeMap`. All of these - * values will be valid in the `PARCTreeMap`. The caller will own the - * list of values and should release it when done. The list of values - * will be sorted as per the provided or key's default compare - * function. - * - * @param [in] tree A pointer to a `PARCTreeMap`. - * @return A list of (pointers to) values. - * - * Example: - * @code - * { - * PARCTreeMap * tree1 = parcTreeMap_Create(.....); - * - * ... - * - * PARCList *values = parcTreeMap_AcquireValues(tree1); - * for (size_t i=0; i < parcList_Size(values); ++i) { - * ... - * } - * - * parcList_Release(&keys); - * parcTreeMap_Release(&tree1); - * } - * @endcode - */ -PARCList *parcTreeMap_AcquireValues(const PARCTreeMap *tree); - -/** - * Calculate if two `PARCTreeMap`s are equal. - * - * Two trees are equal if they have the same keys associated with the - * same values. The keys & values will be compared using the - * parcObject_Equals(...); - * - * @param [in] tree1 A pointer to a `PARCTreeMap`. - * @param [in] tree2 A pointer to another `PARCTreeMap`. - * @return true if the trees are equal, zero otherwise - * - * Example: - * @code - * { - * PARCTreeMap * tree1 = parcTreeMap_Create(.....); - * PARCTreeMap * tree2 = parcTreeMap_Create(.....); - * - * ... - * - * if (parcTreeMap_Equals(tree1, tree2)) { - * ... - * } - * - * parcTreeMap_Release(&tree1); - * parcTreeMap_Release(&tree2); - * } - * @endcode - */ -bool parcTreeMap_Equals(const PARCTreeMap *tree1, const PARCTreeMap *tree2); - -/** - * Copy a TreeMap. - * - * This will create a completely new tree. It will copy every key and - * every value using parcObject_Copy(...). - * - * @param [in] sourceTree A pointer to a `PARCTreeMap` to be copied - * @return NULL Error copying the tree. - * @return Non-NULL A copy of the `PARCTreeMap`. - * - * Example: - * @code - * { - * PARCTreeMap * source_tree = parcTreeMap_Create(.....); - * - * ... operations on tree ... - * - * PARCTreeMap * tree_copy = parcTreeMap_Copy(source_tree); - * - * ... operations on tree ... - * - * parcTreeMap_Release(&source_tree); - * parcTreeMap_Release(&tree_copy); - * } - * @endcode - */ -PARCTreeMap *parcTreeMap_Copy(const PARCTreeMap *sourceTree); - - -/** - * Create a new instance of PARCIterator that iterates through the keys of the specified `PARCTreeMap`. - * The returned iterator must be released via {@link parcIterator_Release}. - * - * @param [in] hashMap A pointer to a valid `PARCTreeMap`. - * - * @see parcIterator_Release - * Example: - * @code - * { - * PARCIterator *iterator = parcTreeMap_CreateKeyIterator(myTreeMap); - * - * while (parcIterator_HasNext(iterator)) { - * PARCObject *object = parcIterator_Next(iterator); - * } - * - * parcIterator_Release(&iterator); - * } - * @endcode - */ -PARCIterator *parcTreeMap_CreateKeyIterator(PARCTreeMap *tree); - -/** - * Create a new instance of PARCIterator that iterates through the values of the specified `PARCTreeMap`. - * The returned iterator must be released via {@link parcIterator_Release}. - * - * @param [in] hashMap A pointer to a valid `PARCTreeMap`. - * - * @see parcIterator_Release - * Example: - * @code - * { - * PARCIterator *iterator = parcTreeMap_CreateValueIterator(myTreeMap); - * - * while (parcIterator_HasNext(iterator)) { - * PARCObject *object = parcIterator_Next(iterator); - * } - * - * parcIterator_Release(&iterator); - * } - * @endcode - */ -PARCIterator *parcTreeMap_CreateValueIterator(PARCTreeMap *tree); - -/** - * Create a new instance of PARCIterator that iterates through the KeyValue elements of the specified `PARCTreeMap`. - * The returned iterator must be released via {@link parcIterator_Release}. - * - * @param [in] hashMap A pointer to a valid `PARCTreeMap`. - * - * @see parcIterator_Release - * Example: - * @code - * { - * PARCIterator *iterator = parcTreeMap_CreateKeyValueIterator(myTreeMap); - * - * while (parcIterator_HasNext(iterator)) { - * PARCObject *object = parcIterator_Next(iterator); - * } - * - * parcIterator_Release(&iterator); - * } - * @endcode - */ -PARCIterator *parcTreeMap_CreateKeyValueIterator(PARCTreeMap *tree); -#endif // libparc_parc_TreeMap_h |