set.h

Go to the documentation of this file.

 
#include <stdint.h>
 
#include "common.h"
#include "debug.h"
 
#ifdef ONLY_FOR_DOXYGEN
#include "key.h"
#endif //ONLY_FOR_DOXYGEN
 
#ifndef RBT_SET_H_PREFIX_
#error RBT_SET_H_PREFIX_ is not defined.
#endif // RBT_SET_H_PREFIX_
 
#ifndef RBT_KEY_T
#error RBT_KEY_T is not defined.
#endif // RBT_KEY_T
 
#ifndef RBT_KEY_COUNT_BITS
#error RBT_KEY_COUNT_BITS is not defined.
#endif // RBT_KEY_COUNT_BITS
 
#ifndef RBT_KEY_PTR
#error RBT_KEY_PTR is not defined.
#endif // RBT_KEY_PTR
 
#ifndef RBT_KEY_FPRINT
#error RBT_KEY_FPRINT is not defined.
#endif // RBT_KEY_FPRINT
 
 
#undef RBT_SET_ADD
#define RBT_SET_ADD                          RBT_TOKEN_2_W(RBT_SET_H_PREFIX_, set_add)
 
#undef RBT_SET_DIFFERENCE
#define RBT_SET_DIFFERENCE                   RBT_TOKEN_2_W(RBT_SET_H_PREFIX_, set_difference)
 
#undef RBT_SET_EXCLUSIVE_DISJUNCTION
#define RBT_SET_EXCLUSIVE_DISJUNCTION        RBT_TOKEN_2_W(RBT_SET_H_PREFIX_, set_exclusive_disjunction)
 
#undef RBT_SET_INCLUDES
#define RBT_SET_INCLUDES                     RBT_TOKEN_2_W(RBT_SET_H_PREFIX_, set_includes)
 
#undef RBT_SET_INTERSECTION
#define RBT_SET_INTERSECTION                 RBT_TOKEN_2_W(RBT_SET_H_PREFIX_, set_intersection)
 
#undef RBT_SET_IS_SUBSET
#define RBT_SET_IS_SUBSET                    RBT_TOKEN_2_W(RBT_SET_H_PREFIX_, set_is_subset)
 
#undef RBT_SET_REMOVE
#define RBT_SET_REMOVE                       RBT_TOKEN_2_W(RBT_SET_H_PREFIX_, set_remove)
 
#undef RBT_SET_UNION
#define RBT_SET_UNION                        RBT_TOKEN_2_W(RBT_SET_H_PREFIX_, set_union)
 
#undef RBT_SET_MODIFY_DIFFERENCE
#define RBT_SET_MODIFY_DIFFERENCE            RBT_TOKEN_2_W(RBT_SET_H_PREFIX_, set_modify_difference)
 
#undef RBT_SET_MODIFY_EXCLUSIVE_DISJUNCTION
#define RBT_SET_MODIFY_EXCLUSIVE_DISJUNCTION RBT_TOKEN_2_W(RBT_SET_H_PREFIX_, set_modify_exclusive_disjunction)
 
#undef RBT_SET_MODIFY_INTERSECTION
#define RBT_SET_MODIFY_INTERSECTION          RBT_TOKEN_2_W(RBT_SET_H_PREFIX_, set_modify_intersection)
 
#undef RBT_SET_MODIFY_UNION
#define RBT_SET_MODIFY_UNION                 RBT_TOKEN_2_W(RBT_SET_H_PREFIX_, set_modify_union)
 
 
 
/*
  Internal definitions.
*/
#undef _RBT_SET_DIFFERENCE_TRAVERSE
#define _RBT_SET_DIFFERENCE_TRAVERSE                   _RBT_TOKEN_2_W(RBT_SET_H_PREFIX_, set_difference_traverse)
 
#undef _RBT_SET_MODIFY_EXCLUSIVE_DISJUNCTION_TRAVERSE
#define _RBT_SET_MODIFY_EXCLUSIVE_DISJUNCTION_TRAVERSE _RBT_TOKEN_2_W(RBT_SET_H_PREFIX_, set_modify_exclusive_disjunction_traverse)
 
#undef _RBT_SET_MODIFY_INTERSECTION_FILTER
#define _RBT_SET_MODIFY_INTERSECTION_FILTER            _RBT_TOKEN_2_W(RBT_SET_H_PREFIX_, set_modify_intersection_filter)
 
#undef _RBT_SET_MODIFY_INTERSECTION_TRAVERSE
#define _RBT_SET_MODIFY_INTERSECTION_TRAVERSE          _RBT_TOKEN_2_W(RBT_SET_H_PREFIX_, set_modify_intersection_traverse)
 
#undef _RBT_SET_MODIFY_IS_SUBSET_TRAVERSE
#define _RBT_SET_MODIFY_IS_SUBSET_TRAVERSE             _RBT_TOKEN_2_W(RBT_SET_H_PREFIX_, set_modify_subset_traverse)
 
#undef _RBT_SET_MODIFY_UNION_TRAVERSE
#define _RBT_SET_MODIFY_UNION_TRAVERSE                 _RBT_TOKEN_2_W(RBT_SET_H_PREFIX_, set_modify_union_traverse)
 
#undef _RBT_SET_MODIFY_DIFFERENCE_TRAVERSE
#define _RBT_SET_MODIFY_DIFFERENCE_TRAVERSE            _RBT_TOKEN_2_W(RBT_SET_H_PREFIX_, set_modify_difference_traverse)
 
 
 
 
#undef RBT_NODE_H_PREFIX_
#define RBT_NODE_H_PREFIX_ RBT_SET_H_PREFIX_
 
#undef RBT_VALUE_T
#define RBT_VALUE_T int
 
#undef RBT_VALUE_NULL
#define RBT_VALUE_NULL 0
 
#undef RBT_VALUE_IS_EQUAL
#define RBT_VALUE_IS_EQUAL(a, b) (a == b)
 
#undef RBT_VALUE_COPY
#define RBT_VALUE_COPY(var,val,fail) var = val
 
#undef RBT_VALUE_FREE
#define RBT_VALUE_FREE(val)
 
#undef RBT_VALUE_FPRINT
#define RBT_VALUE_FPRINT(fd, val) \
do \
{ \
  if (val != RBT_VALUE_NULL) \
  { \
    fprintf(fd, "%d", val); \
  } \
} while(0)
 
#include "node.h"
#include "traverse_with_key.h"
 
#undef RBT_WRAPPER_H_PREFIX_
#define RBT_WRAPPER_H_PREFIX_ RBT_SET_H_PREFIX_
#include "wrapper.h"
 
 
 
int
_RBT_SET_MODIFY_UNION_TRAVERSE(
  RBT_KEY_DATA_T * key_data,
  RBT_KEY_SIZE_T height,
  va_list args
)
{
  RBT_NODE_T * target;
 
  if (! RBT_VALUE_IS_NULL(key_data->node->value))
  {
    target = va_arg(args, RBT_NODE_T *);
 
    RBT_NODE_RETRIEVE(
      target, key_data->key, key_data->bits, RBT_RETRIEVE_ACTION_INSERT, 1, NULL
    );
  }
  return 0;
}
 
void
RBT_SET_MODIFY_UNION(RBT_NODE_T * a, RBT_NODE_T * b)
{
  RBT_NODE_TRAVERSE_WITH_KEY(b, _RBT_SET_MODIFY_UNION_TRAVERSE, a);
}
 
 
RBT_NODE_T *
RBT_SET_UNION(RBT_NODE_T * a, RBT_NODE_T * b)
{
  RBT_NODE_T * c;
 
  c = RBT_NODE_COPY(a);
  RBT_NODE_TRAVERSE_WITH_KEY(b, _RBT_SET_MODIFY_UNION_TRAVERSE, c);
  return c;
}
 
 
 
 
 
 
int
_RBT_SET_MODIFY_DIFFERENCE_TRAVERSE(
  RBT_KEY_DATA_T * key_data,
  RBT_KEY_SIZE_T height,
  va_list args
)
{
  RBT_NODE_T * target, * parent;
 
  if (! RBT_VALUE_IS_NULL(key_data->node->value))
  {
    target = va_arg(args, RBT_NODE_T *);
 
    target = RBT_NODE_RETRIEVE(
      target, key_data->key, key_data->bits, RBT_RETRIEVE_ACTION_NOTHING, RBT_VALUE_NULL, &parent
    );
    if (target != NULL)
    {
      RBT_NODE_REMOVE(target, parent);
    }
  }
  return 0;
}
 
void
RBT_SET_MODIFY_DIFFERENCE(RBT_NODE_T * a, RBT_NODE_T * b)
{
  RBT_NODE_TRAVERSE_WITH_KEY(b, _RBT_SET_MODIFY_DIFFERENCE_TRAVERSE, a);
}
 
int
_RBT_SET_DIFFERENCE_TRAVERSE(
  RBT_KEY_DATA_T * key_data,
  RBT_KEY_SIZE_T height,
  va_list args
)
{
  RBT_NODE_T * b, * c;
 
  if (! RBT_VALUE_IS_NULL(key_data->node->value))
  {
    b = va_arg(args, RBT_NODE_T *);
    c = va_arg(args, RBT_NODE_T *);
 
    b = RBT_NODE_RETRIEVE(
      b, key_data->key, key_data->bits, RBT_RETRIEVE_ACTION_NOTHING, RBT_VALUE_NULL, NULL
    );
    /*
      If the value does not exist in b, insert it.
    */
    if (b == NULL)
    {
      RBT_NODE_RETRIEVE(
        c, key_data->key, key_data->bits, RBT_RETRIEVE_ACTION_INSERT_OR_REPLACE, b->value, NULL
      );
    }
  }
  return 0;
}
 
RBT_NODE_T *
RBT_SET_DIFFERENCE(RBT_NODE_T * a, RBT_NODE_T * b)
{
  RBT_NODE_T * c;
 
  c = RBT_NODE_NEW();
  RBT_NODE_TRAVERSE_WITH_KEY(a, _RBT_SET_DIFFERENCE_TRAVERSE, b, c);
  return c;
}
 
 
 
 
int
_RBT_SET_MODIFY_INTERSECTION_FILTER(
  RBT_KEY_DATA_T * key_data,
  va_list args
)
{
  RBT_NODE_T * target;
 
  if (! RBT_VALUE_IS_NULL(key_data->node->value))
  {
    target = va_arg(args, RBT_NODE_T *);
 
    target = RBT_NODE_RETRIEVE(
      target, key_data->key, key_data->bits, RBT_RETRIEVE_ACTION_NOTHING, RBT_VALUE_NULL, NULL
    );
    return (target == NULL);
  }
  return 1;
}
 
void
RBT_SET_MODIFY_INTERSECTION(RBT_NODE_T * a, RBT_NODE_T * b)
{
  RBT_NODE_FILTER_WITH_KEY(a, _RBT_SET_MODIFY_INTERSECTION_FILTER, 0, b);
}
 
RBT_NODE_T *
RBT_SET_INTERSECTION(RBT_NODE_T * a, RBT_NODE_T * b)
{
  RBT_NODE_T * c;
  c = RBT_NODE_COPY(a);
  RBT_SET_MODIFY_INTERSECTION(c, b);
  return c;
}
 
 
 
int
_RBT_SET_MODIFY_EXCLUSIVE_DISJUNCTION_TRAVERSE(
  RBT_KEY_DATA_T * key_data,
  RBT_KEY_SIZE_T height,
  va_list args
)
{
  RBT_NODE_T * target, * parent;
 
  if (! RBT_VALUE_IS_NULL(key_data->node->value))
  {
    target = va_arg(args, RBT_NODE_T *);
 
    target = RBT_NODE_RETRIEVE(
      target, key_data->key, key_data->bits, RBT_QUERY_ACTION_INSERT, RBT_VALUE_NULL, &parent
    );
    if (target->value)
    {
      RBT_NODE_REMOVE(target, parent);
    }
    else
    {
      target->value = 1;
    }
  }
  return 0;
}
 
void
RBT_SET_MODIFY_EXCLUSIVE_DISJUNCTION(RBT_NODE_T * a, RBT_NODE_T * b)
{
  RBT_NODE_TRAVERSE_WITH_KEY(b, _RBT_SET_MODIFY_EXCLUSIVE_DISJUNCTION_TRAVERSE, a);
}
 
RBT_NODE_T *
RBT_SET_EXCLUSIVE_DISJUNCTION(RBT_NODE_T * a, RBT_NODE_T * b)
{
  RBT_NODE_T * c;
  c = RBT_NODE_COPY(a);
  RBT_NODE_TRAVERSE_WITH_KEY(b, _RBT_SET_MODIFY_EXCLUSIVE_DISJUNCTION_TRAVERSE, c);
  return c;
}
 
 
 
int
_RBT_SET_IS_SUBSET_TRAVERSE(
  RBT_KEY_DATA_T * key_data,
  RBT_KEY_SIZE_T height,
  va_list args
)
{
  int * is_subset;
  RBT_NODE_T * target;
 
  if (! RBT_VALUE_IS_NULL(key_data->node->value))
  {
    target = va_arg(args, RBT_NODE_T *);
    is_subset = va_arg(args, int *);
 
    target = RBT_NODE_RETRIEVE(
      target, key_data->key, key_data->bits, RBT_RETRIEVE_ACTION_NOTHING, RBT_VALUE_NULL, NULL
    );
    if (target == NULL)
    {
      * is_subset = 0;
      return 1;
    }
  }
  return 0;
}
 
int
RBT_SET_IS_SUBSET(RBT_NODE_T * a, RBT_NODE_T * b)
{
  int is_subset;
  is_subset = 1;
  /*
    a and b are "switched" here compared to previous functions because each node
    in `a` must be found in `b`, i.e. `a` is traversed.
  */
  RBT_NODE_TRAVERSE_WITH_KEY(a, _RBT_SET_IS_SUBSET_TRAVERSE, b, &is_subset);
  return is_subset;
}
 
 
 
 
void
RBT_SET_ADD(RBT_NODE_T * set, RBT_KEY_T item)
{
  RBT_INSERT(set, item, 1);
}
 
void
RBT_SET_REMOVE(RBT_NODE_T * set, RBT_KEY_T item)
{
  RBT_DELETE(set, item);
}
 
int
RBT_SET_INCLUDES(RBT_NODE_T * set, RBT_KEY_T item)
{
  return RBT_HAS_KEY(set, item);
}