|
ok, untested code (sorry) but I think it should work, in principle...
public struct FATransition : IComparable<FATransition>
{
public int Min;
public int Max;
public FA To;
public FATransition(int min, int max, FA to)
{
if (max < min)
throw new ArgumentOutOfRangeException(nameof(max));
Min = min;
Max = max;
To = to;
}
public FATransition(FA to)
{
Min = Max = -1;
To = to;
}
public int CompareTo(FATransition other)
{
var c = Min.CompareTo(other.Min);
if (c != 0) return c;
return Max.CompareTo(other.Max);
}
}
public class FA : ICollection<FATransition>
{
List<FATransition> _transitions = new List<FATransition>();
public bool IsDeterministic { get; private set; } = true;
int FindIndex(int min)
{
int iMin = 0, iMax = _transitions.Count;
while (iMin + 1 < iMax)
{
int i = (iMin + iMax) / 2;
var t = _transitions[i];
if (t.Min >= min)
iMax = i;
else
iMin = i;
}
return iMin;
}
public void Add(FATransition item)
{
int start = FindIndex(item.Min);
for (int i = _transitions.Count - 1; i >= start; i--)
{
var t = _transitions[i];
if (t.To == item.To && t.Min <= item.Max)
{
item.Max = t.Max;
_transitions.RemoveAt(i);
}
else if (t.To != item.To && t.Min <= item.Max && t.Max > item.Min)
{
IsDeterministic = false;
}
}
_transitions.Insert(start, item);
}
bool ICollection<FATransition>.Remove(FATransition item)
=> throw new NotSupportedException();
public int Count => _transitions.Count;
bool ICollection<FATransition>.IsReadOnly => false;
public void Clear()
{
_transitions.Clear();
IsDeterministic = true;
}
public bool Contains(FATransition item) => _transitions.Contains(item);
public void CopyTo(FATransition[] array, int arrayIndex)
=> _transitions.CopyTo(array, arrayIndex);
public IEnumerator<FATransition> GetEnumerator() => _transitions.GetEnumerator();
IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
}
modified 30-Dec-21 16:27pm.
|
|
|
|
|
Nope, that just does a sorted insert. That's simple, but not what I need.
What do you do when a range overlaps?
You've done nothing in that case. You just insert the range. You aren't merging overlapping ranges that have the same To.
Edit: I see. never mind, I missed it the first time. sorry.
Real programmers use butterflies
|
|
|
|
|
your answer confuses me, it looks like you haven't read the code (lack of sleep perhaps?), or I misunderstand the question (lack of sleep on my part perhaps).
Because the code quite obviously merge overlap range on insert so... could you be more clear on what's wrong?
For clarity I paste the add method again below with added comment
public void Add(FATransition item)
{
int start = FindIndex(item.Min);
for (int i = _transitions.Count - 1; i >= start; i--)
{
var t = _transitions[i];
if (t.To == item.To && t.Min <= item.Max)
{
item.Max = t.Max;
_transitions.RemoveAt(i);
}
else if (t.To != item.To && t.Min <= item.Max && t.Max > item.Min)
{
IsDeterministic = false;
}
}
_transitions.Insert(start, item);
}
|
|
|
|
|
It was my fault - i had since edited my comment accordingly - I missed it the first time through.
Real programmers use butterflies
|
|
|
|
|
I guess brain ache doesn't help!
No worries!
|
|
|
|
|
just amended the Add() method
for (int i = _transitions.Count - 1; i >= start; i--)
obviously count down to start , not 0!
|
|
|
|
|
That is basically what the map does on my post above.
Unless we are misunderstanding something.
Best regards
|
|
|
|
|
I rarely load "ranges" since they rarely make sense as specified; e.g. 100-200; 200-300; etc.
I just load the max values for each range.
"Before entering on an understanding, I have meditated for a long time, and have foreseen what might happen. It is not genius which reveals to me suddenly, secretly, what I have to say or to do in a circumstance unexpected by other people; it is reflection, it is meditation." - Napoleon I
|
|
|
|
|
Well I think? I see what you're saying, but in this case I need the minimums too.
In this case the ranges are Unicode Codepoints, and those are often laid out in runs of related characters, so you wind up, with for example, whitespace being, instead of a hundred individual characters, a series of i don't know, like 3 or 4 ranges.
If it were simply that, I'd store a marker id for each type of range (whitespace, digit, letter, etc), but ranges can and must be added to, removed from and intersected with other ranges.
I have to preserve the entire set of data, not just the maximums.
Real programmers use butterflies
|
|
|
|
|
|
Umm, you dramatically misunderstand the problem.
Unicode categories are not the only ranges I need.
Forget they exist, as they will only confuse things.
Let me put it this way.
ASCII has 127 characters.
UTF32 has 0x10FFFF (however many that is)
If I didn't use ranges, I would have to store each character transition individually.
That is not realistic for unicode. Period.
The way to make it realistic is to use ranges.
Not to use unicode categories, because that wouldn't make sense.
Real programmers use butterflies
|
|
|
|
|
Code Points, Code Points
|
|
|
|
|
yeah yeah, codepoints. point is there are a lot of them.
Real programmers use butterflies
|
|
|
|
|
Yeah; I still don't understand dramatically; particularly the drama.
"Before entering on an understanding, I have meditated for a long time, and have foreseen what might happen. It is not genius which reveals to me suddenly, secretly, what I have to say or to do in a circumstance unexpected by other people; it is reflection, it is meditation." - Napoleon I
|
|
|
|
|
Off topic,
But just wanted to mention that C++20 has std::ranges[^] along with some new additions to <algorithm>[^] that would make this easy.
|
|
|
|
|
That's cool. I heard C# might eventually wind up with something like that too.
Real programmers use butterflies
|
|
|
|
|
Ignore the wrinkle. Instead of trying to ever merge, split into smaller ranges in case of overlap. Exception is if new entry is totally encompassed by existing entry in which case new entry is discarded.
It is only safe to merge if there is not another To that conflicts with that range. For each new entry’s overlap with an existing entry, split both new and existing into matched smaller ranges.
This is classic “bin” (as in bucket) data structure problem with your twist.
[1,5]A
[1,5]B
Insert [3,7]A
[1,3]A
[1,3]B
[3,5]A
[3,5]B
[5,7]A
Or adding another level where the range holds a list which it sounds like you want to avoid.
[1,3] [A,B]
[3,5] [A,B]
[5,7] [A]
Good luck!
|
|
|
|
|
|
Burn the book of Christmas Cracker jokes...
"I have no idea what I did, but I'm taking full credit for it." - ThisOldTony
"Common sense is so rare these days, it should be classified as a super power" - Random T-shirt
AntiTwitter: @DalekDave is now a follower!
|
|
|
|
|
Griff, you're lucky that I am one of the few Americans who actually know what on Earth a Christmas Cracker is...
|
|
|
|
|
Strange, given that: Passengers on commercial flights in and to the United States are explicitly prohibited from carrying Christmas crackers on board or in checked baggage
"I have no idea what I did, but I'm taking full credit for it." - ThisOldTony
"Common sense is so rare these days, it should be classified as a super power" - Random T-shirt
AntiTwitter: @DalekDave is now a follower!
|
|
|
|
|
Okay, well I am from Alabama, we don't have Christmas Crackers.
|
|
|
|
|
Also Griff, read and weep."Quote: To the uninitiated, English crackers seem more suited to a New Year's Eve celebration than to Christmas. Britain's Rather Silly Christmas Tradition - The New York Times "
Also to answer your question.
Christmas crackers are very uncommon in the US. I've gotten two of them in my entire life.
|
|
|
|
|
|
I searched, but cannot find the video of the commercial that immediately sprung to mind. I think it may have been a super bowl ad. Sometime in the 90s. Don't even remember what the commercial was for, but it had a magician and he made a hamster or guinea pig disappear. Then the magician's assistant does a little flourish with her arms next to him and you see the hamster is in her armpit and looks like crazy armpit hair. I laughed so hard and still remember it decades later.
|
|
|
|