# HG changeset patch
# User Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
# Date 1453194315 -32400
# Node ID 00d4c6fa49696cf21c1de6050af01918369f8b21
# Parent  ac04428e673974a7fc1639c8f13598d2ce392d99# Parent  547c23f3a898f5cc4847ba34e09078d6184a6060
merge

diff -r ac04428e6739 -r 00d4c6fa4969 .hgignore
--- a/.hgignore	Tue Jan 19 16:21:03 2016 +0900
+++ b/.hgignore	Tue Jan 19 18:05:15 2016 +0900
@@ -13,4 +13,5 @@
 
 # binary
 src/llrb/llrb
+src/llrb/llrb_with_put_verify
 
diff -r ac04428e6739 -r 00d4c6fa4969 src/llrb/CMakeLists.txt
--- a/src/llrb/CMakeLists.txt	Tue Jan 19 16:21:03 2016 +0900
+++ b/src/llrb/CMakeLists.txt	Tue Jan 19 18:05:15 2016 +0900
@@ -14,3 +14,13 @@
                origin_cs.c
 )
 
+
+add_executable(llrb_with_put_verify
+               main.c
+               llrb.c
+               llrbContext.c
+               allocate.c
+               compare.c
+               stack.c
+               verify_put_cs.c
+)
diff -r ac04428e6739 -r 00d4c6fa4969 src/llrb/verify_put_cs.c
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/llrb/verify_put_cs.c	Tue Jan 19 18:05:15 2016 +0900
@@ -0,0 +1,75 @@
+/* Verification of LLRB-Tree height in put operations.
+ * LLRB-Tree allows (max-height) <= 2*(min-height).
+ */
+
+#include <stdlib.h>
+#include <stdio.h>
+#include <time.h>
+#include "llrbContext.h"
+
+void verify_tree_height(struct Node*);
+
+__code meta(struct Context* context, enum Code next) {
+    if (next == Put) {
+        verify_tree_height(context->data[Tree]->tree.root);
+    }
+    goto (context->code[next])(context);
+}
+
+__code start_code(struct Context* context, enum Code next) {
+    unsigned int seed = (unsigned int)time(NULL);
+
+    printf("--- srand(%u)\n", seed);
+    goto meta(context, next);
+}
+
+__code exit_code(struct Context* context) {
+    free(context->code);
+    free(context->data);
+    free(context->heapStart);
+    goto exit(0);
+}
+
+unsigned int min_height(struct Node* node, unsigned int height) {
+    if ((node->left == NULL) && (node->right == NULL)) return height;
+    if (node->left  == NULL) return min_height(node->right, height+1);
+    if (node->right == NULL) return min_height(node->left, height+1);
+
+    unsigned int left_min  = min_height(node->left, height+1);
+    unsigned int right_min = min_height(node->right, height+1);
+
+    if (left_min < right_min) {
+        return left_min;
+    } else {
+        return right_min;
+    }
+}
+
+unsigned int max_height(struct Node* node, unsigned int height) {
+    if ((node->left == NULL) && (node->right == NULL)) return height;
+    if (node->left  == NULL) return max_height(node->right, height+1);
+    if (node->right == NULL) return max_height(node->left, height+1);
+
+    unsigned int left_max  = max_height(node->left, height+1);
+    unsigned int right_max = max_height(node->right, height+1);
+
+    if (left_max > right_max) {
+        return left_max;
+    } else {
+        return right_max;
+    }
+}
+
+void verify_tree_height(struct Node* root) {
+    if (root == NULL) return;
+
+    unsigned int min_h = min_height(root, 1);
+    unsigned int max_h = max_height(root, 1);
+
+    if (max_h >= 2*min_h) {
+        printf("llrb-condition violated.\n");
+        printf("\tmin-height %u", min_h);
+        printf("\tmax-height %u", max_h);
+        exit(EXIT_FAILURE);
+    }
+}