## gskrbtreemacros

gskrbtreemacros — Flexible Red-Black Trees implemented as macros

## Synopsis

    #define             GSK_RBTREE_INSERT                   (tree, node, collision_node)
    #define             GSK_RBTREE_REMOVE                   (tree, node)
    #define             GSK_RBTREE_LOOKUP                   (tree, key, out)
    #define             GSK_RBTREE_LOOKUP_COMPARATOR        (tree, key, key_comparator, out)
    #define             GSK_RBTREE_FIRST                    (tree, out)
    #define             GSK_RBTREE_LAST                     (tree, out)
    #define             GSK_RBTREE_NEXT                     (tree, in, out)
    #define             GSK_RBTREE_PREV                     (tree, in, out)
    #define             GSK_RBTREE_SUPREMUM                 (tree, key, out)
    #define             GSK_RBTREE_SUPREMUM_COMPARATOR      (tree, key, key_comparator, out)
    #define             GSK_RBTREE_INFIMUM                  (tree, key, out)
    #define             GSK_RBTREE_INFIMUM_COMPARATOR       (tree, key, key_comparator, out)
    #define             GSK_RBCTREE_INSERT                  (tree, node, collision_node)
    #define             GSK_RBCTREE_REMOVE                  (tree, node)
    #define             GSK_RBCTREE_LOOKUP                  (tree, key, out)
    #define             GSK_RBCTREE_LOOKUP_COMPARATOR       (tree, key, key_comparator, out)
    #define             GSK_RBCTREE_FIRST                   (tree, out)
    #define             GSK_RBCTREE_LAST                    (tree, out)
    #define             GSK_RBCTREE_NEXT                    (tree, in, out)
    #define             GSK_RBCTREE_PREV                    (tree, in, out)
    #define             GSK_RBCTREE_SUPREMUM                (tree, key, out)
    #define             GSK_RBCTREE_SUPREMUM_COMPARATOR     (tree, key, key_comparator, out)
    #define             GSK_RBCTREE_INFIMUM                 (tree, key, out)
    #define             GSK_RBCTREE_INFIMUM_COMPARATOR      (tree, key, key_comparator, out)
    #define             GSK_RBCTREE_GET_BY_INDEX            (tree, index, out)
    #define             GSK_RBCTREE_GET_BY_INDEX_UNCHECKED  (tree, index, out)
    #define             GSK_RBCTREE_GET_NODE_INDEX          (tree, node, index_out)

## Description

The macros defined here allow you to implement efficient red-black trees which put their data in existing node structures. Besides efficiency, this can be much more convenient because the same node may be a member of multiple trees. It shares these characteristics in common with the gsklistmacros, so that a member of a rbtree may be a member of a gsk-list, etc etc. all simultanteously.

TODO: Description of what an rbtree is.

The actual rbtree consists of a macro with eight arguments:

top | ...
type* | ...
is_red | ...
set_is_red | ...
parent | ...
left, right | ...
comparator | ...

TODO: Description of what an rbctree is.

The actual rbctree consists of a macro with ten arguments:

top | ...
type* | ...
is_red | ...
set_is_red | ...
get_count | ...
set_count | ...
parent | ...
left, right | ...
comparator | ...

TODO: example use cases.

TODO: Some example programs.

## Details

### GSK_RBTREE_INSERT()

    #define             GSK_RBTREE_INSERT(tree, node, collision_node)

Add a new node into the rbtree, potentially removing another node of the same key, which will be returned in `collision_node`.

`tree` : | The RBTree (a macro that expands to eight arguments) to affect.
`node` : | The node to insert. It should not be in the tree initially. Its parent, left and right pointers will be initialized.
`collision_node` : | A variable that will be set to NULL if there was no collision, or the node that was replaced if there was a collision.

### GSK_RBTREE_REMOVE()

    #define             GSK_RBTREE_REMOVE(tree, node)

Remove a new from the tree.

`tree` : | The RBTree (a macro that expands to eight arguments) to affect.
`node` : | The node to remove from the tree.

### GSK_RBTREE_LOOKUP()

    #define             GSK_RBTREE_LOOKUP(tree, key, out)

Lookup a node in the tree.

This will use the same comparator as the normal tree lookup, so the `key` should probably be something that looks like a node. See GSK_RBTREE_LOOKUP_COMPARATOR for a method to do the lookup using a key that is in a different format.

`tree` : | The RBTree (a macro that expands to eight arguments) to query.
`key` : | A node whose equivalent we are trying to find.
`out` : | The node that was found, or NULL if no node was found.

### GSK_RBTREE_LOOKUP_COMPARATOR()

    #define             GSK_RBTREE_LOOKUP_COMPARATOR(tree, key, key_comparator, out)

Lookup a node in the tree.

`tree` : | The RBTree (a macro that expands to eight arguments) to query.
`key` : | A key to lookup.
`key_comparator` : | A macro that takes three arguments: the `key`, a node from the tree, and a variable which should be set to -1,0,1 if the key is less than, equal to or greater than the node, respectively.
`out` : | The node that was found, or NULL if no node was found.

### GSK_RBTREE_FIRST()

    #define             GSK_RBTREE_FIRST(tree, out)

Get the first element of the tree. (The first element is the least element, as determined by the comparator)

`tree` : | The RBTree (a macro that expands to eight arguments) to query.
`out` : | A variable which will be set to the first element in the tree, or NULL if the tree is empty.

### GSK_RBTREE_LAST()

    #define             GSK_RBTREE_LAST(tree, out)

Get the last element of the tree. (The last element is the greatest element, as determined by the comparator)

`tree` : | The RBTree (a macro that expands to eight arguments) to query.
`out` : | A variable which will be set to the last element in the tree, or NULL if the tree is empty.

### GSK_RBTREE_NEXT()

    #define             GSK_RBTREE_NEXT(tree, in, out)

Get the next element in the tree, after a given element.

`in` and `out` may be the same variable.

`tree` : | The RBTree (a macro that expands to eight arguments) to traverse.
`in` : | The starting element (must be non-NULL)
`out` : | A variable which will be set to the next element in the tree, or NULL if `in` was the last element.

### GSK_RBTREE_PREV()

    #define             GSK_RBTREE_PREV(tree, in, out)

Get the previous element in the tree, after a given element.

`in` and `out` may be the same variable.

`tree` : | The RBTree (a macro that expands to eight arguments) to traverse.
`in` : | The starting element (must be non-NULL)
`out` : | A variable which will be set to the previous element in the tree, or NULL if `in` was the first element.

### GSK_RBTREE_SUPREMUM()

    #define             GSK_RBTREE_SUPREMUM(tree, key, out)

Find the first node in the tree which is after or equal to `key`.

`tree` : | The RBTree (a macro that expands to eight arguments) to query.
`key` : | The key to lookup.
`out` : | Set the the first node in the tree which is after or equal to `key`, according to the usual tree comparator, or NULL if no element is greater than or equal to `key`.

### GSK_RBTREE_SUPREMUM_COMPARATOR()

    #define             GSK_RBTREE_SUPREMUM_COMPARATOR(tree, key, key_comparator, out)

Find the first node in the tree which is after or equal to `key`.

`tree` : | The RBTree (a macro that expands to eight arguments) to query.
`key` : | The key to lookup.
`key_comparator` : | A macro that takes three arguments: the `key`, a node from the tree, and a variable which should be set to -1,0,1 if the key is less than, equal to or greater than the node, respectively.
`out` : | Set the the first node in the tree which is after or equal to `key`, according to `key_comparator`, or NULL if no element is greater than or equal to `key`.

### GSK_RBTREE_INFIMUM()

    #define             GSK_RBTREE_INFIMUM(tree, key, out)

Find the last node in the tree which is before or equal to `key`.

`tree` : | The RBTree (a macro that expands to eight arguments) to query.
`key` : | The key to lookup.
`out` : | Set the the last node in the tree which is before or equal to `key`, according to the usual tree comparator, or NULL if no element is less than or equal to `key`.

### GSK_RBTREE_INFIMUM_COMPARATOR()

    #define             GSK_RBTREE_INFIMUM_COMPARATOR(tree, key, key_comparator, out)

Find the last node in the tree which is before or equal to `key`.

`tree` : | The RBTree (a macro that expands to eight arguments) to query.
`key` : | The key to lookup.
`key_comparator` : | A macro that takes three arguments: the `key`, a node from the tree, and a variable which should be set to -1,0,1 if the key is less than, equal to or greater than the node, respectively.
`out` : | Set the the last node in the tree which is before or equal to `key`, according to `key_comparator`, or NULL if no element is less than or equal to `key`.

### GSK_RBCTREE_INSERT()

    #define             GSK_RBCTREE_INSERT(tree, node, collision_node)

Add a new node into the rbtree, potentially removing another node of the same key, which will be returned in `collision_node`.

`tree` : | The RBCTree (a macro that expands to ten arguments) to affect.
`node` : | The node to insert. It should not be in the tree initially. Its parent, left and right pointers will be initialized.
`collision_node` : | A variable that will be set to NULL if there was no collision, or the node that was replaced if there was a collision.

### GSK_RBCTREE_REMOVE()

    #define             GSK_RBCTREE_REMOVE(tree, node)

Remove a new from the tree.

`tree` : | The RBCTree (a macro that expands to ten arguments) to affect.
`node` : | The node to remove from the tree.

### GSK_RBCTREE_LOOKUP()

    #define             GSK_RBCTREE_LOOKUP(tree, key, out)

Lookup a node in the tree.

This will use the same comparator as the normal tree lookup, so the `key` should probably be something that looks like a node. See GSK_RBCTREE_LOOKUP_COMPARATOR for a method to do the lookup using a key that is in a different format.

`tree` : | The RBCTree (a macro that expands to ten arguments) to query.
`key` : | A node whose equivalent we are trying to find.
`out` : | The node that was found, or NULL if no node was found.

### GSK_RBCTREE_LOOKUP_COMPARATOR()

    #define             GSK_RBCTREE_LOOKUP_COMPARATOR(tree, key, key_comparator, out)

Lookup a node in the tree.

`tree` : | The RBCTree (a macro that expands to ten arguments) to query.
`key` : | A key to lookup.
`key_comparator` : | A macro that takes three arguments: the `key`, a node from the tree, and a variable which should be set to -1,0,1 if the key is less than, equal to or greater than the node, respectively.
`out` : | The node that was found, or NULL if no node was found.

### GSK_RBCTREE_FIRST()

    #define             GSK_RBCTREE_FIRST(tree, out)

Get the first element of the tree. (The first element is the least element, as determined by the comparator)

`tree` : | The RBCTree (a macro that expands to ten arguments) to query.
`out` : | A variable which will be set to the first element in the tree, or NULL if the tree is empty.

### GSK_RBCTREE_LAST()

    #define             GSK_RBCTREE_LAST(tree, out)

Get the last element of the tree. (The last element is the greatest element, as determined by the comparator)

`tree` : | The RBCTree (a macro that expands to eight arguments) to query.
`out` : | A variable which will be set to the last element in the tree, or NULL if the tree is empty.

### GSK_RBCTREE_NEXT()

    #define             GSK_RBCTREE_NEXT(tree, in, out)

Get the next element in the tree, after a given element.

`in` and `out` may be the same variable.

`tree` : | The RBCTree (a macro that expands to ten arguments) to traverse.
`in` : | The starting element (must be non-NULL)
`out` : | A variable which will be set to the next element in the tree, or NULL if `in` was the last element.

### GSK_RBCTREE_PREV()

    #define             GSK_RBCTREE_PREV(tree, in, out)

Get the previous element in the tree, after a given element.

`in` and `out` may be the same variable.

`tree` : | The RBCTree (a macro that expands to ten arguments) to traverse.
`in` : | The starting element (must be non-NULL)
`out` : | A variable which will be set to the previous element in the tree, or NULL if `in` was the first element.

### GSK_RBCTREE_SUPREMUM()

    #define             GSK_RBCTREE_SUPREMUM(tree, key, out)

Find the first node in the tree which is after or equal to `key`.

`tree` : | The RBCTree (a macro that expands to ten arguments) to query.
`key` : | The key to lookup.
`out` : | Set the the first node in the tree which is after or equal to `key`, according to the usual tree comparator, or NULL if no element is greater than or equal to `key`.

### GSK_RBCTREE_SUPREMUM_COMPARATOR()

    #define             GSK_RBCTREE_SUPREMUM_COMPARATOR(tree, key, key_comparator, out)

Find the first node in the tree which is after or equal to `key`.

`tree` : | The RBCTree (a macro that expands to ten arguments) to query.
`key` : | The key to lookup.
`key_comparator` : | A macro that takes three arguments: the `key`, a node from the tree, and a variable which should be set to -1,0,1 if the key is less than, equal to or greater than the node, respectively.
`out` : | Set the the first node in the tree which is after or equal to `key`, according to `key_comparator`, or NULL if no element is greater than or equal to `key`.

### GSK_RBCTREE_INFIMUM()

    #define             GSK_RBCTREE_INFIMUM(tree, key, out)

Find the last node in the tree which is before or equal to `key`.

`tree` : | The RBCTree (a macro that expands to ten arguments) to query.
`key` : | The key to lookup.
`out` : | Set the the last node in the tree which is before or equal to `key`, according to the usual tree comparator, or NULL if no element is less than or equal to `key`.

### GSK_RBCTREE_INFIMUM_COMPARATOR()

    #define             GSK_RBCTREE_INFIMUM_COMPARATOR(tree, key, key_comparator, out)

Find the last node in the tree which is before or equal to `key`.

`tree` : | The RBCTree (a macro that expands to ten arguments) to query.
`key` : | The key to lookup.
`key_comparator` : | A macro that takes three arguments: the `key`, a node from the tree, and a variable which should be set to -1,0,1 if the key is less than, equal to or greater than the node, respectively.
`out` : | Set the the last node in the tree which is before or equal to `key`, according to `key_comparator`, or NULL if no element is less than or equal to `key`.

### GSK_RBCTREE_GET_BY_INDEX()

    #define             GSK_RBCTREE_GET_BY_INDEX(tree, index, out)

Find the N-th node in the tree.

`tree` : | The RBCTree (a macro that expands to ten arguments) to query.
`index` : | The index of the node which you want to find.
`out` : | variable to store the `index`-th node in, or NULL if `index` is out-of-range.

### GSK_RBCTREE_GET_BY_INDEX_UNCHECKED()

    #define             GSK_RBCTREE_GET_BY_INDEX_UNCHECKED(tree, index, out)

Find the N-th node in the tree, assuming that `index` is valid.

`tree` : | The RBCTree (a macro that expands to ten arguments) to query.
`index` : | The index of the node which you want to find.
`out` : | variable to store the `index`-th node in. This routine will crash if `index` is out-of-range.

### GSK_RBCTREE_GET_NODE_INDEX()

    #define             GSK_RBCTREE_GET_NODE_INDEX(tree, node, index_out)

Get the index of an arbitrary node.

`tree` : | The RBCTree (a macro that expands to ten arguments) to query.
`node` : | The node to obtain the index of.
`index_out` : | variable to store the index of `node` in.

## See Also

gskqsortmacro