Review
Good things:
IEnumerable in place of List - IEnumerable is more than enough to get the desired data.- Argument checking - never trust the input.
- Use of
StringBuilder - often forgotten(not known) initially but very performance-wise approach.
- Code seems not to have problems at the start or the end of a sequence (forgetting to return some ranges for items at the beginning or the end in some edge cases)
Possible issues:
CompactNumberRanges is an instance method, but doesn't use any instance data. It, perhaps, was your design decision to avoid static helpers, or if it wasn't, then you may want to consider refactoring it into some helper method.
Correctness issues
- The most visible is that while you check the
requiredRangeCount, you do not check numbers variable for being null. It is not critical, but will make your method a bit more bullet-proof and a lot more consistent.
- This code will probably have some problems with duplicates, because inner loop doesn't account for them - it searches for next incremented value each new iteration.
Performance issues:
- Array.IndexOf use - it is implemented with linear search, so it doesn't take advantage of the fact that the array is already ordered.
- And
Array.IndexOf is called multiple times, executing linear search for an item existence of which that can be checked from the array[current index + 1] element.
Style issues
- It has been already mentioned in another answer, but for the sake of completeness, use of nondescriptive variable names shall be pointed :
i is not a problem, because it is just an index, but use of j that actually means next item to find and cv can probably be made more clear with few more letters.
Other(design) issues
- This method actually does two things at once - processes the original sequence to discern ranges of sequential elements and aggregates these ranges into one string. While doing it at the same time may seem simpler, it really combines two concrete and reusable operations into one. It is a mix of a domain-related logic (getting ranges) and presentation logic(creating their string representations)
Alternative generic solution
As an alternative, I can propose to you the following solution that separates range-finding and string formatting logic with LINQ-like extension method that operates using yield sequence generation.
Range class
Create some class to represent a Range (as first and last element or as only the first element). For simplicity we will make ToString method to output exactly the desired format:
public class Range<T>
{
public Range(T start, T end)
{
this.Start = start;
this.End = end;
}
public Range(T startOnly)
{
this.Start = startOnly;
}
public T Start
{
get;
private set;
}
private T m_end;
public T End
{
get
{
if (!this.HasEnd)
throw new InvalidOperationException("Range is a single element");
return this.m_end;
}
private set
{
this.HasEnd = true;
this.m_end = value;
}
}
public Boolean HasEnd
{
get;
private set;
}
public override string ToString()
{
if (this.HasEnd)
return String.Format("{0}-{1}", this.Start, this.End);
return this.Start.ToString();
}
}
Generic method
Create generic method that requires additional Func delegate to determine whether item are in a sequential range. WARNING: This method assumes that collection is either a nondecreasing or a nonincreasing sequence, so unordered sequences must be ordered before calling it:
public static IEnumerable<Range<T>> CompactOrderedRanges<T>(this IEnumerable<T> collection, Int32 minForRange, Func<T, T, Boolean> areNeighbours)
{
if (collection == null)
throw new ArgumentNullException("collection");
if (minForRange < 1)
throw new ArgumentException("minForRange");
if (areNeighbours == null)
throw new ArgumentNullException("areNeighbours");
List<T> range = new List<T>()
{
collection.First()
};
foreach (var item in collection.Skip(1))
{
if (areNeighbours(range.Last(), item))
{
range.Add(item);
continue;
}
if (range.Count >= minForRange)
{
// Yield range
yield return new Range<T>(range.First(), range.Last());
}
else
{
// Yield items in range one by one
foreach (var rangeItem in range)
{
yield return new Range<T>(rangeItem);
}
}
range.Clear();
range.Add(item);
}
// Deal with leftovers. Code duplication, but I am not sure that it can
// be avoided due to yields other than with another helper function
// that returns IEnumerable<Range<T>>, so for now leave it as it is.
if (range.Count >= minForRange)
{
// Yield range
yield return new Range<T>(range.First(), range.Last());
}
else
{
// Yield items in range one by one
foreach (var rangeItem in range)
{
yield return new Range<T>(rangeItem);
}
}
}
Int32 specialization
For simplicity, also create specialized method that deals with IEnumerable<Int32> collections:
public static IEnumerable<Range<Int32>> CompactOrderedRanges(this IEnumerable<Int32> collection, Int32 minForRange)
{
return collection.CompactOrderedRanges(minForRange,
(a, b) =>
{
checked { return Math.Abs(a - b) <= 1; }
});
}
Use
List<List<Int32>> numberSequences = new List<List<Int32>>
{
new List<Int32> { 1 },
new List<Int32> { 1, 2 },
new List<Int32> { 1, 3 },
new List<Int32> { 1, 2, 3 },
new List<Int32> { 1, 5, 3 },
new List<Int32> { 1, 2, 4, 5 },
new List<Int32> { 1, 2, 3, 4, 10 },
new List<Int32> { -5, 1, 2, 3, 4},
new List<Int32> { 1, 2, 3, 4, 7, 11, 12, 13},
new List<Int32> { 1, 2, 1 }, // fails because it is unoredered
new List<Int32> { 1, 1, 2 } // works
};
foreach (var sequence in numberSequences)
{
Console.WriteLine("{0} : {1}",
String.Join(",", sequence),
String.Join(",",
sequence
.CompactOrderedRanges(3)));
}
PROS
- It is quite generic.
- It has LINQ friendly interface, so it can be easily weaved into other scenarios.
- It doesn't use any additional Find(IndexOf) methods and, basically, touches all elements sequentially and at worst two times.
CONS
- It requires the sequence to be ordered (this can be avoided by adding additional comparer delegate parameter and checking the "direction" of items' proximity to each other).
