001/* 002 * Java Genetic Algorithm Library (jenetics-7.1.0). 003 * Copyright (c) 2007-2022 Franz Wilhelmstötter 004 * 005 * Licensed under the Apache License, Version 2.0 (the "License"); 006 * you may not use this file except in compliance with the License. 007 * You may obtain a copy of the License at 008 * 009 * http://www.apache.org/licenses/LICENSE-2.0 010 * 011 * Unless required by applicable law or agreed to in writing, software 012 * distributed under the License is distributed on an "AS IS" BASIS, 013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 014 * See the License for the specific language governing permissions and 015 * limitations under the License. 016 * 017 * Author: 018 * Franz Wilhelmstötter (franz.wilhelmstoetter@gmail.com) 019 */ 020package io.jenetics.prog.op; 021 022import static java.lang.String.format; 023import static java.util.Objects.requireNonNull; 024import static io.jenetics.internal.util.Hashes.hash; 025 026import java.io.Serial; 027import java.io.Serializable; 028import java.util.Objects; 029import java.util.function.BiFunction; 030import java.util.random.RandomGenerator; 031 032import io.jenetics.util.ISeq; 033import io.jenetics.util.RandomRegistry; 034 035import io.jenetics.ext.util.FlatTree; 036import io.jenetics.ext.util.Tree; 037import io.jenetics.ext.util.TreeNode; 038 039/** 040 * This class composes a given operation tree to a new operation. which can 041 * serve as a sub <em>program</em> in another operation tree. 042 * 043 * @param <T> the argument type of the operation 044 * 045 * @author <a href="mailto:franz.wilhelmstoetter@gmail.com">Franz Wilhelmstötter</a> 046 * @version 4.1 047 * @since 3.9 048 */ 049public class Program<T> implements Op<T>, Serializable { 050 051 @Serial 052 private static final long serialVersionUID = 1L; 053 054 private final String _name; 055 private final Tree<? extends Op<T>, ?> _tree; 056 057 /** 058 * Create a new program with the given name and the given operation tree. 059 * The arity of the program is calculated from the given operation tree and 060 * set to the maximal arity of the operations of the tree. 061 * 062 * @param name the program name 063 * @param tree the operation tree 064 * @throws NullPointerException if one of the given arguments is {@code null} 065 * @throws IllegalArgumentException if the given operation tree is invalid, 066 * which means there is at least one node where the operation arity 067 * and the node child count differ. 068 */ 069 public Program(final String name, final Tree<? extends Op<T>, ?> tree) { 070 _name = requireNonNull(name); 071 _tree = requireNonNull(tree); 072 check(tree); 073 } 074 075 @Override 076 public String name() { 077 return _name; 078 } 079 080 @Override 081 public int arity() { 082 return 0; 083 } 084 085 /** 086 * Return the underlying expression tree. 087 * 088 * @since 4.1 089 * 090 * @return the underlying expression tree 091 */ 092 public Tree<Op<T>, ?> tree() { 093 return TreeNode.ofTree(_tree); 094 } 095 096 @Override 097 public T apply(final T[] args) { 098 if (args.length < arity()) { 099 throw new IllegalArgumentException(format( 100 "Arguments length is smaller than program arity: %d < %d", 101 args.length, arity() 102 )); 103 } 104 105 return eval(_tree, args); 106 } 107 108 /** 109 * Convenient method, which lets you apply the program function without 110 * explicitly create a wrapper array. 111 * 112 * @see #apply(Object[]) 113 * 114 * @param args the function arguments 115 * @return the evaluated value 116 * @throws NullPointerException if the given variable array is {@code null} 117 * @throws IllegalArgumentException if the length of the arguments array 118 * is smaller than the program arity 119 */ 120 @SafeVarargs 121 public final T eval(final T... args) { 122 return apply(args); 123 } 124 125 @Override 126 public int hashCode() { 127 return hash(_name, hash(_tree)); 128 } 129 130 @Override 131 public boolean equals(final Object obj) { 132 return obj == this || 133 obj instanceof Program<?> other && 134 Objects.equals(other._name, _name) && 135 Objects.equals(other._tree, _tree); 136 } 137 138 @Override 139 public String toString() { 140 return _name; 141 } 142 143 144 /* ************************************************************************* 145 * Static helper methods. 146 * ************************************************************************/ 147 148 /** 149 * Evaluates the given operation tree with the given variables. This method 150 * is equivalent to 151 * <pre>{@code 152 * final T result = tree.reduce(variables, Op::apply); 153 * }</pre> 154 * but handles the variable sized {@code variables} array more conveniently. 155 * 156 * @see Tree#reduce(Object[], BiFunction) 157 * 158 * @param <T> the argument type 159 * @param tree the operation tree 160 * @param variables the input variables 161 * @return the result of the operation tree evaluation 162 * @throws NullPointerException if one of the arguments is {@code null} 163 * @throws IllegalArgumentException if the length of the variable array 164 * is smaller than the program arity 165 */ 166 @SafeVarargs 167 public static <T> T eval( 168 final Tree<? extends Op<T>, ?> tree, 169 final T... variables 170 ) { 171 return tree.reduce(variables, Op::apply); 172 } 173 174 /** 175 * Validates the given program tree. 176 * 177 * @param program the program to validate 178 * @throws NullPointerException if the given {@code program} is {@code null} 179 * @throws IllegalArgumentException if the given operation tree is invalid, 180 * which means there is at least one node where the operation arity 181 * and the node child count differ. 182 */ 183 public static void check(final Tree<? extends Op<?>, ?> program) { 184 program.forEach(Program::checkArity); 185 } 186 187 private static void checkArity(final Tree<? extends Op<?>, ?> node) { 188 if (node.value() != null && 189 node.value().arity() != node.childCount()) 190 { 191 throw new IllegalArgumentException(format( 192 "Op arity != child count: %d != %d", 193 node.value().arity(), node.childCount() 194 )); 195 } 196 } 197 198 /** 199 * Create a new, random program from the given (non) terminal operations 200 * with the desired depth. The created program tree is a <em>full</em> tree. 201 * 202 * @since 4.1 203 * 204 * @param name the program name 205 * @param depth the desired depth of the program tree 206 * @param operations the list of <em>non</em>-terminal operations 207 * @param terminals the list of terminal operations 208 * @param <A> the operational type 209 * @return a new program 210 * @throws NullPointerException if one of the given operations is 211 * {@code null} 212 * @throws IllegalArgumentException if the given tree depth is smaller than 213 * zero 214 */ 215 public static <A> Program<A> of( 216 final String name, 217 final int depth, 218 final ISeq<? extends Op<A>> operations, 219 final ISeq<? extends Op<A>> terminals 220 ) { 221 return new Program<>(name, of(depth, operations, terminals)); 222 } 223 224 /** 225 * Create a new, random program from the given (non) terminal operations 226 * with the desired depth. The created program tree is a <em>full</em> tree. 227 * 228 * @since 4.1 229 * 230 * @param name the program name 231 * @param depth the desired depth of the program tree 232 * @param operations the list of <em>non</em>-terminal operations 233 * @param terminals the list of terminal operations 234 * @param random the random engine used for creating the program 235 * @param <A> the operational type 236 * @return a new program 237 * @throws NullPointerException if one of the given operations is 238 * {@code null} 239 * @throws IllegalArgumentException if the given tree depth is smaller than 240 * zero 241 */ 242 public static <A> Program<A> of( 243 final String name, 244 final int depth, 245 final ISeq<? extends Op<A>> operations, 246 final ISeq<? extends Op<A>> terminals, 247 final RandomGenerator random 248 ) { 249 return new Program<>(name, of(depth, operations, terminals, random)); 250 } 251 252 /** 253 * Create a new, random program tree from the given (non) terminal 254 * operations with the desired depth. The created program tree is a 255 * <em>full</em> tree. 256 * 257 * @param depth the desired depth of the program tree 258 * @param operations the list of <em>non</em>-terminal operations 259 * @param terminals the list of terminal operations 260 * @param <A> the operational type 261 * @return a new program tree 262 * @throws NullPointerException if one of the given operations is 263 * {@code null} 264 * @throws IllegalArgumentException if the given tree depth is smaller than 265 * zero 266 */ 267 public static <A> TreeNode<Op<A>> of( 268 final int depth, 269 final ISeq<? extends Op<A>> operations, 270 final ISeq<? extends Op<A>> terminals 271 ) { 272 return of(depth, operations, terminals, RandomRegistry.random()); 273 } 274 275 /** 276 * Create a new, random program tree from the given (non) terminal 277 * operations with the desired depth. The created program tree is a 278 * <em>full</em> tree. 279 * 280 * @since 4.1 281 * 282 * @param depth the desired depth of the program tree 283 * @param operations the list of <em>non</em>-terminal operations 284 * @param terminals the list of terminal operations 285 * @param random the random engine used for creating the program 286 * @param <A> the operational type 287 * @return a new program tree 288 * @throws NullPointerException if one of the given operations is 289 * {@code null} 290 * @throws IllegalArgumentException if the given tree depth is smaller than 291 * zero 292 */ 293 public static <A> TreeNode<Op<A>> of( 294 final int depth, 295 final ISeq<? extends Op<A>> operations, 296 final ISeq<? extends Op<A>> terminals, 297 final RandomGenerator random 298 ) { 299 if (depth < 0) { 300 throw new IllegalArgumentException( 301 "Tree depth is smaller than zero: " + depth 302 ); 303 } 304 if (!operations.forAll(o -> !o.isTerminal())) { 305 throw new IllegalArgumentException( 306 "Operation list contains terminal op." 307 ); 308 } 309 if (!terminals.forAll(Op::isTerminal)) { 310 throw new IllegalArgumentException( 311 "Terminal list contains non-terminal op." 312 ); 313 } 314 315 final TreeNode<Op<A>> root = TreeNode.of(); 316 fill(depth, root, operations, terminals, random); 317 return root; 318 } 319 320 private static <A> void fill( 321 final int level, 322 final TreeNode<Op<A>> tree, 323 final ISeq<? extends Op<A>> operations, 324 final ISeq<? extends Op<A>> terminals, 325 final RandomGenerator random 326 ) { 327 final Op<A> op = level == 0 328 ? terminals.get(random.nextInt(terminals.size())) 329 : operations.get(random.nextInt(operations.size())); 330 331 tree.value(op); 332 333 if (level > 1) { 334 for (int i = 0; i < op.arity(); ++i) { 335 final TreeNode<Op<A>> node = TreeNode.of(); 336 fill(level - 1, node, operations, terminals, random); 337 tree.attach(node); 338 } 339 } else { 340 for (int i = 0; i < op.arity(); ++i) { 341 final Op<A> term = terminals.get(random.nextInt(terminals.size())); 342 tree.attach(TreeNode.of(term)); 343 } 344 } 345 } 346 347 /** 348 * Creates a valid program tree from the given flattened sequence of 349 * op nodes. The given {@code operations} and {@code termination} nodes are 350 * used for <em>repairing</em> the program tree, if necessary. 351 * 352 * @param nodes the flattened, possible corrupt, program tree 353 * @param terminals the usable non-terminal operation nodes to use for 354 * reparation 355 * @param <A> the operation argument type 356 * @return a new valid program tree build from the flattened program tree 357 * @throws NullPointerException if one of the arguments is {@code null} 358 * @throws IllegalArgumentException if the {@code nodes} sequence is empty 359 */ 360 public static <A> TreeNode<Op<A>> toTree( 361 final ISeq<? extends FlatTree<? extends Op<A>, ?>> nodes, 362 final ISeq<? extends Op<A>> terminals 363 ) { 364 if (nodes.isEmpty()) { 365 throw new IllegalArgumentException("Tree nodes must not be empty."); 366 } 367 368 final Op<A> op = requireNonNull(nodes.get(0).value()); 369 final TreeNode<Op<A>> tree = TreeNode.of(op); 370 return toTree( 371 tree, 372 0, 373 nodes, 374 offsets(nodes), 375 terminals, 376 RandomRegistry.random() 377 ); 378 } 379 380 private static <A> TreeNode<Op<A>> toTree( 381 final TreeNode<Op<A>> root, 382 final int index, 383 final ISeq<? extends FlatTree<? extends Op<A>, ?>> nodes, 384 final int[] offsets, 385 final ISeq<? extends Op<A>> terminals, 386 final RandomGenerator random 387 ) { 388 if (index < nodes.size()) { 389 final FlatTree<? extends Op<A>, ?> node = nodes.get(index); 390 final Op<A> op = node.value(); 391 392 for (int i = 0; i < op.arity(); ++i) { 393 assert offsets[index] != -1; 394 395 final TreeNode<Op<A>> treeNode = TreeNode.of(); 396 if (offsets[index] + i < nodes.size()) { 397 treeNode.value(nodes.get(offsets[index] + i).value()); 398 } else { 399 treeNode.value(terminals.get(random.nextInt(terminals.size()))); 400 } 401 402 toTree( 403 treeNode, 404 offsets[index] + i, 405 nodes, 406 offsets, 407 terminals, 408 random 409 ); 410 root.attach(treeNode); 411 } 412 } 413 414 return root; 415 } 416 417 /** 418 * Create the offset array for the given nodes. The offsets are calculated 419 * using the arity of the stored operations. 420 * 421 * @param nodes the flattened tree nodes 422 * @return the offset array for the given nodes 423 */ 424 static int[] 425 offsets(final ISeq<? extends FlatTree<? extends Op<?>, ?>> nodes) { 426 final int[] offsets = new int[nodes.size()]; 427 428 int offset = 1; 429 for (int i = 0; i < offsets.length; ++i) { 430 final Op<?> op = nodes.get(i).value(); 431 432 offsets[i] = op.isTerminal() ? -1 : offset; 433 offset += op.arity(); 434 } 435 436 return offsets; 437 } 438 439}