First version of Cursor, Iterator and getSize()

7 files changed, 193 insertions, 16 deletions

diff --git a/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/VersionedMap.java b/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/VersionedMap.java
index 41fd55b7..d5c636d9 100644
--- a/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/VersionedMap.java
+++ b/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/VersionedMap.java
@@ -3,9 +3,10 @@ package org.eclipse.viatra.solver.data.map;
 import java.util.Iterator;
 import java.util.Map;
 
+import org.eclipse.viatra.solver.data.map.internal.MapCursor;
+import org.eclipse.viatra.solver.data.map.internal.MapEntryIterator;
 import org.eclipse.viatra.solver.data.map.internal.MutableNode;
 import org.eclipse.viatra.solver.data.map.internal.Node;
-import org.eclipse.viatra.solver.data.map.internal.NodeIterator;
 
 public class VersionedMap<KEY,VALUE> implements Versioned{
 
@@ -47,7 +48,7 @@ public class VersionedMap<KEY,VALUE> implements Versioned{
                 }
         }
         Iterator<Map.Entry<KEY,VALUE>> getIterator() {
-                return new NodeIterator<KEY, VALUE>(this.root);
+                return new MapEntryIterator<>(this.root);
         }
 
         @Override
diff --git a/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/ImmutableNode.java b/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/ImmutableNode.java
index e2bc06a9..908d335c 100644
--- a/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/ImmutableNode.java
+++ b/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/ImmutableNode.java
@@ -158,9 +158,15 @@ public class ImmutableNode<KEY, VALUE> extends Node<KEY, VALUE> {
         }
         
         
+        @SuppressWarnings("unchecked")
         @Override
         public int getSize() {
-                throw new UnsupportedOperationException();
+                int result = Integer.bitCount(this.dataMap);
+                for(int subnodeIndex = 0; subnodeIndex < Integer.bitCount(this.nodeMap); subnodeIndex++) {
+                        ImmutableNode<KEY,VALUE> subnode = (ImmutableNode<KEY, VALUE>) this.content[this.content.length-1-subnodeIndex];
+                        result += subnode.getSize();
+                }
+                return result;
         }
         
         @Override
@@ -173,6 +179,48 @@ public class ImmutableNode<KEY, VALUE> extends Node<KEY, VALUE> {
                 return this;
         }
         
+        @SuppressWarnings("unchecked")
+        @Override
+        boolean moveToNext(MapCursor<KEY, VALUE> cursor) {
+                // 1. try to move to data
+                int datas = Integer.bitCount(this.dataMap);
+                if(cursor.dataIndex != MapCursor.IndexFinish) {
+                        int newDataIndex = cursor.dataIndex + 1;
+                        if(newDataIndex < datas) {
+                                cursor.dataIndex = newDataIndex;
+                                cursor.key = (KEY) this.content[newDataIndex*2];
+                                cursor.value = (VALUE) this.content[newDataIndex*2+1];
+                                return true;
+                        } else {
+                                cursor.dataIndex = MapCursor.IndexFinish;
+                        }
+                }
+                
+                // 2. look inside the subnodes
+                int nodes = Integer.bitCount(this.nodeMap);
+                int newNodeIndex = cursor.nodeIndexStack.peek() + 1;
+                if(newNodeIndex < nodes) {
+                        // 2.1 found next subnode, move down to the subnode
+                        Node<KEY, VALUE> subnode = (Node<KEY, VALUE>) this.content[this.content.length-1-newNodeIndex];
+                        cursor.dataIndex = MapCursor.IndexStart;
+                        cursor.nodeStack.add(subnode);
+                        cursor.nodeIndexStack.add(newNodeIndex);
+                        return subnode.moveToNext(cursor);
+                } else {
+                        // 3. no subnode found, move up
+                        cursor.nodeStack.pop();
+                        cursor.nodeIndexStack.pop();
+                        if(!cursor.nodeStack.empty()) {
+                                Node<KEY, VALUE> supernode = cursor.nodeStack.peek();
+                                return supernode.moveToNext(cursor);
+                        } else {
+                                cursor.key = null;
+                                cursor.value = null;
+                                return false;
+                        }
+                }
+        }
+        
         @Override
         protected void prettyPrint(StringBuilder builder, int depth, int code) {
                 for(int i = 0; i<depth; i++) {
diff --git a/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/MapCursor.java b/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/MapCursor.java
new file mode 100644
index 00000000..4a4912d8
--- /dev/null
+++ b/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/MapCursor.java
@@ -0,0 +1,52 @@
+package org.eclipse.viatra.solver.data.map.internal;
+
+import java.util.Stack;
+
+public class MapCursor<KEY,VALUE> {
+        // Constants
+        static int IndexStart = -1;
+        static int IndexFinish = -2;
+        
+        // Tree stack
+        Stack<Node<KEY,VALUE>> nodeStack;
+        Stack<Integer> nodeIndexStack;
+        int dataIndex;
+        
+        // Values
+        KEY key;
+        VALUE value;
+        
+        public MapCursor(Node<KEY, VALUE> root) {
+                // Initializing tree stack
+                super();
+                this.nodeStack = new Stack<>();
+                this.nodeStack.add(root);
+                this.nodeIndexStack = new Stack<>();
+                this.nodeIndexStack.add(IndexStart);
+                this.dataIndex = IndexStart;
+                
+                // Initializing cache
+                this.key = null;
+                this.value = null;
+        }
+        
+        public KEY getKey() {
+                return key;
+        }
+        
+        public VALUE getValue() {
+                return value;
+        }
+        
+        public boolean isTerminated() {
+                return this.nodeStack.empty();
+        }
+        
+        public boolean move() {
+                if(this.isTerminated()) {
+                        return false;
+                } else {
+                        return true;
+                }
+        }
+}
diff --git a/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/MapEntryIterator.java b/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/MapEntryIterator.java
new file mode 100644
index 00000000..82983484
--- /dev/null
+++ b/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/MapEntryIterator.java
@@ -0,0 +1,40 @@
+package org.eclipse.viatra.solver.data.map.internal;
+
+import java.util.AbstractMap;
+import java.util.Iterator;
+import java.util.Map;
+import java.util.Map.Entry;
+import java.util.NoSuchElementException;
+
+/**
+ * Preorder iterator for map {@link #Node}s. 
+ * 
+ * @author Oszkar Semerath
+ *
+ * @param <KEY>
+ * @param <VALUE>
+ */
+public class MapEntryIterator<KEY,VALUE> extends MapCursor<KEY, VALUE> implements Iterator<Map.Entry<KEY,VALUE>>{
+
+        public MapEntryIterator(Node<KEY, VALUE> root) {
+                super(root);
+                // move to first
+                move();
+        }
+        
+        @Override
+        public boolean hasNext() {
+                return this.isTerminated();
+        }
+
+        @Override
+        public Entry<KEY, VALUE> next() {
+                if(!this.hasNext()) {
+                        Map.Entry<KEY, VALUE> result = new AbstractMap.SimpleEntry<KEY, VALUE>(this.key, this.value);
+                        this.move();
+                        return result;
+                } else {
+                        throw new NoSuchElementException();
+                }
+        }
+}
diff --git a/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/MutableNode.java b/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/MutableNode.java
index f6d0323e..9b30dbb7 100644
--- a/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/MutableNode.java
+++ b/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/MutableNode.java
@@ -203,6 +203,48 @@ public class MutableNode<KEY,VALUE> extends Node<KEY,VALUE> {
                 return new ImmutableNode<KEY,VALUE>(this);
         }
         
+        @SuppressWarnings("unchecked")
+        @Override
+        boolean moveToNext(MapCursor<KEY, VALUE> cursor) {
+                // 1. try to move to data
+                if(cursor.dataIndex != MapCursor.IndexFinish) {
+                        for(int index = cursor.dataIndex+1; index < factor; index++) {
+                                if(this.content[index*2]!=null) {
+                                        // 1.1 found next data
+                                        cursor.dataIndex = index;
+                                        cursor.key = (KEY) this.content[index*2];
+                                        cursor.value = (VALUE) this.content[index*2+1];
+                                        return true;
+                                }
+                        }
+                }
+                cursor.dataIndex = MapCursor.IndexFinish;
+                // 2. look inside the subnodes
+                for(int index = cursor.nodeIndexStack.peek()+1; index < factor; index++) {
+                        if(this.content[index*2]==null && this.content[index*2+1] !=null) {
+                                // 2.1 found next subnode, move down to the subnode
+                                Node<KEY, VALUE> subnode = (Node<KEY, VALUE>) this.content[index*2+1];
+                                
+                                cursor.dataIndex = MapCursor.IndexStart;
+                                cursor.nodeStack.add(subnode);
+                                cursor.nodeIndexStack.add(index);
+                                
+                                return subnode.moveToNext(cursor);
+                        }
+                }
+                // 3. no subnode found, move up
+                cursor.nodeStack.pop();
+                cursor.nodeIndexStack.pop();
+                if(!cursor.nodeStack.empty()) {
+                        Node<KEY, VALUE> supernode = cursor.nodeStack.peek();
+                        return supernode.moveToNext(cursor);
+                } else {
+                        cursor.key = null;
+                        cursor.value = null;
+                        return false;
+                }
+        }
+        
         @Override
         protected void prettyPrint(StringBuilder builder, int depth, int code) {
                 for(int i = 0; i<depth; i++) {
diff --git a/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/Node.java b/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/Node.java
index 89c52f7f..7a6599a2 100644
--- a/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/Node.java
+++ b/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/Node.java
@@ -55,6 +55,13 @@ public abstract class Node<KEY,VALUE>{
         abstract protected MutableNode<KEY, VALUE> toMutable();
         abstract protected ImmutableNode<KEY, VALUE> toImmutable();
         
+        /**
+         * Moves a {@link MapCursor} to its next position.
+         * @param cursor the cursor
+         * @return Whether there was a next value to move on.
+         */
+        abstract boolean moveToNext(MapCursor<KEY,VALUE> cursor);
+        
         ///////// For iterators
         //abstract boolean moveIteratorToNextData(NodeIterator<KEY,VALUE> iterator, int currentIndex);
         //abstract boolean moveIteratorToNextNode(NodeIterator<KEY,VALUE> iterator, int currentIndex);
diff --git a/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/NodeIterator.java b/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/NodeIterator.java
deleted file mode 100644
index 4c426b1e..00000000
--- a/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/NodeIterator.java
+++ /dev/null
@@ -1,13 +0,0 @@
-package org.eclipse.viatra.solver.data.map.internal;
-
-import java.util.Iterator;
-import java.util.Map;
-
-public abstract class NodeIterator<NODETYPE extends Node<KEY,VALUE>,KEY,VALUE>
-        implements Iterator<Map.Entry<KEY,VALUE>>
-{
-        protected NODETYPE node;
-        public NodeIterator(NODETYPE node) {
-                this.node = node;
-        }
-}