Mercurial > hg > GearsTemplate

changeset 446:41a6f8482374

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
fix RedBlackTree.cbc Insert, printTree. but occur error
author ryokka
date Wed, 29 Nov 2017 22:13:05 +0900
parents f02bd096af64
children bb29a1fe43ee
files src/parallel_execution/RedBlackTree.cbc
diffstat 1 files changed, 178 insertions(+), 157 deletions(-) [+]
line wrap: on
line diff
--- a/src/parallel_execution/RedBlackTree.cbc	Tue Nov 28 22:15:23 2017 +0900
+++ b/src/parallel_execution/RedBlackTree.cbc	Wed Nov 29 22:13:05 2017 +0900
@@ -4,6 +4,8 @@
 
 // extern enum Relational compare(struct Node* node1, struct Node* node2);
 
+extern enum Relational compare(struct Node* node1, struct Node* node2);
+
 
 Tree* createRedBlackTree(struct Context* context) {
     struct Tree* tree = new Tree();
@@ -12,53 +14,54 @@
     redBlackTree->root = NULL;
     redBlackTree->nodeStack = (union Data*)createSingleLinkedStack(context);
 
-    // tree->put = C_putRedBlackTree;
+     tree->put = C_putRedBlackTree;
     // tree->get = C_getRedBlackTree;
     // tree->remove = C_removeRedBlackTree;
     // tree->clear = C_clearRedBlackTree;
     return tree;
 }
 
-// void printTree(union Data* data) {
-//     printTree1(data);
-//     printf("\n");
-// }
-//
-// void printTree1(union Data* data) {
-//   struct Node* node = &data->Node;
-//   if (node == NULL) {
-//     printf("NULL");
-//   } else {
-//     printf("key = %d (", node->key);
-//     printTree1((union Data*)(node->right));
-//     printf("), (");
-//     printTree1((union Data*)(node->left));
-//     printf(")");
-//   }
-// }
-//
-// __code putRedBlackTree(struct RedBlackTree* tree, struct Node* node) {
-//     struct Node* newNode = &ALLOCATE(context, Node)->Node;
-//     struct Node* root = tree->root;
-//     printTree(tree->root);
-//     tree->newNode = newNode;
-//     tree->root = newNode; // this should done at stackClear
-//     tree->parent = NULL;
-//     if (root) {
-//         tree->current = root;
-//         tree->result = compare(tree->current, node);
-//         goto insertRBTree(tree);
-//     }
-//     goto insertRBTree(tree, node);
-// }
+__code printTree(struct RedBlackTree* tree) {
+    printTree1(tree);
+    printf("\n");
+}
+
+__code printTree1(struct RedBlackTree* tree) {
+  struct Node* node = tree->current;
+  if (node == NULL) {
+    printf("Leaf");
+  } else {
+    printf("key = %d (", node->key);
+    printTree1(node->right);
+    printf("), (");
+    printTree1(node->left);
+    printf(")");
+  }
+}
 
-__code stackClear(struct RedBlackTree* tree, struct Stack* nodeStack, __code next(...)) {
-  tree->current = 0;
-  nodeStack->stack = (union Data*)tree->nodeStack;
-  nodeStack->next = next;
-  goto meta(context, tree->nodeStack->clear);
+__code putRedBlackTree(struct Node* node, struct RedBlackTree* tree) {
+    struct Node* newNode = &ALLOCATE(context, Node)->Node;
+    struct Node* root = tree->root;
+    printTree((tree->root));
+    tree->newNode = newNode;
+    // tree->root = newNode; // this should done at stackClear
+    tree->parent = NULL;
+    if (root) {
+        tree->current = root;
+        // tree->result = compare(tree->current, node);
+        goto insertRBTree(newNode, tree);
+    }
+    print("error : __code putRedBlackTree");
+    goto next(...);
 }
 
+//__code stackClear(struct RedBlackTree* tree, struct Stack* nodeStack, __code next(...)) {
+  //  tree->current = 0;
+  //  nodeStack->stack = tree->nodeStack;
+  //  nodeStack->next = next;
+  //  goto meta(context, tree->nodeStack->clear);
+  //}
+
 // __code getRedBlackTree(struct RedBlackTree* tree, __code next(...)) {
   //   if (tree->root) {
     //     tree->current = tree->root;
@@ -69,114 +72,132 @@
   //   goto next(...);
   // }
 
-__code insertRBTree(struct Node* newNode,struct Stack* nodeStack, struct RedBlackTree* rbtree) {
-  rbtree->current = rbtree->root;
-  goto insertLocate(newNode, nodeStack, rbtree);
+__code insertRBTree(struct Node* node, struct RedBlackTree* tree) {
+  tree->current = node;
+  struct Stack* nodeStack = tree->nodeStack;
+
+  if (tree->root == null){
+    tree->root = tree->current;
+    tree->root->color = Black;
+    goto next(...);
+  }else{
+    goto searchInsertLocatetion(newNode, nodeStack, tree);
+  }
+
 }
 
-__code insertLocate(struct Node* node, struct Stack* nodeStack, struct RedBlackTree* rbtree) {
 
+__code searchInsertLocation(struct Node* node, struct Stack* nodeStack, struct RedBlackTree* tree) {
   struct Stack* nodeStack = tree->nodeStack;
-  struct Node* trace = rbtree->current;
+  struct Node* trace = tree->current;
+
+
 
-  // i think faster  "compare rbtree->current, node" than  "switch case EQ, LT, RT"
-  if (rbtree->current > node) {
-    goto nodestack->push(nodeStack,trace,insertLocate);
-  } else if (rbtree->current < node) {
-    goto nodestack->push(nodeStack, trace, insertLocate);
-  } else if (rbtree->current == node) {
-    printf("alady member this node(insertLocate)");
+  // i think faster  "compare tree->current, node" than  "switch case EQ, LT, RT"
+  if (tree->current > node || tree->current < node) {
+    goto nodestack->push(nodeStack,trace, searchInsertLocation);
+  } else if (tree->current == node) {
+    printf("alady member this node : __code searchInsertLocation()");
     goto next(...);
-  } else if (rbtree->current == null){
-    rbtree->current = node;
+  } else if (tree->current == null){
+    tree->current = node;
     goto nodeStack->pop(nodeStack,insertBalance);
   }else{
-    rbtree->root = node;
+    printf("$insert value tree : __code searchInsertLocation()");
     goto next(...);
   }
 }
 
-__code insertBalance(struct RedBlackTree* rbtree, struct Node* nodeStack, struct Node* node){
-  rbtree->current = nodeStack->data;
-    // insert case
+__code insertBalance(struct RedBlackTree* tree, struct Node* nodeStack, struct Node* node){
+  tree->current = nodeStack->data;
+
+  // exit insertion code
+  if (tree->current == tree->root) {
+    tree->current->color = Black;
+    printTree(((union Data* ) (tree->root)));
+    //printTree
+    goto next(...);
+  }
+
+  //current color eq Red
+  if (current->color == Red)
+    goto nodeStack->pop(nodeStack, trace, insertBalance);
+
+  // current color eq Black
   if (current->left->left || current->left->right){
-    goto insertBalanceLeft(rbtree,nodeStack);
+    goto insertBalanceLeft(tree,nodeStack);
   }else if (current->right->left || current->right->right){
-    goto insertBalanceRight(rbtree,nodeStack);
+    goto insertBalanceRight(tree,nodeStack);
   }else{
     goto nodeStack->pop(nodeStack,insertBalance);
   }
 }
 
-__code insesrtBalanceLeft(struct RedBlackTree* rbtree, struct Node* nodeStack, struct Node* node){
+__code insertBalanceLeft(struct RedBlackTree* tree, struct Node* nodeStack, struct Node* node){
 
   if (current->color == Black && current->left->color == Red && current->left->left->color == Red){
-    struct Node* tmp0 = rbtree->current;
-    struct Node* tmp1 = rbtree->current->left;
-    struct Node* tmp2 = rbtree->current->left->left;
+    struct Node* tmpCurrent  = tree->current;
+    struct Node* tmpLeft     = tree->current->left;
+    struct Node* tmpLeftLeft = tree->current->left->left;
 
-    rbtree->current = tmp1;
-    rbtree->current->right = tmp0;
-    rbtree->current->left = tmp2;
-    rbtree->current->right->right = tmp0->right;
-    rbtree->current->right->left = tmp1->right;
-    rbtree->current->color = Black;
-    rbtree->current->left->color = Red;
-    rbtree->current->right->color = Red;
+    tree->current = tmpLeft;
+    tree->current->right = tmpCurrent;
+    tree->current->left = tmpLeftLeft;
+    tree->current->right->left = tmpLeft->right;
+    tree->current->color = Red;
+    tree->current->left->color = Black;
+    tree->current->right->color = Black;
     goto nodeStack->pop(nodeStack,insertBalance);
 
   } else if(current->color == Black && current->left->color == Red && current->left->right->color == Red){
-    struct Node* tmp0 = rbtree->current;
-    struct Node* tmp1 = rbtree->current->left;
-    struct Node* tmp2 = rbtree->current->left->right;
+    struct Node* tmpCurrent   = tree->current;
+    struct Node* tmpLeft      = tree->current->left;
+    struct Node* tmpLeftRight = tree->current->left->right;
 
-    rbtree->current = tmp1;
-    rbtree->current->right = tmp0;
-    rbtree->current->left = tmp2;
-    rbtree->current->right->right = tmp0->right;
-    rbtree->current->right->left = tmp1->right;
-    rbtree->current->color = Black;
-    rbtree->current->left->color = Red;
-    rbtree->current->right->color = Red;
+    tree->current = tmpLeft;
+    tree->current->right = tmpCurrent;
+    tree->current->left = tmpLeftRight;
+    tree->current->right->left = tmpLeft->left;
+    tree->current->color = Red;
+    tree->current->left->color = Black;
+    tree->current->right->color = Black;
     goto nodeStack->pop(nodeStack,insertBalance);
 
   }
 }
 
-__code insertBalanceRight(struct RedBlackTree* rbtree, struct Node* nodeStack, struct Node* node){
+__code insertBalanceRight(struct RedBlackTree* tree, struct Node* nodeStack, struct Node* node){
   if (current->color == Black && current->right->color == Red && current->right->right->color == Red){
-    struct Node* tmp0 = rbtree->current;
-    struct Node* tmp1 = rbtree->current->left;
-    struct Node* tmp2 = rbtree->current->left->right;
+    struct Node* tmpCurrent    = tree->current;
+    struct Node* tmpRight      = tree->current->right;
+    struct Node* tmpRightRight = tree->current->right->right;
 
-    rbtree->current = tmp1;
-    rbtree->current->right = tmp0;
-    rbtree->current->left = tmp2;
-    rbtree->current->right->right = tmp0->right;
-    rbtree->current->right->left = tmp1->right;
-    rbtree->current->color = Black;
-    rbtree->current->left->color = Red;
-    rbtree->current->right->color = Red;
+    tree->current = tmpRight;
+    tree->current->left = tmpCurrent;
+    tree->current->Right = tmpRightRight;
+    tree->current->left->right = tmpRight->left;
+    tree->current->color = Red;
+    tree->current->left->color = Black;
+    tree->current->right->color = Black;
     goto nodeStack->pop(nodeStack,insertBalance);
 
   } else if (current->color == Black && current->right->color == Red && current->right->left->color == Red){
 
-    struct Node* tmp0 = rbtree->current;
-    struct Node* tmp1 = rbtree->current->right;
-    struct Node* tmp2 = rbtree->current->right->left;
+    struct Node* tmpCurrent = tree->current;
+    struct Node* tmpRight = tree->current->right;
+    struct Node* tmpRightLeft = tree->current->right->left;
 
-    rbtree->current = tmp1;
-    rbtree->current->right = tmp0;
-    rbtree->current->left = tmp2;
-    rbtree->current->right->right = tmp0->right;
-    rbtree->current->right->left = tmp1->right;
-    rbtree->current->color = Black;
-    rbtree->current->left->color = Red;
-    rbtree->current->right->color = Red;
+    tree->current = tmpRight;
+    tree->current->right = tmpCurrent;
+    tree->current->left = tmpRightLeft;
+    tree->current->left->right = tmpRight->right;
+    tree->current->color = Red;
+    tree->current->left->color = Black;
+    tree->current->right->color = Black;
     goto nodeStack->pop(nodeStack,insertBalance);
 
   } else {
-    printf("error insertBalanceRight");
+    printf("unkwon error : __code insertBalanceRight()");
     goto next(...);
   }
 }
@@ -186,68 +207,68 @@
 
 
 
-// __code deleteRBTree(struct RedBlackTree newNode, struct RedBlackTree* rbtree) {
-//   rbtree->current = rbtree->root;
-//   goto deleteLocate;
-// }
+/* __code deleteRBTree(struct RedBlackTree newNode, struct RedBlackTree* tree) { */
+/*   tree->current = tree->root; */
+/*   goto deleteLocate; */
+/* } */
 
-// __code deleteLocate(struct Node* node, struct Stack* nodeStack, struct RedBlackTree* rbtree) {
-//   /\* check delete node locate and push route node *\/
-//   struct Stack* nodeStack = tree->nodeStack;
-//   struct Node* trace = rbtree->current;
+/* __code deleteLocate(struct Node* node, struct Stack* nodeStack, struct RedBlackTree* tree) { */
+/*   /\* check delete node locate and push route node *\/ */
+/*   struct Stack* nodeStack = tree->nodeStack; */
+/*   struct Node* trace = tree->current; */
 
-//   if (rbtree->current > node) {
-//     goto nodeStack->push(nodeStack,trace,deleteLocate);
-//   } else if (rbtree->current < node) {
-//     goto nodeStack->push(trace,deleteLocate);
-//   } else if (rbtree->current == node) {
-//     // trace = rbtree->current;
-//     goto deleteNode(struct Stack* nodeStack, struct RedBlackTree* rbtree,struct Node* trace);
-//     // goto nodeStack->push(trace,deleteNode);
-//   } else if (rbtree->current == null){
-//     printf("No member Delete node (__code deleteLocate)");
-//     goto next(...);
-//   } else {
-//     printf("Error,__code deleteLocate");
-//     goto next(...);
-//   }
-// }
+/*   if (tree->current > node) { */
+/*     goto nodeStack->push(nodeStack,trace,deleteLocate); */
+/*   } else if (tree->current < node) { */
+/*     goto nodeStack->push(trace,deleteLocate); */
+/*   } else if (tree->current == node) { */
+/*     // trace = tree->current; */
+/*     goto deleteNode(struct Stack* nodeStack, struct RedBlackTree* tree,struct Node* trace); */
+/*     // goto nodeStack->push(trace,deleteNode); */
+/*   } else if (tree->current == null){ */
+/*     printf("No member Delete node (__code deleteLocate)"); */
+/*     goto next(...); */
+/*   } else { */
+/*     printf("Error,__code deleteLocate"); */
+/*     goto next(...); */
+/*   } */
+/* } */
 
-// __code deleteNode(struct Node* node, struct Stack* nodeStack, struct RedBlackTree* rbtree) {
-//   struct Stack* nodeStack = tree->nodeStack;
-//   struct Node* replaceNode = nodeStack->data;
+/* __code deleteNode(struct Node* node, struct Stack* nodeStack, struct RedBlackTree* tree) { */
+/*   struct Stack* nodeStack = tree->nodeStack; */
+/*   struct Node* replaceNode = nodeStack->data; */
 
-//   if(replaceNode->right == null){
-//     rbtree->current = replaceNode;
-//     rbtree->current = rbtree->current->left;
-//     goto deleteUnbalance(nodeStack,replaceNode);
-//   }else if(replaceNode->left == null){
-//     rbtree->current = replaceNode;
-//     rbtree->current = rbtree->current->right;
-//     goto deleteUnbalance(nodeStack,replaceNode);
-//     //goto deleteNodeReplaceNull();
-//   }else{
-//     // goto nodeStack->push(nodeStack,replaceNode,deleteNodeReplace);
-//     goto deleteNodeReplace(nodeStack,replaceNode);
-//   }
-// }
+/*   if(replaceNode->right == null){ */
+/*     tree->current = replaceNode; */
+/*     tree->current = tree->current->left; */
+/*     goto deleteUnbalance(nodeStack,replaceNode); */
+/*   }else if(replaceNode->left == null){ */
+/*     tree->current = replaceNode; */
+/*     tree->current = tree->current->right; */
+/*     goto deleteUnbalance(nodeStack,replaceNode); */
+/*     //goto deleteNodeReplaceNull(); */
+/*   }else{ */
+/*     // goto nodeStack->push(nodeStack,replaceNode,deleteNodeReplace); */
+/*     goto deleteNodeReplace(nodeStack,replaceNode); */
+/*   } */
+/* } */
 
 
-// __code deleteNodeReplace(){
+/* __code deleteNodeReplace(){ */
 
-//   if (replaceNode->left != null){
-//     replaceNode = replaceNode->left;
-//     goto deleteNodeReplace();
-//   }else if(){
+/*   if (replaceNode->left != null){ */
+/*     replaceNode = replaceNode->left; */
+/*     goto deleteNodeReplace(); */
+/*   }else if(){ */
 
 
-//   }
+/*   } */
 
-// }
+/* } */
 
 
-// __code deleteUnbalance() {
-//   if () {
-//   }
+/* __code deleteUnbalance() { */
+/*   if () { */
+/*   } */
+/* } */
 
-// }