Data structure for Integer ranges

[Tommi Prami 130]

Hello,

 

Was looking for what is out there and Interval tree etc has too much functionality than I need, but still might be way to go, not sure.

 

I have ranges of integer, which do not overlap, and are inherently in right order while adding. In which I need to search if the given more than  less random integer falls in any of those ranges, and retrive what type of the range is (Currently there is only two distinct types, and of course the state when integer value is not found in any of the ranges.) List would have 0-couple hundred of ranges at max, usually low numbers.

 

That's why I was thinking that balancing of the tree structures while adding might be unwanted overhead.

Was thinking using list that could use list, adn starts are in ascending order, and binary search, but was thinking how to binary search something that most likely is not in the list. Now that I write it out, have to just compare two items and/or is it first/last at the list, quite complex compare but nothing too bad, I think). For the list I was thinking that is there list implementation that can be marked as sorted without doing actual sort operation and would have binary search that could have custom compare that I could find the start of the range, maybe end of the range in the dictionary with start as a key.

 

As you can see, I am not sure how this would be smart to implement.

[Kas Ob. 121]

Hi,

 

I am having hard time understand the problem or the proposed solution, so to recap what i get you have non-overlapped integer ranges in a list, and want to implement the best solution to check for an integer to get its range if exist, right ?

 

In that case then make sure to sort them by the left side ( the start point of the each range), and check for the middle item in that list for the required value, by checking i mean use >Ri  or <Li

"here Li and Ri are start of and the end of range i, i in the range [0..Last] which is the list of ranges, starting i with (Last div 2)"

 

then based on these comparison you either get i the range, or the value is in bigger i or smaller i ( i will become i div 2 or i+(Last-i) div 2 ) , repeat.

 

This will should be fast to handle even thousands of ranges.

[Tommi Prami 130]

26 minutes ago, Kas Ob. said:

so to recap what i get you have non-overlapped integer ranges in a list, and want to implement the best solution to check for an integer to get its range if exist, right ?

I think exactly that.

integer ranges like
1-5: 1
15-40: 1

102-150: 2

and if I search for:
 1 -> I'll get that range exists and get also associated value 1
 7 -> No range, and no value
 149 -> Range exists and associated value 2 returned

code could be something like:
 

if FRanges.Contains(1, LRangeValue) then
begin
  case LRangeValue of
    1: HandleRangeType1; 
    2: HandleRangeType2;
  end;
end;

 

Edited January 4 by Tommi Prami

[Kas Ob. 121]

34 minutes ago, Tommi Prami said:

and if I search for:
 1 -> I'll get that range exists and get also associated value 1
 7 -> No range, and no value
 149 -> Range exists and associated value 2 returned

I really hate that !, "no range no value" does sound like undefined behavior.

 

For me, always one of two for a search result :

1) return (-1) for not found or a valid index in a simple and plain list, array.... , same with pointers and linked list return 0 for not found, can be checked with Assigned.

2) return a boolean true for success with var parameter for index, internal associated data....structures, pointers...could also return a pointer and the next one or the previous in one go...

[Uwe Raabe 2057]

A pretty simple implementation (assuming ranges are non-overlapping and added in the right order) could look like this:

type
  TRanges = class
  private
    FLow: TArray<Integer>;
    FHigh: TArray<Integer>;
    FType: TArray<Integer>;
  public
    procedure AddRange(ALow, AHigh, AType: Integer);
    function Contains(AValue: Integer; out AType: Integer): Boolean;
  end;

procedure TRanges.AddRange(ALow, AHigh, AType: Integer);
begin
  FLow := FLow + [ALow];
  FHigh := FHigh + [AHigh];
  FType := FType + [AType];
end;

function TRanges.Contains(AValue: Integer; out AType: Integer): Boolean;
var
  idx: Integer;
begin
  Result := False;
  if not TArray.BinarySearch<Integer>(FLow, AValue, idx) then begin
    if idx < 1 then Exit;
    Dec(idx);
  end;
  if AValue <= FHigh[idx] then begin
    AType := FType[idx];
    Result := True;
  end;
end;

 

Edited January 4 by Uwe Raabe

[Tommi Prami 130]

18 hours ago, Kas Ob. said:

I really hate that !, "no range no value" does sound like undefined behavior.

Meaning "No value given to the Container". If not added value, there can't be any it has... 

Most likely I'll return defined value, but that is just implementation detail.

 

-Tee-

Edited January 5 by Tommi Prami

[Tommi Prami 130]

Just to point it out:

I am looking for ideas how to make it fast and simple etc... 

 

I made simple proof of concept. Make some Unit Tests for it some point- If there is better idea, easy to test that then.

@Uwe Raabe made very simple implementation indeed. 
 

-Tee-

[Clément 148]

How low is you range. Can you use a simple array?

 

A[1]:=1;

A[2]:=1;

A[3]:=1;

...

A[7]:=-1; // Non existing range

...

A[102]:=2;

A[103]:=2;

....

A[149]:=2;

A[150]:=2;

 

All elements must have a value. 

 

 

 

[Tommi Prami 130]

17 minutes ago, Clément said:

How low is you range. Can you use a simple array?

 

A[1]:=1;

A[2]:=1;

A[3]:=1;

...

A[7]:=-1; // Non existing range

...

A[102]:=2;

A[103]:=2;

....

A[149]:=2;

A[150]:=2;

 

All elements must have a value. 

 

 

 

Very small ranges that would be simple lookup. I think I have to realistically be mentally prepared upper bounds of few hundreds of  thousands, Maybe even millions.

Most case it will be 100k or less..

But anyhow, interesting take on this. Thanks...

 

-Tee-

[Clément 148]

44 minutes ago, Tommi Prami said:

Most case it will be 100k or less

Using SQL then might also work.

Table (Ranges) with fields

      loRange

      HiRange

      Value

The SQL would be very simple:

 

Select value from ranges where  :elem between loRange and HiRange

 

Since your ranges are unique you can create a unique index for loRange, hiRange

 

Should be very easy to maintain and would handle millions of row. 

[Tommi Prami 130]

9 hours ago, Clément said:

The SQL would be very simple:

 

It sure would be handy and easy, with more than all features needed. I am afraid that it also would be too slow and too much resource overhead,

There will be easily thousands of data structure populations and searches can raise millions even more.

 

-Tee-

[David Heffernan 2345]

Surely this could be done using regular expressions

[Tommi Prami 130]

1 hour ago, David Heffernan said:

Surely this could be done using regular expressions

Most likely.

[Attila Kovacs 629]

For me it sounds like an indexing task, store the data to the integer and not the opposite.

[Pat Foley 51]

Or like the minesweeper game. Test for "open water" or "good ice".  A test returns the position in range with start and stop of range when found and could return the size of the "open water" when not found.   

[Tommi Prami 130]

55 minutes ago, Attila Kovacs said:

For me it sounds like an indexing task, store the data to the integer and not the opposite.

I don't quite follow, could you elaborate a bit?

[Uwe Raabe 2057]

1 hour ago, Attila Kovacs said:

For me it sounds like an indexing task, store the data to the integer and not the opposite.

I cannot speak for Tommi, but I had a need for such a data structure where ranges of numbers were given in string format like "2,3,5,7-11,15-31" and the numbers going up to 6 digits. The actual testing for a given number being part of that was implemented by parsing the string each time, which turned out to be a bit time consuming. So we refactored it using a data structure similar to that shown above. 

[Attila Kovacs 629]

8 hours ago, Uwe Raabe said:

I cannot speak for Tommi

me neither, I just read what he wrote

On 1/4/2024 at 8:51 AM, Tommi Prami said:

usually low numbers

So maybe he could store the group number to the integer, as he is writing he is using this as a lookup table.