Home > Software design >  Fill empty spaces in List of custom type
Fill empty spaces in List of custom type

Time:10-15

I'm searching for easy, preferably LINQ solution to this problem. I did write a method that solves it, but its full scale custom method which also requires sorting, which can potentially slow it down.

public class CustomType
{
   public int X {get;set;}
   public int Y {get;set;}
}

Example list:

List<CustomType> ListOfCustomTypes = new List<CustomType>();

Lets say it contains this:

X Y
0 1
1 2
4 3
5 4
8 4

And now what I mean by "fill empty spaces". I want to add missing elements to the list so it looks like this:

X Y
0 1
1 2
2 0
3 0
4 3
5 4
6 0
7 0
8 4

Y values are irrelevant, problematic part is reading what is in between X.

Here is my current solution:

            ListOfCustomTypes = ListOfCustomTypes.OrderBy(x => x.X).ToList();
            var helper = new List<CustomType>();
            for (int i = 1; i < ListOfCustomTypes.Count; i  ) //check whole list
            {
                if (ListOfCustomTypes[i].X - 1 != ListOfCustomTypes[i - 1].X) //if gap is found
                {
                    var lowerValue = ListOfCustomTypes[i - 1].X;
                    var higherValue = ListOfCustomTypes[i].X;
                    for (int j = lowerValue   1; j < higherValue; j  ) //start filling the gap
                    {
                        var temp = new CustomType();
                        temp.X = j;
                        temp.Y = 0;
                        helper.Add(temp);
                    }
                }
            }
            ListOfCustomTypes.AddRange(helper); //add filled gaps to the list

Honestly this method is probably fine, but I just love LINQ, and it hurts me when I have to process data without it.

CodePudding user response:

You can come up with a simple loop over all sorted items:

  private static IEnumerable<CustomType> Fill(IEnumerable<CustomType> source) {
    int expected = 0; // let compiler be happy, we'll rewrite this value
    bool first = true;        

    foreach (var item in source.OrderBy(x => x.X)) {
      // Filling the hole if any detected
      if (!first && item.X > expected)
        while (item.X > expected)
          yield return new CustomType() { X = expected  , Y = 0 };

      first = false;
      expected = item.X   1;

      yield return item;
    }
  }

Then you can put

   ListOfCustomTypes = Fill(ListOfCustomTypes).ToList();

Edit:

Demo. First we need some CustomType:

class CustomType {
  public int X;
  public int Y;

  public override string ToString() => $"{X,2} : {Y,3}";
}

Then we can put

  List<CustomType> demo = new List<CustomType>() {
    new CustomType() {  X = 0, Y =   0 },
    new CustomType() {  X = 1, Y =  10 },
    new CustomType() {  X = 4, Y =  40 },
    new CustomType() {  X = 5, Y =  50 },
    new CustomType() {  X = 8, Y =  80 },
    new CustomType() { X = 10, Y = 100 },
    new CustomType() { X = 10, Y = 101 },
    new CustomType() { X = 12, Y = 120 },
  };

  string report = string.Join(Environment.NewLine, Fill(demo));

  Console.Write(report);

Outcome:

 0 :   0
 1 :  10
 2 :   0
 3 :   0
 4 :  40
 5 :  50
 6 :   0
 7 :   0
 8 :  80
 9 :   0
10 : 100
10 : 101
11 :   0
12 : 120

CodePudding user response:

This doesn't use LINQ, but it's a bit simpler than the version in your post. (Run it here.)

using System;
using System.Collections.Generic;

public class CustomType
{
    public int X;
    public int Y;
}

public class Program
{
    static List<CustomType> BuildSampleList()
    {
        var testData = new int[]{
            0, 1, 
            1, 2, 
            4, 3, 
            8, 2, 
            5, 5, 
            5, 6
            };

        var list = new List<CustomType>();
        for (var i = 0; i < testData.Length; i  = 2)
        {
            list.Add(new CustomType { X=testData[i], Y=testData[i   1] });
        }

        return list;
    }

    static void print(IEnumerable<CustomType> list)
    {
        foreach (var item in list)
        {
            Console.WriteLine($"{item.X} {item.Y}");
        }
    }
    
    static IEnumerable<CustomType> FillHoles(List<CustomType> list)
    {
        var key = 0;
        var i = 0;

        // in-place sort
        list.Sort((a,b) => a.X.CompareTo(b.X));
        
        while (i < list.Count)
        {
            if (key > list[i].X)
            {
                yield return list[i];
                  i;
            }
            else if (key < list[i].X)
            {
                yield return new CustomType { X=key, Y=0 };
                  key;
            }
            else 
                  key;
        }

    }

    public static void Main()
    {
        var inputList = BuildSampleList();
        print(inputList);
    
        Console.WriteLine("Output:");
        var outputList = FillHoles(inputList);
        print(outputList);

        Console.WriteLine("Done");
    }
}
  • Related