循環参照検知：続・考察２

昨日の続き、記載通りを素直に実装してみた。とりあえず循環参照の検出は出来ている。

// code coloring/formated by http://manoli.net/csharpformat/
using System;
using Lx.Collections.Generic;

public static class Program
{
    static LinkList<int> CreateList()
    {
        LinkList<int> list = new LinkList<int>(10);
        list.Insert(5)
            .Insert(1)
            .Insert(3)
            .Insert(40)
            .Insert(1)
            .Insert(9);

        return list;
    }

    static void Main()
    {
        // 循環なし
        LinkList<int> list1 = CreateList();
        Console.WriteLine(HasLoop(list1));

        // 距離のある循環による終端
        list1.Next.Next.Next.Next.Next.SetNext(list1.Next.Next.Next);
        Console.WriteLine(HasLoop(list1));

        // 自己循環による終端
        LinkList<int> list2 = CreateList();
        list2.Last.SetNext(list2.Last);
        Console.WriteLine(HasLoop(list2));

        // 完全循環
        LinkList<int> list3 = CreateList();
        list3.Last.SetNext(list3);
        Console.WriteLine(HasLoop(list3));
        
        // 要素数１で自己循環
        LinkList<int> list4 = new LinkList<int>(10);
        list4.Last.SetNext(list4.Last);
        Console.WriteLine(HasLoop(list4));
    }

    static bool HasLoop<T>(LinkList<T> node)
    {
        if (node.Next == null) return false;

        int m = 1;
        while (true)
        {
            // 先頭から m 個の要素を調べる
            LinkList<T> cur = node;
            for (int i = 0; i < m; i++)
            {
                // m - i 個目まで調べる
                int n = HasLoop(cur, m - i);

                // 終端を発見
                if (n < m - i) return (n < 0);

                // 次の要素を調べる
                cur = cur.Next;
            }
            m++;
        }
    }

    /// <param name="m">最大のステップ数</param>
    /// <returns>
    /// 0 以上 : node と終端の間にある要素数<br>
    /// 0 未満 : ループの検出
    /// </returns>
    static int HasLoop<T>(LinkList<T> node, int m)
    {
        if (node.Next == null) return 0;

        int n = 0;
        foreach (LinkList<T> cur in node.Next.Walk())
        {
            n++;

            if (cur == node) return -n;
            if (n == m) break;
        }

        return n;
    }
}