2013-05-24 活动

提供数据fid,parentid 一一对应
1. 根据fid,获取从根版到子版的路径
2. 根据fid,获取直接子版
3. 根据fid,获取所有子版

为了增加这次CodeKata活动的趣味性与挑战性，要求完成时不使用或尽量不使用Java API提供的一些数据结构如，List,Map,等
本周的活动请来了小虎哥作为顾问全程参与了活动,期间小虎哥针对我们的开发以及活动本身提出了一些宝贵的建议,主要包括以下几点:
关于开发:

• 1.数据结构优于算法
• 2.如果不知道如何得到结果,就先穷举

关于活动本身:
本次活动中遇到了一点小障碍,关于准备本次题目所需要用到的数据,本来是不属于程序的一部分,但是在活动开始时大家却

把添加数据也作为了程序的一部分,并围绕相应的测试代码反复讨论,偏离了题目的本意,小虎哥对此予以了纠正

• 1.测试驱动也需要先设计好代码及测试代码的结构(无需实现),不应过快动手
• 2.如果有现成的生产环境下的数据,尽量使用

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

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

下面帖出题目的解决方案的单元测试代码与实现代码
单元测试代码如下
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;
        
    }
    
   
    
}
				

实现代码如下
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;
    }
}