How to determine if position Z is within regions with start X and end Y

Question

I have a JTextArea where the user can create regions using special syntax. I am looking for some assistance in the best way (most efficient using a linear time algorithm) to determine if the current position is within one of the non-overlapping regions.

Let's assume I have the following to determine the user defined regions (I scan the document at the start using regex to determine the regions):

REGION START = 0, END = 20
REGION START = 21, END = 24
REGION START = 34, END = 40

I don't care what region the user is in, I just need to determine if they are in or out of a region, given position X. I could store the regions as an array and loop through the entries until I find one that matches, but this isn't linear time and would take longer if it didn't match a region.

Is there an easier way to do this using an algorithm or storing the data in a certain way?

Answer 1

Actually the algorithm you are proposing is indeed linear. Here is another one, a bit more complicated, but faster:

• You need to use a Cumulative Table data structure, like Binary Indexed Tree (BIT). A BIT allows you to implement the following operations with logarithmic complexity:
  • Update lo, hi, val: add at the indices [lo, hi] the value val
  • Query x: return the sum at index x
• For each region [lo, hi], you call Update(lo, hi, 1), adding 1 to the appropriate positions in the BIT
• For each query just check if Query(x) is zero. If yes, then x, does not overlap with a region

About Binary Indexed Trees: http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees

And some code:

public class BIT {

  // AddAtPosition: adds at binary indexed tree [bit] the value [v]
  // exactly at position [i]. The binary indexed tree has size [size]

  public static void AddAtPosition(int [] bit, int size, int i, int v) {
    while(i < size) {
      bit[i] += v;
      i += (i & -i);
    }
  }

  // AddAtInterval: adds at binary indexed tree [bit] the value [v]
  // to all position from [lo] to [hi]. The binary indexed tree has size [size]

  public static void AddAtInterval(int [] bit, int size, int lo, int hi, int v) {
    AddAtPosition(bit, size, lo+1, v);
    AddAtPosition(bit, size, hi+2, -v);
  }

  // QueryAtPosition: returns the value of index [i] at binary indexed tree [bit]

  public static int QueryAtPosition(int [] bit, int i) {
    int ans = 0;
    i++;
    while(i > 0) {
      ans += bit[i];
      i -= (i & -i);
    }
    return ans;
  }

  public static void main(String [] args) {
    int [] bit = new int[10+1]; // for values from 0-9
    AddAtInterval(bit, 11, 0, 5, 1);
    AddAtInterval(bit, 11, 4, 7, 1);
    for(int i=0; i<=9; ++i) {
      System.out.print("Query At position " + i + ": ");
      System.out.println(QueryAtPosition(bit, i));
    }
  }
}

Answer 2

I could store the regions as an array and loop through the entries until I find one that matches, but this isn't linear time

It is linear.

Assuming that regions are sorted, you could use Binary Search.

Answer 3

Although I like the BIT example, I think I might use a simpler solution which I am hoping doesn't have a huge performance impact compared to a BIT - is there, considering I need the same length of array to start with? I have defined an array in the same way based on the length of my JText Area:

int[] pC = new int[myArea.getText().length()];

I then search for my regions and whenever I find a region I set the appropriate position to 1 in my array:

for (int i = m.start(); i < m.end(); i++) {
  pC[i] = 1;
}

I can then do a simple check against position Z using the following syntax:

if (pC[Z] == 0) {
  // OUTSIDE REGION
}
else {
  // INSIDE REGION
}