環状キュークラス
ジェネリックな環状キューを作ってます。改善点はいろいろありますが、System.Collection.Generic.Queue(T) クラスとメンバ名の同期が取れていないのが一番の改善点でしょうか。なんとなく、ATL の std::queue のほうが頭にあったため、中途半端に混ざってます。
詳細とか改善とか、また書きます (多分)
/// <summary> /// 環状キュークラス /// </summary> /// <typeparam name="TSource">キューの要素</typeparam> public class RingQueue<TSource> : IRingQueue<TSource> { protected List<TSource> _collection; protected int _currentPos = 0; /// <summary> /// コンストラクタ /// </summary> public RingQueue () { _collection = new List<TSource> (); _currentPos = -1; } /// <summary> /// コンストラクタ /// </summary> /// <param name="collection">新しい RingQueue(T) にコピーする要素のコレクション</param> public RingQueue (IEnumerable<TSource> collection) { _collection = new List<TSource> (collection); } #region IRingQueue<TSource> メンバ /// <summary> /// キューに要素を追加する。 /// </summary> /// <param name="item">追加する要素</param> public void Push (TSource item) { lock (_collection) { //HACK: ゼロを判断しなくてよくならないか? var count = _collection.Count; if (count == 0) { _collection.Add (item); _currentPos = 0; } else { var insertPos = (_currentPos + count - 1) % count + 1; _collection.Insert (insertPos, item); _currentPos = (insertPos + 1) % _collection.Count; } } } /// <summary> /// RingQueue(T) の現在の要素を削除して返す。 /// </summary> /// <returns>RingQueue(T) 現在の要素</returns> public TSource Pop () { lock (_collection) { //HACK: 要素がない場合の例外が何が返るか確認のこと。適切でなければ再スローすること。 var item = Peek (); _collection.RemoveAt (_currentPos); if (_collection.Count == 0) _currentPos = -1; else _currentPos = _currentPos % _collection.Count; return item; } } /// <summary> /// RingQueue(T) の現在の要素を削除せずに返す。 /// </summary> /// <returns>RingQueue(T) 現在の要素</returns> public TSource Peek () { //HACK: 要素がない場合の例外が何が返るか確認のこと。適切でなければ再スローすること。 return _collection [_currentPos]; } /// <summary> /// RingQueue(T) を次の要素に進める。 /// </summary> public void MoveNext () { if (IsEmpty) throw new InvalidOperationException ("キューに要素がありません。"); _currentPos = (_currentPos + 1) % _collection.Count; } /// <summary> /// RingQueue(T) からすべての要素を削除する。 /// </summary> public void Clear () { _collection.Clear (); _currentPos = -1; } /// <summary> /// RingQueue(T) に格納されている要素の数を取得する。 /// </summary> public int Count { get { return _collection.Count; } } /// <summary> /// RingQueue(T) が空かどうかを示す値を取得する。 /// </summary> public bool IsEmpty { get { return _collection.Count == 0; } } #endregion /// <summary> /// 指定したコレクションの要素を RingQueue(T) の末尾に追加する。 /// </summary> /// <param name="collection">追加する要素を含むコレクション</param> public void PushRange (IEnumerable<TSource> collection) { lock (_collection) { //HACK: ゼロを判断しなくてよくならないか? var count = _collection.Count; if (count == 0) { _collection.AddRange (collection); _currentPos = 0; } else { var addCount = collection.Count (); var insertPos = (_currentPos + count - 1) % count + 1; _collection.InsertRange (insertPos, collection); _currentPos = (insertPos + addCount) % _collection.Count; } } } #region IEnumerable<TSource> メンバ /// <summary> /// RingQueue(T) を反復処理する列挙子を返す。 /// </summary> /// <returns>コレクションの列挙子</returns> public IEnumerator<TSource> GetEnumerator () { return _collection.Skip (_currentPos).Concat (_collection.Take (_currentPos)).GetEnumerator (); } #endregion #region IEnumerable メンバ /// <summary> /// RingQueue(T) を反復処理する列挙子を返す。 /// </summary> /// <returns>コレクションの列挙子</returns> System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator () { return GetEnumerator (); } #endregion }
class Test { static void Main (string [] args) { RingQueue<int> queue = new RingQueue<int> (); // 出力用 Action write = () => Console.WriteLine ("count: {0}, current item: {1}, {2}", queue.Count, queue.Peek (), queue.Aggregate (new StringBuilder (), (builder, item) => builder.AppendFormat ("[{0}]", item), builder => builder.ToString ())); queue.Push (1); write (); queue.MoveNext (); write (); queue.Push (2); write (); queue.MoveNext (); write (); queue.Push (3); write (); queue.MoveNext (); write (); queue.Pop (); write (); queue.Push (4); write (); queue.MoveNext (); write (); queue. Pop(); write (); } }
トラックバック
- このエントリーにトラックバック:
- http://frog.raindrop.jp/cgi-bin/mt/mt-tb.cgi/2349
コメント