Grouping into ranges of continuous integers

Question

I have checked other postings including Group by variable integer range using Linq

but i have not found anything that is similar to my question...I am trying to group into integer ranges where the integer sequence is discontinuous. For example, if i have a set of continuous integers from 1-100 and then my set skips 101, i would want to create a record that takes the date from record #1 and #100, where the date from record #1 is the begin date and #100 is the end date.

Each range of continuous integers creates a new record to add to a list of records that indicate the date at the start and end of the range. if the range contains only one integer value (e.g. the integer ranges go from 1-100, 102, and 104-200) the single integer range would have the same start and end date.

Any suggestions?

Answer 1

Here's a sample class I created that might help. It converts a sequence of integers into a set of ranges. The code works in LINQPad.

void Main()
{
    ContiguousNumberLine line = new ContiguousNumberLine();

    List<Int64> testItems = new List<Int64>() { 1, 2, 4, 5, 7, 9, 11, 10, 3, 6, 8, 8 };
    foreach(Int64 item in testItems)
    {
        line.Add(item);
        line.numberLine.Dump(string.Format("After adding {0}", item));
    }

    line.Add(new List<Int64>() { 12, 14, 15, 16 });
    line.numberLine.Dump("After adding 12, 14, 15, 16");
    line.Add(new List<Int64>() { 17, 18, 19, 20 });
    line.numberLine.Dump("After adding 17, 18, 19, 20");

    foreach(var item in line.numberLine)
    {
        Console.WriteLine(string.Format("{0}\t{1}", item.Key, item.Value));
    }
}

// Define other methods and classes here
public class ContiguousNumberLine
{
    public SortedList<Int64, Int64> numberLine { get; private set; }

    public ContiguousNumberLine()
    {
        numberLine = new SortedList<Int64, Int64>();
    }

    public bool IsPresent(Int64 input)
    {
        if (numberLine.ContainsKey(input))
        {
            return true;
        }
        else
        {
            foreach(var numRange in numberLine)
            {
                if (numRange.Key > input)
                {
                    return false;
                }
                if (numRange.Value < input)
                {
                    continue;
                }
                if (numRange.Key <= input && input <= numRange.Value)
                {
                    return true;
                }
            }
            return false;
        }
    }

    public bool IsPresent(List<Int64> input)
    {
        if (IsContiguous(input))
        {
            return IsPresentRange(input.First(), input.Last());
        }
        else
        {
            foreach(Int64 item in input)
            {
                if (this.IsPresent(item))
                {
                    return true;
                }
            }
        }
        return false;
    }

    public bool IsPresentRange(Int64 first, Int64 last)
    {
        // naive implementation
        for(Int64 i = first; i <= last; i++)
        {
            if (this.IsPresent(i))
            {
                return true;
            }
        }
        return false;
    }

    public bool IsContiguous(List<Int64> input)
    {
        Int64? first = null;
        Int64? last = null;
        foreach(Int64 item in input)
        {
            if (first == null)
            {
                first = item;
                last = item;
                continue;
            }
            if (last.Value +1 == item)
            {
                last = item;
                continue;
            }
            else
            {
                return false;
            }
        }
        return true;
    }

    public bool Add(Int64 input)
    {
        if (IsPresent(input))
        {
            return false;
        }
        else
        {
            //numberLine.Add(input, input);
            // extend the last number of an existing range, then check if it bridges the gap to the next range
            KeyValuePair<Int64, Int64>? itemToRemove1 = null;
            KeyValuePair<Int64, Int64>? itemToRemove2 = null;
            KeyValuePair<Int64, Int64> itemToAdd = new KeyValuePair<Int64, Int64>(input, input) ;

            foreach(var numRange in numberLine)
            {
                if (numRange.Value + 1 == input)
                {
                    itemToRemove1 = numRange;
                    itemToAdd = new KeyValuePair<Int64, Int64>(numRange.Key, numRange.Value + 1);
                    continue;
                } else if (itemToRemove1 != null && numRange.Key -1 == input)
                {
                    itemToRemove2 = new KeyValuePair<Int64, Int64>(numRange.Key, numRange.Value);
                    KeyValuePair<Int64, Int64> newRange = new KeyValuePair<Int64, Int64>(itemToAdd.Key, numRange.Value);
                    itemToAdd = newRange;
                    break;
                } else if (numRange.Key - 1 == input)
                {
                    itemToRemove1 = numRange;
                    itemToAdd = new KeyValuePair<Int64, Int64>(input, numRange.Value);
                    break;
                } else if (numRange.Key > input)
                {
                    itemToAdd = new KeyValuePair<Int64, Int64>(input, input);
                    break;
                }
            }

            if (itemToRemove1 != null)
            {
                numberLine.Remove(itemToRemove1.Value.Key);
            }
            if (itemToRemove2 != null)
            {
                numberLine.Remove(itemToRemove2.Value.Key);
            }
            numberLine.Add(itemToAdd.Key, itemToAdd.Value);
            return true;
        }
    }

    public bool Add(List<Int64> input)
    {
        // check if we can use the optimized version
        if (IsContiguous(input))
        {
            return this.AddRange(input.First(), input.Last());
        }
        else
        {
            if(IsPresent(input))
            {
                return false;
            }
            foreach(Int64 item in input)
            {
                this.Add(item);
            }
            return true;
        }

    }

    public bool AddRange(Int64 first, Int64 last)
    {
        //throw new NotImplementedException();
        if(IsPresentRange(first, last))
        {
            return false;
        }
        // naive implementation below (TODO: write optimized version)
        for(Int64 i = first; i <= last; i++)
        {
            this.Add(i);
        }
        return true;
    }

}

Answer 2

You can make an extension method that will do this:

static class EnumerableIntExtensions {
    public static IEnumerable<IEnumerable<T>> ToContiguousSequences<T>(
        this IEnumerable<T> sequence,
        Func<T, T> next
    ) {
        Contract.Requires(sequence != null);
        Contract.Requires(next != null);
        var e = sequence.GetEnumerator();
        if (!e.MoveNext()) {
            throw new InvalidOperationException("Sequence is empty.");
        }
        var currentList = new List<T> { e.Current };
        while (e.MoveNext()) {
            T current = e.Current;
            if (current.Equals(next(currentList.Last()))) {
                currentList.Add(current);
            }
            else {
                yield return currentList;
                currentList = new List<T> { current };
            }
        }
        yield return currentList;
    }
}

Usage:

var sequence = Enumerable.Range(1, 100)
                         .Concat(new[] { 102 })
                         .Concat(Enumerable.Range(104, 97));
var sequences = sequence.ToContiguousSequences(n => n + 1);
foreach(var contiguousSequence in sequences) {
    Console.WriteLine(String.Join(", ", contiguousSequence.Select(n => n.ToString())));
}

Output:

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100
102
104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127, 128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143, 144, 145, 146, 147, 148, 149, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159, 160, 161, 162, 163, 164, 165, 166, 167, 168, 169, 170, 171, 172, 173, 174, 175, 176, 177, 178, 179, 180, 181, 182, 183, 184, 185, 186, 187, 188, 189, 190, 191, 192, 193, 194, 195, 196, 197, 198, 199, 200

Answer 3

I don't know if you'd be able to do this using the provided LINQ functions, but the following function:

public static IEnumerable<IEnumerable<T>> GroupWhile<T>(this IEnumerable<T> values, Func<Int32, Boolean> predicate)
{
    var i = 0;
    var currentSet = new List<T>();
    while (i < values.Count())
    {
        if (predicate(i))
            currentSet.Add(values.Skip(i).First());
        else
        {
            yield return currentSet;
            currentSet = new List<T>(new[] {values.Skip(i).First()});
        }
        i++;
    }
    yield return currentSet;
}

used as follows:

var ints = new[] {1, 2, 4, 5, 7, 8};
var groups = ints.GroupWhile(i => i == 0 || ints[i - 1] == ints[i] - 1).ToList();

may fit the bill.