CODEWITHSUNDEEP
java
Cowboy
Cowboy

Reputation: 525

Find String range using String parameter

I have a collection of the following type:

class Container
{
   private String startValue;
   private String endValue;
}

Let's say it contains these entries...

{"123, "789"},
{"1", "8"},
{"9", "10"},

Then I want to ask the collection to give me all entries which satisfy the predicate between start and end values of each Container, such as the String "5" parameter would return the two first entries above (but not the last one) whereas "9" would only return the first one (and so on).

It should behave as SQL BETWEEN operator on a VARCHAR column.

Changing type from String is not an option. Changing data structure is not an issue.

Performance is also a very importan here. The data structure is rarely changed, but retrieval is very common. A bit extra space taken if speed can be gained is also fine.

Any ideas?

Upvotes: 0

Views: 111

Answers (3)

Pedro Vítor
Pedro Vítor

Reputation: 191

Well... without Integer conversion and change the structure...

You can use stringToCompare.compareTo(str) to compare Strings.

Or, you can use a fixed array of Strings like {"1", "2", "3", "4", "5", "6", "7", "8", "9"}. So, you can split the Strings startValue and endValue, getting character by character and verifying the index (a int) in your array. With this int value you can do some comparisons.

Upvotes: 1

Ruslan Ostafiichuk
Ruslan Ostafiichuk

Reputation: 4692

You have to implement "Interval search tree" using red-black BST.

http://algs4.cs.princeton.edu/92search/ https://d396qusza40orc.cloudfront.net/algs4partI/slides%2F99GeometricSearch.pdf

Find all elements will cost R*logN, where R - number of elements to return, N - number of all elements.

Upvotes: 1

Dawood ibn Kareem
Dawood ibn Kareem

Reputation: 79838

Add this method to the Container class

public boolean contains(String argument) {
    return argument != null && startValue.compareTo(argument) <= 0 && endValue.compareTo(argument) >= 0;
}

Then iterate through your collection, calling contains on each element.

Upvotes: 2

Related Questions