Anonymous user
Algebraic data types: Difference between revisions
Added a Java (JDK 21 + Preview features) translation for the existing Kotlin solution. Removed the omission tag for Java.
(→{{header|TXR}}: New section.) |
imported>Maruseron (Added a Java (JDK 21 + Preview features) translation for the existing Kotlin solution. Removed the omission tag for Java.) |
||
| (2 intermediate revisions by 2 users not shown) | |||
Line 978:
Finally a caution: red black trees exhibit poor cache coherency. In many (perhaps most or all) cases an amortized hierarchical linear sort mechanism will perform better than a red black tree implementation. (And that characteristic is especially true of this particular implementation.)
{{trans|Kotlin}}
{{works with|OpenJDK|21 (Preview)}}
Java 21 has added support for ADTs (in the form of sealed types), which are narrowable through a switch expression. Despite having no fully-fledged pattern matching, a combination of record deconstruction patterns and guarded patterns allows for something very similar through switch expressions:
<syntaxhighlight lang="java">public class Task {
enum Color { R, B }
sealed interface Tree<A extends Comparable<A>> permits E, T {
default Tree<A> insert(A a) {
return switch(ins(a)) {
case T(_, var l, var v, var r) -> new T<>(Color.B, l, v, r);
case E() -> new E<>();
};
}
Tree<A> ins(A a);
}
record E<A extends Comparable<A>>() implements Tree<A> {
@Override
public Tree<A> ins(A a) {
return new T<>(Color.R, new E<>(), a, new E<>());
}
@Override
public String toString() { return "E"; }
}
record T<A extends Comparable<A>>(Color color, Tree<A> left,
A value, Tree<A> right) implements Tree<A> {
@Override
public Tree<A> ins(A a) {
return switch(Integer.valueOf(a.compareTo(value))) {
case Integer i when i < 0 -> new T<>(color, left.ins(a), value, right).balance();
case Integer i when i > 0 -> new T<>(color, left, value, right.ins(a)).balance();
default -> this;
};
}
private Tree<A> balance() {
if (color == Color.R) return this;
return switch (this) {
// unnamed patterns (case T<A>(_, ...)) are a JDK21 Preview feature
case T<A>(_, T<A>(_, T<A>(_, var a, var x, var b), var y, var c), var z, var d)
when left instanceof T<A> le && le.left instanceof T<A> le_le &&
le.color == Color.R && le_le.color == Color.R ->
new T<>(Color.R, new T<>(Color.B, a, x, b), y, new T<>(Color.B, c, z, d));
case T<A>(_, T<A>(_, var a, var x, T<A>(_, var b, var y, var c)), var z, var d)
when left instanceof T<A> le && le.right instanceof T<A> le_ri &&
le.color == Color.R && le_ri.color == Color.R ->
new T<>(Color.R, new T<>(Color.B, a, x, b), y, new T<>(Color.B, c, z, d));
case T<A>(_, var a, var x, T<A>(_, T<A>(_, var b, var y, var c), var z, var d))
when right instanceof T<A> ri && ri.left instanceof T<A> ri_le &&
ri.color == Color.R && ri_le.color == Color.R ->
new T<>(Color.R, new T<>(Color.B, a, x, b), y, new T<>(Color.B, c, z, d));
case T<A>(_, var a, var x, T<A>(_, var b, var y, T<A>(_, var c, var z, var d)))
when right instanceof T<A> ri && ri.right instanceof T<A> ri_ri &&
ri.color == Color.R && ri_ri.color == Color.R ->
new T<>(Color.R, new T<>(Color.B, a, x, b), y, new T<>(Color.B, c, z, d));
default -> this;
};
}
@Override
public String toString() {
return STR."T[\{color}, \{left}, \{value}, \{right}]"; // String templates are a JDK 21 Preview feature
}
}
public static void main(String[] args) {
Tree<Integer> tree = new E<>();
for (var i : IntStream.rangeClosed(1, 16).toArray()) {
tree = tree.insert(i);
}
System.out.println(tree);
}
}
</syntaxhighlight>
{{out}}
<pre>
T[B, T[B, T[B, T[B, E, 1, E], 2, T[B, E, 3, E]], 4, T[B, T[B, E, 5, E], 6, T[B, E, 7, E]]], 8, T[B, T[B, T[B, E, 9, E], 10, T[B, E, 11, E]], 12, T[B, T[B, E, 13, E], 14, T[B, E, 15, T[R, E, 16, E]]]]]
</pre>
=={{header|jq}}==
Line 2,382 ⟶ 2,466:
end balance
templates ins&{into:}
when <?($into <´node´ ={}>)> do { colour: 'red', left: {}, value: $, right: {}} !
when <..$into.value::raw> do { $into..., left: $ -> ins&{into: $into.left}} -> balance !
otherwise { $into..., right: $ -> ins&{into: $into.right}} -> balance !
Line 2,608 ⟶ 2,692:
{{trans|Go}}
Wren doesn't have either algebraic data types or pattern matching though, despite that, the ''T.balance()'' method looks better than I thought it would :)
<syntaxhighlight lang="
var B = "B"
Line 2,701 ⟶ 2,785:
{{omit from|BBC BASIC}}
{{omit from|C}}
▲{{omit from|Java}}
{{omit from|Pascal}}
{{omit from|Processing}}
| |||