|
Captain See Sharp wrote: it does not matter how large the selection is, it will always be two longs
Two ints would be just fine unless you anticipate working with buffers >1.99GB.
I haven't analyzed your code in depth, but it looks sufficient provided you don't have a large number of selection ranges (and in most cases you wouldn't). But if you think it would be wise to plan for that, then a double loop is not a good idea (O(N^2) performance overhead - i.e. the code in the inner loop is executed N*N times, where N is the number of ranges).
Performance-wise, it would be best to do the following (provided that you want the selection ranges to always stay non-overlapping). When adding a new range:- 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).
This will take significantly less time, and you have the added bonus of always having your selection range collection arranged in sorted order. That is what I did with text change ranges in a textbox I wrote for a client, where text changes are stored up and the text layout/flow is updated in a batched layout pass.
|
|
|
|
|
Thanks for you input.
I'm building a new version of my hex editor control just to let you know.
J. Dunlap wrote: Two ints would be just fine unless you anticipate working with buffers >1.99GB.
In the last version of my control I used ints. 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. If the program selects data that is not loaded into memory it will still need to know the index of the data so I will use longs.
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?
█▒▒▒▒▒██▒█▒██
█▒█████▒▒▒▒▒█
█▒██████▒█▒██
█▒█████▒▒▒▒▒█
█▒▒▒▒▒██▒█▒██
|
|
|
|
|
Captain See Sharp wrote: Thanks for you input.
You're welcome. I'm hoping to make this forum grow and bring some people together who can share design ideas and expertise.
Captain See Sharp wrote: I'm building a new version of my hex editor control just to let you know.
Is there going to be an article about it? I was going to write one myself but have never had the time. I wanted to write a tool that would make it easier to deconstruct binary file formats.
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.
Nice!
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?
Use the MinValue. If you add them together, then you will get indeterminate sort results and you won't be able to just check for overlap with the 2 ranges before and at the insertion location, which defeats the purpose. Implement IComparable<T> on your Range class like this:
int IComparable<Range>CompareTo(Range other)
{
if(MinValue>other.MinValue)
return 1;
if(MinValue<other.MinValue)
return -1;
return 0;
}
Then all you have to do is insert them in the correct sorted location as you add them. (I assume you don't modify the ranges after they are created, other than to combine them when they overlap? If you do you will need to update the sort order on modification as well.) You can use binary search, as I mentioned, to find the insertion location, assuming the structure is a List<Range>:
int insertIdx=ranges.BinarySearch(newRange);
if(insertIdx<0)
insertIdx=~insertIdx;
Or you can do it this way (Fast custom binary search with comparison built in, and no bitwise complement needed):
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;
}
Then here is an adapted version of my code to insert ranges:
int insertIdx=GetInsertIndex(ranges,range.MinValue);
if (insertIdx < ranges.Count && ranges[insertIdx].MinValue <= range.MaxValue)
ranges[insertIdx] = CombineRanges(range, ranges[insertIdx]);
else
ranges.Insert(insertIdx, range);
if (insertIdx > 0 && ranges[insertIdx - 1].MaxValue >= range.MinValue)
{
ranges[insertIdx - 1] = CombineRanges(range, ranges[insertIdx - 1]);
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)
);
}
|
|
|
|
|
Excellent, I see how its all going to fit together. When I get the index to insert the new Range will be it like this?
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?
Yeah, I had an article written for version 1.0. Version 1.0 was slow and limited. If you wanted to do copy and paste operations or undo/redo operations you had to type a lot of code to work with the control. I made a hex editor to go along with it and I realized that it wasn't as good as I want it to be. Its still good but not good enough. It had too many loops and and arrays, it was inefficient. The very core of the control is called the Data class and it does the hard work, its the smallest class in the program but all other code is wrapped around it and its the most performance critical part. Thats what all this is going into, the core. Then I can build the public API and UI part of the control which is much easier especially since I have an extensive API (from 1.0) that only needs slight additions and modifications.
Implementing binary search and sorting seems pretty simple. Hopefully it will stay that way when I'm actually implementing it. Thanks for your help.
█▒▒▒▒▒██▒█▒██
█▒█████▒▒▒▒▒█
█▒██████▒█▒██
█▒█████▒▒▒▒▒█
█▒▒▒▒▒██▒█▒██
|
|
|
|
|
I think I got it. I just want to share the code in case you or someone else finds that its flawed or something.
UPDATE: I am currently testing it and it seems to work as planned. I think this should work for about any control that selects sequential data such as a text box or whatever you can think of.
public void SelectData(long start, long end)
{
bool addNewRange = true;
byte inc = 0;
int insertIndex = _selected.BinarySearch(new Range(start, 0));
if (insertIndex < 0)
insertIndex = ~insertIndex;
if (_selected.Count > 0)
{
if (_selected.Count == insertIndex)
{
insertIndex--;
inc = 1;
}
if (end >= _selected[insertIndex].MinValue - 1)
{
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);
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 > _selected[i].MaxValue)
{
_selected.RemoveAt(i);
i--;
}
}
}
}
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));
}
-- modified at 1:38 Thursday 4th January, 2007
-- modified at 21:34 Thursday 4th January, 2007
-- modified at 22:11 Thursday 4th January, 2007
█▒▒▒▒▒██▒█▒██
█▒█████▒▒▒▒▒█
█▒██████▒█▒██
█▒█████▒▒▒▒▒█
█▒▒▒▒▒██▒█▒██
|
|
|
|
|
I know.. I know... Place your ones wherever
ss
Brad
Australian
-CAUTION-
The previous statement may contain traces of PHP, and by reading this statement you negate the right to vote me down.
|
|
|
|
|
I go away for a bit and I come back to find that the powers-that-be have granted my request! Thanks Chris! I will post some things here when I get back into the swing of coding after Christmas.
|
|
|
|
|
Umm, excluding zero and one that is.
Sheesh, the math one isn't used much except by me. Where's that geek icon when you need it?
"Marge, don't discourage the boy! Weasling out of things is important to learn. It's what separates us from the animals! Except the weasel." - Homer Simpson
Web - Blog - RSS - Math - LinkedIn - BM
|
|
|
|
|
two & three are suffering about your discrimination. Though not perfects, they think to be square too...
If the Lord God Almighty had consulted me before embarking upon the Creation, I would have recommended something simpler.
-- Alfonso the Wise, 13th Century King of Castile.
|
|
|
|
|
Bassam Abdul-Baki wrote: he math one isn't used much except by me
I visit the Math/Algorithms forum a bit, but not a whole bunch going on there. I've wondered about putting math quiz questions in there to help keep people's math skills sharp...
Some people have a memory and an attention span, you should try them out one day. - Jeremy Falcon
|
|
|
|
|
As long as the maths questions are not too difficult. Remember not every programmer is a maths genius, and many don't have a need to be.
modified 1-Aug-19 21:02pm.
|
|
|
|
|
Richard A. Abbott wrote: Remember not every programmer is a maths genius, and many don't have a need to be.
I figured maybe something of different challenge levels. I could only go as far as calculus or linear algebra. Any partial differential equations questions would get me :->
Some people have a memory and an attention span, you should try them out one day. - Jeremy Falcon
|
|
|
|
|
Try Sudoku or logic puzzles. Those may make for an interesting challenge.
"Marge, don't discourage the boy! Weasling out of things is important to learn. It's what separates us from the animals! Except the weasel." - Homer Simpson
Web - Blog - RSS - Math - LinkedIn - BM
|
|
|
|
|
Bassam Abdul-Baki wrote: Try Sudoku or logic puzzles.
Yep, they are a lot of fun. I got a Kakuro[^] puzzle book for Christmas and it's pretty addictive
Some people have a memory and an attention span, you should try them out one day. - Jeremy Falcon
|
|
|
|
|
Played that once. Make's Sudoku look like child's play. There's an interesting Sudoku[^] client here that you can try. Check the messages for the executable.
"Marge, don't discourage the boy! Weasling out of things is important to learn. It's what separates us from the animals! Except the weasel." - Homer Simpson
Web - Blog - RSS - Math - LinkedIn - BM
|
|
|
|
|
Bassam Abdul-Baki wrote: There's an interesting Sudoku[^] client here that you can try.
I'll look at it closer later today. Looks really cool
|
|
|
|
|
|
That looks really fun
|
|
|
|
|
I don't use it to ask or answer questions but to post interesting math articles I've read. Would be nice if others started doing that too.
"Marge, don't discourage the boy! Weasling out of things is important to learn. It's what separates us from the animals! Except the weasel." - Homer Simpson
Web - Blog - RSS - Math - LinkedIn - BM
|
|
|
|
|
Bassam Abdul-Baki wrote: Would be nice if others started doing that too.
I'll try to make more effort to help you add to the interesting articles part
Some people have a memory and an attention span, you should try them out one day. - Jeremy Falcon
|
|
|
|
|
PaulC1972 wrote: I'll try to make more effort to help you add to the interesting articles part
By all means.
PaulC1972 wrote: Some people have a memory and an attention span, you should try them out one day.
Saw this in the email reply and I wondered how I pissed you off.
"Marge, don't discourage the boy! Weasling out of things is important to learn. It's what separates us from the animals! Except the weasel." - Homer Simpson
Web - Blog - RSS - Math - LinkedIn - BM
|
|
|
|
|
Bassam Abdul-Baki wrote: Saw this in the email reply and I wondered how I pissed you off.
You didn't piss me off. It is a sig from one post by Jeremy Falcon...It is getting old, so back to my one favorite Star Wars quote
That's no moon, it's a space station. - Obi-wan Kenobi
|
|
|
|
|
I figured that out when I saw the message, but the email does't use HTML so I wasn't sure until I opened it.
"Marge, don't discourage the boy! Weasling out of things is important to learn. It's what separates us from the animals! Except the weasel." - Homer Simpson
Web - Blog - RSS - Math - LinkedIn - BM
|
|
|
|
|
Good idea. I know it's sad, but I do get off a bit on really good maths sites/texts. I often toyed with the idea of posting things about different (common) algorithms.
the last thing I want to see is some pasty-faced geek with skin so pale that it's almost translucent trying to bump parts with a partner - John Simmons / outlaw programmer
Deja View - the feeling that you've seen this post before.
|
|
|
|
|
Do you use design patterns?
I used Composite and Singleton , occasionally.
If the Lord God Almighty had consulted me before embarking upon the Creation, I would have recommended something simpler.
-- Alfonso the Wise, 13th Century King of Castile.
|
|
|
|