CODEWITHSUNDEEP
javaalgorithmdata-structuresset
Max
Max

Reputation: 113

Java sorted data structure that allows for logarithmic time removal of values within a range

I was wondering if there's an interface in the Java built in libraries that implements a data structure which is ordered and supports removal over a range. For example, if we call the data structure S (let's say of Integers), I'd like to be able to search for and remove the subset Q of S such that Q consists of all elements in S in the range [start, end] in O(|Q| log |S|) time.

I know in C++, there is an erase method to the Set interface, but it doesn't seem like Java's TreeSet has something similar. Can anyone help? Thanks!

Upvotes: 1

Views: 74

Answers (2)

c.abate
c.abate

Reputation: 442

I don't know of any interfaces/libraries, but you could try using a histogram like structure...

For example, let's say we know our structure will only hold integers between min and max inclusive. Then we can simply make an array in the following manor...

int[] hist = new int[max - min + 1];

If we want to add a number i to the histogram, we can simply do...

hist[i - min]++;

Each index in the array represents a number in the predefined range. Each value in the array represents the number of occurrences of a number in the range.

This structure is extremely powerful since it allows for constant time addition, removal, and search.

Let's say we want to remove all elements in the inclusive range Q = [s, e]. We can run the following linear loop...

for (int i = s; i <= e; i++) {
    hist[i - min] = 0;
}

This runs in O(|Q|).

Lastly, If we wanted to make the above structure an ordered set instead of an ordered sequence, we could change our array to hold booleans instead of integers.

For more info check out https://en.wikipedia.org/wiki/Counting_sort.

Upvotes: 0

Andy Turner
Andy Turner

Reputation: 140494

SortedSet.subSet returns a view, which you can then clear().

For example:

TreeSet<String> set = new TreeSet<>(Arrays.asList("A", "B", "C", "D", "E"));
System.out.println(set);  //  [A, B, C, D, E]
set.subSet("B", "D").clear(); // Inclusive of B, exclusive of D.
System.out.println(set);  //  [A, D, E]

(The documentation of SortedSet describes how to modify the bounds of subSet to be exclusive and inclusive, respectively, at least for String).

Upvotes: 3

Related Questions