Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Is there an IndexSet and a Range class for Java?

In Objective-C Cocoa we have the NSIndexSet class which stores a series of unique indexes efficiently by keeping an array of ranges. E.g. the set 1, 2, ... 30, 57 would be stored as the ranges 1-30 and 57 rather than an array of 32 numbers. This facilitates huge selections to be stored in a simple and fast way. For example, if all rows between 1 and a million in a table selected, the index set collapses to just a tiny range and is fast to compare and intersect with.

Unfortunately this turns out to be rather hard to Google for. Is there an equivalent class for Java?

like image 218
Alexander Ljungberg Avatar asked Jan 10 '11 15:01

Alexander Ljungberg


2 Answers

There is the Apache commons IntRange

like image 155
Navi Avatar answered Sep 28 '22 18:09

Navi


It seems a useful class, and I don't recall a standard implementation.

Here's a bunch of some -perhaps useful- pointers.

A range intersection algorithm better than O(n)?

http://www.codeproject.com/KB/recipes/rangeset.aspx

http://healpix-rangeset.googlecode.com/svn/trunk/healpix-rangeset/src/org/asterope/healpix/LongRangeSet.java

http://pcj.sourceforge.net/docs/api/bak/pcj/set/IntRangeSet.html

Data structure to build and lookup set of integer ranges

Representing sparse integer sets?

http://www.iis.uni-stuttgart.de/intset/doc/intset/TreeIntegerSet.html

like image 43
leonbloy Avatar answered Sep 28 '22 19:09

leonbloy