kds4j

Kinetic Data Structures for Java 8+. Note this is a WIP to learn about kinetic data structures, so no claims about how performant or correct they are!

What is it?

Data structures where the ordering is a function of time.

Why?

Typically kinetic data structures are used in graphics applications, in which case it is unlikely you will be using java. See CGAL and this for a c++ implementation of some kinetic data structures that could be useful in that scenario.

However, there is a wider application of use of such alogithms and this package provides a useful variety of them. For instance you may want to:

1. Track relationships between actors moving in space, eg closest pair
2. Run some scheduling system where the priorities of jobs is a function of time, eg priority queue
3. Keep a bounding box of elements moving in space
4. Maintain an index for a set of elements that may change over time

Use it

All Kinetic Data Structures have a method to advance time. It is the client's repsonsibility to advance time in the data structure. It probably shouldn't be done in a constant loop though!

Boolean advance(final Double t);

Creating a KineticSortedList:

final Double startTime = 0.0;
final KineticSortedList<String> myKineticSortedList = new KineticSortedList<String>(startTime);

You can add Strings with an associated priority function to the list

myKineticSortedList.add(new OneDimensionalKineticElement<>("A", x -> 8 - x)); // A simple function
myKineticSortedList.add(new OneDimensionalKineticElement<>("B", x -> (x * x) / 2 - 4 * x)); // Something a bit more complicated
myKineticSortedList.add(new OneDimensionalKineticElement<>("C", x -> (x * x) / 2 * Math.sin(x) - 4 * x +  Math.cos(5-x))); // Something a bit more complicated

The lambda function is a plain java 8 Function<Double, Double>. Note that these data structures are only well defined for continuous functions since they use numerical methods for solving the intersection of functions. In particular it uses BracketingNthOrderBrentSolver from the Apache Commons Math package.

You can advance the time to any time in the future

Boolean anyReordering = myKineticSortedList.advance(4.0);
//anyReordering will be true if the order of any elements has changed.
//An exception will be thrown if you try to advance time backwards 

You can remove an element at an index

myKineticSortedList.remove(10);

Kinetic PriorityQueue:

KineticPriorityQueue<String> queue = new KineticPriorityQueue<String>(0.0);

queue.add(new OneDimensionalKineticElement<>("A", x -> 8 - x));
queue.add(new OneDimensionalKineticElement<>("B", x -> x / 2 + 5));

assertThat(queueUnderTest.peek().element).isEqualTo("A");
assertThat(queueUnderTest.advance(11.0)).isTrue();
assertThat(queueUnderTest.poll().element).isEqualTo("C");

Kinetic Bounding Box

KineticBoundingBox<String> boundingBox = new KineticBoundingBox<String>(0.0);
boundingBox.add(new TwoDimensionalKineticElement<>("A", x -> 8 - x, x -> 8 + x));
boundingBox.add(new TwoDimensionalKineticElement<>("B", x -> x / 2 + 5, x -> x * x - x/3));

boundingBox.getBoundingBox();

Current Data Structures supported

1. Kinetic sorted list
   • Maintain a fully sorted list of all elements
   • link
2. Kinetic priority queue, see wikipedia:
   • A special case of a sort list where it is only necessary to to have persists the current top priority element at any given time
3. Kinetic bounding box
   • Maintain a bounding box of elements moving in a two dimensional space.

Future work

3. Kinetic convex hull
4. Kinetic closest pair
5. Kinetic minimum spanning tree

Sources

1. Lecture notes from stanford, link
2. Another lecture
3. Nice website
4. A PhD thesis on the topic