Mercurial > hg > Members > shoshi > TreeCMSv2

comparison src/treecms/tree/util/PreorderTreewalker.java @ 3:5fa718b63cd5

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
finished treecms.memory basic implementation ( not tested yet. )
author shoshi
date Fri, 18 Feb 2011 02:14:10 +0900
parents
children 12604eb6b615
comparison
equal deleted inserted replaced
2:4a5ee88f02cf 3:5fa718b63cd5
1 package treecms.tree.util;
2
3 import java.util.Iterator;
4 import java.util.Stack;
5 import treecms.api.Node;
6
7 public class PreorderTreewalker implements Iterable<Node>
8 {
9 private Node m_root;
10
11 public PreorderTreewalker(Node _root)
12 {
13 m_root = _root;
14 }
15
16
17 @Override
18 public Iterator<Node> iterator()
19 {
20 return new IteratorImpl();
21 }
22
23 private class IteratorImpl implements Iterator<Node>
24 {
25 private Stack<Pair<Node,Iterator<Node>>> m_depth;
26 private Node m_next;
27
28 public IteratorImpl()
29 {
30 m_depth = new Stack<Pair<Node,Iterator<Node>>>();
31 m_next = m_root;
32 m_depth.add(new Pair<Node,Iterator<Node>>(m_next,m_next.getData().list().iterator())); // ワケがわからないよ！
33 }
34
35 @Override
36 public boolean hasNext()
37 {
38 return (m_next != null) ? true : false;
39 }
40
41 @Override
42 public Node next()
43 {
44 Node next = m_next;
45
46 //forward.
47 Pair<Node,Iterator<Node>> context = m_depth.peek();
48 Iterator<Node> itr = context.m_right;
49 if(itr.hasNext()){
50 m_next = itr.next();
51 m_depth.add(new Pair<Node,Iterator<Node>>(m_next,m_next.getData().list().iterator())); // ワケがわからないよ！
52 }else{
53 m_depth.pop();
54 while(!m_depth.isEmpty()){
55 Pair<Node,Iterator<Node>> back = m_depth.peek();
56 if(back.m_right.hasNext()){
57 m_next = back.m_right.next();
58 break;
59 }
60 m_depth.pop();
61 }
62 m_next = null;
63 }
64
65 return next;
66 }
67
68 @Override
69 public void remove()
70 {
71 //not supported.
72 }
73 }
74
75 private class Pair<L,R>
76 {
77 @SuppressWarnings("unused")
78 public L m_left;
79 public R m_right;
80
81 public Pair(L _left,R _right)
82 {
83 m_left = _left;
84 m_right = _right;
85 }
86 }
87 }