Changeset 6461

Timestamp:

02/10/08 02:47:49 (5 years ago)

Author:

mrkn

Message:

lang/c/rbtree/branches/bst_inherit_impl/:
* bstree.c: Left and right rotation are implemented.
* bstree_test/bstree_test_module.c, bstree_test/bstree_spec.rb: Tests for left and right rotation are implemented.

Location:

lang/c/rbtree/branches/bst_inherit_impl

Files:

• ChangeLog (modified) (1 diff)
• bstree.c (modified) (1 diff)
• bstree.h (modified) (1 diff)
• bstree_test/bstree_spec.rb (modified) (1 diff)
• bstree_test/bstree_test_module.c (modified) (4 diffs)

lang/c/rbtree/branches/bst_inherit_impl/ChangeLog

@@ +1 @@
+2008-02-10  Kenta Murata  <muraken@gmail.com>
+
+        * bstree.c: Left and right rotation are implemented.
+
+        * bstree_test/bstree_test_module.c, bstree_test/bstree_spec.rb:
+        Tests for left and right rotation are implemented.
+
 2008-02-09  Kenta Murata  <mrkn@gmail.com>
 

lang/c/rbtree/branches/bst_inherit_impl/bstree.c

@@ -75 +75 @@
 
 struct bstree_node*
+bstree_node_rotate_left(struct bstree_node* node)
+{
+  if (0 == node) return 0;
+
+  node->right->parent = node->parent;
+  node->parent = node->right;
+  node->right = node->parent->left;
+  node->parent->left = node;
+
+  return node->parent;
+}
+
+struct bstree_node*
+bstree_node_rotate_right(struct bstree_node* node)
+{
+  if (0 == node) return 0;
+
+  node->left->parent = node->parent;
+  node->parent = node->left;
+  node->left = node->parent->right;
+  node->parent->right = node;
+  
+  return node->parent;
+}
+
+struct bstree_node*
 bstree_node_lookup_lower_bound(struct bstree_node* root,
                                bstree_compare_f compare,

lang/c/rbtree/branches/bst_inherit_impl/bstree.h

@@ -129 +129 @@
 #define bstree_node_is_maximum(node) (0==bstree_node_next(node))
 
+struct bstree_node* bstree_node_rotate_left(struct bstree_node* node);
+struct bstree_node* bstree_node_rotate_right(struct bstree_node* node);
+
 /* returns the maximum node which has a value less than or equal to
  * the given value. */

lang/c/rbtree/branches/bst_inherit_impl/bstree_test/bstree_spec.rb

@@ -167 +167 @@
 end
 
+describe BSTreeNode, "in terms of rotation" do
+  before do
+    @a = BSTreeNode.new 'A'
+    @b = BSTreeNode.new 'B'
+    @c = BSTreeNode.new 'C'
+    @a.children = @b, @c
+    @d = BSTreeNode.new 'D'
+    @e = BSTreeNode.new 'E'
+    @b.children = @d, @e
+    @f = BSTreeNode.new 'F'
+    @g = BSTreeNode.new 'G'
+    @c.children = @f, @g
+  end
+
+  it "check precondition" do
+    @a.parent.should be_nil
+    @a.left.should == @b
+    @a.right.should == @c
+    @b.parent.should == @a
+    @b.left.should == @d
+    @b.right.should == @e
+    @d.parent.should == @b
+    @d.left.should be_nil
+    @d.right.should be_nil
+    @e.parent.should == @b
+    @e.left.should be_nil
+    @e.right.should be_nil
+    @c.parent.should == @a
+    @c.left.should == @f
+    @c.right.should == @g
+    @f.parent.should == @c
+    @f.left.should be_nil
+    @f.right.should be_nil
+    @g.parent.should == @c
+    @g.left.should be_nil
+    @g.right.should be_nil
+  end
+
+  # left rotation at the node `A'
+  #
+  #      A              C
+  #     ,^.            ,^.
+  #    B   C    =>    A   G
+  #       ,^.        ,^.
+  #      F   G      B   F
+  it "@a.rotate_left should returns @c" +
+    ", @c.parent is nil, @c.left is @a" +
+    ", @a.parent is @c, and @a.right is @f" do
+    @a.rotate_left.should == @c
+    @c.parent.should be_nil
+    @c.left.should == @a
+    @c.right.should == @g
+    @a.parent.should == @c
+    @a.left.should == @b
+    @a.right.should == @f
+  end
+
+  # right rotation at the node `A'
+  #
+  #      A             B
+  #     ,^.           ,^.
+  #    B   C    =>   D   A
+  #   ,^.               ,^.
+  #  D   E             E   C
+  it "@a.rotate_right should returns @b" +
+    ", @b.parent is nil, @b.right is @a" +
+    ", @a.parent is @b, and @a.left is @e" do
+    @a.rotate_right.should == @b
+    @b.parent.should be_nil
+    @b.left.should == @d
+    @b.right.should == @a
+    @a.parent.should == @b
+    @a.left.should == @e
+    @a.right.should == @c
+  end
+end

lang/c/rbtree/branches/bst_inherit_impl/bstree_test/bstree_test_module.c

@@ -54 +54 @@
 
   return data->vself;
+}
+
+static VALUE
+rb_bstree_node_initialize(int argc, VALUE* argv, VALUE vself)
+{
+  struct bstree_node* self;
+  struct rb_bstree_node_data* data;
+  VALUE value;
+
+  Data_Get_Struct(vself, struct bstree_node, self);
+  data = (struct rb_bstree_node_data*)BSTREE_NODE_DATA(self);
+
+  rb_scan_args(argc, argv, "01", &value);
+  data->value = value;
+
+  return vself;
 }
 
@@ -295 +311 @@
 }
 
+static VALUE
+rb_bstree_node_rotate_left(VALUE vself)
+{
+  struct bstree_node* self;
+  struct bstree_node* res;
+  struct rb_bstree_node_data* res_data;
+
+  Data_Get_Struct(vself, struct bstree_node, self);
+  res = bstree_node_rotate_left(self);
+  if (0 != res) {
+    res_data = (struct rb_bstree_node_data*)BSTREE_NODE_DATA(res);
+    return res_data->vself;
+  }
+
+  return Qnil;
+}
+
+static VALUE
+rb_bstree_node_rotate_right(VALUE vself)
+{
+  struct bstree_node* self;
+  struct bstree_node* res;
+  struct rb_bstree_node_data* res_data;
+
+  Data_Get_Struct(vself, struct bstree_node, self);
+  res = bstree_node_rotate_right(self);
+  if (0 != res) {
+    res_data = (struct rb_bstree_node_data*)BSTREE_NODE_DATA(res);
+    return res_data->vself;
+  }
+
+  return Qnil;
+}
+
 void
 Init_bstree_test_module(void)
@@ -302 +352 @@
   cBSTreeNode = rb_define_class("BSTreeNode", rb_cData);
   rb_define_alloc_func(cBSTreeNode, rb_bstree_node_s_allocate);
+  rb_define_method(cBSTreeNode, "initialize", rb_bstree_node_initialize, -1);
   rb_define_method(cBSTreeNode, "inspect", rb_bstree_node_inspect, 0);
   rb_define_method(cBSTreeNode, "left", rb_bstree_node_left, 0);
@@ -320 +371 @@
   rb_define_method(cBSTreeNode, "lookup_upper_bound",
                    rb_bstree_node_lookup_upper_bound, 1);
-}
+
+  rb_define_method(cBSTreeNode, "rotate_left",
+                   rb_bstree_node_rotate_left, 0);
+  rb_define_method(cBSTreeNode, "rotate_right",
+                   rb_bstree_node_rotate_right, 0);
+}