StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>How many ranges do you have? Is it acceptable that the algorithm is O(number of ranges)? </p> <p>If so, below is the description of the algorithm. Let me explain it on your (original) example.</p> <pre><code> 100 200 300 400 500 600 700 800 |----------|----------|----------|----------| 0% 100% </code></pre> <p>1) What you're doing to do is to map the value X in range A (100-800) to the value Y in continous range B (0-399) (as the total number of elements in your range is 400). Then it's easy to change position in B to percents, I will omit this part.</p> <p>2) Create a list of records, where each records represents one range mapping.</p> <pre><code>struct RangeRecord { int start_in_a; int start_in_b; }; </code></pre> <p>In your case, you will get the following list:</p> <pre><code>{100, 0}, {300, 100}, {500, 200}, {700, 300} </code></pre> <p>3) When you need to map a number X from A to B, you iterate the list to find first record with start_in_a <= X.Then your value Y is</p> <pre><code>Y = X + start_in_b - start_in_a; </code></pre> <p>4) The algorithm is symmettric, you just iterate the list to find the first record with start_in_b <= Y, and then</p> <pre><code>X = Y + start_in_a - start_in_b. </code></pre> <p>Note 1. For error checking purposes, you might keep the range size in RangeRecord, as well.</p> <p>Note 2. If O(number of ranges) is not good enough, keep the records as a tree instead of a list. You will need O(log(number of ranges)) operations then,</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload