Determine Groups and Children In Collection

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 position)
{
return false; //We passed the position, this is no group item
}
else
{
return true; //The p

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 groupMap = new Dictionary();
    private IDictionary> childMap = new Dictionary>();
    private HashSet childIndexSet = new HashSet();
    private HashSet groupIndexSet = new HashSet();

    public GroupChildIndex(List 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();
                }

                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 list = new List()
            {
                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.

StackExchange Code Review Q#153119, answer score: 2