Class: AutoC::TreeSet

Inherits:

Collection

• Object
• Code
• Type
• Collection
• AutoC::TreeSet

Includes:

Iterators::Bidirectional, Sets

Defined in:

lib/autoc/collection/tree_set.rb

Overview

TreeSet< E > is a sorted container holding unique elements.

The TreeSet implements the Red-Black Tree algorithm.

This code is an adaptation of the rbtree code from the NLNetLabs LDNS project.

The collection’s C++ counterpart is std::set<> template class.

Generated C interface

Collection management

void typeCopy(Type * dst, Type * src)	Create a new set dst filled with the contents of src. A copy operation is performed on every element in src. NOTE: Previous contents of dst is overwritten.
void typeCtor(Type * self)	Create a new empty set self. NOTE: Previous contents of self is overwritten.
void typeDtor(Type * self)	Destroy set self. Stored elements are destroyed as well by calling the respective destructors.
int typeEqual(Type * lt, Type * rt)	Return non-zero value if sets lt and rt are considered equal by contents and zero value otherwise.
size_t typeIdentify(Type * self)	Return hash code for set self.

Basic operations

int typeContains(Type * self, E what)	Return non-zero value if set self contains an element considered equal to the element what and zero value otherwise.
int typeEmpty(Type * self)	Return non-zero value if set self contains no elements and zero value otherwise.
E typeGet(Type * self, E what)	Return a copy of the element in self considered equal to the element what. WARNING: self must contain such element otherwise the behavior is undefined. See typeContains().
E typePeekLowest(Type * self)	Return a copy of the lowest element in self. WARNING: self must not be empty otherwise the behavior is undefined. See typeEmpty().
E typePeekHighest(Type * self)	Return a copy of the highest element in self. WARNING: self must not be empty otherwise the behavior is undefined. See typeEmpty().
void typePurge(Type * self)	Remove and destroy all elements stored in self.
int typePut(Type * self, E what)	Put a copy of the element what into self only if there is no such element in self which is considered equal to what. Return non-zero value on successful element put (that is there was not such element in self) and zero value otherwise.
int typeReplace(Type * self, E with)	If self contains an element which is considered equal to the element with, replace that element with a copy of with, otherwise do nothing. Replaced element is destroyed. Return non-zero value if the replacement was actually performed and zero value otherwise.
int typeRemove(Type * self, E what)	Remove and destroy an element in self which is considered equal to the element what. Return non-zero value on successful element removal and zero value otherwise.
size_t typeSize(Type * self)	Return number of elements stored in self.

Logical operations

void typeExclude(Type * self, Type * other)	Perform the difference operation that is self will retain only the elements not contained in other. Removed elements are destroyed.
void typeInclude(Type * self, Type * other)	Perform the union operation that is self will contain the elements from both self and other. self receives the copies of extra elements in other.
void typeInvert(Type * self, Type * other)	Perform the symmetric difference operation that is self will retain the elements contained in either self or other, but not in both. Removed elements are destroyed, extra elements are copied.
void typeRetain(Type * self, Type * other)	Perform the intersection operation that is self will retain only the elements contained in both self and other. Removed elements are destroyed.

Iteration

void itCtor(IteratorType * it, Type * self)	Create a new ascending iterator it on tree self. See itCtorEx(). NOTE: Previous contents of it is overwritten.
void itCtorEx(IteratorType * it, Type * self, int ascending)	Create a new iterator it on tree self. Non-zero value of ascending specifies an ascending (lowest to highest element traversal) iterator, zero value specifies a descending (highest to lowest element traversal) iterator. NOTE: Previous contents of it is overwritten.
int itMove(IteratorType * it)	Advance iterator position of it and return non-zero value if new position is valid and zero value otherwise.
E itGet(IteratorType * it)	Return a copy of current element pointed to by the iterator it. WARNING: current position must be valid otherwise the behavior is undefined. See itMove().

Instance Attribute Summary

Attributes inherited from Collection

#element, #it_ref

Attributes inherited from Type

#type, #type_ref

Instance Method Summary

• #initialize(*args) ⇒ TreeSet constructor

  A new instance of TreeSet.

• #write_impls(stream, define) ⇒ Object
• #write_intf_decls(stream, declare, define) ⇒ Object
• #write_intf_types(stream) ⇒ Object

Methods inherited from Collection

#==, #comparable?, #constructible?, #copyable?, #destructible?, #entities, #hash, #hashable?, #initializable?

Methods inherited from Type

#==, #abort, #assert, #calloc, coerce, #comparable?, #constructible?, #copyable?, #destructible?, #entities, #extern, #free, #hash, #hashable?, #initializable?, #inline, #malloc, #method_missing, #orderable?, #prefix, #private?, #public?, #sortable?, #static, #static?, #write_decls, #write_defs, #write_intf

Methods inherited from Code

#attach, #entities, #priority, #source_size, #write_decls, #write_defs, #write_intf

Constructor Details

#initialize(*args) ⇒ TreeSet

Returns a new instance of TreeSet

# File 'lib/autoc/collection/tree_set.rb', line 175

def initialize(*args)
  super
  key_requirement(element)
end

Dynamic Method Handling

This class handles dynamic methods through the method_missing method in the class AutoC::Type

Instance Method Details

#write_impls(stream, define) ⇒ Object

# File 'lib/autoc/collection/tree_set.rb', line 212

def write_impls(stream, define)
  super
  stream << %$
    #define #{isRed}(x) (x->color)
    #define #{isBlack}(x) !#{isRed}(x)
    #define #{setRed}(x) (x->color = 1)
    #define #{setBlack}(x) (x->color = 0)
    #define #{compare}(lt, rt) (#{element.equal(:lt, :rt)} ? 0 : (#{element.less(:lt, :rt)} ? -1 : +1))
    static #{node} #{nullNode} = {0, NULL, NULL, NULL};
    static #{node}* #{null} = &#{nullNode};
    static void #{destroyNode}(#{node}* node) {
      #{assert}(node);
      #{assert}(node != #{null});
      #{element.dtor("node->element")};
      #{free}(node);
    }
    #{define} #{ctor.definition} {
      #{assert}(self);
      self->size = 0;
      self->root = #{null};
    }
    static void #{destroy}(#{node}* node) {
      if(node != #{null}) {
        #{destroy}(node->left);
        #{destroy}(node->right);
        #{destroyNode}(node);
      }
    }
    #{define} #{dtor.definition} {
      #{assert}(self);
      #{destroy}(self->root); /* FIXME recursive algorithm might be inefficient */
    }
    #{define} void #{purge}(#{type_ref} self) {
      #{assert}(self);
      #{dtor}(self);
      #{ctor}(self);
    }
    static void #{rotateLeft}(#{type_ref} self, #{node}* node) {
      #{node}* right = node->right;
      node->right = right->left;
      if(right->left != #{null}) right->left->parent = node;
      right->parent = node->parent;
      if(node->parent != #{null}) {
        if(node == node->parent->left) {
          node->parent->left = right;
        } else {
          node->parent->right = right;
        }
      } else {
        self->root = right;
      }
      right->left = node;
      node->parent = right;
    }
    static void #{rotateRight}(#{type_ref} self, #{node}* node) {
      #{node}* left = node->left;
      node->left = left->right;
      if(left->right != #{null}) left->right->parent = node;
      left->parent = node->parent;
      if(node->parent != #{null}) {
        if(node == node->parent->right) {
          node->parent->right = left;
        } else {
          node->parent->left = left;
        }
      } else {
        self->root = left;
      }
      left->right = node;
      node->parent = left;
    }
    static void #{insertFixup}(#{type_ref} self, #{node}* node) {
      #{node}* uncle;
      while(node != self->root && #{isRed}(node->parent)) {
        if(node->parent == node->parent->parent->left) {
          uncle = node->parent->parent->right;
          if(#{isRed}(uncle)) {
            #{setBlack}(node->parent);
            #{setBlack}(uncle);
            #{setRed}(node->parent->parent);
            node = node->parent->parent;
          } else {
            if(node == node->parent->right) {
              node = node->parent;
              #{rotateLeft}(self, node);
            }
            #{setBlack}(node->parent);
            #{setRed}(node->parent->parent);
            #{rotateRight}(self, node->parent->parent);
          }
        } else {
          uncle = node->parent->parent->left;
          if(#{isRed}(uncle)) {
            #{setBlack}(node->parent);
            #{setBlack}(uncle);
            #{setRed}(node->parent->parent);
            node = node->parent->parent;
          } else {
            if(node == node->parent->left) {
              node = node->parent;
              #{rotateRight}(self, node);
            }
            #{setBlack}(node->parent);
            #{setRed}(node->parent->parent);
            #{rotateLeft}(self, node->parent->parent);
          }
        }
      }
      #{setBlack}(self->root);
    }
    static void #{deleteFixup}(#{type_ref} self, #{node}* child, #{node}* child_parent) {
      #{node}* sibling;
      int go_up = 1;
      if(child_parent->right == child) sibling = child_parent->left; else sibling = child_parent->right;
      while(go_up) {
        if(child_parent == #{null}) return;
        if(#{isRed}(sibling)) {
          #{setRed}(child_parent);
          #{setBlack}(sibling);
          if(child_parent->right == child) #{rotateRight}(self, child_parent); else #{rotateLeft}(self, child_parent);
          if(child_parent->right == child) sibling = child_parent->left; else sibling = child_parent->right;
        }
        if(#{isBlack}(child_parent) && #{isBlack}(sibling) && #{isBlack}(sibling->left) && #{isBlack}(sibling->right)) {
          if(sibling != #{null}) #{setRed}(sibling);
          child = child_parent;
          child_parent = child_parent->parent;
          if(child_parent->right == child) sibling = child_parent->left; else sibling = child_parent->right;
        } else go_up = 0;
      }
      if(#{isRed}(child_parent) && #{isBlack}(sibling) && #{isBlack}(sibling->left) && #{isBlack}(sibling->right)) {
        if(sibling != #{null}) #{setRed}(sibling);
        #{setBlack}(child_parent);
        return;
      }
      if(child_parent->right == child && #{isBlack}(sibling) && #{isRed}(sibling->right) && #{isBlack}(sibling->left)) {
        #{setRed}(sibling);
        #{setBlack}(sibling->right);
        #{rotateLeft}(self, sibling);
        if(child_parent->right == child) sibling = child_parent->left; else sibling = child_parent->right;
      } else if(child_parent->left == child && #{isBlack}(sibling) && #{isRed}(sibling->left) && #{isBlack}(sibling->right)) {
        #{setRed}(sibling);
        #{setBlack}(sibling->left);
        #{rotateRight}(self, sibling);
        if(child_parent->right == child) sibling = child_parent->left; else sibling = child_parent->right;
      }
      sibling->color = child_parent->color;
      #{setBlack}(child_parent);
      if(child_parent->right == child) {
        #{setBlack}(sibling->left);
        #{rotateRight}(self, child_parent);
      } else {
        #{setBlack}(sibling->right);
        #{rotateLeft}(self, child_parent);
      }
    }
    static #{node}* #{findNode}(#{type_ref} self, #{element.type} element) {
      int r;
      #{node}* node;
      #{assert}(self);
      node = self->root;
      while(node != #{null}) {
        if((r = #{compare}(element, node->element)) == 0) {
          return node;
        }
        if(r < 0) {
          node = node->left;
        } else {
          node = node->right;
        }
      }
      return NULL;
    }
    #{define} int #{contains}(#{type_ref} self, #{element.type} element) {
      #{assert}(self);
      return #{findNode}(self, element) != NULL;
    }
    #{define} #{element.type} #{get}(#{type_ref} self, #{element.type} element) {
      #{node} *node;
      #{element.type} result;
      #{assert}(self);
      #{assert}(#{contains}(self, element));
      node = #{findNode}(self, element);
      #{element.copy("result", "node->element")}; /* Here we rely on NULL pointer dereference to manifest the failure! */
      return result;
    }
    #{define} int #{put}(#{type_ref} self, #{element.type} element) {
      int r;
      #{node}* data;
      #{node}* node;
      #{node}* parent;
      #{assert}(self);
      node = self->root;
      parent = #{null};
      while(node != #{null}) {
        if((r = #{compare}(element, node->element)) == 0) {
          return 0;
        }
        parent = node;
        if (r < 0) {
          node = node->left;
        } else {
          node = node->right;
        }
      }
      data = #{malloc}(sizeof(#{node})); #{assert}(data);
      #{element.copy("data->element", "element")};
      data->parent = parent;
      data->left = data->right = #{null};
      #{setRed}(data);
      ++self->size;
      if(parent != #{null}) {
        if(r < 0) {
          parent->left = data;
        } else {
          parent->right = data;
        }
      } else {
        self->root = data;
      }
      #{insertFixup}(self, data);
      return 1;
    }
    #{define} int #{replace}(#{type_ref} self, #{element.type} element) {
      int removed;
      #{assert}(self);
      /* FIXME removing followed by putting might be inefficient */
      if((removed = #{remove}(self, element))) #{put}(self, element);
      return removed;
    }
    static void #{swapColors}(#{node}* x, #{node}* y) {
      int t = x->color;
      #{assert}(x);
      #{assert}(y);
      x->color = y->color;
      y->color = t;
    }
    static void #{swapNodes}(#{node}** x, #{node}** y) {
      #{node}* t = *x; *x = *y; *y = t; 
    }
    static void #{changeParent}(#{type_ref} self, #{node}* parent, #{node}* old_node, #{node}* new_node) {
      if(parent == #{null}) {
        if(self->root == old_node) self->root = new_node;
        return;
      }
      if(parent->left == old_node) parent->left = new_node;
      if(parent->right == old_node) parent->right = new_node;
    }
    static void #{changeChild}(#{node}* child, #{node}* old_node, #{node}* new_node) {
      if(child == #{null}) return;
      if(child->parent == old_node) child->parent = new_node;
    }
    int #{remove}(#{type_ref} self, #{element.type} element) {
      #{node}* to_delete;
      #{node}* child;
      #{assert}(self);
      if((to_delete = #{findNode}(self, element)) == NULL) return 0;
      if(to_delete->left != #{null} && to_delete->right != #{null}) {
        #{node} *smright = to_delete->right;
        while(smright->left != #{null}) smright = smright->left;
        #{swapColors}(to_delete, smright);
        #{changeParent}(self, to_delete->parent, to_delete, smright);
        if(to_delete->right != smright) #{changeParent}(self, smright->parent, smright, to_delete);
        #{changeChild}(smright->left, smright, to_delete);
        #{changeChild}(smright->left, smright, to_delete);
        #{changeChild}(smright->right, smright, to_delete);
        #{changeChild}(smright->right, smright, to_delete);
        #{changeChild}(to_delete->left, to_delete, smright);
        if(to_delete->right != smright) #{changeChild}(to_delete->right, to_delete, smright);
        if(to_delete->right == smright) {
          to_delete->right = to_delete;
          smright->parent = smright;
        }
        #{swapNodes}(&to_delete->parent, &smright->parent);
        #{swapNodes}(&to_delete->left, &smright->left);
        #{swapNodes}(&to_delete->right, &smright->right);
      }
      if(to_delete->left != #{null}) child = to_delete->left; else child = to_delete->right;
      #{changeParent}(self, to_delete->parent, to_delete, child);
      #{changeChild}(child, to_delete, to_delete->parent);
      if(#{isRed}(to_delete)) {} else if(#{isRed}(child)) {
        if(child != #{null}) #{setBlack}(child);
      } else #{deleteFixup}(self, child, to_delete->parent);
      #{destroyNode}(to_delete);
      --self->size;
      return 1;
    }
    static #{node}* #{lowestNode}(#{type_ref} self) {
      #{node}* node;
      #{assert}(self);
      node = self->root;
      if(self->root != #{null}) {
        for(node = self->root; node->left != #{null}; node = node->left);
      }
      return node;
    }
    static #{node}* #{highestNode}(#{type_ref} self) {
      #{node}* node;
      #{assert}(self);
      node = self->root;
      if(self->root != #{null}) {
        for(node = self->root; node->right != #{null}; node = node->right);
      }
      return node;
    }
    static #{node}* #{nextNode}(#{node}* node) {
      #{node}* parent;
      #{assert}(node);
      if(node->right != #{null}) {
        for(node = node->right;
          node->left != #{null};
          node = node->left);
      } else {
        parent = node->parent;
        while(parent != #{null} && node == parent->right) {
          node = parent;
          parent = parent->parent;
        }
        node = parent;
      }
      return node;
    }
    static #{node}* #{prevNode}(#{node}* node) {
      #{node}* parent;
      #{assert}(node);
      if(node->left != #{null}) {
        for(node = node->left;
          node->right != #{null};
          node = node->right);
      } else {
        parent = node->parent;
        while(parent != #{null} && node == parent->left) {
          node = parent;
          parent = parent->parent;
        }
        node = parent;
      }
      return node;
    }
    #{define} #{element.type} #{peekLowest}(#{type_ref} self) {
      #{node}* node;
      #{element.type} result;
      #{assert}(self);
      #{assert}(!#{empty}(self));
      node = #{lowestNode}(self);
      #{assert}(node);
      #{assert}(node != #{null});
      #{element.copy("result", "node->element")};
      return result;
    }
    #{define} #{element.type} #{peekHighest}(#{type_ref} self) {
      #{node}* node;
      #{element.type} result;
      #{assert}(self);
      #{assert}(!#{empty}(self));
      node = #{highestNode}(self);
      #{assert}(node);
      #{assert}(node != #{null});
      #{element.copy("result", "node->element")};
      return result;
    }
    #{define} void #{itCtorEx}(#{it_ref} self, #{type_ref} tree, int ascending) {
      #{assert}(self);
      #{assert}(tree);
      self->node = (self->ascending = ascending) ? #{lowestNode}(tree) : #{highestNode}(tree);
      self->start = 1;
    }
    #{define} int #{itMove}(#{it_ref} self) {
      #{assert}(self);
      if(self->start) {
        self->start = 0;
      } else {
        self->node = self->ascending ? #{nextNode}(self->node) : #{prevNode}(self->node);
      }
      return self->node != #{null};
    }
    static #{element.type_ref} #{itGetRef}(#{it_ref} self) {
      #{assert}(self);
      #{assert}(self->node);
      #{assert}(self->node != #{null});
      return &self->node->element;
    }
    #{define} #{element.type} #{itGet}(#{it_ref} self) {
      #{element.type} result;
      #{assert}(self);
      #{element.copy("result", "*#{itGetRef}(self)")};
      return result;
    }
  $
end

#write_intf_decls(stream, declare, define) ⇒ Object

# File 'lib/autoc/collection/tree_set.rb', line 204

def write_intf_decls(stream, declare, define)
  super
  stream << %$
    #{declare} #{element.type} #{peekLowest}(#{type_ref});
    #{declare} #{element.type} #{peekHighest}(#{type_ref});
  $
end

#write_intf_types(stream) ⇒ Object

# File 'lib/autoc/collection/tree_set.rb', line 180

def write_intf_types(stream)
  super
  stream << %$
    typedef struct #{type} #{type};
    typedef struct #{node} #{node};
    typedef struct #{it} #{it};
    struct #{type} {
      #{node}* root;
      size_t size;
    };
    struct #{it} {
      int start, ascending;
      #{node}* node;
    };
    struct #{node} {
      int color;
      #{node}* left;
      #{node}* right;
      #{node}* parent;
      #{element.type} element;
    };
  $
end