First merge numbers and then check generated list is in sorted order:
rangeList
.OrderBy(p => p.FromNumber)
.Select(p => new[] { p.FromNumber, p.ToNumber })
.SelectMany(p => p)
.Aggregate((p, q) => q >= p ? q : int.MaxValue) == int.MaxValue
Question
I have a list of ranges and I would like to find out if they overlap.
I have the following code. Which does not seem to be working. Is there an easier way to do this or a way that works :)
Thanks in advance for any advice.
public partial class Form1 : Form
{
public Form1()
{
InitializeComponent();
}
private IList<Range> rangeList;
private void Form1_Load(object sender, EventArgs e)
{
rangeList.Add(new Range{FromNumber = 0, ToNumber = 100});
rangeList.Add(new Range { FromNumber = 101, ToNumber = 200 });
// this range should over lap and throw an exception
rangeList.Add(new Range { FromNumber = 199, ToNumber = 300 });
}
private bool RangesOverlap()
{
var bigList = new List<List<int>>();
foreach (var range in this.rangeList)
{
bigList.Add(new List<int> { range.FromNumber , range.ToNumber });
}
IEnumerable<IEnumerable<int>> lists = bigList;
return lists
.Where(c => c != null && c.Any())
.Aggregate(Enumerable.Intersect)
.ToList().Count > 0;
}
}
public class Range
{
public int FromNumber { get; set; }
public int ToNumber { get; set; }
}
Solution
First merge numbers and then check generated list is in sorted order:
rangeList
.OrderBy(p => p.FromNumber)
.Select(p => new[] { p.FromNumber, p.ToNumber })
.SelectMany(p => p)
.Aggregate((p, q) => q >= p ? q : int.MaxValue) == int.MaxValue
OTHER TIPS
In the past I faced a challenge where I had to write a validating algorithm for ranges that are created by the user (integers or reals). I had to check 3 things:
So I came up with the following PHP algorithm.
//Let's hardcode an array of integers (it can be of reals as well):
$range = array
(
array(1, 13),
array(14, 20),
array(21, 45),
array(46, 50),
array(51, 60)
);
//And the validation algorithm:
$j = 0;
$rows = sizeof($range);
$step = 1; // This indicates the step of the values.
// 1 for integers, 0.1 or 0.01 for reals
for ($x=0; $x<$rows; $x++)
for ($y=0; $y<$rows; $y++) {
if ( ($range[$x][0] <= $range[$y][0]) AND ($range[$y][0] <= $range[$x][1]) AND ($x != $y) ) {
echo "Ranges intercepting"; // replace with error handling code
break 3;
}
if ( $range[$x][0] > $range[$x][1] ) {
echo "Not valid high & low"; // replace with error handling code
break 3;
}
if ( $range[$x][0] - $range[$y][1] == $step ) {
$j++;
}
}
if ( $j != $rows - $step )
echo "Not continuous"; // replace with error handling code
We iterate through the ranges and compare them in pairs. For each pair we:
If none of the above occurs, we count the difference of end - start points. This number must be equals to the number of ranges minus the step (1, 0.1, 0.01, etc). Otherwise we raise an error.
Hope this helps!
You can fulfill your new requirement with a slight modification of RezaArabs answer:
rangeList
.Select(p => new[] { p.FromNumber, p.ToNumber })
.SelectMany(p => p.Distinct())
.Aggregate((p, q) => q >= p ? q : int.MaxValue) == int.MaxValue
The solution to this problem can be as simple as writing your own RangeList : IList<Range>
whose Add()
method throws an exception when the specified range overlaps with one or more ranges that are already in the collection.
Working example:
class Range
{
public int FromNumber { get; set; }
public int ToNumber { get; set; }
public bool Intersects(Range range)
{
if ( this.FromNumber <= range.ToNumber )
{
return (this.ToNumber >= range.FromNumber);
}
else if ( this.ToNumber >= range.FromNumber )
{
return (this.FromNumber <= range.ToNumber);
}
return false;
}
}
class RangeList : IList<Range>
{
private readonly IList<Range> innerList;
#region Constructors
public RangeList()
{
this.innerList = new List<Range>();
}
public RangeList(int capacity)
{
this.innerList = new List<Range>(capacity);
}
public RangeList(IEnumerable<Range> collection)
{
if ( collection == null )
throw new ArgumentNullException("collection");
var overlap = from left in collection
from right in collection.SkipWhile(right => left != right)
where left != right
select left.Intersects(right);
if ( overlap.SkipWhile(value => value == false).Any() )
throw new ArgumentOutOfRangeException("collection", "The specified collection contains overlapping ranges.");
this.innerList = new List<Range>(collection);
}
#endregion
private bool IsUniqueRange(Range range)
{
if ( range == null )
throw new ArgumentNullException("range");
return !(this.innerList.Any(range.Intersects));
}
private Range EnsureUniqueRange(Range range)
{
if ( !IsUniqueRange(range) )
{
throw new ArgumentOutOfRangeException("range", "The specified range overlaps with one or more other ranges in this collection.");
}
return range;
}
public Range this[int index]
{
get
{
return this.innerList[index];
}
set
{
this.innerList[index] = EnsureUniqueRange(value);
}
}
public void Insert(int index, Range item)
{
this.innerList.Insert(index, EnsureUniqueRange(item));
}
public void Add(Range item)
{
this.innerList.Add(EnsureUniqueRange(item));
}
#region Remaining implementation details
public int IndexOf(Range item)
{
return this.innerList.IndexOf(item);
}
public void RemoveAt(int index)
{
this.innerList.RemoveAt(index);
}
public void Clear()
{
this.innerList.Clear();
}
public bool Contains(Range item)
{
return this.innerList.Contains(item);
}
public void CopyTo(Range[] array, int arrayIndex)
{
this.innerList.CopyTo(array, arrayIndex);
}
public int Count
{
get { return this.innerList.Count; }
}
public bool IsReadOnly
{
get { return this.innerList.IsReadOnly; }
}
public bool Remove(Range item)
{
return this.innerList.Remove(item);
}
public IEnumerator<Range> GetEnumerator()
{
return this.innerList.GetEnumerator();
}
System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
{
return this.innerList.GetEnumerator();
}
#endregion
}
Usage:
IList<Range> rangeList = new RangeList();
try
{
rangeList.Add(new Range { FromNumber = 12, ToNumber = 12 });
rangeList.Add(new Range { FromNumber = 13, ToNumber = 20 }); // should NOT overlap
rangeList.Add(new Range { FromNumber = 12, ToNumber = 20 }); // should overlap
}
catch ( ArgumentOutOfRangeException exception )
{
Console.WriteLine(exception.Message);
}