← Back to branch summary

~ubuntu-branches/ubuntu/precise/weka/precise

« back to all changes in this revision

Viewing changes to weka/core/neighboursearch/kdtrees/KDTreeNode.java

  • Committer: Bazaar Package Importer
  • Author(s): Soeren Sonnenburg
  • Date: 2008-02-24 09:18:45 UTC
  • Revision ID: james.westby@ubuntu.com-20080224091845-1l8zy6fm6xipbzsr
Tags: upstream-3.5.7+tut1
Import upstream version 3.5.7+tut1

Show diffs side-by-side

added added

removed removed

Lines of Context:
weka/core/neighboursearch/kdtrees/KDTreeNode.java
 
1
/*
 
2
 *    This program is free software; you can redistribute it and/or modify
 
3
 *    it under the terms of the GNU General Public License as published by
 
4
 *    the Free Software Foundation; either version 2 of the License, or
 
5
 *    (at your option) any later version.
 
6
 *
 
7
 *    This program is distributed in the hope that it will be useful,
 
8
 *    but WITHOUT ANY WARRANTY; without even the implied warranty of
 
9
 *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
10
 *    GNU General Public License for more details.
 
11
 *
 
12
 *    You should have received a copy of the GNU General Public License
 
13
 *    along with this program; if not, write to the Free Software
 
14
 *    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 
15
 */
 
16
 
 
17
/*
 
18
 * KDTreeNode.java
 
19
 * Copyright (C) 2007 University of Waikato, Hamilton, New Zealand
 
20
 */
 
21
 
 
22
package weka.core.neighboursearch.kdtrees;
 
23
 
 
24
import java.io.Serializable;
 
25
 
 
26
/**
 
27
 * A class representing a KDTree node. A node does not explicitly
 
28
 * store the instances that it contains. Instead, it only stores 
 
29
 * the start and end index of a portion in a master index array. Each
 
30
 * node is assigned a portion in the master index array that stores 
 
31
 * the indices of the instances that the node contains. Every time a 
 
32
 * node is split by the KDTree's contruction method, the instances of 
 
33
 * its left child are moved to the left and the instances of its 
 
34
 * right child are moved to the right, in the portion of the master 
 
35
 * index array belonging to the node. The start and end index in each
 
36
 * of its children are then set accordingly within that portion so 
 
37
 * that each have their own portion which contains their instances.   
 
38
 * P.S.: The master index array is only stored in KDTree class.
 
39
 * 
 
40
 * @author Ashraf M. Kibriya (amk14[at-the-rate]cs[dot]waikato[dot]ac[dot]nz)
 
41
 * @version $Revision: 1.1 $
 
42
 */
 
43
public class KDTreeNode
 
44
  implements Serializable {
 
45
   
 
46
  /** for serialization. */
 
47
  private static final long serialVersionUID = -3660396067582792648L;
 
48
 
 
49
  /** node number (only for debug). */
 
50
  public int m_NodeNumber;
 
51
 
 
52
  /** left subtree; contains instances with smaller or equal to split value. */
 
53
  public KDTreeNode m_Left = null;
 
54
 
 
55
  /** right subtree; contains instances with larger than split value. */
 
56
  public KDTreeNode m_Right = null;
 
57
 
 
58
  /** value to split on. */
 
59
  public double m_SplitValue;
 
60
 
 
61
  /** attribute to split on. */
 
62
  public int m_SplitDim;
 
63
 
 
64
  /**
 
65
   * lowest and highest value and width (= high - low) for each
 
66
   * dimension.
 
67
   */
 
68
  public double[][] m_NodeRanges;
 
69
 
 
70
  /** 
 
71
   * The lo and high bounds of the hyper rectangle described by the
 
72
   * node.
 
73
   */
 
74
  public double[][] m_NodesRectBounds;
 
75
 
 
76
  /**
 
77
   * The start index of the portion of the master index array, 
 
78
   * which stores the indices of the instances/points the node 
 
79
   * contains.
 
80
   */
 
81
  public int m_Start = 0;
 
82
  
 
83
  /**
 
84
   * The end index of the portion of the master index array, 
 
85
   * which stores indices of the instances/points the node 
 
86
   * contains.
 
87
   */
 
88
  public int m_End = 0;
 
89
 
 
90
  /**
 
91
   * Constructor.
 
92
   */
 
93
  public KDTreeNode() {}
 
94
 
 
95
  /**
 
96
   * Constructor.
 
97
   * 
 
98
   * @param nodeNum The node number/id.
 
99
   * @param startidx The start index of node's portion 
 
100
   * in master index array.
 
101
   * @param endidx The start index of node's portion 
 
102
   * in master index array.
 
103
   * @param nodeRanges The attribute ranges of the 
 
104
   * Instances/points contained in this node.
 
105
   */
 
106
  public KDTreeNode(int nodeNum, int startidx, int endidx, double[][] nodeRanges) {
 
107
    m_NodeNumber = nodeNum;
 
108
    m_Start = startidx; m_End = endidx;
 
109
    m_NodeRanges = nodeRanges;
 
110
  }
 
111
 
 
112
  /**
 
113
   * 
 
114
   * @param nodeNum The node number/id.
 
115
   * @param startidx The start index of node's portion 
 
116
   * in master index array.
 
117
   * @param endidx The start index of node's portion 
 
118
   * in master index array.
 
119
   * @param nodeRanges The attribute ranges of the 
 
120
   * Instances/points contained in this node.
 
121
   * @param rectBounds The range of the rectangular 
 
122
   * region in the point space that this node 
 
123
   * represents (points inside this rectangular
 
124
   * region can have different range).
 
125
   */
 
126
  public KDTreeNode(int nodeNum, int startidx, int endidx, double[][] nodeRanges, double[][] rectBounds) {
 
127
    m_NodeNumber = nodeNum;
 
128
    m_Start = startidx; m_End = endidx;
 
129
    m_NodeRanges = nodeRanges;
 
130
    m_NodesRectBounds = rectBounds;
 
131
  }
 
132
 
 
133
  /**
 
134
   * Gets the splitting dimension.
 
135
   * 
 
136
   * @return            splitting dimension
 
137
   */
 
138
  public int getSplitDim() {
 
139
    return m_SplitDim;
 
140
  }
 
141
 
 
142
  /**
 
143
   * Gets the splitting value.
 
144
   * 
 
145
   * @return            splitting value
 
146
   */
 
147
  public double getSplitValue() {
 
148
    return m_SplitValue;
 
149
  }
 
150
 
 
151
  /**
 
152
   * Checks if node is a leaf.
 
153
   * 
 
154
   * @return            true if it is a leaf
 
155
   */
 
156
  public boolean isALeaf() {
 
157
    return (m_Left == null);
 
158
  }         
 
159
 
 
160
  /**
 
161
   * Returns the number of Instances 
 
162
   * in the rectangular region defined 
 
163
   * by this node.
 
164
   * @return The number of instances in
 
165
   * this KDTreeNode.
 
166
   */
 
167
  public int numInstances() {
 
168
    return (m_End-m_Start+1);
 
169
  }
 
170
}