Templated Hierarchical Repeater Control

using System;
using System.Collections.Generic;
using System.Text;
using System.Text.RegularExpressions;
using DaveControls.HierarchicalControls.Data;

namespace DaveControls.HierarchicalControls.NestedSortable
{
    public class HierarchyDataSorter
    {
        private const string _rootExp = @"node\[(?<position>\d+)\]";
        private const string _idExp = @"\[id\]=(?<id>\d+)";
        private const string _childExp = @"\[children\]\[(?<childLevel{0}>\d+)\]";

        private HierarchyDataItemBase _hierarchyData;
        public HierarchyDataItemBase HierarchyData
        {
            get { return _hierarchyData; }
        }

        private string _serialisedItems;
        public string SerialisedItems 
        {
            get { return _serialisedItems; }
        }

        public HierarchyDataSorter(HierarchyDataItemBase previousHierarchyData, string controlClientId, string serialisedItems)
        {
            _hierarchyData = previousHierarchyData;

            // remove the long client id of the list and replace it with "node" just to make it easier to read
            _serialisedItems = serialisedItems.Replace(controlClientId, "node");
        }


        /// <summary>
        /// This is the method that reorders the HierarchyData object.
        /// </summary>
        /// <param name="currentNavigationId"></param>
        /// <returns></returns>
        public void ReOrderHierarchyData()
        {
            if (String.IsNullOrEmpty(SerialisedItems))
            {
                return;
            }

            if (HierarchyData.Count <= 0)
            {
                return;
            }

            // first step is to flattern the old items and their children into 
            // one long, sequential list
            List<ResolvedHierarchyDataItem> flattenedOldItems = new List<ResolvedHierarchyDataItem>();

            AddResolvedNavigationItems(HierarchyData, flattenedOldItems);

            // second step, create the new structure with the old items wrapped in ResolvedHierarchyDataItem objects
            ResolvedHierarchyDataItem newNavItems = new ResolvedHierarchyDataItem(HierarchyData);

            // puts the data items at the first level into the new object in their correct positions
            GetNewRootItems(flattenedOldItems, newNavItems);

            // now add the children level by level
            GetNewChildItems(flattenedOldItems, newNavItems);

            // we now have the correct structure and order. We just need to remove the ResolvedHierarchyDataItem
            // objects and create the structure with the containing HierarchyDataItemBase objects.
            ReOrderHierarchyData(newNavItems);
        }

        private void AddResolvedNavigationItems(HierarchyDataItemBase oldItems, List<ResolvedHierarchyDataItem> flattenedOldItems)
        {
            for (int i = 0; i < oldItems.Count; i++)
            {
                HierarchyDataItemBase n = oldItems[i];

                ResolvedHierarchyDataItem newResolvedItem = new ResolvedHierarchyDataItem(n);

                // add the item
                flattenedOldItems.Add(newResolvedItem);

                // then add all of its children
                if (n.Count > 0)
                {
                    AddResolvedNavigationItems(n, flattenedOldItems);
                }
            }
        }

        private void GetNewRootItems(List<ResolvedHierarchyDataItem> flattenedOldItems, ResolvedHierarchyDataItem newItemsRoot)
        {
            Regex rootLevelRegEx = new Regex(_rootExp + _idExp, RegexOptions.Compiled);

            MatchCollection rootMatches = rootLevelRegEx.Matches(SerialisedItems);

            foreach (Match m in rootMatches)
            {
                int newPosition = Convert.ToInt32(m.Groups["position"].Value);
                int oldPosition = Convert.ToInt32(m.Groups["id"].Value);

                if (newItemsRoot.ResolvedChildren.ContainsKey(newPosition))
                {
                    throw new NavigationDeserializerException(SerialisedItems, m.Value, "Attempting to add item " + newPosition + " to the list when there is already an item at this position");
                }

                if (oldPosition >= flattenedOldItems.Count)
                {
                    throw new NavigationDeserializerException(SerialisedItems, m.Value, "Cannot find old item at position " + oldPosition + ". There are only " + flattenedOldItems.Count + " in the list");
                }

                newItemsRoot.ResolvedChildren.Add(newPosition, flattenedOldItems[oldPosition]);
            }
        }

        private void GetNewChildItems(List<ResolvedHierarchyDataItem> flattenedOldItems, ResolvedHierarchyDataItem newItems)
        {
            bool hasMatches = true;
            int depth = 0;

            while (hasMatches)
            {
                depth++;

                // create regEx expression for the depth level
                StringBuilder sb = new StringBuilder(_rootExp);

                for (int i = 0; i < depth; i++)
                {
                    sb.Append(String.Format(_childExp, i.ToString()));
                }
                sb.Append(_idExp);

                Regex childMatchRegEx = new Regex(sb.ToString(), RegexOptions.Compiled);

                MatchCollection childMatches = childMatchRegEx.Matches(SerialisedItems);

                hasMatches = childMatches.Count > 0;

                // iterate through matches if there are any
                foreach (Match m in childMatches)
                {
                    int newRootPosition = Convert.ToInt32(m.Groups["position"].Value);
                    int oldPosition = Convert.ToInt32(m.Groups["id"].Value);

                    if (!newItems.ResolvedChildren.ContainsKey(newRootPosition))
                    {
                        throw new NavigationDeserializerException(SerialisedItems, m.Value, "Attempting to add a child to root level " + newRootPosition + " when it does not exist");
                    }

                    // the new child list is the list that the new item is to be added to. Recurse through the resolved children lists to locate
                    // the correct one
                    SortedList<int, ResolvedHierarchyDataItem> newChildList = newItems.ResolvedChildren[newRootPosition].ResolvedChildren;

                    for (int j = 0; j < depth; j++)
                    {
                        string groupName = String.Format("childLevel{0}", j);
                        int newPosition = Convert.ToInt32(m.Groups[groupName].Value);

                        if (j < depth - 1)
                        {
                            // this is a [children][n] match in the string that is not the last one. We need to just locate the sublist
                            // that should already exist
                            if (!newChildList.ContainsKey(newPosition))
                            {
                                throw new NavigationDeserializerException(SerialisedItems, m.Value, "Cannot get child item " + newPosition + " because it does not exist");
                            }
                            else
                            {
                                newChildList = newChildList[newPosition].ResolvedChildren;
                            }
                        }
                        else
                        {
                            // this is the last [children][n] in the string - it is the position we are adding
                            if (newChildList.ContainsKey(newPosition))
                            {
                                throw new NavigationDeserializerException(SerialisedItems, m.Value, "Attempting to add leaf " + newPosition + " when it already exists");
                            }

                            if (oldPosition >= flattenedOldItems.Count)
                            {
                                throw new NavigationDeserializerException(SerialisedItems, m.Value, "Cannot find old item at position " + oldPosition + ". There are only " + flattenedOldItems.Count + " in the list");
                            }

                            newChildList.Add(newPosition, flattenedOldItems[oldPosition]);
                        }
                    }
                }
            }
        }

        private void ReOrderHierarchyData(ResolvedHierarchyDataItem newResolvedItems)
        {
            HierarchyDataItemBase root = newResolvedItems.OriginalDataItem;

            // remove old children from the original object
            root.Clear();

            for (int i = 0; i < newResolvedItems.ResolvedChildren.Keys.Count; i++)
            {
                int key = newResolvedItems.ResolvedChildren.Keys[i];
                ResolvedHierarchyDataItem res = newResolvedItems.ResolvedChildren[key];

                root.Add(res.OriginalDataItem);

                ReOrderHierarchyData(res);
            }
        }
    }

    [global::System.Serializable]
    public class NavigationDeserializerException : Exception
    {
        //
        // For guidelines regarding the creation of new exception types, see
        //    http://msdn.microsoft.com/library/default.asp?url=/library/en-us/cpgenref/html/cpconerrorraisinghandlingguidelines.asp
        // and
        //    http://msdn.microsoft.com/library/default.asp?url=/library/en-us/dncscol/html/csharp07192001.asp
        //

        private string _serialisedItems;
        public string SerialisedItems 
        {
            get { return _serialisedItems; }
        }

        private string _currentItem;
        public string CurrentItem
        {
            get { return _currentItem; }
        }

        public NavigationDeserializerException(string serialisedItems, string currentItem, string message)
            : base(message)
        {
            _serialisedItems = serialisedItems;
            _currentItem = currentItem;
        }
    }
}