BidirectionalList, IndexedBidirectionalList
BidirectionalList 双方向リスト
IndexedBidirectionalList 双方向リスト(栞付き)
IndexedBidirectionalList はインデクサ[]でのアクセスが早くなっています
Combination
双方向リストの優位性(List と比べて)を検証するためのクラス
Cache
双方向リストと Dictionary を組み合わせた特殊用途のクラス
BidirectionalList.cs
//#define INSPECTION
//#define DIAGNOSTICS
#if INSPECTION || DIAGNOSTICS
using System.Windows.Forms;
#endif
#if DIAGNOSTICS
using System.Diagnostics;
#endif
namespace System.Collections.Generic
{
public class BidirectionalList<T>
{//双方向リスト
protected class Element
{
public T t;
public Element prev, next;
public Element(T t, Element prev, Element next)
{
this.t = t;
this.prev = prev;
this.next = next;
}
}
protected Element top, last;
protected int count;
public int Count
{
get
{
return count;
}
}
public BidirectionalList()
{
Clear();
}
public void Clear()
{
top = last = null;
count = 0;
}
public void Add(T t)
{
count++;
if (last == null)
{
Element e = new Element(t, null, null);
top = last = e;
}
else
{
Element e = new Element(t, last, null);
last.next = e;
last = e;
}
}
public void AddRange(IEnumerable<T> collection)
{
int collection_count;
if (collection == null || (collection_count = collection.Count()) <= 0)
{
return;
}
int i = 0;
if (last == null)
{
Element e = new Element(collection.ElementAt(0), null, null);
top = last = e;
i++;
}
for (; i < collection_count; i++)
{
Element e = new Element(collection.ElementAt(i), last, null);
last.next = e;
last = e;
}
count += collection_count;
}
public void Push(T t)
{
count++;
if (top == null)
{
Element e = new Element(t, null, null);
top = last = e;
}
else
{
Element e = new Element(t, null, top);
top.prev = e;
top = e;
}
}
public T Pop()
{
if (top == null)
{
throw new InvalidOperationException();
}
T t = top.t;
if (top.next == null)
{
top = last = null;
}
else
{
top.next.prev = null;
top = top.next;
}
count--;
return t;
}
public T Pop(int index)
{
if ((uint)index >= (uint)count)
{
throw new IndexOutOfRangeException();
}
T t;
if (index == 0)
{
t = top.t;
if (top.next == null)
{
top = last = null;
}
else
{
top.next.prev = null;
top = top.next;
}
}
else if (index == count - 1)
{
t = last.t;
last.prev.next = null;
last = last.prev;
}
else
{
Element e = At(index);
t = e.t;
e.next.prev = e.prev;
e.prev.next = e.next;
}
count--;
return t;
}
public void RemoveAt(int index)
{
if ((uint)index >= (uint)count)
{
return;
}
if (index == 0)
{
if (top.next == null)
{
top = last = null;
}
else
{
top.next.prev = null;
top = top.next;
}
}
else if (index == count - 1)
{
last.prev.next = null;
last = last.prev;
}
else
{
Element e = At(index);
e.next.prev = e.prev;
e.prev.next = e.next;
}
count--;
}
protected Element At(int index)
{
if (index >= count / 2)
{
Element e = last;
int i = count - 1 - index;
for (; i > 0; i--)
{
e = e.prev;
}
return e;
}
else
{
Element e = top;
int i = index;
for (; i > 0; i--)
{
e = e.next;
}
return e;
}
}
public T this[int index]
{
set
{
if ((uint)index >= (uint)count)
{
throw new IndexOutOfRangeException();
}
Element e = At(index);
e.t = value;
}
get
{
if ((uint)index >= (uint)count)
{
throw new IndexOutOfRangeException();
}
Element e = At(index);
return e.t;
}
}
}
public class IndexedBidirectionalList<T> : BidirectionalList<T>
{//双方向リスト(インデックス付き)
protected List<Element> indexes;
protected int indexes_interval;
public IndexedBidirectionalList(int indexes_interval = 1000)
{
if (indexes_interval <= 1)
{
throw new ArgumentOutOfRangeException();
}
//top = last = null;
//count = 0;
indexes = new List<Element>();
this.indexes_interval = indexes_interval;
}
public new void Clear()
{
base.Clear();
//top = last = null;
//count = 0;
indexes.Clear();
}
public new void Add(T t)
{
count++;
if (last == null)
{
Element e = new Element(t, null, null);
top = last = e;
}
else
{
Element e = new Element(t, last, null);
last.next = e;
last = e;
if (count > (indexes.Count + 1) * indexes_interval)
{
indexes.Add(e);
}
}
}
public new void AddRange(IEnumerable<T> collection)
{
int collection_count;
if (collection == null || (collection_count = collection.Count()) <= 0)
{
return;
}
int i = 0;
if (last == null)
{
Element e = new Element(collection.ElementAt(0), null, null);
top = last = e;
count++;
i++;
}
int n = (indexes.Count + 1) * indexes_interval;
for (; i < collection_count; i++)
{
Element e = new Element(collection.ElementAt(i), last, null);
last.next = e;
last = e;
count++;
if (count > n)
{
indexes.Add(e);
n += indexes_interval;
}
}
}
public new void Push(T t)
{
if (top == null)
{
Element e = new Element(t, null, null);
top = last = e;
}
else
{
Element e = new Element(t, null, top);
top.prev = e;
top = e;
}
count++;
for (int i = 0; i < indexes.Count; i++)
{
indexes[i] = indexes[i].prev;
}
if (count > (indexes.Count + 1) * indexes_interval)
{
indexes.Add(last);
}
}
protected new Element At(int index)
{
if (index <= indexes_interval)
{
if (count <= indexes_interval && index >= count / 2)
{
Element e = last;
int i = count - 1 - index;
for (; i > 0; i--)
{
e = e.prev;
}
return e;
}
else if (indexes.Count > 0 && index >= indexes_interval / 2)
{
Element e = indexes[0];
int i = indexes_interval - index;
for (; i > 0; i--)
{
e = e.prev;
}
return e;
}
else
{
Element e = top;
int i = index;
for (; i > 0; i--)
{
e = e.next;
}
return e;
}
}
else
{
int n1 = (index / indexes_interval) - 1;
int n2 = index - ((n1 + 1) * indexes_interval);
int n3, n4;
if (n1 < indexes.Count - 1 && n2 >= indexes_interval / 2)
{
n3 = indexes_interval - n2;
Element e = indexes[n1 + 1];
for (; n3 > 0; n3--)
{
e = e.prev;
}
return e;
}
else if ((n3 = index - (indexes.Count * indexes_interval)) > 0 && n3 > (n4 = count - index - 1))
{
Element e = last;
for (; n4 > 0; n4--)
{
e = e.prev;
}
return e;
}
else
{
Element e = indexes[n1];
for (; n2 > 0; n2--)
{
e = e.next;
}
return e;
}
}
}
public new T Pop()
{
if (top == null)
{
throw new InvalidOperationException();
}
T t = top.t;
if (top.next == null)
{
top = last = null;
}
else
{
top.next.prev = null;
top = top.next;
}
count--;
for (int i = 0; i < indexes.Count; i++)
{
indexes[i] = indexes[i].next;
}
if (indexes.Count > 0 && count <= indexes.Count * indexes_interval)
{
indexes.RemoveAt(indexes.Count - 1);
}
return t;
}
public new T Pop(int index)
{
if ((uint)index >= (uint)count)
{
throw new IndexOutOfRangeException();
}
T t;
if (index == 0)
{
t = top.t;
if (top.next == null)
{
top = last = null;
}
else
{
top.next.prev = null;
top = top.next;
}
}
else if (index == count - 1)
{
t = last.t;
last.prev.next = null;
last = last.prev;
}
else
{
Element e = At(index);
t = e.t;
e.next.prev = e.prev;
e.prev.next = e.next;
}
count--;
for (int i = (index - 1) / indexes_interval; i < indexes.Count; i++)
{
indexes[i] = indexes[i].next;
}
if (indexes.Count > 0 && count <= indexes.Count * indexes_interval)
{
indexes.RemoveAt(indexes.Count - 1);
}
return t;
}
public new void RemoveAt(int index)
{
if ((uint)index >= (uint)count)
{
return;
}
if (index == 0)
{
if (top.next == null)
{
top = last = null;
}
else
{
top.next.prev = null;
top = top.next;
}
}
else if (index == count - 1)
{
last.prev.next = null;
last = last.prev;
}
else
{
Element e = At(index);
e.next.prev = e.prev;
e.prev.next = e.next;
}
count--;
for (int i = (index - 1) / indexes_interval; i < indexes.Count; i++)
{
indexes[i] = indexes[i].next;
}
if (indexes.Count > 0 && count <= indexes.Count * indexes_interval)
{
indexes.RemoveAt(indexes.Count - 1);
}
}
public new T this[int index]
{
set
{
if ((uint)index >= (uint)count)
{
throw new IndexOutOfRangeException();
}
Element e = At(index);
e.t = value;
}
get
{
if ((uint)index >= (uint)count)
{
throw new IndexOutOfRangeException();
}
Element e = At(index);
return e.t;
}
}
}
public static class Combination
{
#if DIAGNOSTICS
public class Diagnostics
{
Stopwatch sw;
public long ms;
public Diagnostics()
{
sw = new Stopwatch();
Clear();
}
public void Start()
{
Clear();
sw.Restart();
}
public void Stop()
{
sw.Stop();
ms = sw.ElapsedMilliseconds;
}
public void Clear()
{
ms = 0;
}
}
public static Diagnostics diagnostics = new Diagnostics();
#endif
#if INSPECTION
public static IConsole log;
#endif
public static bool Raffle<T>(IList<T> il, int n, out T[] a, Random rnd = null)
{//IList<T> il から int n 個を抽選して T[] a に取得する
if (il == null || il.Count <= 0 || n <= 0 || il.Count < n)
{
a = null;
return false;
}
#if INSPECTION
if (log == null)
{
a = null;
return false;
}
#endif
a = new T[n];
if (il.Count == n)
{
for (int i = 0; i < n; i++)
{
a[i] = il[i];
}
}
else
{
if (rnd == null)
{
rnd = new Random();
}
#if DIAGNOSTICS
diagnostics.Start();
#endif
IndexedBidirectionalList<int> bil = new IndexedBidirectionalList<int>();
#if INSPECTION
List<int> l2 = new List<int>(il.Count);
#endif
for (int i = 0; i < il.Count; i++)
{
bil.Add(i);
#if INSPECTION
l2.Add(i);
#endif
}
for (int i = 0; i < n; i++)
{
int index1 = rnd.Next(bil.Count);
int index2 = bil.Pop(index1);
a[i] = il[index2];
#if INSPECTION
l2.RemoveAt(index1);
#endif
}
#if DIAGNOSTICS
diagnostics.Stop();
#endif
#if INSPECTION
bool error = false;
if (bil.Count != l2.Count)
{
log.WriteLine("Error1 bl.Count != l.Count");
error = true;
}
else
{
for (int i = 0; i < l2.Count; i++)
{
//if (Comparer<T>.Default.Compare(bil[i], l[i]) != 0)
if (bil[i] != l2[i])
{
log.WriteLine("Error2 index = {0} bl[index] = {1} l[index] = {2}", i, bil[i], l2[i]);
error = true;
break;
}
}
}
if (!error)
{
log.WriteLine("No Error");
}
#endif
}
return true;
}
#if DIAGNOSTICS
public static bool Raffle_List<T>(IList<T> il, int n, out T[] a, Random rnd = null)
{//IList<T> il から int n 個を抽選して T[] a に取得する
if (il == null || il.Count <= 0 || n <= 0 || il.Count < n)
{
a = null;
return false;
}
a = new T[n];
if (il.Count == n)
{
for (int i = 0; i < n; i++)
{
a[i] = il[i];
}
}
else
{
if (rnd == null)
{
rnd = new Random();
}
diagnostics.Start();
List<int> l = new List<int>(il.Count);
for (int i = 0; i < il.Count; i++)
{
l.Add(i);
}
for (int i = 0; i < n; i++)
{
int index1 = rnd.Next(l.Count);
int index2 = l[index1];
a[i] = il[index2];
l.RemoveAt(index1);
}
diagnostics.Stop();
}
return true;
}
public static bool Raffle_BidirectionalList<T>(IList<T> il, int n, out T[] a, Random rnd = null)
{//IList<T> il から int n 個を抽選して T[] a に取得する
if (il == null || il.Count <= 0 || n <= 0 || il.Count < n)
{
a = null;
return false;
}
a = new T[n];
if (il.Count == n)
{
for (int i = 0; i < n; i++)
{
a[i] = il[i];
}
}
else
{
if (rnd == null)
{
rnd = new Random();
}
diagnostics.Start();
BidirectionalList<int> l = new BidirectionalList<int>();
for (int i = 0; i < il.Count; i++)
{
l.Add(i);
}
for (int i = 0; i < n; i++)
{
int index1 = rnd.Next(l.Count);
int index2 = l[index1];
a[i] = il[index2];
l.RemoveAt(index1);
}
diagnostics.Stop();
}
return true;
}
#endif
}
public class Cache<Key, Value>
{
protected class Element
{
public Key key;
public Value value;
public Element prev, next;
public Element(Key key, Value value, Element prev, Element next)
{
this.key = key;
this.value = value;
this.prev = prev;
this.next = next;
}
}
protected Dictionary<Key, Element> dictionary;
protected Element top, last;
protected int max_element_count;
public Cache(int max_element_count)
{
if (max_element_count <= 0)
{
throw new ArgumentOutOfRangeException();
}
dictionary = new Dictionary<Key, Element>();
top = last = null;
this.max_element_count = max_element_count;
}
public int Count
{
get
{
return dictionary.Count;
}
}
public void Clear()
{
dictionary.Clear();
top = last = null;
}
public delegate void CallbackHandler(Value value);
public CallbackHandler Removed = null;
public void Add(Key key, Value value)
{
Element e;
if (top == null)
{
e = new Element(key, value, null, null);
last = e;
}
else
{
e = new Element(key, value, null, top);
top.prev = e;
}
top = e;
if (dictionary.Count >= max_element_count)
{
dictionary.Remove(last.key);
last.prev.next = null;
last = last.prev;
if (Removed != null)
{
Removed(last.value);
}
}
dictionary.Add(key, e);
}
public bool TryGetValue(Key key, out Value value)
{
Element e;
if (!dictionary.TryGetValue(key, out e))
{
value = default(Value);
return false;
}
value = e.value;
if (e.prev != null)
{
if (e.next == null)
{
e.prev.next = null;
last = e.prev;
}
else
{
e.prev.next = e.next;
e.next.prev = e.prev;
}
top.prev = e;
e.next = top;
e.prev = null;
top = e;
}
return true;
}
}
}