XieJiann commented on code in PR #29644:
URL: https://github.com/apache/doris/pull/29644#discussion_r1444479365
##########
fe/fe-core/src/main/java/org/apache/doris/nereids/util/ImmutableEqualSet.java:
##########
@@ -17,64 +17,73 @@
package org.apache.doris.nereids.util;
+import com.google.common.collect.ImmutableList;
import com.google.common.collect.ImmutableMap;
import com.google.common.collect.ImmutableSet;
import java.util.HashMap;
+import java.util.List;
import java.util.Map;
import java.util.Set;
/**
- * EquivalenceSet
+ * A class representing an immutable set of elements with equivalence
relations.
*/
-public class ImmutableEquivalenceSet<T> {
- final Map<T, T> root;
+public class ImmutableEqualSet<T> {
+ private final Map<T, T> root;
- ImmutableEquivalenceSet(Map<T, T> root) {
+ ImmutableEqualSet(Map<T, T> root) {
this.root = ImmutableMap.copyOf(root);
}
- public static <T> ImmutableEquivalenceSet<T> of() {
- return new ImmutableEquivalenceSet<>(ImmutableMap.of());
+ public static <T> ImmutableEqualSet<T> empty() {
+ return new ImmutableEqualSet<>(ImmutableMap.of());
}
/**
- * Builder of ImmutableEquivalenceSet
+ * Builder for ImmutableEqualSet.
*/
public static class Builder<T> {
- final Map<T, T> parent = new HashMap<>();
+ private final Map<T, T> parent = new HashMap<>();
+ private final Map<T, Integer> size = new HashMap<>();
+ /**
+ * Add a equal pair
+ */
public void addEqualPair(T a, T b) {
- parent.computeIfAbsent(b, v -> v);
- parent.computeIfAbsent(a, v -> v);
- union(a, b);
- }
-
- private void union(T a, T b) {
T root1 = findRoot(a);
T root2 = findRoot(b);
if (root1 != root2) {
- parent.put(b, root1);
- findRoot(b);
+ // merge by size
+ if (size.get(root1) < size.get(root2)) {
+ parent.put(root1, root2);
+ size.put(root2, size.get(root2) + size.get(root1));
+ } else {
+ parent.put(root2, root1);
+ size.put(root1, size.get(root1) + size.get(root2));
+ }
Review Comment:
The size is not necessary. Because we always fold all equal set when
building
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
