001 package org.jaga.individualRepresentation.booleanFormulas;
002
003 import org.jaga.reproduction.booleanFormulas.nodes.*;
004 import java.util.HashMap;
005 import java.util.Iterator;
006 import org.jaga.definitions.*;
007
008 /**
009 * TODO: Complete these comments.
010 *
011 * <p><u>Project:</u> JAGA - Java API for Genetic Algorithms.</p>
012 *
013 * <p><u>Company:</u> University College London and JAGA.Org
014 * (<a href="http://www.jaga.org" target="_blank">http://www.jaga.org</a>).
015 * </p>
016 *
017 * <p><u>Copyright:</u> (c) 2004 by G. Paperin.<br/>
018 * This program is free software; you can redistribute it and/or modify
019 * it under the terms of the GNU General Public License as published by
020 * the Free Software Foundation, ONLY if you include a note of the original
021 * author(s) in any redistributed/modified copy.<br/>
022 * This program is distributed in the hope that it will be useful,
023 * but WITHOUT ANY WARRANTY; without even the implied warranty of
024 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
025 * GNU General Public License for more details.<br/>
026 * You should have received a copy of the GNU General Public License
027 * along with this program; if not, write to the Free Software
028 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
029 * or see http://www.gnu.org/licenses/gpl.html</p>
030 *
031 * @author Greg Paperin (greg@jaga.org)
032 *
033 * @version JAGA public release 1.0 beta
034 */
035
036 public class BooleanFormulaTree implements Individual {
037
038 // remember the max-depth constrain
039
040 private int numberOfParameters = 0;
041 private Fitness fitness = null;
042 private HashMap nodes = new HashMap();
043 private BooleanFormulaTreeNode root = null;
044 private long nextHandleToGenerate = -Long.MIN_VALUE;
045
046
047 private BooleanFormulaTree() {
048 throw new java.lang.UnsupportedOperationException("Use the other constructor");
049 }
050
051 public BooleanFormulaTree(int numberOfParameters) {
052 this.numberOfParameters = numberOfParameters;
053 root = new FalseNode();
054 addToNodeList(root, 0);
055 }
056
057 private Long generateNewHandle() {
058 if (Long.MAX_VALUE == nextHandleToGenerate)
059 throw new RuntimeException("nextHandleToGenerate="
060 + nextHandleToGenerate + ", which is too big; "
061 + " In this version, a formula tree cannot "
062 + "generate that much handles");
063 Long handle = new Long(nextHandleToGenerate++);
064 if (0 == nextHandleToGenerate)
065 nextHandleToGenerate = 1;
066 return handle;
067 }
068
069 public Fitness getFitness() {
070 return this.fitness;
071 }
072
073 public void setFitness(Fitness fitness) {
074 this.fitness = fitness;
075 }
076
077 public int getNumberOfParameters() {
078 return this.numberOfParameters;
079 }
080
081 public Long selectRootNode() {
082 return root.getHandle();
083 }
084
085 public int getNodeCount() {
086 return this.nodes.size();
087 }
088
089 public Long selectRandomNode(GAParameterSet params) {
090 int nodeCount = getNodeCount();
091 if (0 == nodeCount)
092 return new Long(0);
093 int rndNum = params.getRandomGenerator().nextInt(0, nodeCount);
094 Iterator key = getHandlersIterator();
095 Object keyVal = key.next();
096 int i = 0;
097 while (i++ < rndNum)
098 keyVal = key.next();
099 return (Long) keyVal;
100 }
101
102 public Iterator getHandlersIterator() {
103 return nodes.keySet().iterator();
104 }
105
106 public BooleanFormulaTreeNode exportNode(Long handle) {
107 BooleanFormulaTreeNode node = getNode(handle);
108 BooleanFormulaTreeNode clone = (BooleanFormulaTreeNode) node.clone();
109 return clone;
110 }
111
112 public int getNodeDepth(Long handle) {
113 BooleanFormulaTreeNode node = getNode(handle);
114 return node.getDepth();
115 }
116
117 public int getNodeHeight(Long handle) {
118 BooleanFormulaTreeNode node = getNode(handle);
119 return node.getHeight();
120 }
121
122 private BooleanFormulaTreeNode getNode(Long handle) {
123 if (0 == handle.longValue())
124 throw new IllegalArgumentException("The handle 0 is illegal");
125 BooleanFormulaTreeNode node = (BooleanFormulaTreeNode) nodes.get(handle);
126 assert null != node : "Must be an invalid handle (" + handle.longValue() + ")";
127 return node;
128 }
129
130 public void replaceNode(Long oldNodeHandle, BooleanFormulaTreeNode newNode) {
131
132 if (null == newNode)
133 throw new NullPointerException("Cannot replace a node by a null-pointer");
134
135 BooleanFormulaTreeNode toReplace = getNode(oldNodeHandle);
136
137 if (root == toReplace) { // if we are replacing the root:
138 nodes.clear();
139 root = newNode;
140 addToNodeList(newNode, 0);
141 root.recalcHeight();
142
143 } else { // any other node:
144 removeFromNodeList(toReplace);
145 OperatorNode parent = toReplace.getParent();
146 assert null != parent : "Node has no parent!";
147 int chInd = parent.findChild(toReplace);
148 assert chInd >= 0 : "Need debug !!!!";
149 parent.setChild(chInd, newNode);
150 addToNodeList(newNode, parent.getDepth() + 1);
151 parent.recalcHeight();
152 }
153 }
154
155 public boolean evaluate(boolean [] parameters) {
156 return root.evaluate(parameters);
157 }
158
159 /*
160 public boolean isIndividualValid(IndividualConstraint[] constraints) {
161 for (int i = 0; i < constraints.length; i++) {
162 if (!constraints[i].getApplicableClass().isInstance(this))
163 throw new IllegalArgumentException("Constraint number " + i
164 + " can only be applied to "
165 + constraints[i].getApplicableClass().getName()
166 + " and does not support this class ("
167 + this.getClass().getName() + ")");
168 if (!constraints[i].isIndividualLegal(this))
169 return false;
170 }
171 return true;
172 }
173 */
174
175 public String toString() {
176 return toString(true);
177 }
178
179 public String toString(boolean infix) {
180 StringBuffer s = new StringBuffer("{formula=[");
181 s.append(root.toStringBuffer(infix));
182 s.append("], ");
183 if (null == fitness) {
184 s.append("fitness not known}");
185 } else {
186 s.append("fitness=");
187 s.append(fitness.toString());
188 s.append("}");
189 }
190 return s.toString();
191 }
192
193 private void removeFromNodeList(BooleanFormulaTreeNode node) {
194 Long key = node.getHandle();
195 nodes.remove(key);
196 if (node instanceof OperatorNode) {
197 OperatorNode parent = (OperatorNode) node;
198 for (int i = 0; i < parent.getRequiredChildrenNumber(); i++) {
199 BooleanFormulaTreeNode kid = parent.getChild(i);
200 if (null != kid)
201 removeFromNodeList(kid);
202 }
203 }
204 node.setHandle(new Long(0));
205 }
206
207 private void addToNodeList(BooleanFormulaTreeNode node, int depth) {
208
209 Long handle = null;
210
211 node.setDepth(depth);
212 handle = generateNewHandle();
213 nodes.put(handle, node);
214 node.setHandle(handle);
215
216 if (node instanceof OperatorNode) {
217 OperatorNode parent = (OperatorNode) node;
218 for (int i = 0; i < parent.getRequiredChildrenNumber(); i++) {
219 BooleanFormulaTreeNode kid = parent.getChild(i);
220 if (null != kid)
221 addToNodeList(kid, depth + 1);
222 }
223 }
224 }
225
226 }