k.inaba さんの sub/BtsQ.java を C# に移植してみた

Generics > Template なところ - d.y.d.』にあった "sub/BtsQ.java" を C# に書き換えてみました.なんか機械的に置き換えるだけでコンパイルが通ってしまったのが怖いような.

// original version by k.inaba
// http://www.kmonos.net/wlog/85.html#_0753080507

using System;
using System.Linq;
using System.Text;

/// とてもシンプルな単方向リンクリスト(空リストはnullで表す)
/// LispとかHaskellとかOCamlだと組み込みであるやつ
public class List<E>
{
    public readonly E car;
    public readonly List<E> cdr;

    public List(E car, List<E> cdr)
    {
        this.car = car;
        this.cdr = cdr;
    }

    public List<E> reverse()
    {
        List<E> rev = null;
        for (List<E> p = this; p != null; p = p.cdr)
            rev = new List<E>(p.car, rev);
        return rev;
    }
}

/// Queue<List<E>> を実装に使っている Queue<E>
public class Queue<E>
{
    readonly private List<E> head;
    readonly private Queue<List<E>> middle;
    readonly private List<E> tail;

    readonly private int hmSize;
    readonly private int tSize;

    /// 空キューを作成
    public Queue() { head = tail = null; middle = null; hmSize = tSize = 0; }

    /// 先頭要素を返す
    public E top()
    {
        return head.car;
    }

    /// 先頭要素を除いた残りのキューを返す
    public Queue<E> pop()
    {
        return new Queue<E>(head.cdr, middle, tail, hmSize - 1, tSize);
    }

    /// 新しい要素をtailに突っ込んだキューを返す
    public Queue<E> push(E e)
    {
        return new Queue<E>(head, middle, new List<E>(e, tail), hmSize, tSize + 1);
    }

    /// サイズ
    public int size()
    {
        return hmSize + tSize;
    }

    /// コンストラクタ。不変条件を満たすようにメンバを設定
    ///   invariant { hmSize >= tSize
    ///               if hmSize>0 then h!=null }
    private Queue(List<E> h, Queue<List<E>> m, List<E> t, int hms, int ts)
    {
        if (hms >= ts) // head+middle の方が tail より長い場合はほぼそのまま
        {
            if (hms > 0 && h == null)
            {
                head = m.top(); // h は埋めておく
                middle = m.pop();
            }
            else
            {
                head = h;
                middle = m;
            }
            tail = t;
            hmSize = hms;
            tSize = ts;
        }
        else // tail の方が長い場合は tail を head+middle 側に突っ込む
        {
            if (h == null)
            {
                // 修正 --> http://d.hatena.ne.jp/NyaRuRu/20080510/p2#c
                if (m == null || m.size() == 0)
                {
                    head = t.reverse();
                    middle = null;
                }
                else
                {
                    head = m.top();
                    middle = m.pop().push(t.reverse());
                }
            }
            else
            {
                head = h;
                middle = (m == null ? new Queue<List<E>>() : m).push(t.reverse());
            }
            tail = null;
            hmSize = hms + ts;
            tSize = 0;
        }
    }
}

/// てすつ
public static class BtsQ
{
    public static void Main(String[] arg)
    {
        Queue<int> q = new Queue<int>();

        Random rnd = new Random();
        System.Collections.Generic.Queue<int> referenceQ
            = new System.Collections.Generic.Queue<int>();

        for (int i = 0; i != 100; ++i)
        {
            int set = rnd.Next(10) + 5;
            for (int j = 0; j != set; ++j)
            {
                int e = rnd.Next(100);
                q = q.push(e);
                referenceQ.Enqueue(e);
            }

            int get = rnd.Next(q.size());
            for (int j = 0; j != set; ++j)
            {
                int e1 = q.top();
                int e2 = referenceQ.Dequeue();
                Console.WriteLine(e1 + " " + e2 + (e1 == e2 ? "" : "BUG!!!!!!!"));
                q = q.pop();
            }
        }

        while (q.size() > 0)
        {
            int e1 = q.top();
            int e2 = referenceQ.Dequeue();
            Console.WriteLine(e1 + " " + e2 + (e1 == e2 ? "" : "BUG!!!!!!!"));
            q = q.pop();
        }
        if (referenceQ.Count() == 0)
            Console.WriteLine("BUG!!!!!!!");
    }
}

更新履歴

  • 2008年5月10日
    • 初版
  • 2008年5月11日
    • オリジナルバージョンの変更を反映