ConcurrentEntryMergeSorter

package saker.build.thirdparty.saker.util

public final class ConcurrentEntryMergeSorter<K, V>

saker.build.thirdparty.saker.util.ConcurrentEntryMergeSorter<K, V>

java.lang.Object

Class for concurrently collecting sorted Map.Entry iterables and then later merge-sorting them.

This class provides functionality for concurrently accumulating iterables of map entries, and the later efficiently sorting them or iterating over them via merge-sort. The concurrent nature of the class comes from the fact that iterables can be added to it without requiring synchronization between threads.

Important: Any added entry iterable must be already stricly ordered by the comparator that is going to be used for merge-sorting. Violating this requirement will result in incorrect operationg of the merge-sorted results.

Generally, an instance of this class is used in the following way:

A new instance is created.
Some arbitrary work is done by the caller, which results in one or more map entries that need to be sorted.
Sorted iterables are added to the sorter instance, this can happen concurrently by multiple threads.
The user decides to collect the entries, which is done by merge-sorting the previously collected sorted iterables and putting them into an appropriate collection, or iterator.
The created collection/iterator can be used by the caller.

During a merge-sort, multiple values can be mapped to the same keys. To resolve this ambiguity, users can supply a MatchingKeyPolicy for the merge-sort to decide which value to keep for the given key.

Using this class instead of directly putting the entries into a result collection can be more efficient, as the sorting can be done with fewer comparisons. However, in order for this class to work, the added iterables must be already sorted. If you're unsure whether the iterables that you're using with this class, don't use this, and fall back to some other solution, as the sorting algorithm in this class will break if unsorted iterables are added to it.

The iterables are to be added with their estimated sizes provided. With this size, the sorter can allocate a result storage for the sorted collections more efficiently, that can result in fewer reallocations. These sizes are estimates, clients are not required to provide actually correct values, but they are strongly encouraged to do so.

KThe key type.

VThe value type.

Nested types

public enum	MatchingKeyPolicy Enumeration for specifying which value should be kept if there are multiple conflicting keys.

Constructors

public	ConcurrentEntryMergeSorter() Creates a new empty instance.

Methods

public void	add(Iterable<? extends Entry<? extends K, ? extends V>> entries, int size) Adds an iterable of entries with the estimated size to the sorter.
public void	add(Collection<? extends Entry<? extends K, ? extends V>> entries) Adds a collection of entries to the sorter.
public void	add(Map<? extends K, ? extends V> map) Adds the entries of a map to the sorter.
public void	add(Map<? extends K, ? extends V> map, int size) Adds the entries of a map with the estimated size to the sorter.
public ConcurrentSkipListMap<K, V>	createConcurrentSkipListMap() Executes the sorting for the currently added iterables and creates a new ConcurrentSkipListMap.
public ConcurrentSkipListMap<K, V>	createConcurrentSkipListMap(Comparator<? super K> comparator) Executes the sorting for the currently added iterables and creates a new ConcurrentSkipListMap.
public ConcurrentSkipListMap<K, V>	createConcurrentSkipListMap(MatchingKeyPolicy matchingPolicy) Executes the sorting for the currently added iterables and creates a new ConcurrentSkipListMap.
public ConcurrentSkipListMap<K, V>	createConcurrentSkipListMap(MatchingKeyPolicy matchingPolicy, Comparator<? super K> comparator) Executes the sorting for the currently added iterables and creates a new ConcurrentSkipListMap.
public NavigableMap<K, V>	createImmutableNavigableMap() Executes the sorting for the currently added iterables and creates a new immutable navigable map.
public NavigableMap<K, V>	createImmutableNavigableMap(Comparator<? super K> comparator) Executes the sorting for the currently added iterables and creates a new immutable navigable map.
public NavigableMap<K, V>	createImmutableNavigableMap(MatchingKeyPolicy matchingPolicy) Executes the sorting for the currently added iterables and creates a new immutable navigable map.
public NavigableMap<K, V>	createImmutableNavigableMap(MatchingKeyPolicy matchingPolicy, Comparator<? super K> comparator) Executes the sorting for the currently added iterables and creates a new immutable navigable map.
public TreeMap<K, V>	createTreeMap() Executes the sorting for the currently added iterables and creates a new TreeMap.
public TreeMap<K, V>	createTreeMap(Comparator<? super K> comparator) Executes the sorting for the currently added iterables and creates a new TreeMap.
public TreeMap<K, V>	createTreeMap(MatchingKeyPolicy matchingPolicy) Executes the sorting for the currently added iterables and creates a new TreeMap.
public TreeMap<K, V>	createTreeMap(MatchingKeyPolicy matchingPolicy, Comparator<? super K> comparator) Executes the sorting for the currently added iterables and creates a new TreeMap.
public boolean	isAnyIterableAdded() Checks if any iterables was added to this merge sorter.
public Iterator<? extends Entry<? extends K, ? extends V>>	iterator() Executes the sorting for the currently added iterables and returns an iterator for the entries.
public Iterator<? extends Entry<? extends K, ? extends V>>	iterator(Comparator<? super K> comparator) Executes the sorting for the currently added iterables and returns an iterator for the entries.
public Iterator<? extends Entry<? extends K, ? extends V>>	iterator(MatchingKeyPolicy matchingPolicy) Executes the sorting for the currently added iterables and returns an iterator for the entries.
public Iterator<? extends Entry<? extends K, ? extends V>>	iterator(MatchingKeyPolicy matchingPolicy, Comparator<? super K> comparator) Executes the sorting for the currently added iterables and returns an iterator for the entries.

Inherited methods
From: Object clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

public ConcurrentEntryMergeSorter()

Creates a new empty instance.

public void add(Iterable<? extends Entry<? extends K, ? extends V>> entries, int size) throws IllegalArgumentException, NullPointerException

Adds an iterable of entries with the estimated size to the sorter.

The iteration order of the entries must be sorted by the comparator that is going to be used for sorting.

entriesThe iterable of entries.

sizeThe estimated size.

IllegalArgumentExceptionIf the size is negative.

NullPointerExceptionIf the entries iterable is null.

public void add(Collection<? extends Entry<? extends K, ? extends V>> entries) throws NullPointerException

Adds a collection of entries to the sorter.

The estimated size of the iterable will be based on the Collection.size(). If the collection is a concurrent collection, consider calling add(Iterable<? extends Entry<? extends K, ? extends V>>, int) instead.

The iteration order of the entries must be sorted by the comparator that is going to be used for sorting.

entriesThe entries to add.

NullPointerExceptionIf the collection is null.

public void add(Map<? extends K, ? extends V> map) throws NullPointerException

Adds the entries of a map to the sorter.

The estimated size of the iterable will be based on the Map.size(). If the map is a concurrent map, consider calling add(Map<? extends K, ? extends V>, int) instead.

The iteration order of the entries must be sorted by the comparator that is going to be used for sorting.

mapThe map entries to add.

NullPointerExceptionIf the map is null.

public void add(Map<? extends K, ? extends V> map, int size) throws IllegalArgumentException, NullPointerException

Adds the entries of a map with the estimated size to the sorter.

The iteration order of the entries must be sorted by the comparator that is going to be used for sorting.

mapThe map entries to add.

sizeThe estimated size.

IllegalArgumentExceptionIf the size is negative.

NullPointerExceptionIf the entries iterable is null.

public ConcurrentSkipListMap<K, V> createConcurrentSkipListMap()

Executes the sorting for the currently added iterables and creates a new ConcurrentSkipListMap.

Callers must ensure that all previously added iterables are sorted by their natural order.

This is the same as:

 createConcurrentSkipListMap(MatchingKeyPolicy.DONT_CARE, null);

The created map.

public ConcurrentSkipListMap<K, V> createConcurrentSkipListMap(Comparator<? super K> comparator)

Executes the sorting for the currently added iterables and creates a new ConcurrentSkipListMap.

Callers must ensure that all previously added iterables are sorted by the argument comparator.

This is the same as:

 createConcurrentSkipListMap(MatchingKeyPolicy.DONT_CARE, comparator);

comparatorThe comparator that defines the sorting order, or null to use the natural order of the keys.

The created map.

public ConcurrentSkipListMap<K, V> createConcurrentSkipListMap(MatchingKeyPolicy matchingPolicy) throws NullPointerException

Executes the sorting for the currently added iterables and creates a new ConcurrentSkipListMap.

Callers must ensure that all previously added iterables are sorted by their natural order.

This is the same as:

 createConcurrentSkipListMap(matchingPolicy, null);

matchingPolicyThe matching policy for determining which values to keep for conflicting keys.

The created map.

NullPointerExceptionIf the matching policy is null.

public ConcurrentSkipListMap<K, V> createConcurrentSkipListMap(MatchingKeyPolicy matchingPolicy, Comparator<? super K> comparator) throws NullPointerException

Executes the sorting for the currently added iterables and creates a new ConcurrentSkipListMap.

Callers must ensure that all previously added iterables are sorted by the argument comparator.

matchingPolicyThe matching policy for determining which values to keep for conflicting keys.

comparatorThe comparator that defines the sorting order, or null to use the natural order of the keys.

The created map.

NullPointerExceptionIf the matching policy is null.

public NavigableMap<K, V> createImmutableNavigableMap()

Executes the sorting for the currently added iterables and creates a new immutable navigable map.

Callers must ensure that all previously added iterables are sorted by their natural order.

This is the same as:

 createImmutableNavigableMap(MatchingKeyPolicy.DONT_CARE, null);

The created map.

public NavigableMap<K, V> createImmutableNavigableMap(Comparator<? super K> comparator)

Executes the sorting for the currently added iterables and creates a new immutable navigable map.

Callers must ensure that all previously added iterables are sorted by the argument comparator.

This is the same as:

 createImmutableNavigableMap(MatchingKeyPolicy.DONT_CARE, comparator);

comparatorThe comparator that defines the sorting order, or null to use the natural order of the keys.

The created map.

public NavigableMap<K, V> createImmutableNavigableMap(MatchingKeyPolicy matchingPolicy) throws NullPointerException

Executes the sorting for the currently added iterables and creates a new immutable navigable map.

Callers must ensure that all previously added iterables are sorted by their natural order.

This is the same as:

 createImmutableNavigableMap(matchingPolicy, null);

matchingPolicyThe matching policy for determining which values to keep for conflicting keys.

The created map.

NullPointerExceptionIf the matching policy is null.

public NavigableMap<K, V> createImmutableNavigableMap(MatchingKeyPolicy matchingPolicy, Comparator<? super K> comparator) throws NullPointerException

Executes the sorting for the currently added iterables and creates a new immutable navigable map.

Callers must ensure that all previously added iterables are sorted by the argument comparator.

matchingPolicyThe matching policy for determining which values to keep for conflicting keys.

comparatorThe comparator that defines the sorting order, or null to use the natural order of the keys.

The created map.

NullPointerExceptionIf the matching policy is null.

public TreeMap<K, V> createTreeMap()

Executes the sorting for the currently added iterables and creates a new TreeMap.

Callers must ensure that all previously added iterables are sorted by their natural order.

This is the same as:

 createTreeMap(MatchingKeyPolicy.DONT_CARE, null);

The created map.

public TreeMap<K, V> createTreeMap(Comparator<? super K> comparator)

Executes the sorting for the currently added iterables and creates a new TreeMap.

Callers must ensure that all previously added iterables are sorted by the argument comparator.

This is the same as:

 createTreeMap(MatchingKeyPolicy.DONT_CARE, comparator);

comparatorThe comparator that defines the sorting order, or null to use the natural order of the keys.

The created map.

public TreeMap<K, V> createTreeMap(MatchingKeyPolicy matchingPolicy) throws NullPointerException

Executes the sorting for the currently added iterables and creates a new TreeMap.

Callers must ensure that all previously added iterables are sorted by their natural order.

This is the same as:

 createTreeMap(matchingPolicy, null);

matchingPolicyThe matching policy for determining which values to keep for conflicting keys.

The created map.

NullPointerExceptionIf the matching policy is null.

public TreeMap<K, V> createTreeMap(MatchingKeyPolicy matchingPolicy, Comparator<? super K> comparator) throws NullPointerException

Executes the sorting for the currently added iterables and creates a new TreeMap.

Callers must ensure that all previously added iterables are sorted by the argument comparator.

matchingPolicyThe matching policy for determining which values to keep for conflicting keys.

comparatorThe comparator that defines the sorting order, or null to use the natural order of the keys.

The created map.

NullPointerExceptionIf the matching policy is null.

public boolean isAnyIterableAdded()

Checks if any iterables was added to this merge sorter.

Note that if there was any iterable added, the result of the sorting may still be empty.

true if there is at least one iterable in this sorter.

public Iterator<? extends Entry<? extends K, ? extends V>> iterator()

Executes the sorting for the currently added iterables and returns an iterator for the entries.

Callers must ensure that all previously added iterables are sorted by their natural order.

The actual sorting is done while the entries are being iterated. The class will not pre-allocate any storage or sort the entries before returning the iterator for the sorted entries.

The entries that the iterator iterates over are the same entry objects which are present in the iterables added to this sorter.

This is the same as:

 iterator(MatchingKeyPolicy.DONT_CARE, null);

An iterator that iterates over the sorted entries.

public Iterator<? extends Entry<? extends K, ? extends V>> iterator(Comparator<? super K> comparator)

Executes the sorting for the currently added iterables and returns an iterator for the entries.

Callers must ensure that all previously added iterables are sorted by the argument comparator.

The actual sorting is done while the entries are being iterated. The class will not pre-allocate any storage or sort the entries before returning the iterator for the sorted entries.

The entries that the iterator iterates over are the same entry objects which are present in the iterables added to this sorter.

This is the same as:

 iterator(MatchingKeyPolicy.DONT_CARE, comparator);

comparatorThe comparator that defines the sorting order, or null to use the natural order of the keys.

An iterator that iterates over the sorted entries.

public Iterator<? extends Entry<? extends K, ? extends V>> iterator(MatchingKeyPolicy matchingPolicy) throws NullPointerException

Executes the sorting for the currently added iterables and returns an iterator for the entries.

Callers must ensure that all previously added iterables are sorted by their natural order.

The actual sorting is done while the entries are being iterated. The class will not pre-allocate any storage or sort the entries before returning the iterator for the sorted entries.

The entries that the iterator iterates over are the same entry objects which are present in the iterables added to this sorter.

This is the same as:

 iterator(matchingPolicy, null);

matchingPolicyThe matching policy for determining which values to keep for conflicting keys.

An iterator that iterates over the sorted entries.

NullPointerExceptionIf the matching policy is null.

public Iterator<? extends Entry<? extends K, ? extends V>> iterator(MatchingKeyPolicy matchingPolicy, Comparator<? super K> comparator) throws NullPointerException

Executes the sorting for the currently added iterables and returns an iterator for the entries.

Callers must ensure that all previously added iterables are sorted by the argument comparator.

The actual sorting is done while the entries are being iterated. The class will not pre-allocate any storage or sort the entries before returning the iterator for the sorted entries.

The entries that the iterator iterates over are the same entry objects which are present in the iterables added to this sorter.

matchingPolicyThe matching policy for determining which values to keep for conflicting keys.

comparatorThe comparator that defines the sorting order, or null to use the natural order of the keys.

An iterator that iterates over the sorted entries.

NullPointerExceptionIf the matching policy is null.