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>
---
 .../solver/data/map/internal/MutableNode.java      | 411 +++++++++++++++++++++
 1 file changed, 411 insertions(+)
 create mode 100644 model-data/src/main/java/org/eclipse/viatra/solver/data/map/internal/MutableNode.java

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

diff --git a/model-data/src/main/java/org/eclipse/viatra/solver/data/map/internal/MutableNode.java b/model-data/src/main/java/org/eclipse/viatra/solver/data/map/internal/MutableNode.java
new file mode 100644
index 00000000..963ce111
--- /dev/null
+++ b/model-data/src/main/java/org/eclipse/viatra/solver/data/map/internal/MutableNode.java
@@ -0,0 +1,411 @@
+package org.eclipse.viatra.solver.data.map.internal;
+
+import java.util.Arrays;
+import java.util.Map;
+
+import org.eclipse.viatra.solver.data.map.ContinousHashProvider;
+
+public class MutableNode<KEY,VALUE> extends Node<KEY,VALUE> {
+	int cachedHash;
+	protected Object[] content;
+	
+	protected MutableNode() {
+		this.content = new Object[2*factor];
+		updateHash();
+	}
+	public static <KEY,VALUE> MutableNode<KEY,VALUE> initialize(
+			KEY key, VALUE value,
+			ContinousHashProvider<? super KEY> hashProvider,
+			VALUE defaultValue)
+	{
+		if(value == defaultValue) {
+			return null;
+		} else {
+			int hash = hashProvider.getHash(key, 0);
+			int fragment = hashFragment(hash, 0);
+			MutableNode<KEY, VALUE> res = new MutableNode<KEY, VALUE>();
+			res.content[2*fragment] = key;
+			res.content[2*fragment+1] = value;
+			res.updateHash();
+			return res;
+		}
+	}
+	
+	/**
+	 * Constructs a {@link MutableNode} as a copy of an {@link ImmutableNode}
+	 * @param node
+	 */
+	protected MutableNode(ImmutableNode<KEY,VALUE> node) {
+		this.content = new Object[2*factor]; 
+		int dataUsed=0;
+		int nodeUsed=0;
+		for(int i=0; i<factor; i++) {
+			int bitposition = 1 << i;
+			if((node.dataMap & bitposition) != 0) {
+				content[2*i] = node.content[dataUsed*2];
+				content[2*i+1] = node.content[dataUsed*2+1];
+				dataUsed++;
+			} else if((node.nodeMap & bitposition) != 0) {
+				content[2*i+1] = node.content[node.content.length-1-nodeUsed];
+				nodeUsed++;
+			}
+		}
+		this.cachedHash = node.hashCode();
+	}
+	
+	@SuppressWarnings("unchecked")
+	@Override
+	public VALUE getValue(KEY key, ContinousHashProvider<? super KEY> hashProvider, VALUE defaultValue, int hash, int depth) {
+		int selectedHashFragment = hashFragment(hash,shiftDepth(depth));
+		KEY keyCandidate = (KEY) this.content[2*selectedHashFragment];
+		if(keyCandidate != null) {
+			if(keyCandidate.equals(key)) {
+				return (VALUE) this.content[2*selectedHashFragment+1];
+			} else {
+				return defaultValue;
+			}
+		} else {
+			Node<KEY,VALUE> nodeCandidate = (Node<KEY,VALUE>) content[2*selectedHashFragment+1];
+			if(nodeCandidate != null) {
+				int newDepth = depth+1;
+				int newHash = newHash(hashProvider, key, hash, newDepth);
+				return nodeCandidate.getValue(key, hashProvider, defaultValue, newHash, newDepth);
+			} else {
+				return defaultValue;
+			}
+		}
+	}
+	
+	private boolean hasContent() {
+		for(Object element : this.content) {
+			if(element != null) return true;
+		}
+		return false;
+	}
+	
+	@SuppressWarnings("unchecked")
+	@Override
+	public Node<KEY,VALUE> putValue(KEY key, VALUE value, ContinousHashProvider<? super KEY> hashProvider, VALUE defaultValue, int hash, int depth) {
+		int selectedHashFragment = hashFragment(hash,shiftDepth(depth));
+		KEY keyCandidate = (KEY) content[2*selectedHashFragment];
+		if(keyCandidate != null) {
+			// If has key
+			if(keyCandidate.equals(key)) {
+				// The key is equals to an existing key -> update entry
+				if(value == defaultValue) {
+					return removeEntry(selectedHashFragment);
+				} else {
+					return updateValue(value,selectedHashFragment);
+				}
+			} else {
+				// The key is not equivalent to an existing key on the same hash bin
+				//   -> split entry if it is necessary 
+				if(value == defaultValue) {
+					// Value is default -> do not need to add new node
+					return this;
+				} else {
+					// Value is not default -> Split entry data to a new node
+					return moveDownAndSplit(hashProvider, key, value, keyCandidate, hash, depth, selectedHashFragment);
+				}
+			}
+		} else {
+			// If it does not have key, check for value
+			Node<KEY,VALUE> nodeCandidate =  (Node<KEY,VALUE>) content[2*selectedHashFragment+1];
+			if(nodeCandidate != null) {
+				// If it has value, it is a subnode -> upate that
+				Node<KEY, VALUE> newNode = nodeCandidate.putValue(key, value, hashProvider, defaultValue, newHash(hashProvider, key, hash, depth+1), depth+1);
+				return updateSubNode(selectedHashFragment,newNode);
+			} else {
+				// If it does not have value, put it in the empty place
+				if(value == defaultValue) {
+					// dont need to add new key-value pair
+					return this;
+				} else {
+					return addEntry(key, value, selectedHashFragment);
+				}
+				
+			}
+		}
+	}
+	
+
+
+	private Node<KEY, VALUE> addEntry(KEY key, VALUE value, int selectedHashFragment) {
+		content[2*selectedHashFragment] = key;
+		content[2*selectedHashFragment+1] = value;
+		updateHash();
+		return this;
+	}
+	/**
+	 * Updates an entry in a selected hash-fragment to a non-default value.
+	 * @param value
+	 * @param selectedHashFragment
+	 * @return
+	 */
+	Node<KEY, VALUE> updateValue(VALUE value, int selectedHashFragment) {
+		content[2*selectedHashFragment+1] = value;
+		updateHash();
+		return this;
+	}
+	
+	/**
+	 * 
+	 * @param selectedHashFragment
+	 * @param newNode
+	 * @return
+	 */
+	Node<KEY, VALUE> updateSubNode(int selectedHashFragment, Node<KEY, VALUE> newNode) {
+		content[2*selectedHashFragment+1] = newNode;
+		for(int i = 0; i<this.content.length; i++) {
+			if(content[i]!=null) {
+				updateHash();
+				return this;
+			}
+		}
+		return null;
+	}
+	
+	@SuppressWarnings("unchecked")
+	private Node<KEY, VALUE> moveDownAndSplit(
+			ContinousHashProvider<? super KEY> hashProvider,
+			KEY newKey, VALUE newValue, KEY previousKey,
+			int hashOfNewKey, int depth, int selectedHashFragmentOfCurrentDepth)
+	{
+		VALUE previousValue = (VALUE) content[2*selectedHashFragmentOfCurrentDepth+1];
+				
+		//final int newHash = newHash(hashProvider, newKey, hashOfNewKey, newDepth);
+		MutableNode<KEY,VALUE> newSubNode = newNodeWithTwoEntries(
+			hashProvider,
+			previousKey, previousValue, hashProvider.getHash(previousKey, hashDepth(depth)),
+			newKey, newValue, hashOfNewKey,
+			depth+1);
+		
+		content[2*selectedHashFragmentOfCurrentDepth] = null;
+		content[2*selectedHashFragmentOfCurrentDepth+1] = newSubNode;
+		updateHash();
+		return this;
+	}
+	private MutableNode<KEY,VALUE> newNodeWithTwoEntries(
+			ContinousHashProvider<? super KEY> hashProvider,
+			KEY key1, VALUE value1, int oldHash1,
+			KEY key2, VALUE value2, int oldHash2,
+			int newdepth)
+	{
+//		final int depthLimit = 4000;
+//		if(newdepth>depthLimit) {
+//			final int newHashes = 4000/numberOfFactors;
+//			throw new IllegalArgumentException(
+//				"Continuous hash was same " + newHashes + " times for non-equivalent objects " + key1 + " and " + key2 +".");
+//		}
+		int newHash1 = newHash(hashProvider, key1, oldHash1, newdepth);
+		int newHash2 = newHash(hashProvider, key2, oldHash2, newdepth);
+		int newFragment1 = hashFragment(newHash1, shiftDepth(newdepth));
+		int newFragment2 = hashFragment(newHash2, shiftDepth(newdepth));
+		
+		MutableNode<KEY,VALUE> subNode = new MutableNode<KEY,VALUE>();
+		if(newFragment1 != newFragment2) {
+			subNode.content[newFragment1*2]=key1;
+			subNode.content[newFragment1*2+1]=value1;
+			
+			subNode.content[newFragment2*2]=key2;
+			subNode.content[newFragment2*2+1]=value2;
+		} else {
+			MutableNode<KEY,VALUE> subSubNode = newNodeWithTwoEntries(
+					hashProvider,
+					key1, value1, newHash1,
+					key2, value2, newHash2,
+					newdepth+1);
+			subNode.content[newFragment1*2+1] = subSubNode;
+		}
+		subNode.updateHash();
+		return subNode;
+	}
+	
+	Node<KEY, VALUE> removeEntry(int selectedHashFragment) {
+		content[2*selectedHashFragment] = null;
+		content[2*selectedHashFragment+1] = null;
+		if(hasContent()) {
+			updateHash();
+			return this;
+		} else {
+			return null;
+		}
+	}
+	
+	@SuppressWarnings("unchecked")
+	@Override
+	public long getSize() {
+		int size = 0;
+		for(int i=0; i<factor; i++) {
+			if(content[i*2]!=null) {
+				size++;
+			} else{
+				 Node<KEY,VALUE> nodeCandidate = (Node<KEY, VALUE>) content[i*2+1];
+				 if(nodeCandidate!=null) {
+					 size+=nodeCandidate.getSize();
+				 }
+			}
+		}
+		return size;
+	}
+
+	@Override
+	protected MutableNode<KEY,VALUE> toMutable() {
+		return this;
+	}
+	
+	@Override
+	public ImmutableNode<KEY,VALUE> toImmutable() {
+		return ImmutableNode.constructImmutable(this,null);
+	}
+	
+	@Override
+	public ImmutableNode<KEY, VALUE> toImmutable(Map<Node<KEY, VALUE>, ImmutableNode<KEY, VALUE>> cache) {
+		return ImmutableNode.constructImmutable(this,cache);
+	}
+	
+	@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.nodeIndexStack.pop();
+				cursor.nodeIndexStack.push(index);
+				cursor.nodeIndexStack.push(MapCursor.IndexStart);
+				cursor.nodeStack.push(subnode);
+				
+				
+				return subnode.moveToNext(cursor);
+			}
+		}
+		// 3. no subnode found, move up
+		cursor.nodeStack.pop();
+		cursor.nodeIndexStack.pop();
+		if(!cursor.nodeStack.isEmpty()) {
+			Node<KEY, VALUE> supernode = cursor.nodeStack.peek();
+			return supernode.moveToNext(cursor);
+		} else {
+			cursor.key = null;
+			cursor.value = null;
+			return false;
+		}
+	}
+	
+	@Override
+	public void prettyPrint(StringBuilder builder, int depth, int code) {
+		for(int i = 0; i<depth; i++) {
+			builder.append("\t");
+		}
+		if(code>=0) {
+			builder.append(code);
+			builder.append(":");
+		}
+		builder.append("Mutable(");
+		// print content
+		boolean hadContent = false;
+		for(int i = 0; i<factor; i++) {
+			if(content[2*i] != null) {
+				if(hadContent) {
+					builder.append(",");
+				}
+				builder.append(i);
+				builder.append(":[");
+				builder.append(content[2*i].toString());
+				builder.append("]->[");
+				builder.append(content[2*i+1].toString());
+				builder.append("]");
+				hadContent = true;
+			}
+		}
+		builder.append(")");
+		// print subnodes
+		for(int i = 0; i<factor; i++) {
+			if(content[2*i] == null && content[2*i+1]!=null) {
+				@SuppressWarnings("unchecked")
+				Node<KEY,VALUE> subNode = (Node<KEY, VALUE>) content[2*i+1];
+				builder.append("\n");
+				subNode.prettyPrint(builder, depth+1, i);
+			}
+		}
+	}
+	@SuppressWarnings({"unchecked"})
+	@Override
+	public void checkIntegrity(ContinousHashProvider<? super KEY> hashProvider, VALUE defaultValue, int depth) {
+		for(int i = 0; i<factor; i++) {
+			if(this.content[2*i] != null) {
+				KEY key = (KEY) this.content[2*i];
+				VALUE value = (VALUE) this.content[2*i+1];
+				
+				if(value == defaultValue) {
+					throw new IllegalStateException("Node contains default value!");
+				}
+				int hashCode = hashProvider.getHash(key, hashDepth(depth));
+				int shiftDepth = shiftDepth(depth);
+				int selectedHashFragment = hashFragment(hashCode, shiftDepth);
+				if(i != selectedHashFragment) {
+					throw new IllegalStateException(
+						"Key "+key+" with hash code "+hashCode+" is in bad place! Fragment=" + selectedHashFragment +", Place="+i);
+				}
+			}
+		}
+		for(int i = 0; i<factor; i++) {
+			if(this.content[2*i+1] != null && this.content[2*i] == null) {
+				Node<KEY,VALUE> subNode = (Node<KEY, VALUE>) this.content[2*i+1];
+				subNode.checkIntegrity(hashProvider, defaultValue, depth+1);
+			}
+		}
+		int oldHash = this.cachedHash;
+		updateHash();
+		int newHash = this.cachedHash;
+		if(oldHash != newHash) {
+			throw new IllegalStateException("Hash code was not up to date! (old="+oldHash+",new="+newHash+")");
+		}
+	}
+	
+	
+	protected void updateHash() {
+		this.cachedHash = Arrays.hashCode(content);
+	}
+	
+	@Override
+	public int hashCode() {
+		return this.cachedHash;
+	}
+	
+	
+	@Override
+	public boolean equals(Object obj) {
+		if (this == obj)
+			return true;
+		if (obj == null)
+			return false;
+		if (obj instanceof MutableNode<?, ?>) {
+			MutableNode<?,?> other = (MutableNode<?,?>) obj;
+			return Arrays.deepEquals(this.content, other.content);
+		} else if(obj instanceof ImmutableNode<?,?>) {
+			ImmutableNode<?,?> other = (ImmutableNode<?,?>) obj;
+			return ImmutableNode.compareImmutableMutable(other, this);
+		} else {
+			return false;
+		}
+	}
+}
-- 
cgit v1.2.3-54-g00ecf