changeset 8:abed5bd92fcb

commit
author shoshi <shoshi@cr.ie.u-ryukyu.ac.jp>
date Tue, 03 Jul 2012 18:59:28 +0900
parents c3c65308a11b
children bb96e631f022
files memo.txt src/main/java/jungle/core/graph/EdgeList.java src/main/java/jungle/core/graph/Graph.java src/main/java/jungle/core/graph/Vertex.java src/main/java/jungle/core/graph/Vertexes.java src/main/java/jungle/core/graph/simple/SimpleGraph.java src/main/java/jungle/core/graph/simple/SimpleVertex.java src/main/java/jungle/core/graph/simple/SimpleVertexes.java src/main/java/jungle/impl/SimpleEditor.java src/test/java/jungle/misc/fj/ImmutableSetExample.java src/test/java/jungle/misc/fj/XMLNodeTest.java
diffstat 11 files changed, 353 insertions(+), 107 deletions(-) [+]
line wrap: on
line diff
--- a/memo.txt	Fri Jun 29 00:03:12 2012 +0900
+++ b/memo.txt	Tue Jul 03 18:59:28 2012 +0900
@@ -53,4 +53,8 @@
  ・SimpleTreeGroup , SimpleTree , SimpleNode をどうするか
  
 2012/06/27
- ・Graph を用いた SimpleJungle の設計をもっと考える
\ No newline at end of file
+ ・Graph を用いた SimpleJungle の設計をもっと考える
+
+2012/06/28
+ ・SimpleJungle 実装を完成させた。テストコードはまだ書いていない
+ ・SimpleEditor の部分がまだだった。明日完成させよう
\ No newline at end of file
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/main/java/jungle/core/graph/EdgeList.java	Tue Jul 03 18:59:28 2012 +0900
@@ -0,0 +1,26 @@
+package jungle.core.graph;
+
+import java.util.Collection;
+
+public interface EdgeList extends Iterable<Vertex>
+{
+	public int getLength();
+	public Vertex at(int _i);
+	public Collection<Vertex> asVertexCollection();
+	
+	public void appendVertex(Vertex _vertex);
+	public void appendVertexAt(Vertex _vertex,int _index);
+	public void appendVertexCollection(Collection<Vertex> _collection);
+	
+	public boolean removeFirst(Vertex _vertex);
+	public boolean removeFirst(Collection<Vertex> _collection);
+	public Vertex remove(int _index);
+	
+	public Vertex replace(Vertex _vertex,int _index);
+	public boolean replaceFirst(Vertex _vertex,Vertex _newVertex);
+	
+	public boolean compareAndSwap(int _index,Vertex _vertex,Vertex _newVertex);
+	public boolean contains(Vertex _vertex);
+	
+	public String getName();
+}
--- a/src/main/java/jungle/core/graph/Graph.java	Fri Jun 29 00:03:12 2012 +0900
+++ b/src/main/java/jungle/core/graph/Graph.java	Tue Jul 03 18:59:28 2012 +0900
@@ -1,13 +1,15 @@
 package jungle.core.graph;
 
-import java.util.Iterator;
-
+/*
+ * multiedge property graph
+ */
 public interface Graph
 {
 	public Vertex getVertex(String _id);
 	public Vertex createVertex(String _id);
 	public Vertex createVertex();
+	public Vertex cloneVertex(Vertex _base);
+	public Vertex cloneVertex(String _id,Vertex _base);
 	
-	public boolean isSame(Graph _g);
-	public Iterator<Vertex> vertexes();
+	public boolean isSameGraph(Graph _g);
 }
--- a/src/main/java/jungle/core/graph/Vertex.java	Fri Jun 29 00:03:12 2012 +0900
+++ b/src/main/java/jungle/core/graph/Vertex.java	Tue Jul 03 18:59:28 2012 +0900
@@ -3,15 +3,20 @@
 public interface Vertex
 {
 	public String getID();
-	public Graph getGraph();
+	public boolean isSameVertex();
+	public Graph getOwnerGraph();
 	
-	public String getProperty(String _key);
-	public void setProperty(String _key,String _value);
-	public String setPropertyIfAbsent(String _key,String _value);
-	public String removeProperty(String _key);
-	public boolean compareAndSwapProprety(String _key,String _except,String _value);
+	public String getAttribute(String _key);
+	public void setAttribute(String _key,String _value);
+	public String setAttributeIfAbsent(String _key,String _value);
+	public Iterable<String> getAttributeKeys();
+	public String removeAttribute(String _key);
+	public boolean replaceAttribute(String _key,String _except,String _value);
 	
-	public Vertexes removeVertexes(String _type);
-	public Vertexes getVertexes(String _type);
-	public Vertexes createVertexes(String _type);
+	public Vertex getNamedEdgeAt(String _name,int _index);
+	public void appendEdge(String _name,Vertex _vertex);
+	public void insertEdge(String _name,int _index,Vertex _vertex);
+	public void removeEdge(String _name,Vertex _vertex);
+	public void replaceEdge(String _name,Vertex _expectVertex,Vertex _updateVertex);
+	public Iterable<String> getEdgeNames();
 }
--- a/src/main/java/jungle/core/graph/Vertexes.java	Fri Jun 29 00:03:12 2012 +0900
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,28 +0,0 @@
-package jungle.core.graph;
-
-import java.util.Collection;
-
-public interface Vertexes extends Iterable<Vertex>
-{
-	public int size();
-	public Vertex at(int _i);
-	
-	public void add(Vertex _v);
-	public void add(Vertex _v,int _i);
-	public void add(Collection<Vertex> _vs);
-	public void add(Vertexes _vs);
-	
-	public boolean removeFirst(Vertex _v);
-	public boolean removeFirst(Collection<Vertex> _vs);
-	public boolean removeFirst(Vertexes _vs);
-	public Vertex remove(int _i);
-	
-	public Vertex replace(Vertex _v,int _i);
-	public boolean replaceFirst(Vertex _vertex,Vertex _newVertex);
-	
-	public boolean compareAndSwap(int _index,Vertex _vertex,Vertex _newVertex);
-	public boolean contains(Vertex _v);
-	
-	public Graph getGraph();
-	public String type();
-}
--- a/src/main/java/jungle/core/graph/simple/SimpleGraph.java	Fri Jun 29 00:03:12 2012 +0900
+++ b/src/main/java/jungle/core/graph/simple/SimpleGraph.java	Tue Jul 03 18:59:28 2012 +0900
@@ -32,7 +32,7 @@
 	}
 	
 	@Override
-	public boolean isSame(Graph _g)
+	public boolean isSameGraph(Graph _g)
 	{
 		if(_g instanceof SimpleGraph){
 			return _g == this;
@@ -80,4 +80,27 @@
 		};
 		return wrapper;
 	}
+	
+	@Override
+	public Vertex createVertexFromTemplate(Vertex _template)
+	{
+		String newID = Long.toString(ids.incrementAndGet());
+		
+	}
+
+	@Override
+	public Vertex createVertexFromTemplate(String _id,Vertex _template)
+	{
+		if(_template instanceof SimpleVertex){
+			SimpleVertex template = (SimpleVertex)_template;
+			if(template.getGraph().equals(this)){
+				SimpleVertex newVertex = new SimpleVertex(this,_id,_template);
+				
+			}
+			
+			throw new IllegalArgumentException("_template is a vertex from other graph.");
+		}
+		
+		throw new IllegalArgumentException("_template is not a instance of SimpleVertex");
+	}
 }
--- a/src/main/java/jungle/core/graph/simple/SimpleVertex.java	Fri Jun 29 00:03:12 2012 +0900
+++ b/src/main/java/jungle/core/graph/simple/SimpleVertex.java	Tue Jul 03 18:59:28 2012 +0900
@@ -1,24 +1,52 @@
 package jungle.core.graph.simple;
 
-import java.util.concurrent.ConcurrentHashMap;
-
+import java.util.Iterator;
+import java.util.concurrent.atomic.AtomicReference;
+import fj.Ord;
+import fj.P2;
+import fj.data.Option;
+import fj.data.TreeMap;
 import jungle.core.graph.Graph;
 import jungle.core.graph.Vertex;
 import jungle.core.graph.Vertexes;
+import jungle.util.Pair;
 
 public class SimpleVertex implements Vertex
 {
 	private String id;
 	private final SimpleGraph parent;
-	private final ConcurrentHashMap<String,String> properties;
-	private final ConcurrentHashMap<String,SimpleVertexes> relations;
+	private final AtomicReference<TreeMap<String,String>> propertiesHolder;
+	private final AtomicReference<TreeMap<String,SimpleVertexes>> relationsHolder;
+	
+	private static final TreeMap<String,String> EMPTY_PROPERTIES_MAP = TreeMap.empty(Ord.stringOrd);
+	private static final TreeMap<String,SimpleVertexes> EMPTY_RELATIONS_MAP = TreeMap.empty(Ord.stringOrd);
 	
 	public SimpleVertex(SimpleGraph _parent,String _id)
 	{
 		id = _id;
 		parent = _parent;
-		properties = new ConcurrentHashMap<String,String>();
-		relations = new ConcurrentHashMap<String,SimpleVertexes>();
+		propertiesHolder = new AtomicReference<TreeMap<String,String>>(EMPTY_PROPERTIES_MAP);
+		relationsHolder = new AtomicReference<TreeMap<String,SimpleVertexes>>(EMPTY_RELATIONS_MAP);
+	}
+	
+	public SimpleVertex(SimpleGraph _parent,String _id,SimpleVertex _template)
+	{
+		id = _id;
+		parent = _parent;
+		
+		//get snapshot
+		TreeMap<String,String> snapshotProperties = _template.
+		
+		propertiesHolder = new AtomicReference<TreeMap<String,String>>();
+		relationsHolder = new AtomicReference<TreeMap<String,SimpleVertexes>>();
+	}
+	
+	private Pair<TreeMap<String,String>,TreeMap<String,SimpleVertexes>> createVertexSnapshot()
+	{
+		TreeMap<String,String> snapshotProperties = propertiesHolder.get();
+		TreeMap<String,SimpleVertexes> snapshotRelations = relationsHolder.get();
+		
+		return new Pair<TreeMap<Stirng,String>>
 	}
 	
 	void setID(String _id)
@@ -29,8 +57,18 @@
 	@Override
 	public String setPropertyIfAbsent(String _key,String _value)
 	{
-		String previousValue = properties.putIfAbsent(_key,_value);
-		return previousValue;
+		TreeMap<String,String> current,update;
+		do{
+			current = propertiesHolder.get();
+			Option<String> value = current.get(_key);
+			if(value.isSome()){
+				return value.some();
+			}
+			
+			update = current.set(_key,_value);
+		}while(!propertiesHolder.compareAndSet(current,update));
+		
+		return null;
 	}
 	
 	@Override
@@ -48,38 +86,111 @@
 	@Override
 	public String getProperty(String _key)
 	{
-		return properties.get(_key);
+		TreeMap<String,String> current = propertiesHolder.get();
+		Option<String> nullOrValue = current.get(_key);
+		if(nullOrValue.isNone()){
+			return null;
+		}
+		
+		return nullOrValue.some();
 	}
 
 	@Override
 	public void setProperty(String _key, String _value)
 	{
-		properties.put(_key,_value);
+		TreeMap<String,String> current , update;
+		do{
+			current = propertiesHolder.get();
+			update = current.set(_key,_value);
+		}while(!propertiesHolder.compareAndSet(current,update));
 	}
 
 	@Override
 	public String removeProperty(String _key)
 	{
-		return properties.remove(_key);
+		if(_key == null){
+			throw new NullPointerException("_key is null");
+		}
+		
+		String remove;
+		TreeMap<String,String> current , update;
+		do{
+			current = propertiesHolder.get();
+			Option<String> nullOrValue = current.get(_key);
+			if(nullOrValue.isNone()){
+				return null;
+			}
+			
+			remove = nullOrValue.some();
+			update = current.delete(_key);
+		}while(!propertiesHolder.compareAndSet(current,update));
+		
+		return remove;
 	}
 
 	@Override
 	public Vertexes getVertexes(String _key)
 	{
-		return relations.get(_key);
+		if(_key == null){
+			throw new NullPointerException("_key is null");
+		}
+		
+		TreeMap<String,SimpleVertexes> current = relationsHolder.get();
+		Option<SimpleVertexes> nullOrValue = current.get(_key);
+		if(nullOrValue.isNone()){
+			return null;
+		}
+		
+		return nullOrValue.some();
 	}
 	
 	@Override
 	public Vertexes removeVertexes(String _type)
 	{
-		SimpleVertexes vertexes = relations.remove(_type);
-		return vertexes;
+		if(_type == null){
+			throw new NullPointerException("_type is null");
+		}
+		
+		SimpleVertexes remove;
+		TreeMap<String,SimpleVertexes> current , update;
+		do{
+			current = relationsHolder.get();
+			Option<SimpleVertexes> nullOrValue = current.get(_type);
+			if(nullOrValue.isNone()){
+				return null;
+			}
+			
+			remove = nullOrValue.some();
+			update = current.delete(_type);
+		}while(!relationsHolder.compareAndSet(current,update));
+		
+		return remove;
 	}
 
 	@Override
-	public boolean compareAndSwapProprety(String _key, String _except,String _value)
+	public boolean compareAndSwapProprety(String _key,final String _except,final String _value)
 	{
-		return properties.replace(_key,_except,_value);
+		if(_key == null || _except == null || _value == null){
+			throw new NullPointerException("_key or _except or _value is null");
+		}
+		
+		TreeMap<String,String> current , update;
+		do{
+			current = propertiesHolder.get();
+			Option<String> nullOrValue = current.get(_key);
+			if(nullOrValue.isNone()){
+				return false;
+			}
+			
+			String value = nullOrValue.some();
+			if(!value.equals(_except)){
+				return false;
+			}
+			
+			update = current.set(_key,_value);
+		}while(!propertiesHolder.compareAndSet(current,update));
+		
+		return true;
 	}
 	
 	@Override
@@ -91,8 +202,48 @@
 	@Override
 	public Vertexes createVertexes(String _type)
 	{
-		SimpleVertexes vertexes = new SimpleVertexes(_type,parent);
-		SimpleVertexes result = relations.putIfAbsent(_type,vertexes);
-		return result == null ? vertexes : null;
+		TreeMap<String,SimpleVertexes> current , update;
+		
+		SimpleVertexes newVertexes;
+		do{
+			current = relationsHolder.get();
+			Option<SimpleVertexes> nullOrValue = current.get(_type);
+			if(nullOrValue.isSome()){
+				return null;
+			}
+			
+			newVertexes = new SimpleVertexes(_type,parent);
+			update = current.set(_type,newVertexes);
+		}while(!relationsHolder.compareAndSet(current,update));
+		
+		return newVertexes;
+	}
+
+	@Override
+	public Iterable<Pair<String,String>> getProperties()
+	{
+		final TreeMap<String,String> snapshot = propertiesHolder.get();
+		Iterable<Pair<String,String>> snapshotIterableWrapper = new Iterable<Pair<String,String>>(){
+			@Override
+			public Iterator<Pair<String, String>> iterator(){
+				return new Iterator<Pair<String,String>>(){
+					Iterator<P2<String,String>> snapshotKeyValueIterator = snapshot.iterator();
+					@Override
+					public boolean hasNext(){
+						return snapshotKeyValueIterator.hasNext();
+					}
+					@Override
+					public Pair<String, String> next(){
+						P2<String,String> keyValue = snapshotKeyValueIterator.next();
+						return new Pair<String,String>(keyValue._1(),keyValue._2());
+					}
+					@Override
+					public void remove() {
+						throw new UnsupportedOperationException("removing is not supported.");
+					}
+				};
+			}
+		};
+		return snapshotIterableWrapper;
 	}
 }
--- a/src/main/java/jungle/core/graph/simple/SimpleVertexes.java	Fri Jun 29 00:03:12 2012 +0900
+++ b/src/main/java/jungle/core/graph/simple/SimpleVertexes.java	Tue Jul 03 18:59:28 2012 +0900
@@ -11,6 +11,7 @@
 import fj.F;
 import fj.P2;
 import fj.data.List;
+import fj.data.Option;
 
 import jungle.core.graph.Graph;
 import jungle.core.graph.Vertex;
@@ -19,41 +20,20 @@
 public class SimpleVertexes implements Vertexes
 {
 	private final String type;
-	private final AtomicReference<List<SimpleVertex>> vertexes;
+	private final SimpleVertexContext context;
 	private final SimpleGraph parent;
 	
-	public SimpleVertexes(String _type,SimpleGraph _parent)
+	public SimpleVertexes(String _type,SimpleGraph _parent,SimpleVertexContext _context)
 	{
 		parent = _parent;
 		type = _type;
-		List<SimpleVertex> nil = List.nil();
-		vertexes = new AtomicReference<List<SimpleVertex>>(nil);
-	}
-	
-	public static void main(String _args[])
-	{
-		SimpleGraph g = new SimpleGraph();
-		Vertex v = g.createVertex();
-		Vertexes vs = v.createVertexes("test");
-		Vertex a = g.createVertex("a");
-		Vertex b = g.createVertex("b");
-		Vertex c = g.createVertex("c");
-		Vertex d = g.createVertex("d");
-		vs.add(Arrays.asList(a,b,c,d));
-		
-		System.out.println(vs);
-		
-		if(vs.compareAndSwap(2,c,b) == false){
-			System.out.println("^o^...");
-		}
-		
-		System.out.println(vs);
+		context = _context;
 	}
 	
 	@Override
 	public String toString()
 	{
-		return vertexes.get().toString();
+		return context.getRelations().get(type).toString();
 	}
 	
 	
@@ -63,10 +43,12 @@
 		if(_index < 0){
 			throw new IndexOutOfBoundsException("_index < 0");
 		}
+		
 		SimpleVertex head = null;
-		List<SimpleVertex> current = null,update = null;
+		TreeMap<String,List<SimpleVertex>> current = null,update = null;
 		do{
-			current = vertexes.get();
+			Option<List<SimpleVertex>> value = context.getRelations().get(type);
+			
 			if(current.length() < _index + 1){
 				throw new IndexOutOfBoundsException("list.length() < _index");
 			}
@@ -433,4 +415,10 @@
 		
 		return true;
 	}
+	
+	@Override
+	public int hashCode()
+	{
+		return context.
+	}
 }
\ No newline at end of file
--- a/src/main/java/jungle/impl/SimpleEditor.java	Fri Jun 29 00:03:12 2012 +0900
+++ b/src/main/java/jungle/impl/SimpleEditor.java	Tue Jul 03 18:59:28 2012 +0900
@@ -1,30 +1,29 @@
 package jungle.impl;
 
+import java.util.Iterator;
 import java.util.concurrent.ConcurrentHashMap;
 import java.util.concurrent.atomic.AtomicReference;
-
 import jungle.core.Editor;
-
 import jungle.core.Link;
 import jungle.core.Tree;
 import jungle.core.TreeGroup;
 import jungle.core.TreeNode;
 import jungle.core.Node;
+import jungle.core.graph.Graph;
+import jungle.core.graph.Vertex;
 import jungle.util.Pair;
 
 public class SimpleEditor implements Editor
 {
-	private final ConcurrentHashMap<String,Node> changeset;
-	private final TreeGroup group;
-	private final Tree tree;
-	private final AtomicReference<Tree> current;
+	private final SimpleTreeGroup group;
+	private final Graph graph;
+	private AtomicReference<SimpleTree> current;
 	
-	public SimpleEditor(TreeGroup _group,Tree _tree)
+	public SimpleEditor(SimpleTree _tree,Graph _graph)
 	{
-		tree = _tree;
-		group = _group;
-		changeset = new ConcurrentHashMap<String,Node>();
-		current = new AtomicReference<Tree>();
+		graph = _graph;
+		group = (SimpleTreeGroup)_tree.getGroup();
+		current = new AtomicReference<SimpleTree>(_tree);
 	}
 
 	public Tree commit()
@@ -36,10 +35,53 @@
 	{
 		return null;
 	}
-
-	public Link createLinkAt(TreeNode _target, Tree _linkTarget)
+	
+	private boolean checkTreeNode(TreeNode _target)
+	{
+		if(_target instanceof SimpleTreeNode){
+			SimpleTreeNode converted = (SimpleTreeNode)_target;
+			return converted.getGroup().equals(group);
+		}
+		
+		return false;
+	}
+	
+	private SimpleTreeNode convertTreeNode(TreeNode _target)
+	{
+		if(_target instanceof SimpleTreeNode){
+			return (SimpleTreeNode)_target;
+		}
+		
+		return null;
+	}
+	
+	private Vertex cloneTreeNode(Iterable<TreeNode> _path)
 	{
-		return null;
+		Iterator<TreeNode> itr = _path.iterator();
+		String newID = group.newTreeID();
+		
+		if(!itr.hasNext()){
+			return null;
+		}
+		
+		SimpleTreeNode root = convertTreeNode(itr.next());
+		if(root == null){
+			return null;
+		}
+		
+		Vertex rootVertex = root.getVertex();
+		
+		
+		for(TreeNode node : _path){
+			if(checkTreeNode(node)){
+			}
+		}
+	}
+	
+	public Link createLinkAt(Iterable<TreeNode> _path,TreeNode _target, Tree _linkTarget)
+	{
+		
+		throw new IllegalArgumentException("wrong tree group.");
 	}
 
 	public void removeLinkAt(TreeNode _target, Link _removeTarget)
--- a/src/test/java/jungle/misc/fj/ImmutableSetExample.java	Fri Jun 29 00:03:12 2012 +0900
+++ b/src/test/java/jungle/misc/fj/ImmutableSetExample.java	Tue Jul 03 18:59:28 2012 +0900
@@ -1,9 +1,36 @@
 package jungle.misc.fj;
 
+import fj.F;
+import fj.Ord;
+import fj.P2;
+import fj.Show;
+import fj.data.List;
+import fj.data.TreeMap;
+
 
 public class ImmutableSetExample
 {
 	public static void main(String _args[])
 	{
+		TreeMap<String,String> map = TreeMap.empty(Ord.stringOrd);
+		Show<List<P2<String,String>>> s = Show.listShow(Show.p2Show(Show.stringShow,Show.stringShow));
+		
+		TreeMap<String,String> second = map.set("hoge","fuga");
+		TreeMap<String,String> third = second.set("fuga","fuga");
+		s.println(List.iterableList(second));
+		s.println(List.iterableList(third));
+		System.out.println(second.get("hoge").some());
+		
+		F<String,String> predicate = new F<String,String>(){
+			@Override
+			public String f(String str){
+				return null;
+			}
+		};
+		
+		P2<Boolean,TreeMap<String,String>> transformResult = third.update("hoge",predicate);
+		if(transformResult._1()){
+			s.println(List.iterableList(transformResult._2()));
+		}
 	}
 }
--- a/src/test/java/jungle/misc/fj/XMLNodeTest.java	Fri Jun 29 00:03:12 2012 +0900
+++ b/src/test/java/jungle/misc/fj/XMLNodeTest.java	Tue Jul 03 18:59:28 2012 +0900
@@ -12,12 +12,18 @@
 	public static void main(String _args[]) throws Exception
 	{
 		DocumentBuilder b = DocumentBuilderFactory.newInstance().newDocumentBuilder();
-		Document d = b.newDocument();
+		Document g = b.newDocument();
 		
-		Element e = d.createElement("hoge");
+		Element e = g.createElement("hoge");
+		g.appendChild(e);
+		e.appendChild(g.createElement("hoge"));
 		NodeList l1 = e.getElementsByTagName("hoge");
+		System.out.println(l1.getLength());
+		e.appendChild(g.createElement("hoge"));
+		e.appendChild(g.createElement("hoge"));
 		NodeList l2 = e.getElementsByTagName("hoge");
-		System.out.println(l1.toString());
-		System.out.println(l2.toString());
+		
+		System.out.println(l1.getLength());
+		System.out.println(l2.getLength());
 	}
 }