= 2013-05-24 活动 =
{{{
提供数据fid,parentid 一一对应
1. 根据fid,获取从根版到子版的路径
2. 根据fid,获取直接子版
3. 根据fid,获取所有子版
}}}
为了增加这次CodeKata活动的趣味性与挑战性，要求完成时不使用或尽量不使用Java API提供的一些数据结构如，List,Map,等[[BR]]
本周的活动请来了小虎哥作为顾问全程参与了活动,期间小虎哥针对我们的开发以及活动本身提出了一些宝贵的建议,主要包括以下几点:[[BR]]
关于开发:
 * 1.数据结构优于算法
 * 2.如果不知道如何得到结果,就先穷举
关于活动本身:[[BR]]
本次活动中遇到了一点小障碍,关于准备本次题目所需要用到的数据,本来是不属于程序的一部分,但是在活动开始时大家却
	把添加数据也作为了程序的一部分,并围绕相应的测试代码反复讨论,偏离了题目的本意,小虎哥对此予以了纠正
	* 1.测试驱动也需要先设计好代码及测试代码的结构(无需实现),不应过快动手
	* 2.如果有现成的生产环境下的数据,尽量使用


由于时间关系本周的题目最终没有完成,但是大家都表示小虎哥的建议非常切中要点,受益匪浅,争取在下周的活动中吸取教训调整方法,
做出更好的结果。

05-31日，我们按照陈小虎的建议与方法，继续完成上周的CodeKata活动的题目,本周末下午，由于平台组部分同事负责的项目有较紧急的事情[[BR]]
需要处理，所以没有参加，最后，由陈阳与邝巨恒来完成CodeKata活动。由李峰全程协调，指导。尽管这次CodeKata活动的人气少了许多，[[BR]]
但丝毫不影响陈阳与邝巨桓的信心与积极性，两位开发人员，结对编程，以轮流编写代码，另一位协助的方式，各个击破，完成了活动。[[BR]]
按照陈小虎给出的建议的，我们准备了生产环境的数据，用来测试
data.txt
[[BR]]1	0
[[BR]]2	16428
[[BR]]7	15670
[[BR]]9	16427
[[BR]]19	1
[[BR]]22	16427
[[BR]]292	3
[[BR]]293	19
[[BR]]294	3
[[BR]]295	19
[[BR]]297	17136
[[BR]]298	19
[[BR]]301	19
[[BR]]304	19
[[BR]]305	19
[[BR]]306	19
[[BR]]307	19
[[BR]]308	19
[[BR]]312	17125
[[BR]]318	16420
[[BR]]322	9999
[[BR]]327	16428
[[BR]]388	16031
[[BR]]393	18975
[[BR]]715	9999
[[BR]]1307	19
[[BR]]2427	16427
[[BR]]2429	16428
[[BR]]8005	17148
[[BR]]9999	1
[[BR]]13351	17146
[[BR]]13352	1
[[BR]]13372	19
[[BR]]13373	19
[[BR]]13374	16428
[[BR]]13402	1
[[BR]]14033	19
[[BR]]14034	19
[[BR]]14077	19
[[BR]]14087	19
[[BR]]14093	19
[[BR]]14112	19
[[BR]]14119	19
[[BR]]14140	14034
[[BR]]14141	16425
[[BR]]14142	16425
[[BR]]14143	16411
[[BR]]14144	16411
[[BR]]14149	16425
[[BR]]14150	16425
[[BR]]14152	306
[[BR]]14153	306
[[BR]]14221	17133
[[BR]]14250	14077
[[BR]]14306	3
[[BR]]14359	14034
[[BR]]14360	293
[[BR]]14483	305
[[BR]]14493	14093
[[BR]]14505	295
[[BR]]............
[[BR]]19275	19
[[BR]]19276	16072
[[BR]]19285	16072
[[BR]]19287	16072
[[BR]]19295	16072
[[BR]]19305	16072
[[BR]]19315	16072
[[BR]]19335	15961


下面帖出题目的解决方案的单元测试代码与实现代码[[BR]]
单元测试代码如下[[BR]]
NodeContainerTest.java
{{{
/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package findex;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.logging.Level;
import java.util.logging.Logger;
import org.junit.After;
import org.junit.AfterClass;
import org.junit.Assert;
import org.junit.Before;
import org.junit.BeforeClass;
import org.junit.Test;
import static org.junit.Assert.*;

/**
 *
 * @author pc
 */
public class NodeContainerTest {
    @Before
    public void setUp() {
        //getTestData();
    }
    
    @After
    public void tearDown() {
    }


    /**
     * Test of getRoute method, of class NodeContainer.
     */
    @Test
    public void testGetRoute() {
        
        NodeContainer nContain = new NodeContainer(16);
        
        Node[] nodes = getTestData();
        
        nContain.setContainer(nodes);
        
        int[] result = nContain.getRoute(2);
        
        Assert.assertEquals(0, result[0]);
        Assert.assertEquals(1, result[1]);
        Assert.assertEquals(16428, result[2]);
        Assert.assertEquals(2, result[3]);
        
        result = nContain.getRoute(8888);
        Assert.assertEquals(0,result.length);
        
        result = nContain.getRoute(0);
        Assert.assertEquals(0,result.length);
        
        result = nContain.getRoute(-99);
        Assert.assertEquals(0,result.length);
        
    }
    
    @Test
    public void testGetDirectChildren() {
        NodeContainer nContain = new NodeContainer(16);
        
        Node[] nodes = getTestData();
        
        nContain.setContainer(nodes);
        
        //普通节点(正常情况)
        int[] result = nContain.getDirectChildren(9999);
        Assert.assertEquals(5, result.length);
        for (int id : result) {
            Assert.assertTrue(id == 322 || id == 715 || id == 15252 || id == 15253 || id == 15530);
        }
        
        //最根节点
        result = nContain.getDirectChildren(0);
        Assert.assertEquals(1, result.length);
        Assert.assertEquals(1, result[0]);
        
        //不存在节点
        result = nContain.getDirectChildren(-100);
        Assert.assertEquals(0, result.length);
        
        //末节点
        result = nContain.getDirectChildren(18505);
        Assert.assertEquals(0, result.length);
    }
    
    @Test
    public void testGetChildren() {
        NodeContainer nContain = new NodeContainer(16);
        
        Node[] nodes = getTestData();
        
        nContain.setContainer(nodes);
        
        //普通节点(正常情况)
        
        int[] result = nContain.getChildren(16428);
        for(int i=0; i<result.length; i++){
            System.out.println(result[i]);
        }
        
        for (int id : result) {
            Assert.assertTrue(id == 16816 || id == 16031 || id == 15402 
                    || id == 15051 || id == 13374 || id == 2429 
                    || id == 327 || id == 27 || id == 388 || id == 15244
                    || id == 15834 || id == 2);
        }
        
        //子只有一级
        result = nContain.getChildren(18975);
        for (int id : result) {
            Assert.assertTrue(id == 393 || id == 18976 || id == 18985);
        }
        
        //最根节点
        result = nContain.getChildren(1);
        //Assert.assertEquals(nodes.length - 1, result.length);
        
        //不存在节点
        result = nContain.getDirectChildren(-100);
        Assert.assertEquals(0, result.length);
        
        //末节点
        result = nContain.getDirectChildren(18505);
        Assert.assertEquals(0, result.length);
    }

    public Node[] getTestData() {
       
        List<String> lines = new ArrayList<String>(1500);
        InputStream in = this.getClass().getResourceAsStream("/data.txt");
        BufferedReader reader = new BufferedReader(new InputStreamReader(in));
        String line = null;
        try{
            while((line = reader.readLine()) != null){
                lines.add(line);
            }
        }catch(Exception ex){
            
        }finally{
            if(reader != null){
                try {
                    reader.close();
                } catch (IOException ex) {
                    Logger.getLogger(NodeContainerTest.class.getName()).log(Level.SEVERE, null, ex);
                }
            }
        }
        Node[] nodes = new Node[lines.size()];
        for(int i=0, len = lines.size(); i < len; i++){
                String[] data_line = lines.get(i).split("\\s");
                Node node = new Node(Integer.valueOf(data_line[0]),Integer.valueOf(data_line[1]));
                nodes[i] = node;
        }
        
        return nodes;
        
    }
    
   
    
}
				
}}}

实现代码如下[[BR]]
Node.java
{{{
	
/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package findex;

/**
 *
 * @author pc
 */
public class Node {
    private int id;
    private int pid;

    public Node(int id, int pid) {
        this.id = id;
        this.pid = pid;
    }
    
    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    public int getPid() {
        return pid;
    }

    public void setPid(int pid) {
        this.pid = pid;
    }
    
}
	
}}}
NodeContainer.java
{{{
package findex;

/**
 *
 * @author pc
 */
public class NodeContainer {

    private int limit;
    private Node[] nodes;
    private static final int ROOT_ID = 0;

    public int getLimit() {
        return limit;
    }

    public void setLimit(int limit) {
        this.limit = limit;
    }

    public Node[] getContainer() {
        return nodes;
    }

    public void setContainer(Node[] container) {
        this.nodes = container;
    }

    public NodeContainer(int limit) {
        this.limit = limit;
        this.nodes = new Node[this.limit];
    }

    public int getParentId(Node[] nodes,int id){
        for(int i=0, len = nodes.length; i< len; i++){
            Node current = nodes[i];
            if(id == current.getId()){
                return current.getPid();
            }
        }
        return -1;
    }
    
    /**
     * 获取根版到子版的路径
     *
     * @param id 子版ID
     * @return
     */
    public int[] getRoute(int id) {
        int[] result = new int[limit];
        int index = 0;
        if (nodes == null) {
            throw new RuntimeException("没数据");
        }
        
        if(getParentId(nodes,id) == -1){
            return new int[0];
        }
        
        int count = 0;
        
        int tmpId = id;
        while(tmpId != -1) {
            result[index] = tmpId;
            index++;
            tmpId = getParentId(this.nodes, tmpId);
            count++;
        }
        int[] result2 = new int[count];
        for(int i = count -1, j=0; i>=0 ; i--,j++){
            result2[j] = result[i];
           
        }
        return result2;
    }

	// 根据fid,获取直接子版   
    public int[] getDirectChildren(int id) {
        int[] result = new int[nodes.length];
        int index = 0;
        for (Node node : nodes) {
            if (node.getPid() == id) {
               result[index] = node.getId();
               index++;
            }
        }
        int[] tmp = new int[index];
        System.arraycopy(result, 0, tmp, 0, index);
        return tmp;
    }

	//根据fid,获取所有子版   
    public int[] getChildren(int id){
        int[] result = new int[nodes.length];

		//递归将子版添加到result中
        recuri(result,id);
        int len = 0;
        for(int i=0; i<result.length; i++){
            if(result[i] == 0){
                break;
            }
            len++;
        }
        int[] tmp = new int[len];
        System.arraycopy(result, 0, tmp, 0, len);
        return tmp;
    }
    
    public void recuri(int[] childs,int id) {
        
        int[] directChildren = getDirectChildren(id);
        for(int i=0; i<directChildren.length; i++){
            if(hasChild(directChildren[i])){
                 recuri(childs,directChildren[i]);
             }

         }
        int posi = 0;// 记录childs的长度
        for(int j=0; j<childs.length; j++){
            if(childs[j] == 0){
                posi = j;
                break;
            }
        }
        System.arraycopy(directChildren, 0, childs, posi, directChildren.length);
        
    }
    
    private boolean hasChild(int id) {
        for (Node node : nodes) {
            if (node.getPid() == id) {
                return true;
            }
        }
        return false;
    }
}
	
}}}