Cleaner Algorithm for List of Possibly Intersecting Ranges With Properties

user_12470516 0
Viewed 57

I have these objects with a range and list of properties. My goal is to take a list of these objects and create a new list where no ranges overlap. When two ranges are overlapping the overlapping region can be replaced with an object with the union of the properties. I'm hoping a picture can explain this a little better than words can.

Untangling Of Ranges
enter image description here

I was able to achieve this with the following code however it is rather clunky and uses a goto which I try to avoid. The methodology behind this code is to compare every pair of ranges and if there is an intersection, replace both RangeObjects with up to three RangeObjects:

  • One for the part of rangeObject1 that doesn't intersect rangeObject2
  • One for the part of rangeObject2 that doesn't intersect rangeObject1
  • One for the intersection of rangeObject1 and rangeObject2 with unioned properties.
class RangeObject
    {
        RangeObject(int start, int end, List<object> properties)
        {
            Start = start;
            End = end;
            Properties = properties;
        }
        public int Start { get; set; }
        public int End { get; set; }
        public int Length { get => End - Start; }
        public List<object> Properties { get; }
        public bool IsInRange(int value)
        {
            return value > Start && value < End;
        }
        private List<RangeObject> UntangleRangeList(List<RangeObject> list)
        {
            List<RangeObject> list1 = new List<RangeObject>(list);
            list1.Sort();
            int start = 0;
        startover:
            for (int i = start; i < list1.Count; i++)
            {
                for (int j = i + 1; j < list1.Count; j++)
                {
                    if (list1[i].Start < list1[j].End && list1[j].Start < list1[i].End)
                    {
                        list1.AddRange(UntangleRanges(list1[i], list1[j]));
                        list1.Remove(list1[j]);
                        list1.Remove(list1[i]);
                        goto startover;
                    }
                }
                start++;
            }
            list1.Sort();
            return list1;
        }
        public List<RangeObject> UntangleRanges(RangeObject rangeObject1, RangeObject rangeObject2)
        {
            List<RangeObject> result = new List<RangeObject>();

            //This is to reduce the number of if cases by allowing the asumption that rangeObject1 is first
            if (rangeObject1.Start > rangeObject2.Start || ((rangeObject1.Start == rangeObject2.Start) && (rangeObject1.Length > rangeObject2.Length)))
            {
                RangeObject temp = rangeObject1;
                rangeObject1 = rangeObject2;
                rangeObject2 = temp;
            }

            if (rangeObject1.Start == rangeObject2.Start && rangeObject1.End == rangeObject2.End) //Ranges Equal
            {
                result.Add(new RangeObject(rangeObject1.Start, rangeObject1.End, rangeObject1.Properties.Union(rangeObject2.Properties).ToList()));//Return a RangeObject of Unioned Properties
            }
            else if(rangeObject1.IsInRange(rangeObject2.Start) && rangeObject1.IsInRange(rangeObject2.End))//Range2 contained in Range1
            {
                if (rangeObject1.Start != rangeObject2.Start)
                {
                    result.Add(new RangeObject(rangeObject1.Start, rangeObject2.Start - rangeObject1.Start, rangeObject1.Properties));
                }
                result.Add(new RangeObject(rangeObject2.Start, rangeObject2.Length, rangeObject1.Properties.Union(rangeObject2.Properties).ToList()));
                if (rangeObject1.End != rangeObject2.End)
                {
                    result.Add(new RangeObject(rangeObject2.End, rangeObject1.End - rangeObject2.End, rangeObject1.Properties));
                }
            }
            else if (rangeObject1.IsInRange(rangeObject2.Start))//Range2.Start contained in Range1
            {
                result.Add(new RangeObject(rangeObject1.Start, rangeObject2.Start - rangeObject1.Start, rangeObject1.Properties));
                result.Add(new RangeObject(rangeObject2.Start, rangeObject1.End - rangeObject2.Start, rangeObject1.Properties.Union(rangeObject2.Properties).ToList()));
                result.Add(new RangeObject(rangeObject1.End, rangeObject2.End - rangeObject1.End, rangeObject2.Properties));
            }
            else //No intersection, shouldn't happen
            {
                result.Add(rangeObject1);
                result.Add(rangeObject2);
            }
            return result;
        }
    }

Any ideas on how to achieve this a little more elegantly? Or at least avoid the startover because when I cut up the ranges I end up relocating them to the end and changing the length/order of the list so it's hard to tell what ranges I've compared.

range list c#
2 Answers

The following is one way to get rid of goto:

private List<RangeObject> UntangleRangeList(List<RangeObject> list)
{
    List<RangeObject> list1 = new List<RangeObject>(list);
    list1.Sort();
    int start = 0;

    while (!CheckSomething(list1, ref start)) ;

    list1.Sort();
    return list1;
}

private bool CheckSomething(List<RangeObject> list1, ref int start)
{
    for (int i = start; i < list1.Count; i++)
    {
        for (int j = i + 1; j < list1.Count; j++)
        {
            if (list1[i].Start < list1[j].End && list1[j].Start < list1[i].End)
            {
                list1.AddRange(UntangleRanges(list1[i], list1[j]));
                list1.Remove(list1[j]);
                list1.Remove(list1[i]);
                return false;
            }
        }
        start++;
    }

    return true;
}
user_101327380

For the sake of simplicity I first get a big enough range to include all other ranges, but with an empty Properties field. This is achieved by getting the minimum and maximum value of all ranges.

Then I combine the ranges one after the other with a so-called untangled range list which at the beginning consists of only initialRange. During this process, untangledRanges remains sorted and without any overlapping ranges. So in the end, all the ranges are combined into a list of untangled ranges.

Based on your current code, this is all you need:

class RangeObject
{
    public RangeObject(int start, int end, List<object> properties)
    {
        if (start >= end)
            throw new Exception("'start' must be less than 'end'");

        Start = start;
        End = end;
        Properties = properties;
    }

    public int Start { get; set; }
    public int End { get; set; }
    public int Length { get => End - Start; }
    public List<object> Properties { get; set; }

    public List<RangeObject> SplitAt(int point)
    {
        if (point <= this.Start || point >= this.End)
            return new List<RangeObject> { this };

        var result = new List<RangeObject>();

        result.Add(new RangeObject(this.Start, point, this.Properties));
        result.Add(new RangeObject(point, this.End, this.Properties));

        return result;
    }

    public static List<RangeObject> UntangleRangeList(List<RangeObject> list)
    {
        var initialRange = GetInitialRange(list);

        var untangledRanges = new List<RangeObject> { initialRange };

        foreach (var rangeObject in list)
        {
            ExpandUntangleRanges(untangledRanges, rangeObject);
        }

        return untangledRanges;
    }

    private static void ExpandUntangleRanges(
        List<RangeObject> alreadyUntangledRanges, RangeObject newRange)
    {
        int firstRangeIndex = alreadyUntangledRanges
            .FindIndex(x => x.Start <= newRange.Start && newRange.Start < x.End);

        int lastRangeIndex = alreadyUntangledRanges
            .FindIndex(x => x.Start < newRange.End && newRange.End <= x.End);

        var firstRange = alreadyUntangledRanges[firstRangeIndex];
        if (firstRange.Start < newRange.Start)
        {
            // split the first range
            alreadyUntangledRanges.RemoveAt(firstRangeIndex);
            alreadyUntangledRanges.InsertRange(
                firstRangeIndex, firstRange.SplitAt(newRange.Start));

            firstRangeIndex++;
            lastRangeIndex++;
        }

        var lastRange = alreadyUntangledRanges[lastRangeIndex];
        if (newRange.End < lastRange.End)
        {
            // split the last range
            alreadyUntangledRanges.RemoveAt(lastRangeIndex);
            alreadyUntangledRanges.InsertRange(
                lastRangeIndex, lastRange.SplitAt(newRange.End));
        }

        for (int i = firstRangeIndex; i <= lastRangeIndex; i++)
        {
            alreadyUntangledRanges[i].Properties = alreadyUntangledRanges[i]
                .Properties.Union(newRange.Properties).ToList();
        }
    }

    private static RangeObject GetInitialRange(List<RangeObject> rangeObjects)
    {
        int? start = null;
        int? end = null;

        foreach (var rangeObject in rangeObjects)
        {
            if (start == null || rangeObject.Start < start)
                start = rangeObject.Start;

            if (end == null || rangeObject.End > end)
                end = rangeObject.End;
        }

        if (start == null || end == null)
            return null;

        return new RangeObject(start.Value, end.Value, new List<object>());
    }
}
user_101327380
Related