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