# HG changeset patch
# User Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
# Date 1458465838 -32400
# Node ID f0a1f02e8493e12a1444ecc750999afbff174cc0
# Parent  78dce131e9d64d480871952dc216c90835d1dfeb
Enumerate single path using iterator

diff -r 78dce131e9d6 -r f0a1f02e8493 src/insert_verification/akashaLLRBContext.c
--- a/src/insert_verification/akashaLLRBContext.c	Fri Mar 18 10:57:40 2016 +0900
+++ b/src/insert_verification/akashaLLRBContext.c	Sun Mar 20 18:23:58 2016 +0900
@@ -2,9 +2,10 @@
 
 #include "akashaLLRBContext.h"
 
-extern __code insertOnce_stub(struct Context*);
 extern __code showTree_stub(struct Context*);
 extern __code iterateInsertion_stub(struct Context*);
+extern __code putAndGoToNextDepth_stub (struct Context*);
+extern __code duplicateIterator_stub(struct Context*);
 
 /* definitions from llrb */
 extern __code meta(struct Context*, enum Code next);
@@ -58,9 +59,10 @@
 
     context->codeNum = Exit;
 
-    context->code[InsertOnce]       = insertOnce_stub;
-    context->code[ShowTree]         = showTree_stub;
-    context->code[IterateInsertion] = iterateInsertion_stub;
+    context->code[ShowTree]            = showTree_stub;
+    context->code[IterateInsertion]    = iterateInsertion_stub;
+    context->code[PutAndGoToNextDepth] = putAndGoToNextDepth_stub;
+    context->code[DuplicateIterator]   = duplicateIterator_stub;
 
     /* definitions from llrb */
     context->code[Put]           = put_stub;
@@ -127,7 +129,7 @@
 }
 
 __code initIteratorElem(struct Context* context, struct Allocate* allocate, struct IterElem* prev) {
-    if (prev->val >= LIMIT_OF_VERIFICATION_SIZE) { goto initFinishIterator(context, prev); }
+    if (prev->val+1 == LIMIT_OF_VERIFICATION_SIZE) { goto initFinishIterator(context, prev); }
 
     struct IterElem* ie = context->heap;
     allocate->size = sizeof(struct IterElem);
diff -r 78dce131e9d6 -r f0a1f02e8493 src/insert_verification/include/akashaLLRBContext.h
--- a/src/insert_verification/include/akashaLLRBContext.h	Fri Mar 18 10:57:40 2016 +0900
+++ b/src/insert_verification/include/akashaLLRBContext.h	Sun Mar 20 18:23:58 2016 +0900
@@ -2,12 +2,13 @@
 #include "stack.h"
 
 #define ALLOCATE_SIZE 1000
-#define LIMIT_OF_VERIFICATION_SIZE 16
+#define LIMIT_OF_VERIFICATION_SIZE 2
 
 enum Code {
-    InsertOnce,
     ShowTree,
     IterateInsertion,
+    PutAndGoToNextDepth,
+    DuplicateIterator,
 
     /* definitions from llrb */
     Allocator,
diff -r 78dce131e9d6 -r f0a1f02e8493 src/insert_verification/main.c
--- a/src/insert_verification/main.c	Fri Mar 18 10:57:40 2016 +0900
+++ b/src/insert_verification/main.c	Sun Mar 20 18:23:58 2016 +0900
@@ -3,6 +3,8 @@
 #include "akashaLLRBContext.h"
 #include "akashaCS.h"
 
+extern void allocator(struct Context* context);
+
 void printTree(struct Node* node, int n) {
     if (node != 0) {
         printTree(node->left, n+1);
@@ -13,18 +15,6 @@
     }
 }
 
-__code insertOnce_stub(struct Context* context) {
-    goto insertOnce(context, &context->data[Node]->node);
-}
-
-__code insertOnce(struct Context* context, struct Node* node) {
-    node->key   = rand()%100+1;
-    node->value = 100;
-
-    context->next = ShowTree;
-    goto meta(context, Put);
-}
-
 __code showTree_stub(struct Context* context) {
     goto showTree(context, &context->data[Tree]->tree);
 }
@@ -44,17 +34,107 @@
 }
 
 __code iterateInsertion(struct Context* context, struct Iterator* iter, struct Node* node) {
+    // puts all elements in iterator into tree.
+    node->key   = iter->head->val;
+    node->value = iter->head->val;
+    iter->head  = iter->head->next;
+
+    if (iter->head == iter->last) {
+        context->next = ShowTree;
+    } else {
+        context->next = IterateInsertion;
+    }
+    goto meta(context, Put);
+}
+
+__code putAndGoToNextDepth_stub(struct Context* context) {
+    goto putAndGoToNextDepth(context, &context->data[Iter]->iterator, &context->data[Tree]->tree, &context->data[Node]->node);
+}
+
+__code putAndGoToNextDepth(struct Context* context, struct Iterator* iter, struct Tree* tree, struct Node* node) {
     node->key   = iter->head->val;
     node->value = iter->head->val;
     iter->head  = iter->head->next;
-    if (iter->head == iter->last) { goto meta(context, ShowTree); }
 
-    //printf("Trying insertion %d", node->key);
-
-    context->next = IterateInsertion;
+    if (iter->head == iter->last) {
+        context->next = ShowTree; // TODO: add restore and  back trace
+    } else {
+        context->next = DuplicateIterator;
+    }
     goto meta(context, Put);
 }
 
+__code duplicateIterator_stub(struct Context* context) {
+    goto duplicateIterator(context, &context->data[Allocate]->allocate, &context->data[Iter]->iterator);
+}
+
+__code duplicateIterator(struct Context* context, struct Allocate* allocate, struct Iterator* iter) {
+    struct Iterator* newIter = context->heap;
+    allocate->size = sizeof(struct Iterator);
+    allocator(context);
+
+    struct IterElem* dup = context->heap;
+    allocate->size = sizeof(struct IterElem);
+    allocator(context);
+
+    dup->val  = iter->head->val;
+    dup->next = NULL;
+
+    newIter->previousDepth = iter;
+    newIter->head          = dup;
+    newIter->last          = NULL;
+    context->data[Iter]    = (union Data*) newIter;
+
+    goto duplicateIteratorElem_stub(context);
+}
+
+__code duplicateIteratorElem_stub(struct Context* context) {
+    goto duplicateIteratorElem(context, &context->data[Allocate]->allocate, &context->data[Iter]->iterator);
+}
+
+__code duplicateIteratorElem(struct Context* context, struct Allocate* allocate, struct Iterator* iter) {
+    // All elements in iterator must be unique.
+
+    if ((iter->last != NULL) && (iter->last == iter->previousDepth->last)) {
+        goto meta(context, ShowTree); /* copy tree */
+    }
+    struct IterElem* dup = context->heap;
+    allocate->size = sizeof(struct IterElem);
+    allocator(context);
+
+    struct IterElem *oldElem = iter->previousDepth->head;
+    struct IterElem *newElem = iter->head;
+
+
+    while ((newElem->next != NULL) && (oldElem->val == newElem->val)) {
+        // FIXME: simple implementation O(n^2)
+        oldElem = oldElem->next;
+        newElem = newElem->next;
+    }
+
+    dup->val         = oldElem->next->val;
+    newElem->next    = dup;
+
+    if (oldElem->next == iter->previousDepth->last) {
+        dup->next  = iter->head;
+        iter->last = dup;
+        goto duplicateTree_stub(context); // meta
+    }
+
+    goto duplicateIteratorElem_stub(context); // meta
+}
+
+__code duplicateTree_stub(struct Context* context) {
+    goto duplicateTree(context, &context->data[Tree]->tree, &context->data[Iter]->iterator);
+}
+
+__code duplicateTree(struct Context* context, struct Tree* tree, struct Iterator* iter) {
+    // Tree must be non destructive.
+    // If you use destructive tree, you must copy tree.
+    iter->tree = tree;
+    goto meta(context, PutAndGoToNextDepth);
+}
+
 int main(int argc, char const* argv[]) {
-    goto startCode(IterateInsertion);
+    goto startCode(PutAndGoToNextDepth);
 }