Changes between Version 3 and Version 4 of codekata2

Timestamp:

06/03/2013 09:49:40 AM (13 years ago)

Author:

chenyang

Comment:

--

codekata2

@@ -6 +6 @@
 3. 根据fid,获取所有子版
 }}}
-
+为了增加这次CodeKata活动的趣味性与挑战性，要求完成时不使用或尽量不使用Java API提供的一些数据结构如，List,Map,等[[BR]]
 本周的活动请来了小虎哥作为顾问全程参与了活动,期间小虎哥针对我们的开发以及活动本身提出了一些宝贵的建议,主要包括以下几点:[[BR]]
 关于开发:
@@ -17 +17 @@
         * 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;
+    }
+}
+        
+}}}