Determine Groups and Children In Collection

Question

I am currently looking into improving code efficiency while working with a flat string collection in C#. The strings in this collection can be considered a "group" or a "child".

The problem is that the API for this collection is exposed in such a way that the type of each String in the collection is not directly retrievable and must be determined through other properties.

An example collection:

[0] Group Item
[1] Child Item
[2] Child Item
[3] Child Item
[4] Child Item
[5] Group Item
[6] Child Item
[7] Child Item
[8] Group Item
[9] Child Item
[10] Child Item
[11] Child Item

For the collection the following is true:

• Position 0 is always a group item
• There can be 0 to N child items between two group items
• The content of the string does not indicate if a string is a child or a group

The following data is available to determine group/child types:

• ItemCount (The total amount of strings in the collection)
• GroupCount (The total amount of group strings in the collection)
• GetChildCount(int groupIndex) (The amount of child items after the group with groupIndex before the next group item)

The data I need to determine is:

• Group position (The position of a group item based on its zero based index. For example: The group index of 2 should return position 8 from the example collection)

• Child position (The position of a child item based on its zero based group index and child index. For example: The group index of 0 and child index of 3 should return position 4 from the example collection, and a group index of 2 and a child index of 0 should return position 9)

• The reverse of the above (The indexes for the positions)

Currently I have created up the following methods to determine these values:

public bool IsGroupPosition(int position)
{
    int currPosition = 0;
    for(int i = 0;i < GroupCount;i++)
    {
        if(currPosition < position)
        {
            currPosition = currPosition + (GetChildrenCount(i) + 1); //Go to next group item in collection
            continue;
        }
        else if(currPosition > position)
        {
            return false; //We passed the position, this is no group item
        }
        else
        {
            return true; //The position is equal to a group position
        }
    }
    return false;
}

public bool IsChildPosition(int position)
{
    int currPosition = 0;
    for (int i = 0; i < GroupCount; i++)
    {
        if (currPosition == position)
        {
            return false; 
        }
        else if (currPosition > position)
        {
            return true; //We passed the position, this is a child
        }
        else 
        {
            currPosition = currPosition + (GetChildrenCount(i) + 1); //Go to next group in collection
        }
    }
    return false;
}

public int GetGroupIndexForPosition(int position)
{
    int currPosition = 0;
    for (int i = 0; i <= GroupCount; i++)
    {
        int nextGroupPos = currPosition + (GetChildrenCount(i) + 1);
        if (nextGroupPos > position)
        {
            return i;
        }
        currPosition = nextGroupPos;
    }
    return -1;
}

public int GetChildIndexForPosition(int position)
{
    int currPosition = 0;
    for (int i = 0; i < GroupCount; i++)
    {
        int nextGroupPos = currPosition + (GetChildrenCount(i) + 1);
        if (nextGroupPos > position)
        {
            return (position - currPosition) - 1;
        }
        currPosition = nextGroupPos;
    }
    return -1;
}


public int GetPositionForGroup(int groupIndex)
{
    int position = 0;
    for (int i = 0; i < groupIndex; i++)
    {
        position += (GetChildrenCount(i) + 1);
    }
    return position;
}

public int GetPositionForChild(int groupIndex, int childIndex)
{
    return GetPositionForGroup(groupIndex) + childIndex;
}

It's basically enumerating through the collection by a GetChildrenCount(i) amount of steps. And while these methods seem to work fine in terms of functionality, I was wondering if I overlooked something and if there are more efficient ways to determine the group and child positions.

Answer 1

I am not a professional C# programmer, so I will review the algorithm only:

You can preprocess in linear time the group/child list such that the queries run in amortised exact constant time, and that is how:

using System;
using System.Collections.Generic;

public class GroupChildIndex
{
    public const bool GROUP = true;
    public const bool CHILD = false;

    private IDictionary<int, int> groupMap = new Dictionary<int, int>();
    private IDictionary<int, IDictionary<int, int>> childMap = new Dictionary<int, IDictionary<int, int>>();
    private HashSet<int> childIndexSet = new HashSet<int>();
    private HashSet<int> groupIndexSet = new HashSet<int>();

    public GroupChildIndex(List<bool> list)
    {
        int groupIndex = -1;
        int childIndex = 0;
        int currentIndex = 0;

        foreach (bool token in list)
        {
            if (token == GROUP)
            {
                groupMap[++groupIndex] = currentIndex;
                groupIndexSet.Add(currentIndex);
                childIndex = 0;
            }
            else
            {
                if (!childMap.ContainsKey(groupIndex))
                {
                    childMap[groupIndex] = new Dictionary<int, int>();
                }

                childMap[groupIndex][childIndex++] = currentIndex;
                childIndexSet.Add(currentIndex);
            }

            currentIndex++;
        }
    }

    public int GetPositionForGroup(int groupIndex)
    {
        return groupMap[groupIndex];
    }

    public int GetPositionForChild(int groupIndex, int childIndex)
    {
        return childMap[groupIndex][childIndex];
    }

    public bool IsChildPosition(int position)
    {
        return childIndexSet.Contains(position);
    }

    public bool IsGroupPosition(int position)
    {
        return groupIndexSet.Contains(position);
    }
}

And the demo driver:

using System;
using System.Collections.Generic;

namespace GroupChildIndexer
{
    class MainClass
    {
        public static void Main(string[] args)
        {
            List<bool> list = new List<bool>()
            {
                GroupChildIndex.GROUP,
                GroupChildIndex.CHILD,
                GroupChildIndex.CHILD,
                GroupChildIndex.CHILD,
                GroupChildIndex.CHILD,

                GroupChildIndex.GROUP,
                GroupChildIndex.CHILD,
                GroupChildIndex.CHILD,
                GroupChildIndex.GROUP,
                GroupChildIndex.CHILD,

                GroupChildIndex.CHILD,
                GroupChildIndex.CHILD
            };

            GroupChildIndex gci = new GroupChildIndex(list);
            Console.WriteLine(gci.GetPositionForGroup(2));
            Console.WriteLine(gci.GetPositionForChild(0, 3));
            Console.WriteLine(gci.GetPositionForChild(2, 0));

            // Yes to these.
            Console.WriteLine(gci.IsChildPosition(4));
            Console.WriteLine(gci.IsChildPosition(9));

            // No to these.
            Console.WriteLine(gci.IsChildPosition(0));
            Console.WriteLine(gci.IsChildPosition(5));

            // Yes to these.
            Console.WriteLine(gci.IsGroupPosition(0));
            Console.WriteLine(gci.IsGroupPosition(5));

            // No to these.
            Console.WriteLine(gci.IsGroupPosition(4));
            Console.WriteLine(gci.IsGroupPosition(9));
        }
    }
}

(The above returns 8, 4, and 9.)

Hope that helps.

Answer 2

This is a minor point as coderodde has already provided an example of preprocessing but I think it's slightly more than a comment on that answer.

Processing your list of strings into a data structure is definitely the way to be more efficient (I.e. only going through the list once) but it also gives you more chance for error checking.

e.g.

public int GetPositionForChild(int groupIndex, int childIndex)
{
    return GetPositionForGroup(groupIndex) + childIndex;
}

You aren't checking whether it's a valid child index or not. You could do that with your current code but it becomes more complex. Imagine instead:

public int GetPositionForChild(int groupIndex, int childIndex)
{
    // groups could be an array or a dictionary
    Group targetGroup = this.groups[groupIndex];       
    if (targetGroup.Children.Length < childIndex + 1)
    {
        // child doesn't exist. Throw a good error here.
    } 
    return targetGroup.Position + childIndex;
}

Answer 3

Pretty minor I would consider simplify

public int GetGroupIndexForPosition(int position)

To return null if it is not a group

public int? GetGroupIndexForPosition(int position)

Then

public bool IsChildPosition(int position) 
{
     return (GetGroupIndexForPosition(int position) == null);
}

Not wasting much processing and less test.

I think you can do everything with two dictionaries
Only one lookup is not O(1)

forward lookup GroupID to Absolute Position
and a reverse lookup Absolute Position to GroupID

private static int? GetGroupIndexForPosition(int pos)
{
    if (pos < 0)
        return null;
    if (pos >= positionTotalCount)
        return null;
    if (absParPosToGroup.ContainsKey(pos))
        return absParPosToGroup[pos];
    else
    {
        // we have a child 
        // save some space by only storing parent and still is close to O(1)
        KeyValuePair<int, int>? parrentPos = absParPosToGroup.Where(x => x.Key < pos).OrderByDescending(x => x.Key).FirstOrDefault();
        if (parrentPos == null)
            throw new IndexOutOfRangeException("parerntPod == null");
        return ((KeyValuePair< int, int>)parrentPos).Key;
    }
}
private static bool? IsParent(int pos)
{
    if (pos < 0)
        return null;
    if (pos >= positionTotalCount)
        return null;
    return (absParPosToGroup.ContainsKey(pos)); 
}
private static bool? IsChild(int pos)
{
    bool? isParent = IsParent(pos);
    if (isParent == null)
        return null;
    return !isParent;
}
private static int? GetPositionForGroup(int groupID)
{
    if (groupID < 0)
        return null;
    if (groupID >= groupCount)
        return null;
    return groupToParPos[groupID];
}
public int? GetChildIndexForPosition(int position)
{
    int? getGroupIndexForPosition = GetGroupIndexForPosition(position);
    if (getGroupIndexForPosition == null)
        return null;
    int? parentPos = GetPositionForGroup((int)getGroupIndexForPosition);
    if (parentPos == null)
        return null;
    return position - (int)parentPos;
}
public int? GetPositionForChild(int groupIndex, int childIndex)
{
    int? getPositionForGroup = GetPositionForGroup(groupIndex);
    if (getPositionForGroup == null)
        return null;
    if (childIndex > groupSize[childIndex])
        return null;
    return (int)getPositionForGroup + childIndex;
}
private static Dictionary<int, int> groupSize = null;
private static int groupCount = 100;
private static Dictionary<int, int> groupToParPos = null;
private static Dictionary<int, int> absParPosToGroup = null;
private static int positionTotalCount = 0;
public static int? GetChildCount(int groupID)
{
    if (groupID < 0)
        return null;
    if (groupID >= groupCount)
        return null;
    if (groupSize == null)
    {
        Random rand = new Random();
        Dictionary<int, int> groupSize = new Dictionary<int, int>();
        int absPos = 0;
        int childCount;
        for (int i = 0; i < groupCount; i++)
        {
            childCount = rand.Next(10);
            groupSize.Add(i, childCount);
            groupToParPos.Add(i, absPos);
            absParPosToGroup.Add(absPos, i);
            absPos += 1 + childCount;
        }
        positionTotalCount = absPos - 1;
    }
    return groupSize[groupID];
}