Design and Architecture

Captain See Sharp wrote:

it does not matter how large the selection is, it will always be two longs

• Do a binary search to find the insertion location for the range.
• Look at the range that is currently at the insertion location, and the one right before it. If the new change overlaps either of these, combine the new range with them.
• Insert the range at the insertion location (calculated via the binary search).

J. Dunlap wrote:

Two ints would be just fine unless you anticipate working with buffers >1.99GB.

Captain See Sharp wrote:

Thanks for you input.

Captain See Sharp wrote:

I'm building a new version of my hex editor control just to let you know.

Captain See Sharp wrote:

It was suffecient however in my new version I want it to be able to work with extremely large files. For large files I'm going to make it so it will not load the entire file so it wont use too much memory.

Captain See Sharp wrote:

A binary search would be a good idea and I may do that, How would I sort the ranges? Could I just add the MaxValue, MinValue, and Range together and sort by that sum?

int IComparable<Range>CompareTo(Range other)
{
   if(MinValue>other.MinValue)
      return 1;
   if(MinValue<other.MinValue)
     return -1;
   return 0;
}

int insertIdx=ranges.BinarySearch(newRange);
if(insertIdx<0) //if there isn't an existing item matching the MinValue in the collection already...
   insertIdx=~insertIdx; //bitwise complement of the insertion index was returned, so complement it again.
//insertIdx is now the location to insert at

int GetInsertIndex(IList<Range> ranges, long minValue)
{
    int left = 0;
    int right = (0 + ranges.Count) - 1;
    while (left <= right)
    {
        int idx = left + ((right - left) >> 1);
        long listVal = ranges[idx].MinValue;
        if (listVal == minValue)
            return idx;
        if (minValue < listVal)
            right = idx - 1;
        else
            left = idx + 1;
    }
    return left;       
}

int insertIdx=GetInsertIndex(ranges,range.MinValue);
//if the range at the insertion location overlaps the range being added...
if (insertIdx < ranges.Count && ranges[insertIdx].MinValue <= range.MaxValue)
    ranges[insertIdx] = CombineRanges(range, ranges[insertIdx]); //combine them
else
    ranges.Insert(insertIdx, range); //insert the range at the insertion location

//if the range before the insertion location overlaps...
if (insertIdx > 0 && ranges[insertIdx - 1].MaxValue >= range.MinValue)
{
    //combine the newly inserted range with the one before it
    ranges[insertIdx - 1] = CombineRanges(range, ranges[insertIdx - 1]);
    //remove the newly inserted range because it has been merged
    ranges.RemoveAt(insertIdx);
}

...

private Range CombineRanges(Range change1, Range change2)
{
    return new Range(
        Math.Min(change1.MinValue, change2.MinValue),
        Math.Max(change1.MaxValue, change2.MaxValue)
        );
}

I get 2 as the place to insert and when I insert it will go between 1 and 2?

     ..<.<.<.<.<.<.<.<------ 
0  1 . 2  3
     .
     ^
  new rage
     ^
0 1  2  3  4

J. Dunlap wrote:

Is there going to be an article about it?

public void SelectData(long start, long end)
{
  //if the range of data being selected does not join with any other selections
  //or there are no selections then this will remain true
  bool addNewRange = true;
  byte inc = 0;
  int insertIndex = _selected.BinarySearch(new Range(start, 0)); //search for the appropriate index to insert a
                                                                 //new selection range
  if (insertIndex < 0)  //if there is not already data selected at the start index then
      insertIndex = ~insertIndex; //figure out where the selection range should be placed

  if (_selected.Count > 0)  //if there is no selected data then checking for range redundancies is not needed
  {
    //if there is only 1 selection range and the new selection needs to be placed at index 1 then
    if (_selected.Count == insertIndex)
    {
      insertIndex--;
      inc = 1;
    }

    if (end >= _selected[insertIndex].MinValue - 1)  //check for reducdancies (overlapping)
    {
      if (start < _selected[insertIndex].MinValue)
      {
        _selected[insertIndex] = new Range(start, _selected[insertIndex].MaxValue);
        addNewRange = false;
      }

      if (end > _selected[insertIndex].MaxValue && start < _selected[insertIndex].MaxValue)
      {
        addNewRange = false;

        _selected[insertIndex] = new Range(_selected[insertIndex].MinValue, end);

        //if the new selection range is longer to the right of the current overlapping range then see how far it goes
        //and remove redundancies
        for (int i = insertIndex + 1; i < _selected.Count; i++)
        {
          if (end < _selected[i].MinValue - 1) break;

          if (end >= _selected[i].MinValue - 1 && end <= _selected[i].MaxValue)
          {
            _selected[insertIndex] = new Range(_selected[insertIndex].MinValue, _selected[i].MaxValue);
            _selected.RemoveAt(i);
            i--;
            continue;
          }
          //if end is greater than i's maxvalue then just remove it because it completely overlaps it
          if (end > _selected[i].MaxValue)
          {
            _selected.RemoveAt(i);
            i--;
          }
        }
      }
    }

    //this block checks to see if the new selection overlaps the selection to the left
    if (insertIndex > 0)
    {
      if (start <= _selected[insertIndex - 1].MaxValue + 1)
      {
        if (!addNewRange)
          end = _selected[insertIndex].MaxValue;

        addNewRange = false;
        _selected[insertIndex - 1] = new Range(_selected[insertIndex - 1].MinValue, end);
      }
    }
  }

  if(addNewRange)
    _selected.Insert(insertIndex + inc, new Range(start, end));

}

Bassam Abdul-Baki wrote:

he math one isn't used much except by me

Richard A. Abbott wrote:

Remember not every programmer is a maths genius, and many don't have a need to be.

Bassam Abdul-Baki wrote:

Try Sudoku or logic puzzles.

Bassam Abdul-Baki wrote:

There's an interesting Sudoku[^] client here that you can try.

Bassam Abdul-Baki wrote:

Would be nice if others started doing that too.

PaulC1972 wrote:

I'll try to make more effort to help you add to the interesting articles part

PaulC1972 wrote:

Some people have a memory and an attention span, you should try them out one day.

Bassam Abdul-Baki wrote:

Saw this in the email reply and I wondered how I pissed you off.