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