From 7f6a2528bf83f93e3d35eff228f7180e0181f4eb Mon Sep 17 00:00:00 2001
From: Kristóf Marussy <marussy@mit.bme.hu>
Date: Thu, 29 Jul 2021 19:01:25 +0200
Subject: Add new data structure for backend
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

Co-authored-by: Oszkár Semeráth <semerath@mit.bme.hu>
---
 .../viatra/solver/data/map/internal/MapCursor.java | 131 +++++++++++++++++++++
 1 file changed, 131 insertions(+)
 create mode 100644 model-data/src/main/java/org/eclipse/viatra/solver/data/map/internal/MapCursor.java

(limited to 'model-data/src/main/java/org/eclipse/viatra/solver/data/map/internal/MapCursor.java')

diff --git a/model-data/src/main/java/org/eclipse/viatra/solver/data/map/internal/MapCursor.java b/model-data/src/main/java/org/eclipse/viatra/solver/data/map/internal/MapCursor.java
new file mode 100644
index 00000000..6c177611
--- /dev/null
+++ b/model-data/src/main/java/org/eclipse/viatra/solver/data/map/internal/MapCursor.java
@@ -0,0 +1,131 @@
+package org.eclipse.viatra.solver.data.map.internal;
+
+import java.util.ArrayDeque;
+import java.util.ConcurrentModificationException;
+import java.util.Iterator;
+import java.util.List;
+
+import org.eclipse.viatra.solver.data.map.Cursor;
+import org.eclipse.viatra.solver.data.map.VersionedMap;
+
+public class MapCursor<KEY,VALUE> implements Cursor<KEY,VALUE> {
+	// Constants
+	static int IndexStart = -1;
+	static int IndexFinish = -2;
+	
+	// Tree stack
+	ArrayDeque<Node<KEY,VALUE>> nodeStack;
+	ArrayDeque<Integer> nodeIndexStack;
+	int dataIndex;
+	
+	// Values
+	KEY key;
+	VALUE value;
+	
+	// Hash code for checking concurrent modifications
+	final VersionedMap<KEY,VALUE> map;
+	final int creationHash; 
+	
+	public MapCursor(Node<KEY, VALUE> root, VersionedMap<KEY,VALUE> map) {
+		// Initializing tree stack
+		super();
+		this.nodeStack = new ArrayDeque<>();
+		this.nodeIndexStack = new ArrayDeque<>();
+		if(root != null) {
+			this.nodeStack.add(root);
+			this.nodeIndexStack.push(IndexStart);
+		}
+		
+		this.dataIndex = IndexStart;
+		
+		// Initializing cache
+		this.key = null;
+		this.value = null;
+		
+		// Initializing state
+		this.map=map;
+		this.creationHash = map.hashCode();
+	}
+	
+	public KEY getKey() {
+		return key;
+	}
+	
+	public VALUE getValue() {
+		return value;
+	}
+	
+	public boolean isTerminated() {
+		return this.nodeStack.isEmpty();
+	}
+	
+	public boolean move() {
+		if(isDirty()) {
+			throw new ConcurrentModificationException();
+		}
+		if(!isTerminated()) {
+			boolean result = this.nodeStack.peek().moveToNext(this);
+			if(this.nodeIndexStack.size() != this.nodeStack.size()) {
+				throw new IllegalArgumentException("Node stack is corrupted by illegal moves!");
+			}
+			return result;
+		}
+		return false;
+	}
+	public boolean skipCurrentNode() {
+		nodeStack.pop();
+		nodeIndexStack.pop();
+		dataIndex = IndexFinish;
+		return move();
+	}
+	@Override
+	public boolean isDirty() {
+		return this.map.hashCode() != this.creationHash;
+	}
+	@Override
+	public List<VersionedMap<KEY, VALUE>> getDependingMaps() {
+		return List.of(this.map);
+	}
+	
+	public static <KEY,VALUE> boolean sameSubnode(MapCursor<KEY,VALUE> cursor1, MapCursor<KEY,VALUE> cursor2) {
+		Node<KEY, VALUE> nodeOfCursor1 = cursor1.nodeStack.peek();
+		Node<KEY, VALUE> nodeOfCursor2 = cursor2.nodeStack.peek();
+		if(nodeOfCursor1 != null && nodeOfCursor2 != null) {
+			return nodeOfCursor1.equals(nodeOfCursor2);
+		} else {
+			return false;
+		}
+	}
+	
+	/**
+	 * 
+	 * @param <KEY>
+	 * @param <VALUE>
+	 * @param cursor1
+	 * @param cursor2
+	 * @returnv Positive number if cursor 1 is behind, negative number if cursor 2 is behind, and 0 if they are at the same position.
+	 */
+	public static <KEY,VALUE> int compare(MapCursor<KEY,VALUE> cursor1, MapCursor<KEY,VALUE> cursor2) {
+		// two cursors are equally deep
+		Iterator<Integer> stack1 = cursor1.nodeIndexStack.descendingIterator();
+		Iterator<Integer> stack2 = cursor2.nodeIndexStack.descendingIterator();
+		if(stack1.hasNext()) {
+			if(!stack2.hasNext()) {
+				// stack 2 has no more element, thus stack 1 is deeper
+				return 1;
+			}
+			int val1 = stack1.next();
+			int val2 = stack2.next();
+			if(val1 < val2) {
+				return -1;
+			} else if(val2 < val1) {
+				return 1;
+			}
+		}
+		if(stack2.hasNext()) {
+			// stack 2 has more element, thus stack 2 is deeper
+			return 1;
+		}
+		return Integer.compare(cursor1.dataIndex, cursor2.dataIndex);
+	}
+}
-- 
cgit v1.2.3-54-g00ecf