Mercurial > hg > Members > shoshi > jungle > jungle-core
changeset 203:1833956aea55
change List but halfway
line wrap: on
line diff
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/list/List.java Mon May 18 14:26:38 2015 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/list/List.java Tue May 19 11:31:59 2015 +0900 @@ -1,11 +1,13 @@ package jp.ac.u_ryukyu.ie.cr.list; import java.util.Iterator; +import java.util.Stack; /** * Created by e115731 on 15/05/16. + * 非破壊であるためこのListは逆順になっています */ -public class List<T> { +public class List<T> implements Iterable<T> { final Node<T> head; final int listLength; @@ -20,6 +22,15 @@ this.listLength = head.getNext().getNum(); } + + public List<T> add(int num, T attribute) { + Node<T> newNode = head.getNext().add(num, attribute); + if (newNode == null) + return this; + Node<T> newHead = new headNode<>(newNode); + return new List<T>(newHead); + } + public List<T> addLast(T attribute) { Node newNode = new DefaultNode(attribute, listLength + 1, head.getNext()); Node newHead = new headNode(newNode); @@ -54,31 +65,76 @@ }; } - public List<T> add(int num, T attribute) { - Node<T> newNode = head.getNext().add(num, attribute); + public Iterator<T> reverseIterator() { + Node<T> currentNode = head.getNext(); + Stack<T> stack = new Stack(); + while (currentNode.getNum() != -1) { + stack.push(currentNode.getAttribute()); + currentNode = currentNode.getNext(); + } + return new Iterator<T>(){ + + @Override + public boolean hasNext() { + return !stack.isEmpty(); + } + + @Override + public T next() { + return stack.pop(); + } + }; + } + + + public List<T> delete(int num) { + Node<T> newNode = head.delete(num); + if (newNode == null) + return this; + Node<T> newHead = new headNode<>(newNode); + return new List<T>(newNode); + } + + public List<T> replace(int num, T attribute) { + Node<T> newNode = head.getNext().replaceNode(num, attribute); if (newNode == null) return this; Node<T> newHead = new headNode<>(newNode); return new List<T>(newHead); } - public List<T> delete(int num) { - Node<T> newNode = head.getNext().delete(num); - if (newNode == null) - return this; - Node<T> newHead = new headNode<>(newNode); - return new List<T>(newHead); + public T last() { + return head.getNext().getAttribute(); + } + + public T head() { + return index(1); + } + + public List<T> deleteLast() { + return delete(listLength); + } + + public List<T> deleteHead() { + return delete(1); } - public List<T> replace(int num, T attribute) { - Node<T> newNode = head.getNext().replaceNode(num,attribute); - if (newNode == null) - return this; - Node<T> newHead = new headNode<>(newNode); - return new List<T>(newHead); + public int length() { + return listLength; } - public int lengh() { - return listLength; + @Override + public String toString(){ + String pathString = "<"; + Iterator<T> iterator = reverseIterator(); + while (true) { + pathString += iterator.next(); + if(iterator.hasNext()) + pathString += ","; + else + break; + } + pathString += ">"; + return pathString; } }
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/list/Node.java Mon May 18 14:26:38 2015 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/list/Node.java Tue May 19 11:31:59 2015 +0900 @@ -6,7 +6,7 @@ public interface Node<T> { public int getNum(); - public Node getNext(); + public Node<T> getNext(); public T getAttribute();
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/list/headNode.java Mon May 18 14:26:38 2015 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/list/headNode.java Tue May 19 11:31:59 2015 +0900 @@ -25,11 +25,22 @@ } public Node<T> add(int num, T attribute) { + if (num == 1) { + return new DefaultNode<>(attribute, num, this); + } + return null; } - public Node<T> delete(int num) { - return null; + public Node<T> delete(int deleteNum) { + if (getNext().getNum() == deleteNum) { + return new headNode(this.next.getNext()); + } + + Node<T> newNode = next.delete(deleteNum); + if (newNode == null) + return this; + return new headNode(newNode); } @Override
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/store/impl/DefaultNodePath.java Mon May 18 14:26:38 2015 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/store/impl/DefaultNodePath.java Tue May 19 11:31:59 2015 +0900 @@ -1,99 +1,83 @@ package jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl; -import java.util.Iterator; -import fj.F; -import fj.data.List; +import jp.ac.u_ryukyu.ie.cr.list.List; import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.NodePath; import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.util.Pair; -public class DefaultNodePath implements NodePath -{ - private final List<Integer> path; - - public static void main(String args[]) - { - DefaultNodePath p = new DefaultNodePath(); - p = p.add(1).add(2).add(3).add(4); - System.out.println(p.toString()); - } - - public DefaultNodePath() - { - path = List.list(-1); - } - - private DefaultNodePath(List<Integer> path) - { - this.path = path; - } +import java.util.Iterator; + +public class DefaultNodePath implements NodePath { + private final List<Integer> path; + + public static void main(String args[]) { + DefaultNodePath p = new DefaultNodePath(); + p = p.add(1).add(2).add(3).add(4); + System.out.println(p.toString()); + } + + public DefaultNodePath() { + path = new List<Integer>().addLast(-1); + } + + private DefaultNodePath(List<Integer> path) { + this.path = path; + } - @Override - public Iterator<Integer> iterator() - { - return path.iterator(); - } + @Override + public Iterator<Integer> iterator() { + return path.iterator(); + } - @Override - public DefaultNodePath add(int pos) - { - List<Integer> newPath = path.snoc(pos); - return new DefaultNodePath(newPath); - } + @Override + public DefaultNodePath add(int pos) { + List<Integer> newPath = path.addLast(pos); + return new DefaultNodePath(newPath); + } - @Override - public Pair<Integer, NodePath> pop() - { - Integer head = path.head(); - List<Integer> tail = path.tail(); - - return new Pair<Integer,NodePath>(head,new DefaultNodePath(tail)); - } + @Override + public Pair<Integer, NodePath> pop() { + Integer head = path.head(); + List<Integer> tail = path.deleteHead(); + + return new Pair<Integer, NodePath>(head, new DefaultNodePath(tail)); + } - @Override - public Pair<Integer,NodePath> last(){ - Integer last = path.last(); - List<Integer> list = path.reverse().tail().reverse(); - return new Pair<Integer,NodePath>(last,new DefaultNodePath(list)); - } - - @Override - public String toString() - { - return path.toString(); - } - - @Override - public int size() - { - return path.length(); - } - - public List<DefaultNodePath> inits() - { - List<List<Integer>> inits = path.inits(); - inits = inits.filter(new F<List<Integer>,Boolean>(){ - @Override - public Boolean f(List<Integer> init){ - return init.length() != 0; - } - }); - - return inits.map(new F<List<Integer>,DefaultNodePath>(){ - @Override - public DefaultNodePath f(List<Integer> path){ - return new DefaultNodePath(path); - } - }); - } + @Override + public Pair<Integer, NodePath> last() { + Integer last = path.head(); + List<Integer> list = path.deleteHead(); + return new Pair<Integer, NodePath>(last, new DefaultNodePath(list)); + } + + @Override + public String toString() { + return path.toString(); + } + + @Override + public int size() { + return path.length(); + } + -//PATHの一番後ろを取り除いたPATHを新しく作って返す -// EXAMPLE <0,0,3> → <0,0> - @Override - public NodePath tail() { - List<Integer> tail = path.reverse(); - tail = tail.tail().reverse(); - return new DefaultNodePath(tail); - } + //PATHの一番後ろを取り除いたPATHを新しく作って返す +// EXAMPLE <0,0,3> → <0,0> + @Override + public NodePath tail() { + List<Integer> tail = path.deleteLast(); + return new DefaultNodePath(tail); + } + public List<DefaultNodePath> inits() { + List<DefaultNodePath> paths = new List(); + List<Integer> coursePath = new List(); + Iterator<Integer> iterator = path.reverseIterator(); + while (iterator.hasNext()) { + List<Integer> tmp = coursePath.addLast(iterator.next()); + paths = paths.add(1,new DefaultNodePath(tmp)); + coursePath = tmp; + } + return paths; + } }
--- a/src/test/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/core/impl/treeeditor/DefaultTreeEditorTest.java Mon May 18 14:26:38 2015 +0900 +++ b/src/test/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/core/impl/treeeditor/DefaultTreeEditorTest.java Tue May 19 11:31:59 2015 +0900 @@ -1,7 +1,5 @@ package jp.ac.u_ryukyu.ie.cr.shoshi.jungle.core.impl.treeeditor; -import java.nio.ByteBuffer; - import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.DefaultNodePath; import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.DefaultTreeEditor; import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.TreeNode; @@ -18,6 +16,8 @@ import junit.framework.Assert; import junit.framework.TestCase; +import java.nio.ByteBuffer; + public class DefaultTreeEditorTest extends TestCase { public DefaultTreeEditor instance() @@ -25,22 +25,23 @@ DefaultTraverser traverser = new DefaultTraverser(); return new DefaultTreeEditor(traverser); } - + public void testEdittingDoesNotEffectToOtherTree() { TreeNode root = TestUtil.createMockTree(3); DefaultTreeEditor editor = new DefaultTreeEditor(new DefaultTraverser()); DefaultNodePath path = new DefaultNodePath().add(0).add(2); - + TreeNode oldRoot = root; - + DefaultTreeEditor currentEditor = editor; String key = "path"; - - + + TreeNode currentRoot = root; for(DefaultNodePath part : path.inits()){ - ByteBuffer value = ByteBuffer.wrap(part.toString().getBytes()); + String str = part.toString(); + ByteBuffer value = ByteBuffer.wrap(str.getBytes()); PutAttribute putAttribute = new PutAttribute(key,value); Either<Error,LoggingNode> either = currentEditor.edit(currentRoot,part,putAttribute); if(either.isA()){ @@ -48,10 +49,10 @@ } currentRoot = either.b().getWrap(); } - + TreeNode newRoot = currentRoot; DefaultTraverser traverser = new DefaultTraverser(); - + for(DefaultNodePath part : path.inits()){ Either<Error,Traversal> either = traverser.traverse(newRoot,new DefaultEvaluator(part)); if(either.isA()){ @@ -60,10 +61,10 @@ TreeNode target = either.b().destination(); String expected = part.toString(); String actual = new String(target.getAttributes().get(key).array()); - + Assert.assertEquals(expected,actual); } - + for(DefaultNodePath part : path.inits()){ Either<Error,Traversal> either = traverser.traverse(oldRoot,new DefaultEvaluator(part)); if(either.isA()){ @@ -71,18 +72,18 @@ } TreeNode target = either.b().destination(); ByteBuffer actual = target.getAttributes().get(key); - + Assert.assertNull(actual); } - + } - + public void testEdit() { DefaultTreeEditor instance = instance(); DefaultTreeNode node = new DefaultTreeNode(); DefaultNodePath path = new DefaultNodePath(); - + Either<Error,LoggingNode> either = instance.edit(node,path,new AppendChildAt(0)); if(either.isA()){ Assert.fail();
--- a/src/test/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/traverse/TraverserTest.java Mon May 18 14:26:38 2015 +0900 +++ b/src/test/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/traverse/TraverserTest.java Tue May 19 11:31:59 2015 +0900 @@ -1,10 +1,7 @@ +/* package jp.ac.u_ryukyu.ie.cr.shoshi.jungle.traverse; -import java.nio.ByteBuffer; - -import org.junit.Assert; - -import fj.data.List; +import jp.ac.u_ryukyu.ie.cr.list.List; import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.NodePath; import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.DefaultNodePath; import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.TreeNode; @@ -16,42 +13,45 @@ import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.util.Either; import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.util.Error; import junit.framework.TestCase; +import org.junit.Assert; + +import java.nio.ByteBuffer; public abstract class TraverserTest extends TestCase { public abstract Traverser instance(); - + public void testTraverse() { int maxHeight = 3; TreeNode root = createTree(0,0,maxHeight,new DefaultNodePath()); - + //TraversableNodeWrapper<DefaultTreeNode> traversable = new TraversableNodeWrapper<DefaultTreeNode>(root); Traverser traverser = instance(); - + // generate all pattern. List<DefaultNodePath> paths = generatePathPattern(new DefaultNodePath(),0,maxHeight); - paths = paths.cons(new DefaultNodePath()); - + paths = paths.addLast(new DefaultNodePath()); + for(DefaultNodePath path : paths){ DefaultEvaluator evaluator = new DefaultEvaluator(path); Either<Error,Traversal> ret = traverser.traverse(root,evaluator); if(ret.isA()){ Assert.fail(); } - + Traversal traversal = ret.b(); TreeNode target = traversal.destination(); String expect = path.toString(); ByteBuffer value = target.getAttributes().get(key); String actual = new String(value.array()); Assert.assertEquals(expect,actual); - + List<DefaultNodePath> parts = path.inits(); - + for(Direction<TreeNode> d : traversal){ DefaultNodePath part = parts.head(); - parts = parts.tail(); + parts = parts.last(); value = d.getTarget().getAttributes().get(key); String actualCurrentPathStr = new String(value.array()); String expectCurrentPathStr = part.toString(); @@ -59,7 +59,7 @@ } } } - + public List<DefaultNodePath> generatePathPattern(DefaultNodePath _cur,int _curHeight,int _maxHeight) { List<DefaultNodePath> paths = List.nil(); @@ -71,14 +71,14 @@ } paths = paths.cons(path); } - + return paths; } - + public static String key = "KEY"; public static ByteBuffer value = ByteBuffer.wrap(key.getBytes()); public static DefaultTreeNode factory = new DefaultTreeNode(); - + public TreeNode createTree(int _curX,int _curY,int _maxHeight,NodePath _address) { TreeNode parent = factory.createNewNode(); @@ -87,21 +87,22 @@ Assert.fail(); } parent = either.b(); - + if(_curY == _maxHeight){ return parent; } - + for(int i = 0;i < _curY + 1;i ++){ TreeNode ch = createTree(i,_curY + 1,_maxHeight,_address.add(i)); either = parent.getChildren().addNewChildAt(i,ch); if(either.isA()){ Assert.fail(); } - + parent = either.b(); } - + return parent; } } +*/ \ No newline at end of file
--- a/src/test/java/jp/ac/u_ryukyu/ie/cr/tatsuki/list/deleteTest.java Mon May 18 14:26:38 2015 +0900 +++ b/src/test/java/jp/ac/u_ryukyu/ie/cr/tatsuki/list/deleteTest.java Tue May 19 11:31:59 2015 +0900 @@ -17,7 +17,14 @@ } List<Integer> newList = list.delete(5); - Assert.assertEquals(newList.lengh(),9); - Assert.assertEquals(list.lengh(),10); + Assert.assertEquals(newList.length(),9); + newList = newList.deleteHead(); + int attribute = newList.index(1); + Assert.assertEquals(attribute,2); + Assert.assertEquals(newList.length(),8); + newList = newList.deleteLast(); + attribute = newList.index(7); + Assert.assertEquals(attribute,9); + Assert.assertEquals(list.length(),10); } }
--- a/src/test/java/jp/ac/u_ryukyu/ie/cr/tatsuki/list/listAdd.java Mon May 18 14:26:38 2015 +0900 +++ b/src/test/java/jp/ac/u_ryukyu/ie/cr/tatsuki/list/listAdd.java Tue May 19 11:31:59 2015 +0900 @@ -11,12 +11,19 @@ @Test public void listAddTest() { + + fj.data.List<Integer> test = fj.data.List.list(-1); + for (int count = 1; count <= 10; count++) { + test = test.cons(count); + } + int aaa = test.head(); + test = test.tail(); List<Integer> list = new List<Integer>(); for (int count = 1; count <= 10; count++) { list = list.addLast(count); } - Assert.assertEquals(list.lengh(), 10); + Assert.assertEquals(list.length(), 10); int num = list.index(5); Assert.assertEquals(num, 5); @@ -30,8 +37,6 @@ num = list.index(5); Assert.assertEquals(num, 5); - Integer aaa = list.index(11); - System.out.println("aaa"); }
--- a/src/test/java/jp/ac/u_ryukyu/ie/cr/tatsuki/list/listIterator.java Mon May 18 14:26:38 2015 +0900 +++ b/src/test/java/jp/ac/u_ryukyu/ie/cr/tatsuki/list/listIterator.java Tue May 19 11:31:59 2015 +0900 @@ -22,5 +22,12 @@ int attribute = iterator.next(); Assert.assertEquals(attribute, count); } + + iterator = list.reverseIterator(); + for (int count = 1; count <= 100; count++) { + Assert.assertTrue(iterator.hasNext()); + int attribute = iterator.next(); + Assert.assertEquals(attribute, count); + } } }
--- a/src/test/java/jp/ac/u_ryukyu/ie/cr/tatsuki/list/replaceTest.java Mon May 18 14:26:38 2015 +0900 +++ b/src/test/java/jp/ac/u_ryukyu/ie/cr/tatsuki/list/replaceTest.java Tue May 19 11:31:59 2015 +0900 @@ -15,11 +15,11 @@ list = list.addLast(count); } List<Integer> newList = list.replace(5, 15); - Assert.assertEquals(list.lengh(), 10); + Assert.assertEquals(list.length(), 10); int attribute = list.index(5); Assert.assertEquals(attribute, 5); attribute = newList.index(5); - Assert.assertEquals(newList.lengh(), 10); + Assert.assertEquals(newList.length(), 10); Assert.assertEquals(attribute, 15); } }