summaryrefslogtreecommitdiffstats
path: root/libparc/parc/algol/parc_TreeMap.h
diff options
context:
space:
mode:
Diffstat (limited to 'libparc/parc/algol/parc_TreeMap.h')
-rwxr-xr-xlibparc/parc/algol/parc_TreeMap.h714
1 files changed, 714 insertions, 0 deletions
diff --git a/libparc/parc/algol/parc_TreeMap.h b/libparc/parc/algol/parc_TreeMap.h
new file mode 100755
index 00000000..5f0ed8d8
--- /dev/null
+++ b/libparc/parc/algol/parc_TreeMap.h
@@ -0,0 +1,714 @@
+/*
+ * 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