Stalin sort seems to be popular, so I will write it in Java. The stream API introduced from Java 8 is already familiar, isn't it? This time, we will create an implementation class of the Collector interface that the Collect method receives so that stream can perform a cool Stalin sort.
/**
*Collector implementation class that implements Stalin sort
*/
public final class StalinSortCollector {
private StalinSortCollector() {}
/**
*Returns a Collector that Stalin sorts the input elements in natural order and converts the result to a Stream.
* @param <T>Input element type
*/
public static <T extends Comparable<? super T>> Collector<T, List<T>, Stream<T>> sorting(){
return new StalinSortCollectorImplements<T, T>(Comparator.naturalOrder(), x -> x);
}
/**
*Returns a Collector that Stalin sorts the input elements in reverse natural order and converts the result to a Stream.
* @param <T>Input element type
*/
public static <T extends Comparable<? super T>> Collector<T, List<T>, Stream<T>> reverseSorting(){
return new StalinSortCollectorImplements<T, T>(Comparator.reverseOrder(), x -> x);
}
/**
*Returns a Collector that Stalin sorts the input elements in the natural order of the values converted by the mapper function and converts the result to a Stream.
* @param mapper Function to convert input elements
* @param <T>Input element type
* @param <A>Type to compare input elements
*/
public static <T, A extends Comparable<? super A>> Collector<T, List<T>, Stream<T>> sortingBy(Function<? super T, ? extends A> mapper){
return new StalinSortCollectorImplements<T, A>(Comparator.naturalOrder(), mapper);
}
/**
*Returns a Collector that Stalin sorts the input elements in the reverse order of the natural order of the values converted by the mapper function and converts the result to a Stream.
* @param mapper Function to convert input elements
* @param <T>Input element type
* @param <A>Type to compare input elements
*/
public static <T, A extends Comparable<? super A>> Collector<T, List<T>, Stream<T>> reverseSortingBy(Function<? super T, ? extends A> mapper){
return new StalinSortCollectorImplements<T, A>(Comparator.reverseOrder(), mapper);
}
/**
*Returns a Collector that Stalin sorts the input elements in the order they are compared by the comparator and converts the result to a Stream.
* @param comparator Comparator for comparing elements
* @param <T>Input element type
*/
public static <T> Collector<T, List<T>, Stream<T>> sorting(Comparator<? super T> comparator){
return new StalinSortCollectorImplements<T, T>(comparator, x -> x);
}
/**
*Returns a Collector that Stalin sorts the input elements converted by the mapper function in the order in which they are compared by the comparator and converts the result to Stream.
* @param mapper Function to convert input elements
* @param comparator Comparator for comparing elements
* @param <T>Input element type
* @param <A>Type to compare input elements
*/
public static <T, A> Collector<T, List<T>, Stream<T>> sortingBy(Function<? super T, ? extends A> mapper, Comparator<? super A> comparator){
return new StalinSortCollectorImplements<T, A>(comparator, mapper);
}
private static class StalinSortCollectorImplements<T, A> implements Collector<T, List<T>, Stream<T>> {
private final Comparator<? super A> comparator;
private final Function<? super T, ? extends A> mapper;
private StalinSortCollectorImplements(Comparator<? super A> comparator, Function<? super T, ? extends A> mapper) {
this.comparator = comparator;
this.mapper = mapper;
}
@Override
public Supplier<List<T>> supplier() {
return ArrayList::new;
}
@Override
public BiConsumer<List<T>, T> accumulator() {
return (list, element) -> {
if(list.isEmpty() || this.comparator.compare(this.mapper.apply(element), this.mapper.apply(list.get(list.size() -1))) >= 0) {
list.add(element);
}
};
}
@Override
public BinaryOperator<List<T>> combiner() {
return (x, y) -> Stream.concat(x.stream(), y.stream().dropWhile(p -> this.comparator.compare(this.mapper.apply(p), this.mapper.apply(x.get(x.size() -1))) < 0)).collect(Collectors.toList());
}
@Override
public Function<List<T>, Stream<T>> finisher() {
return List::stream;
}
@Override
public Set<Characteristics> characteristics() {
return EnumSet.of(Characteristics.CONCURRENT);
}
}
}
Collectors With reference to the class, StalinSortCollector has only static methods that return Collectors. I'm letting you. It is the StalinSortCollectorImplements class that actually implements Stalin sorting.
Collector The interface indicates the collection method by passing it to the collect method of Stream. .. It has 3 type parameters, 5 methods and 2 staic methods (not relevant as it is not implemented).
As an example, if it is a Collector that appends a collection of ints to a StringBuilder and finally returns it as a String, it will be \ <Integer, StringBuilder, String>.
This time, StalinSortCollectorImplements adds T type element to List \
Supplier<A> supplier()
The following is a description of the methods to be implemented.
The supplier returns a Supplier that creates an instance that accumulates the results on the way.
Speaking of for statements, it is what you want to do with for ([here] ;;) (for initialization formula).
Note that the intermediate result uses the instance created by this, so it is not possible to return an empty string and do something like string concatenation. (Because combining strings returns a new instance)
Here we are returning ArrayList :: new.
BiConsumer<A, T> accumulator()
The accumulator takes a T-type input element and returns a BiConsumer that accumulates intermediate results in an A-type instance.
Speaking of for statements, it is what you want to do with for (;;) [here] (the body of for).
Here, it is added to the List when the List that stores the intermediate results is empty or when "input element> = last element of the List". (Conversely, when "input element <last element of List", ** purge **.)
BinaryOperator<A> combiner()
combiner returns a BinaryOperator that combines instances of type A that have accumulated intermediate results. Since Stream may be executed in parallel, it is necessary to concatenate the results produced when executed in parallel with this combiner function. Here, the elements of the List on the concatenated side are discarded (** purged **) until they are equal to or greater than the last element on the concatenated side. Note that dropWhile can only be used with Java 9 or later.
Function<A, R> finisher()
finisher returns the Function of the finishing process for the A type instance that has accumulated all the results. Here, the Stalin-sorted List is returned as a Stream. This allows collect to continue the method chain even though it is a termination operation.
Set
characteristics returns a Set of Collector.Characteristics that indicates the attributes of this Collector. There are three types: CONCURRENT (can be executed in parallel), UNORDERED (no order), and IDENTITY_FINISH (finisher can be omitted). Here, only CONCURRENT is returned because the finisher has some processing and the order is an important sort.
public class Soviet {
public static void main(String... args) {
Stream.of(1,2,2,4,3,5,3,5,7,1,1,9)
.collect(StalinSortCollector.sorting())
.forEach(System.out::println);
}
}
1
2
2
4
5
5
7
9
public class Russia {
public static void main(String... args) {
Stream.of(12,2,23,499,325,51,334,55555,7898,1019,19,12345)
.parallel()
.collect(StalinSortCollector.sortingBy(x -> String.valueOf(x).length()))
.forEach(System.out::println);
}
}
12
23
499
325
334
55555
12345
After all it feels good to be able to process with stream.
Recommended Posts