4

I am trying to split a dynamic number of ranges with associated attributes, so that whenever 2 or more ranges overlap, the overlapping section(s) are split into unique ranges with the combination of all overlapping attributes. To be more specific, say I have

1-10 - attributes a
7-12 - attributes b
9-15 - attributes c

I want to make this

1-6 - attributes a
7-8 - attributes a, b
9 - 10 - attributes a,b,c
11-12 - attributes b,c
13-15 - attributes c

It actually boils down to applying styling to ranges in Open Office XML, but I believe the underlying logic could be solved for any scenario. Thanks for any advice on how to approach this. I'm going to be using node/javascript, but I think any language demonstrating the method would suffice.

6

Here is what I would do:

  • Make an array of triplets (n, attr, e), with two elements per each given interval. One encodes the starting point, and will have e=false, the other encodes the ending point, and will have e=true.

In your example, you will have [(1,a,false), (10,a,true),(7,b,false), (12,b,true),(9,c,false), (15,c,true)].

  • Sort this array on n and e lexicographically (taking false < true)

Now you have [(1,a,false), (7,b,false), (9,c,false), (10,a,true), (12,b,true), (15,c,true)]

  • Now make one pass through the sorted array, keeping the "current" set of attributes S (which, at the beginning, is empty). In each step, update S and then output the interval from the two consecutive elements in the array (adjusting the endpoints by 1 if necessary, and skipping empty intervals). In other words, if you have a pair of consecutive triplets (n, a, e) and (m, b, f), the step is:
    • If e=false, add a to S. If e=true, take away a from S.
    • Define n'=n if e=false or n'=n+1 if e=true
    • Define m'=m-1 if f=false or m'=m if f=true
    • If n' <= m', output (n',m',S), otherwise output nothing.

In our example, the output will be [(1,6, {a}), (7,8, {a,b}), (9,10, {a,b,c}), (11,12, {b,c}), (13,15, {c})].

  • 1
    This answer doesn't take account of gaps (gaps should not appear in output), so I refined it: * If e=false, add a to S. If e=true, take away a from S. * Define n'=n if e=false or n'=n+1 if e=true * Define m'=m-1 if f=false or m'=m if f=true * If n' <= m' and (e and not f) = false, output (n',m',S), otherwise output nothing. – silentman.it Aug 23 '18 at 12:19
  • for what it's worth I don't think this additional condition to exclude gaps is working correctly. – Michael Apr 24 '19 at 23:32
  • see stackoverflow.com/questions/55836442/… – Michael Apr 24 '19 at 23:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.