cicirello/core

Utilities and data structures used by several of my projects

Vincent A Cicirello

	Sites where you can find me or my work
Web and social media
Software development
Publications

If you want to generate the equivalent to the above for your own GitHub profile, check out the cicirello/user-statistician GitHub Action.

core's Issues

Improve runtime of FibonacciHeapDouble.retainAll(Collection)

Summary

The current retainAll has a runtime of O(n + m + (n-m) lg n). The (n-m) lg n term comes from making (n-m) calls to remove(Object). We can eliminate that term with an alternative approach that instead rebuilds the heap with the elements we're keeping. This will be O(n+m).

Remove redundant implements declaration in FibonacciHeapDouble

Summary

FibonacciHeapDouble has a redundant implements declaration, a remnant of before superclass was introduced.

Copying an empty Fibonacci heap throws null pointer exception

Describe the bug
Copying empty Fibonacci heap throws null pointer exception.

To Reproduce
Steps to reproduce the behavior:

1. First, create empty FibonacciHeap or FibonacciHeapDouble.
2. Then call copy method.
3. Observe exception.

Expected behavior
Copying empty heap should give empty heap.

Fix binary heap classes methods with PriorityQueueNode params or returns

Summary

The PriorityQueueNode class is immutable external to its package. For this reason it was assumed safe to directly store instances passed as parameters without copying them as well as to return references to instances.

However, if someone peeks an instance from one heap and then offers it to another heap, two heaps would end up sharing instances. Or if someone offers the same instance to two binary heaps. This is potentially problematic in the case of changing a priority. Change priority in one heap and the value changes in both but one will be structurally invalid.

Possible Solution

It should be sufficient to fix where PriorityQueueNode is a parameter such as in offer method, add method, addAll method, and constructors.

Fix PriorityQueueDouble docs to move doc of distinctness into the class docs

Summary

Some methods of the PriorityQueueDouble interface have documentation that indicates that elements are only added if distinct, documenting exceptions, etc. This is currently true of all of the existing implementations. However, new classes are planned (see #101 and #102) that will allow duplicate elements. Move the documentation of distinctness into the specific implementations that require it, and edit the interface docs to be more general.

Fix PriorityQueue documentation to move distinct elements docs to classes

Summary

Some methods of the PriorityQueue interface have documentation that indicates that elements are only added if distinct, documenting exceptions, etc. This is currently true of all of the existing implementations. However, new classes are planned (see #101 and #102) that will allow duplicate elements. Move the documentation of distinctness into the specific implementations that require it, and edit the interface docs to be more general.

Improve runtime of FibonacciHeap.retainAll(Collection)

Summary

The current retainAll has a runtime of O(n + m + (n-m) lg n). The (n-m) lg n term comes from making (n-m) calls to remove(Object). We can eliminate that term with an alternative approach that instead rebuilds the heap with the elements we're keeping. This will be O(n+m).

Partially filled array of primitive doubles

Summary
An implementation of a partially filled array of primitive double values. Should have similar methods to Java's ArrayList class where possible but without using wrapper objects.

Clean up javadoc comments in Priority Queue classes

Summary

Edit javadoc comments in priority queue interfaces and classes to clean up cases of overriding method just to add doc details, and other messiness.

Enable test coverage

Summary
Enable test coverage reporting on repo.

Improve runtime of BinaryHeapDouble.addAll(Collection)

Summary

BinaryHeapDouble currently relies on the default implementation of the addAll(Collection) method, which simply calls the add method repeatedly, for a worst case runtime of O(m lg (n+m)) where m elements are added to a heap that currently has n elements. This is fine for small m, but in the case where many elements are added at once, this can be improved to O(n + m) by inserting the m new elements arbitrarily into the end of the array and then rebuilding the heap.

Method to merge BinaryHeapDouble objects

Summary

Add a method to the BinaryHeapDouble class for merging heaps.

PriorityQueue interface change method return boolean

Summary

Modify PriorityQueue.change to return a boolean indicating if anything changed.

Improve runtime of BinaryHeap.removeAll(Collection)

Summary

BinaryHeap currently relies on default implementation of removeAll(Collection) which simply calls the remove(Object) method once for each element in the Collection. The runtime of this approach is O(m lg n) where the heap currently has n elements and you are removing m of them. This can be improved to O(n + m) for the case when there are many to remove by rebuilding the heap with only the elements that you want to keep. If a relatively small number are to be removed, the current behavior is still faster. Reimplement with the O(n + m) approach, with a comment related to the small number of removals case.

Disjoint set forest implementation

Summary
Add an implementation of disjoint set forests, which is needed for planned functionality in dependent libraries. Include the following variations:

• Disjoint integer sets (e.g., disjoint set forest of integers in the interval 0 to N).
• Disjoint sets of hashable objects (note that this can utilize the above).

Priority queue promote and demote methods

Summary

The PriorityQueue and PriorityQueueDouble interfaces currently have a change method that can be used to change the priority of an element in the priority queue. This method supports both increasing and decreasing priority. Add a promote method that will only decrease priority for a min-heap or increase for a max-heap, otherwise doing nothing if the new priority is in opposite direction. Similarly add a demote method that does the opposite.

Implement the new interface methods in the binary heap and Fibonacci heap implementations.

Refactor FibonacciHeapDouble to extend SimpleFibonacciHeapDouble

Summary

There is much redundant code between FibonacciHeapDouble and SimpleFibonacciHeapDouble. Refactor FibonacciHeapDouble to extend SimpleFibonacciHeapDouble.

Fibonacci heap implementation of the IntPriorityQueueDouble interface

Summary

Add a Fibonacci heap implementation of the IntPriorityQueueDouble interface.

Method for merging FibonacciHeap objects

Summary

Add a method to the FibonacciHeap class for merging heaps.

Missing `@Override` annotations in FibonacciHeapDouble class

Summary

FibonacciHeapDouble class overrides package access methods without @Override annotations.

Method in priority queue classes for polling next element while adding a new one

Is your feature request related to a problem? Please describe.
Some applications of priority queue may involve adding a new element, while removing the next in priority order. This can obviously be done with a pair of calls to the existing poll() and offer() methods. But for some implementations of a priority queue, there may be a more efficient approach to the combination. E.g., For a binary heap, you can save the root temporarily, insert new element at root, percolate it down the heap, and then return the old root. This would be approximately half the work of the poll() then offer() alternative.

Describe the solution you'd like
A method, perhaps called pollThenOffer() or pollThenAdd() that does the combination of polling the next element in priority order, while adding the new element. Probably pollThenAdd() since the add() methods through an exception for failures to add, while offer returns a boolean to indicate success. Returning a boolean isn't an option, since the polled element will need to be returned. So for naming consistency, an exception approach would better use add in the method name.

Describe alternatives you've considered
See above. Call poll() and then call either offer() or add().

Implement Copyable interface in binary heap classes

Summary

Implement the Copyable interface in the binary heap classes to enable easily copying a binary heap.

MergeablePriorityQueueDouble interface

Summary

Add a MergeablePriorityQueueDouble interface as a sub-interface of PriorityQueueDouble, which includes a merge method.

Fix Sonatype Lift configuration

Summary

The configuration file for Sonatype Lift includes an unnecessary exclusion for the source code of the test cases. The default exclusions should cover that.

Improve runtime of BinaryHeap.retainAll

Summary

The current retainAll has a runtime of O(n + m + (n-m) lg n). The (n-m) lg n term comes from making (n-m) calls to remove(Object). We can eliminate that term with an alternative approach that instead rebuilds the heap with the elements we're keeping. This will be O(n+m).

Binary heap implementation of priority queue

Summary
Planned functionality in dependent libraries will need a priority queue with changeable priorities. Integrate my existing not yet open sourced implementation with the following variations:

• binary minheap with integer priorities
• binary maxheap with integer priorities
• binary minheap with double priorities
• binary maxheap with double priorities

Also provide an interface to provide a common interface. Might need 2 though ine for integer and one for double priorities. The interface would later enable easily introducing other implementations such as fibonacci heap.

MergeablePriorityQueue interface

Summary

Add a MergeablePriorityQueue interface as a sub-interface of PriorityQueue, which includes a merge method.

DisjointIntegerSetForest: implement Copyable interface, equals, and hashCode methods

Summary

In the DisjointIntegerSetForest, implement the Copyable interface, as well as the equals and hashCode methods.

Implement Collections and Queue interfaces in binary heap classes

Summary

Implement the Collections and Queue interfaces in the BinaryHeap and BinaryHeapDouble classes. Consider having PriorityQueue interface extend the Queue interface.

Improve runtime of BinaryHeapDouble.retainAll

Summary

The current retainAll has a runtime of O(n + m + (n-m) lg n). The (n-m) lg n term comes from making (n-m) calls to remove(Object). We can eliminate that term with an alternative approach that instead rebuilds the heap with the elements we're keeping. This will be O(n+m).

Method to merge BinaryHeap objects

Summary

Add a method to the BinaryHeap class for merging heaps.

Improve runtime of BinaryHeapDouble.removeAll(Collection)

Summary

BinaryHeapDouble currently relies on default implementation of removeAll(Collection) which simply calls the remove(Object) method once for each element in the Collection. The runtime of this approach is O(m lg n) where the heap currently has n elements and you are removing m of them. This can be improved to O(n + m) for the case when there are many to remove by rebuilding the heap with only the elements that you want to keep. If a relatively small number are to be removed, the current behavior is still faster. Reimplement with the O(n + m) approach, with a comment related to the small number of removals case.

Migrate Core to Java 17

Summary

Update pom.xml to target Java 17. Also update GitHub Action workflows to Java 17 as well as the project readme.md. Check website for any mention of minimum Java version.

Check code comments for notes on changes related to Java 17.

Be sure to bump major version number.

Add content to the README

Summary
README.md is currently blank. Add content to it.

Fibonacci heap implementation of a priority queue

Summary

Add a Fibonacci heap implementation of a priority queue, including one class that implements PriorityQueue with int-valued priorities, and one class that implements PriorityQueueDouble with double-valued priorities.

Improve jitpack-build workflow

Summary

The jitpack-build workflow triggers an ahead of time build on jitpack for the preferred groupId of org.cicirello on pushes to main for snapshot builds. Currently curls the target directory. Curl the maven metadata file instead to improve consistency of this ahead of time build trick.

Improve runtime of FibonacciHeap.removeAll(Collection)

Summary

FibonacciHeap currently relies on default implementation of removeAll(Collection) which simply calls the remove(Object) method once for each element in the Collection. The amortized runtime of this approach is O(m lg n) where the heap currently has n elements and you are removing m of them. This can be improved to O(n + m) for the case when there are many to remove by rebuilding the heap with only the elements that you want to keep. If a relatively small number are to be removed, the current behavior is still faster. Reimplement with the O(n + m) approach, with a comment related to the small number of removals case.

Simple binary heap implementation of priority queue

Summary

The existing BinaryHeap class supports constant time containment checks which enables efficient priority changes and arbitrary removals. It accomplishes this by maintaining a hash table based index into the heap.

Additionally, the existing class limits use to distinct objects, related to hash table use.

Add a simpler binary heap class without the hash table based index. Some applications may not need containment checks, priority changes, and arbitrary removals. Provide alternative without the overhead associated with this. Also allow duplicates.

Fix documentation of factory methods in binary heap classes

The createMinHeap(Collection) and createMaxHeap(Collection) methods of the BinaryHeap and BinaryHeapDouble classes have javadoc comments that indicate they create an empty heap. This is wrong.

Fibonacci heap implementation of the IntPriorityQueue interface

Summary

Add a Fibonacci heap implementation of the IntPriorityQueue interface.

Refactor FibonacciHeap to subclass SimpleFibonacciHeap

Summary

To minimize redundant code. refactor FibonacciHeap to extend SimpleFibonacciHeap.

Partially filled array of primitive ints

Summary
An implementation of a partially filled array of primitive int values. Should have similar methods to Java's ArrayList class where possible but without using wrapper objects.

Improve FibonacciHeapDouble.removeAll(Collection)

Summary

FibonacciHeapDouble currently relies on default implementation of removeAll(Collection) which simply calls the remove(Object) method once for each element in the Collection. The amortized runtime of this approach is O(m lg n) where the heap currently has n elements and you are removing m of them. This can be improved to O(n + m) for the case when there are many to remove by rebuilding the heap with only the elements that you want to keep. If a relatively small number are to be removed, the current behavior is still faster. Reimplement with the O(n + m) approach, with a comment related to the small number of removals case.

DisjointSetForest same method for checking if two element in same set

Summary

Add a DisjointSetForest same method for checking if two element in same set.

Method for merging FibonaciHeapDouble objects

Summary

Add a method to the FibonacciHeapDouble class for merging heaps.

Improve ahead of time builds of releases on jitpack

Summary

One of the steps of the deployment workflow triggers an ahead of time build on jitpack for the preferred groupId of org.cicirello for each release. Currently curls the target directory. Curl the maven metadata file instead to improve consistency of this ahead of time build trick.

Simple Fibonacci heap implementation of priority queue with integer priorities

Summary

The existing FibonacciHeap class supports constant time containment checks which enables efficient priority changes and arbitrary removals. It accomplishes this by maintaining a hash table based index into the heap.

Additionally, the existing class limits use to distinct objects, related to hash table use.

Add a simpler Fibonacci heap class without the hash table based index. Some applications may not need containment checks, priority changes, and arbitrary removals. Provide alternative without the overhead associated with this. Also allow duplicates.

Simple Fibonacci heap implementation of priority queue with double priorities

Summary

The existing FibonacciHeapDouble class supports constant time containment checks which enables efficient priority changes and arbitrary removals. It accomplishes this by maintaining a hash table based index into the heap.

Additionally, the existing class limits use to distinct objects, related to hash table use.

Add a simpler Fibonacci heap class without the hash table based index. Some applications may not need containment checks, priority changes, and arbitrary removals. Provide alternative without the overhead associated with this. Also allow duplicates.

Add utility class for enforcing array lengths

Is your feature request related to a problem? Please describe.
In multiple of my other libraries, there are methods that take an array as a parameter to hold the result. For example, RandomSampler of the rho-mu library has various sample methods that generate a random sample. In cases like this, the length of the array passed as parameter must be validated against required length, with a new one constructed if too short. Such is also the case in the SequenceSampler class of the jpt library. In both cases, helper methods were implemented for this.

Describe the solution you'd like
A utility class, perhaps called ArrayEnforcer with methods that do null checks and length checks of an array passed as parameter, either returning that array if sufficient length, or returning a new array of adequate length. Should include the following:

• Support for arrays of all primitive types.
• Support for arrays of an object type.
• Two versions of each method, one that enforces exact array length, and one that enforces minimum array length.

Describe alternatives you've considered
Currently, multiple libraries recreate this functionality as private helpers.

Improve runtime of BinaryHeap.addAll(Collection)

Summary

BinaryHeap currently relies on the default implementation of the addAll(Collection) method, which simply calls the add method repeatedly, for a worst case runtime of O(m lg (n+m)) where m elements are added to a heap that currently has n elements. This is fine for small m, but in the case where many elements are added at once, this can be improved to O(n + m) by inserting the m new elements arbitrarily into the end of the array and then rebuilding the heap.