C#アルゴリズム入門から走路第1章:リニアメーターのループチェーンテーブル
14380 ワード
シングルサイクルチェーンテーブル
サイクルチェーンテーブルによるジョセフ問題の解決
using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;
namespace DataStruct.List
{
///
///
///
///
class CycleLinkList : IList, IEnumerable
where T : IComparable
{
///
///
///
public Node Head { get; }
///
///
///
public Node P { get; private set; }
///
///
///
private int count;
///
///
///
public CycleLinkList()
{
this.Head = new Node();
this.Head.Next = this.Head;
this.P = this.Head;
}
///
///
///
///
public CycleLinkList(params T[] array)
{
Node p = this.Head = new Node();
foreach (var item in array)
{
Node t = new Node(item);
p.Next = t;
p = p.Next;
this.count++;
}
p.Next = Head;
this.P = p;
}
///
///
///
///
///
public CycleLinkList(IEnumerable array, bool reverse = false)
{
if (reverse)
{
this.Head = new Node();
bool flag=true;
Node t = null;
foreach (var item in array)
{
if(flag)
{
t = new Node(item, Head);
flag = false;
this.P = t;
}
else
t = new Node(item, Head.Next);
Head.Next = t;
this.count++;
}
}
else
{
Node p = this.Head = new Node();
foreach (var item in array)
{
Node t = new Node(item);
p.Next = t;
p = p.Next;
this.count++;
}
p.Next = Head;
this.P = p;
}
}
///
///
///
///
private void RaiseForIndex(ref int index)
{
if (index < 0)
index += this.count;
if (index < 0 || index >= count)
throw new IndexOutOfRangeException(" ");
}
///
///
///
///
private void RaiseForRange(ref int start, ref int end)
{
if (start < 0) start += count;
if (end < 0) end += count;
var cnt = end - start;
if (start < 0 || end < 0 || cnt <= 0 || start >= count || end > count)
throw new IndexOutOfRangeException(" ");
}
///
///
///
///
///
public Node FindPrevious(int index)
{
RaiseForIndex(ref index);
int i = 0;
Node p = this.Head;
while (i < index && p.Next != this.Head)
{
p = p.Next;
i++;
}
return p;
}
/////
///// index
/////
/////
/////
//public Node FindLast(int index)
//{
// if(index<=0)
// throw new IndexOutOfRangeException(" ");
// Node p= this.Head;
// for (int i = 0; i < index; i++)
// {
// if (p.Next == null)
// throw new IndexOutOfRangeException(" ");
// p = p.Next;
// }
// Node q = this.Head;
// while(p.Next!=null)
// {
// p = p.Next;
// q = q.Next;
// }
// return q.Next;
//}
///
///
///
///
///
public T this[int index]
{
get
{
return FindPrevious(index).Next.Data;
}
set
{
FindPrevious(index).Next.Data = value;
}
}
///
///
///
public int Count => this.count;
///
///
///
///
public void Add(T val)
{
Node t = new Node(val, this.Head);
this.P.Next = t;
this.P =t;
this.count++;
}
///
///
///
public void Clear()
{
this.Head.Next = Head;
this.count = 0;
}
///
///
///
///
///
public int? IndexOf(T val)
{
int i = 0;
var p = this.Head;
while (i < this.count)
{
p = p.Next;
if (p.Data.CompareTo(val) == 0)
return i;
i++;
}
return null;
}
///
///
///
///
///
public void Insert(int index, T val)
{
var p = this.FindPrevious(index);
Node temp = new Node(val, p.Next);
p.Next = temp;
this.count++;
}
///
///
///
///
///
public bool IsContains(T val) => this.IndexOf(val) != null;
///
///
///
///
public bool IsEmpty() => this.Head.Next == this.Head;
///
///
///
///
///
public T Remove(int index)
{
var p = this.FindPrevious(index);
var q = p.Next;
var temp = q.Data;
p.Next = q.Next;
this.count--;
// :
if (p.Next == this.Head)
this.P = p;
return temp;
}
///
/// ToString
///
///
public override string ToString()
{
StringBuilder sb = new StringBuilder();
sb.Append("[");
Node p = this.Head;
while (p.Next != this.Head)
{
p = p.Next;
sb.Append(p);
}
sb.Append("]");
return sb.ToString();
}
///
///
///
///
public T[] ToArray()
{
T[] array = new T[count];
int i = 0;
foreach (var item in this)
array[i++] = item;
return array;
}
///
///
///
///
public static explicit operator CycleLinkList(SequenceList ls) => new CycleLinkList(ls.ToArray());
///
///
///
///
public static implicit operator CycleLinkList(T[] array) => new CycleLinkList(array);
///
///
///
///
public IEnumerator GetEnumerator()
{
var p = this.Head;
while (p.Next != this.Head)
{
p = p.Next;
yield return p.Data;
}
}
///
///
///
///
IEnumerator IEnumerable.GetEnumerator()
{
var p = this.Head;
while (p.Next != this.Head)
{
p = p.Next;
yield return p.Data;
}
}
///
///
///
///
public void AddRange(IEnumerable collection)
{
foreach (var item in collection)
{
this.P.Next = new Node(item, this.Head);
P = P.Next;
this.count++;
}
}
///
///
///
///
///
public void RemoveRange(int start, int end)
{
RaiseForRange(ref start, ref end);
Node pstart = this.FindPrevious(start);
Node pend = this.FindPrevious(end - 1);
pstart.Next = pend.Next.Next;
// :
if (pstart.Next==this.Head)
this.P = pstart;
}
///
/// 1 2
///
/// 1
/// 2
///
///
public static bool TryCopy(CycleLinkList t1, out CycleLinkList t2, int start, int end)
{
if (start < 0) start += t1.count;
if (end < 0) end += t1.count;
var cnt = end - start;
if (start < 0 || end < 0 || cnt <= 0 || start >= t1.count || end > t1.count)
{
t2 = null;
return false;
}
t2 = new CycleLinkList();
Node q = t2.Head, p = t1.FindPrevious(start);
while (p.Next != t1.Head && start < end)
{
p = p.Next;
q.Next = new Node(p.Data, null);
q = q.Next;
start++;
}
q.Next = t2.Head;
t2.P = q;
return true;
}
///
///
///
///
///
///
public CycleLinkList this[(int start, int end) t]
{
get
{
TryCopy(this, out CycleLinkList ans, t.start, t.end);
return ans;
}
}
///
///
///
///
///
///
///
public CycleLinkList this[(int start, int end, int step) t]
{
get
{
if (t.step <= 0)
throw new IndexOutOfRangeException(" ");
RaiseForRange(ref t.start, ref t.end);
var ls = new CycleLinkList();
Node q = ls.Head, p = this.FindPrevious(t.start);
int i = 0;
int cnt = 0;
while (p.Next != this.Head && i < t.end)
{
p = p.Next;
if (cnt == t.step || i == t.start)
{
q.Next = new Node(p.Data, null);
q = q.Next;
cnt = 0;
}
i++;
cnt++;
}
q.Next = ls.Head;
ls.P = q;
return ls;
}
}
///
///
///
///
public T Pop()
{
Node p = this.FindPrevious(this.count - 1);
Node q = p.Next;
var temp = q.Data;
p.Next =q.Next;
this.P = p;
this.count--;
return temp;
}
///
///
///
public void Reverse()
{
Node p = this.Head.Next, q = null, t = null;
while (p != null)
{
t = p.Next;
p.Next = q;
q = p;
p = t;
}
}
} サイクルチェーンテーブルによるジョセフ問題の解決
///
///
///
/// n
/// m
///
public static IEnumerable Josephus(int n, int m)
{
CycleLinkList rec = new CycleLinkList(Util.range(1, n));
Node p = rec.Head.Next;
while (p.Next != p)
{
for (int i = 1; i < m - 1; ++i)
p = p.Next;
Node q = p.Next;
yield return q.Data;
p.Next = q.Next;
p = p.Next;
}
yield return p.Data;
}
}