1 package net.bmahe.genetics4j.gp.utils;
2
3 import java.util.Comparator;
4 import java.util.Iterator;
5 import java.util.List;
6
7 import org.apache.commons.lang3.Validate;
8
9 import net.bmahe.genetics4j.core.Genotype;
10 import net.bmahe.genetics4j.core.chromosomes.TreeChromosome;
11 import net.bmahe.genetics4j.core.chromosomes.TreeNode;
12 import net.bmahe.genetics4j.gp.Operation;
13
14 public class TreeNodeUtils {
15
16 private TreeNodeUtils() {
17
18 }
19
20 public static Comparator<TreeNode<Operation<?>>> TREE_NODE_OPERATION_COMPARATOR = new Comparator<>() {
21
22 @Override
23 public int compare(final TreeNode<Operation<?>> o1, final TreeNode<Operation<?>> o2) {
24 return compare(o1, o2);
25 }
26 };
27
28
29
30
31
32
33
34
35
36
37
38 public static <T> int compare(final TreeNode<Operation<T>> rootA, final TreeNode<Operation<T>> rootB) {
39 if (rootA == null && rootB == null) {
40 return 0;
41 }
42
43 if (rootA == null) {
44 return -1;
45 }
46
47 if (rootB == null) {
48 return 1;
49 }
50
51 final Operation<T> dataA = rootA.getData();
52 final Operation<T> dataB = rootB.getData();
53
54 final int opNameCompare = dataA.getName().compareTo(dataB.getName());
55 if (opNameCompare != 0) {
56 return opNameCompare;
57 }
58
59 final int opPrettyNameCompare = dataA.getPrettyName().compareTo(dataB.getPrettyName());
60 if (opPrettyNameCompare != 0) {
61 return opPrettyNameCompare;
62 }
63
64 if (dataA.getArity() < dataB.getArity()) {
65 return -1;
66 }
67
68 if (dataA.getArity() > dataB.getArity()) {
69 return 1;
70 }
71
72 for (int i = 0; i < dataA.getArity(); i++) {
73 final int classCompare = dataA.acceptedTypes()
74 .get(i)
75 .getCanonicalName()
76 .compareTo(dataB.acceptedTypes().get(i).getCanonicalName());
77
78 if (classCompare != 0) {
79 return classCompare;
80 }
81 }
82
83 final int returnClassCompare = dataA.returnedType()
84 .getCanonicalName()
85 .compareTo(dataB.returnedType().getCanonicalName());
86
87 if (returnClassCompare != 0) {
88 return returnClassCompare;
89 }
90
91 final var childrenA = rootA.getChildren();
92 final var childrenB = rootB.getChildren();
93
94 if (childrenA.size() < childrenB.size()) {
95 return -1;
96 }
97
98 if (childrenA.size() > childrenB.size()) {
99 return 1;
100 }
101
102 for (int i = 0; i < childrenA.size(); i++) {
103 final TreeNode<Operation<T>> childA = childrenA.get(i);
104 final TreeNode<Operation<T>> childB = childrenB.get(i);
105
106 final int childCompare = compare(childA, childB);
107 if (childCompare != 0) {
108 return childCompare;
109 }
110 }
111
112 return 0;
113 }
114
115 public static <T> int compare(final Genotype genotypeA, final Genotype genotypeB, final int chromosomeIndex) {
116 Validate.notNull(genotypeA);
117 Validate.notNull(genotypeB);
118 Validate.isTrue(chromosomeIndex >= 0);
119 Validate.isTrue(chromosomeIndex < genotypeA.getSize());
120 Validate.isTrue(chromosomeIndex < genotypeB.getSize());
121
122 @SuppressWarnings("unchecked")
123 final var chromosomeA = (TreeChromosome<Operation<T>>) genotypeA.getChromosome(chromosomeIndex);
124 final TreeNode<Operation<T>> rootNodeA = chromosomeA.getRoot();
125
126 @SuppressWarnings("unchecked")
127 final var chromosomeB = (TreeChromosome<Operation<T>>) genotypeB.getChromosome(chromosomeIndex);
128 final TreeNode<Operation<T>> rootNodeB = chromosomeB.getRoot();
129
130 return compare(rootNodeA, rootNodeB);
131 }
132
133 public static <T> boolean areSame(final TreeNode<T> rootA, final TreeNode<T> rootB) {
134 if (rootA == null && rootB == null) {
135 return true;
136 }
137
138 if (rootA == null || rootB == null) {
139 return false;
140 }
141
142 final T dataA = rootA.getData();
143 final T dataB = rootB.getData();
144
145 if (dataA.equals(dataB) == false) {
146 return false;
147 }
148
149 final List<TreeNode<T>> childrenA = rootA.getChildren();
150 final List<TreeNode<T>> childrenB = rootB.getChildren();
151
152 if (childrenA.size() != childrenB.size()) {
153 return false;
154 }
155
156 boolean isSame = true;
157 for (int i = 0; i < childrenA.size() && isSame == true; i++) {
158
159 final TreeNode<T> childA = childrenA.get(i);
160 final TreeNode<T> childB = childrenB.get(i);
161
162 isSame = areSame(childA, childB);
163 }
164
165 return isSame;
166 }
167
168 public static <T> boolean areSame(final Genotype genotypeA, final Genotype genotypeB, final int chromosomeIndex) {
169 Validate.notNull(genotypeA);
170 Validate.notNull(genotypeB);
171 Validate.isTrue(chromosomeIndex >= 0);
172 Validate.isTrue(chromosomeIndex < genotypeA.getSize());
173 Validate.isTrue(chromosomeIndex < genotypeB.getSize());
174
175 @SuppressWarnings("unchecked")
176 final var chromosomeA = (TreeChromosome<T>) genotypeA.getChromosome(chromosomeIndex);
177 final TreeNode<T> rootNodeA = chromosomeA.getRoot();
178
179 @SuppressWarnings("unchecked")
180 final var chromosomeB = (TreeChromosome<T>) genotypeB.getChromosome(chromosomeIndex);
181 final TreeNode<T> rootNodeB = chromosomeB.getRoot();
182
183 return areSame(rootNodeA, rootNodeB);
184 }
185
186 public static String toStringTreeNode(final TreeNode<Operation<?>> node) {
187 Validate.notNull(node);
188
189 final Operation<?> operation = node.getData();
190 final List<TreeNode<Operation<?>>> children = node.getChildren();
191
192 final StringBuilder stringBuilder = new StringBuilder();
193
194 stringBuilder.append(operation.getPrettyName());
195 if (children != null && children.isEmpty() == false) {
196 stringBuilder.append("(");
197
198 final Iterator<TreeNode<Operation<?>>> iterator = children.iterator();
199 while (iterator.hasNext()) {
200 final TreeNode<Operation<?>> treeNode = iterator.next();
201
202 stringBuilder.append(toStringTreeNode(treeNode));
203
204 if (iterator.hasNext()) {
205 stringBuilder.append(", ");
206 }
207 }
208
209 stringBuilder.append(")");
210 }
211 return stringBuilder.toString();
212 }
213
214 public static String toStringTreeNode(final Genotype genotype, final int chromosomeIndex) {
215 Validate.notNull(genotype);
216 Validate.isTrue(chromosomeIndex >= 0);
217 Validate.isTrue(chromosomeIndex < genotype.getSize());
218
219 @SuppressWarnings("unchecked")
220 final var chromosome = (TreeChromosome<Operation<?>>) genotype.getChromosome(chromosomeIndex);
221 final TreeNode<Operation<?>> rootNode = chromosome.getRoot();
222
223 return TreeNodeUtils.toStringTreeNode(rootNode);
224 }
225 }