Greg Young [MVP]

Had someone ask an interesting question the other day ... they wanted to serialize call stacks with data in an object, obviously this can't be done. My initial response was to tell them to use a state machine to get around this but it turned out they were doing a depth first search. Since it was a large depth first search they wanted to remember where they were and survive process shut down. I hacked together something in a few minutes as an example.

I am just throwing this code up so I don't lose it and it may be of use to someone else in the future, it is a resumable depth first search. You could do this on an object graph etc so long as the traversal maintains a reference to the graph (so when serialized/deserialized the external objects came back the same). Code is just a simple example of using a crumb trail to remember where you were in recursion so you can re-enter where you left.

 Note this is not thread safe and will only work for one thread. You could make this much more generic, its a quick example on the key feature.

    public class PositionSavingTraversal<T>
    {
       
        private List<T> m_Data;
        private int[] m_Positions;
        public PositionSavingTraversal(IEnumerable<T> _Data)
        {
            m_Data = new List<T>(_Data); //copy to our local list
            m_Positions = new int[m_Data.Count];
        }

        public void Recurse()
        {
            RecurseInternal(0);
            Console.WriteLine("Recursion completed");
        }

        public void RecurseInternal(int _CurrentDepth)
        {
            if (_CurrentDepth == m_Data.Count)
            {
                return;
            }
            if (m_Positions[_CurrentDepth] == m_Data.Count)
            {
                m_Positions[_CurrentDepth] = 0;
            }
            while (m_Positions[_CurrentDepth] < m_Data.Count)
            {
                if (m_Data.Count - _CurrentDepth > 7)
                {
                    Console.WriteLine(new string('\t', _CurrentDepth) + m_Positions[_CurrentDepth]);
                }
                RecurseInternal(_CurrentDepth + 1);
                m_Positions[_CurrentDepth]++;
            }
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            int[] test = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
            PositionSavingTraversal<int> foo = new PositionSavingTraversal<int>(test);
            while (true)
            {
                Thread t = new Thread(new ThreadStart(foo.Recurse));
                t.Start();
                Console.WriteLine("Thread started, press enter to kill thread");
                Console.ReadLine();
                t.Abort();
                Console.WriteLine("press enter to start new thread and resume");
                Console.ReadLine();
            }
        }
    }
 

p.s. answers are written up for quiz and will be posted tonight so if you want to wager a quick guess today is the time to do it.