Mercurial > hg > Members > shoshi > TreeCMSv2

annotate 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
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
3
5fa718b63cd5 finished treecms.memory basic implementation ( not tested yet. )
shoshi
parents:
diff changeset
1 package treecms.tree.util;
5fa718b63cd5 finished treecms.memory basic implementation ( not tested yet. )
shoshi
parents:
diff changeset
2
5fa718b63cd5 finished treecms.memory basic implementation ( not tested yet. )
shoshi
parents:
diff changeset
3 import java.util.Iterator;
5fa718b63cd5 finished treecms.memory basic implementation ( not tested yet. )
shoshi
parents:
diff changeset
4 import java.util.Stack;
5fa718b63cd5 finished treecms.memory basic implementation ( not tested yet. )
shoshi
parents:
diff changeset
5 import treecms.api.Node;
5fa718b63cd5 finished treecms.memory basic implementation ( not tested yet. )
shoshi
parents:
diff changeset
6
5fa718b63cd5 finished treecms.memory basic implementation ( not tested yet. )
shoshi
parents:
diff changeset
7 public class PreorderTreewalker implements Iterable<Node>
5fa718b63cd5 finished treecms.memory basic implementation ( not tested yet. )
shoshi
parents:
diff changeset
8 {
5fa718b63cd5 finished treecms.memory basic implementation ( not tested yet. )
shoshi
parents:
diff changeset
9 private Node m_root;
5fa718b63cd5 finished treecms.memory basic implementation ( not tested yet. )
shoshi
parents:
diff changeset
10
5fa718b63cd5 finished treecms.memory basic implementation ( not tested yet. )
shoshi
parents:
diff changeset
11 public PreorderTreewalker(Node _root)
5fa718b63cd5 finished treecms.memory basic implementation ( not tested yet. )
shoshi
parents:
diff changeset
12 {
5fa718b63cd5 finished treecms.memory basic implementation ( not tested yet. )
shoshi
parents:
diff changeset
13 m_root = _root;
5fa718b63cd5 finished treecms.memory basic implementation ( not tested yet. )
shoshi
parents:
diff changeset
14 }
5fa718b63cd5 finished treecms.memory basic implementation ( not tested yet. )
shoshi
parents:
diff changeset
15
5fa718b63cd5 finished treecms.memory basic implementation ( not tested yet. )
shoshi
parents:
diff changeset
16
5fa718b63cd5 finished treecms.memory basic implementation ( not tested yet. )
shoshi
parents:
diff changeset
17 @Override
5fa718b63cd5 finished treecms.memory basic implementation ( not tested yet. )
shoshi
parents:
diff changeset
18 public Iterator<Node> iterator()
5fa718b63cd5 finished treecms.memory basic implementation ( not tested yet. )
shoshi
parents:
diff changeset
19 {
5fa718b63cd5 finished treecms.memory basic implementation ( not tested yet. )
shoshi
parents:
diff changeset
20 return new IteratorImpl();
5fa718b63cd5 finished treecms.memory basic implementation ( not tested yet. )
shoshi
parents:
diff changeset
21 }
5fa718b63cd5 finished treecms.memory basic implementation ( not tested yet. )
shoshi
parents:
diff changeset
22
5fa718b63cd5 finished treecms.memory basic implementation ( not tested yet. )
shoshi
parents:
diff changeset
23 private class IteratorImpl implements Iterator<Node>
5fa718b63cd5 finished treecms.memory basic implementation ( not tested yet. )
shoshi
parents:
diff changeset
24 {
5fa718b63cd5 finished treecms.memory basic implementation ( not tested yet. )
shoshi
parents:
diff changeset
25 private Stack<Pair<Node,Iterator<Node>>> m_depth;
5fa718b63cd5 finished treecms.memory basic implementation ( not tested yet. )
shoshi
parents:
diff changeset
26 private Node m_next;
5fa718b63cd5 finished treecms.memory basic implementation ( not tested yet. )
shoshi
parents:
diff changeset
27
5fa718b63cd5 finished treecms.memory basic implementation ( not tested yet. )
shoshi
parents:
diff changeset
28 public IteratorImpl()
5fa718b63cd5 finished treecms.memory basic implementation ( not tested yet. )
shoshi
parents:
diff changeset
29 {
5fa718b63cd5 finished treecms.memory basic implementation ( not tested yet. )
shoshi
parents:
diff changeset
30 m_depth = new Stack<Pair<Node,Iterator<Node>>>();
5fa718b63cd5 finished treecms.memory basic implementation ( not tested yet. )
shoshi
parents:
diff changeset
31 m_next = m_root;
5fa718b63cd5 finished treecms.memory basic implementation ( not tested yet. )
shoshi
parents:
diff changeset
32 m_depth.add(new Pair<Node,Iterator<Node>>(m_next,m_next.getData().list().iterator())); // ワケがわからないよ！
5fa718b63cd5 finished treecms.memory basic implementation ( not tested yet. )
shoshi
parents:
diff changeset
33 }
5fa718b63cd5 finished treecms.memory basic implementation ( not tested yet. )
shoshi
parents:
diff changeset
34
5fa718b63cd5 finished treecms.memory basic implementation ( not tested yet. )
shoshi
parents:
diff changeset
35 @Override
5fa718b63cd5 finished treecms.memory basic implementation ( not tested yet. )
shoshi
parents:
diff changeset
36 public boolean hasNext()
5fa718b63cd5 finished treecms.memory basic implementation ( not tested yet. )
shoshi
parents:
diff changeset
37 {
5fa718b63cd5 finished treecms.memory basic implementation ( not tested yet. )
shoshi
parents:
diff changeset
38 return (m_next != null) ? true : false;
5fa718b63cd5 finished treecms.memory basic implementation ( not tested yet. )
shoshi
parents:
diff changeset
39 }
5fa718b63cd5 finished treecms.memory basic implementation ( not tested yet. )
shoshi
parents:
diff changeset
40
5fa718b63cd5 finished treecms.memory basic implementation ( not tested yet. )
shoshi
parents:
diff changeset
41 @Override
5fa718b63cd5 finished treecms.memory basic implementation ( not tested yet. )
shoshi
parents:
diff changeset
42 public Node next()
5fa718b63cd5 finished treecms.memory basic implementation ( not tested yet. )
shoshi
parents:
diff changeset
43 {
5fa718b63cd5 finished treecms.memory basic implementation ( not tested yet. )
shoshi
parents:
diff changeset
44 Node next = m_next;
5fa718b63cd5 finished treecms.memory basic implementation ( not tested yet. )
shoshi
parents:
diff changeset
45
5fa718b63cd5 finished treecms.memory basic implementation ( not tested yet. )
shoshi
parents:
diff changeset
46 //forward.
5fa718b63cd5 finished treecms.memory basic implementation ( not tested yet. )
shoshi
parents:
diff changeset
47 Pair<Node,Iterator<Node>> context = m_depth.peek();
5fa718b63cd5 finished treecms.memory basic implementation ( not tested yet. )
shoshi
parents:
diff changeset
48 Iterator<Node> itr = context.m_right;
5fa718b63cd5 finished treecms.memory basic implementation ( not tested yet. )
shoshi
parents:
diff changeset
49 if(itr.hasNext()){
5fa718b63cd5 finished treecms.memory basic implementation ( not tested yet. )
shoshi
parents:
diff changeset
50 m_next = itr.next();
5fa718b63cd5 finished treecms.memory basic implementation ( not tested yet. )
shoshi
parents:
diff changeset
51 m_depth.add(new Pair<Node,Iterator<Node>>(m_next,m_next.getData().list().iterator())); // ワケがわからないよ！
5fa718b63cd5 finished treecms.memory basic implementation ( not tested yet. )
shoshi
parents:
diff changeset
52 }else{
5fa718b63cd5 finished treecms.memory basic implementation ( not tested yet. )
shoshi
parents:
diff changeset
53 m_depth.pop();
5fa718b63cd5 finished treecms.memory basic implementation ( not tested yet. )
shoshi
parents:
diff changeset
54 while(!m_depth.isEmpty()){
5fa718b63cd5 finished treecms.memory basic implementation ( not tested yet. )
shoshi
parents:
diff changeset
55 Pair<Node,Iterator<Node>> back = m_depth.peek();
5fa718b63cd5 finished treecms.memory basic implementation ( not tested yet. )
shoshi
parents:
diff changeset
56 if(back.m_right.hasNext()){
5fa718b63cd5 finished treecms.memory basic implementation ( not tested yet. )
shoshi
parents:
diff changeset
57 m_next = back.m_right.next();
5fa718b63cd5 finished treecms.memory basic implementation ( not tested yet. )
shoshi
parents:
diff changeset
58 break;
5fa718b63cd5 finished treecms.memory basic implementation ( not tested yet. )
shoshi
parents:
diff changeset
59 }
5fa718b63cd5 finished treecms.memory basic implementation ( not tested yet. )
shoshi
parents:
diff changeset
60 m_depth.pop();
5fa718b63cd5 finished treecms.memory basic implementation ( not tested yet. )
shoshi
parents:
diff changeset
61 }
5fa718b63cd5 finished treecms.memory basic implementation ( not tested yet. )
shoshi
parents:
diff changeset
62 m_next = null;
5fa718b63cd5 finished treecms.memory basic implementation ( not tested yet. )
shoshi
parents:
diff changeset
63 }
5fa718b63cd5 finished treecms.memory basic implementation ( not tested yet. )
shoshi
parents:
diff changeset
64
5fa718b63cd5 finished treecms.memory basic implementation ( not tested yet. )
shoshi
parents:
diff changeset
65 return next;
5fa718b63cd5 finished treecms.memory basic implementation ( not tested yet. )
shoshi
parents:
diff changeset
66 }
5fa718b63cd5 finished treecms.memory basic implementation ( not tested yet. )
shoshi
parents:
diff changeset
67
5fa718b63cd5 finished treecms.memory basic implementation ( not tested yet. )
shoshi
parents:
diff changeset
68 @Override
5fa718b63cd5 finished treecms.memory basic implementation ( not tested yet. )
shoshi
parents:
diff changeset
69 public void remove()
5fa718b63cd5 finished treecms.memory basic implementation ( not tested yet. )
shoshi
parents:
diff changeset
70 {
5fa718b63cd5 finished treecms.memory basic implementation ( not tested yet. )
shoshi
parents:
diff changeset
71 //not supported.
5fa718b63cd5 finished treecms.memory basic implementation ( not tested yet. )
shoshi
parents:
diff changeset
72 }
5fa718b63cd5 finished treecms.memory basic implementation ( not tested yet. )
shoshi
parents:
diff changeset
73 }
5fa718b63cd5 finished treecms.memory basic implementation ( not tested yet. )
shoshi
parents:
diff changeset
74
5fa718b63cd5 finished treecms.memory basic implementation ( not tested yet. )
shoshi
parents:
diff changeset
75 private class Pair<L,R>
5fa718b63cd5 finished treecms.memory basic implementation ( not tested yet. )
shoshi
parents:
diff changeset
76 {
5fa718b63cd5 finished treecms.memory basic implementation ( not tested yet. )
shoshi
parents:
diff changeset
77 @SuppressWarnings("unused")
5fa718b63cd5 finished treecms.memory basic implementation ( not tested yet. )
shoshi
parents:
diff changeset
78 public L m_left;
5fa718b63cd5 finished treecms.memory basic implementation ( not tested yet. )
shoshi
parents:
diff changeset
79 public R m_right;
5fa718b63cd5 finished treecms.memory basic implementation ( not tested yet. )
shoshi
parents:
diff changeset
80
5fa718b63cd5 finished treecms.memory basic implementation ( not tested yet. )
shoshi
parents:
diff changeset
81 public Pair(L _left,R _right)
5fa718b63cd5 finished treecms.memory basic implementation ( not tested yet. )
shoshi
parents:
diff changeset
82 {
5fa718b63cd5 finished treecms.memory basic implementation ( not tested yet. )
shoshi
parents:
diff changeset
83 m_left = _left;
5fa718b63cd5 finished treecms.memory basic implementation ( not tested yet. )
shoshi
parents:
diff changeset
84 m_right = _right;
5fa718b63cd5 finished treecms.memory basic implementation ( not tested yet. )
shoshi
parents:
diff changeset
85 }
5fa718b63cd5 finished treecms.memory basic implementation ( not tested yet. )
shoshi
parents:
diff changeset
86 }
5fa718b63cd5 finished treecms.memory basic implementation ( not tested yet. )
shoshi
parents:
diff changeset
87 }