スキマ配列：GapBuffer ゆーのんがあります。
テキストエディタの実装に用いられてたりします。
可変長配列をふたつ用意し、伸長方向を内側に向けて横に並べます。
□□□□□→ ←□□□□
カーソルは左配列の右端(→んとこ) と 右配列の左端(←んとこ) の間に
挟まってると思いねぇ。
要素の追加は左配列に追加すればカーソル直後、
□□□□□■→ ←□□□□
右配列に追加すればカーソル直前てことになるです。
□□□□□→ ←■□□□□
カーソル移動は左配列の末端要素を右配列に移すのと
右配列の末端要素を左配列に移すので実現できます。
□□□□□■→ ←□□□□
□□□□□→ ←■□□□□
...なんでこんなの思い出したかっつーと、
タスクシステムっぽいもの に使えるんじゃないかってーことで。
using System.Collections.Generic;
namespace SilverBouquet.Collections {
public class GapBuffer<T> {
private List<T> firstHalf_ = new List<T>();
private List<T> secondHalf_ = new List<T>();
/// <summary>
/// コンテナ内の要素数
/// </summary>
public int Count { get { return firstHalf_.Count + secondHalf_.Count; }}
/// <summary>
/// コンテナが空ならtrue
/// </summary>
public bool IsEmpty { get { return Count == 0; }}
/// <summary>
/// カーソルが先頭にあればtrue
/// </summary>
public bool AtHead { get { return firstHalf_.Count == 0; }}
/// <summary>
/// カーソルが末尾にあればtrue
/// </summary>
public bool AtTail { get { return secondHalf_.Count == 0; }}
/// <summary>
/// カーソル位置
/// </summary>
public int Point { get { return firstHalf_.Count; }}
/// <summary>
/// カーソル位置の要素
/// </summary>
public T Current {
get { return secondHalf_[secondHalf_.Count-1]; }
set { secondHalf_[secondHalf_.Count-1] = value; }
}
/// <summary>
/// コンストラクタ。コンテナは空
/// </summary>
public GapBuffer() {}
/// <summary>
/// コンストラクタ。コンテナにitemsの全要素を格納し、カーソルは末尾を指す。
/// </summary>
/// <param name="items">格納要素</param>
public GapBuffer(IEnumerable<T> items) {
foreach ( T item in items ) InsertBefore(item);
}
/// <summary>
/// カーソル位置の直前に要素を挿入する。
/// カーソル位置は挿入された要素の位置へ移動する。
/// </summary>
/// <param name="element">挿入する要素</param>
public void InsertBefore(T element) {
firstHalf_.Add(element);
}
/// <summary>
/// カーソル位置の直後に要素を挿入する。
/// カーソル位置は変化しない。
/// </summary>
/// <param name="element">挿入する要素</param>
public void InsertAfter(T element) {
secondHalf_.Add(element);
}
/// <summary>
/// カーソルを一つ進める
/// </summary>
/// <returns>カーソルが末尾に達していればfalse</returns>
public bool MoveNext() {
if ( secondHalf_.Count == 0 ) return false;
T item = secondHalf_[secondHalf_.Count-1];
secondHalf_.RemoveAt(secondHalf_.Count-1);
firstHalf_.Add(item);
return true;
}
/// <summary>
/// カーソルを一つ戻す
/// </summary>
/// <returns>カーソルが先頭に達していればfalse</returns>
public bool MovePrev() {
if ( firstHalf_.Count == 0 ) return false;
T item = firstHalf_[firstHalf_.Count-1];
firstHalf_.RemoveAt(firstHalf_.Count-1);
secondHalf_.Add(item);
return true;
}
/// <summary>
/// カーソルを先頭に移動
/// </summary>
public void MoveToHead() {
while ( !AtHead ) MovePrev();
}
/// <summary>
/// カーソルを末尾に移動
/// </summary>
public void MoveToTail() {
while ( !AtTail ) MoveNext();
}
}
}