C#で循環リストのようなデータ構造を実現したい

Question

実現したいこと

ループ形状の図の線上にいくつかの点を打ったものを扱うツールを開発しています。
適当な点を原点とし、原点から線を辿った距離を一次元の座標値として点の位置を表現しています。

順番に点を見ていったり、隣接する点を取得したりといった操作をするので、
循環リストのようなものを作れば便利では無いかと考えました。
また、foreachで回せて、どんな順で点を登録しても自動で順に並ぶとより都合が良いと思い、
SortedListを継承してCircularListという自作クラスを実装してみたのですが、
不便さの残る結果となってしまったのでアドバイス頂きたいです。

発生している問題・エラーメッセージ

下記にソースコードを示します。
ある程度思っていた動作はするのですが、
foreach文で回すとその都度Reset()関数を呼ばないとインデックス値が初期化されない、
SortedListベースであるため同じ座標値を登録すると重複で例外が発生してしまうなど微妙な結果となりました。
より良い循環リストの実装方法、もしくは循環リスト以外のより良いアプローチがあればご教示頂きたいです。

該当のソースコード

public class CircularList<TKey, TValue> : SortedList<TKey, TValue>, IEnumerator<KeyValuePair<TKey, TValue>>
    {
        /// <summary>
        /// 循環する整列済みリスト
        /// foreachでは原点から一周する(原点は初期値は0で変更可能)
        /// </summary>
        /// <returns></returns>

        private int originIndex;
        private int currentIndex;
        private int numberOfCall;
        private bool firstFlag;

        public CircularList()
        {
            this.originIndex = 0;
            this.currentIndex = -1;
            this.numberOfCall = 0;
            this.firstFlag = true;
        }

        public CircularList(IComparer<TKey> comparer) : base(comparer)
        {
            this.originIndex = 0;
            this.currentIndex = -1;
            this.numberOfCall = 0;
            this.firstFlag = true;
        }

        public int OriginIndex
        {
            get { return this.originIndex; }
            set { this.originIndex = value; }
        }
        
        public void SetOriginIndex()
        {
            this.originIndex = (this.currentIndex + 1) % this.Count;
        }
        public new IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator()
        {
            return this;
        }
        public KeyValuePair<TKey, TValue> Current
        {
            get { return new KeyValuePair<TKey, TValue>(this.Keys[this.currentIndex], this.Values[this.currentIndex]); }
        }
        object System.Collections.IEnumerator.Current
        {
            get { return this; }
        }
        public bool MoveNext()
        {

            if (this.Count > 0)
            {
                this.currentIndex++;
                this.currentIndex %= this.Count;
                this.numberOfCall = 0;
            }
            
            if (this.currentIndex == this.originIndex && !firstFlag)
            {
                this.currentIndex--;
                if (this.currentIndex < 0)
                {
                    this.currentIndex = this.Count - 1;
                }
                firstFlag = true;
                return false;
            }

            firstFlag = false;

            return true;
        }
        public void Reset()
        {
            this.currentIndex = this.originIndex - 1;
            if (this.currentIndex < 0)
            {
                this.currentIndex = this.Count - 1;
            }
            firstFlag = true;
        }
        public void Dispose()
        {

        }

        public KeyValuePair<TKey, TValue> GetNextPair()
        {
            this.numberOfCall++;
            int nextIndex = (this.currentIndex + this.numberOfCall) % this.Count;
            return new KeyValuePair<TKey, TValue>(this.Keys[nextIndex], this.Values[nextIndex]);
        }

        public void ChangeKey(TKey oldKey, TKey newKey)
        {
            TValue value = this[oldKey];
            this.Remove(oldKey);
            this[newKey] = value;
        }
    }

Comments

[KOZ6.0]

用途がよくわからないですが、Enumerator は別クラスにして GetEnumerator が呼ばれるたびにインスタンスを作成する必要があります。
IEnumerator<KeyValuePair<TKey, TValue>> インターフェイスを実装しておけばいいので、内部クラスにしても良いです。

[KOZ6.0]

.NET Framework のソースを見ると、Enumerator は struct になっていますね。
List<T>.GetEnumerator
https://referencesource.microsoft.com/#mscorlib/system/collections/generic/list.cs,5d3accf5b217bdbf
List<T>.Enumerator
https://referencesource.microsoft.com/#mscorlib/system/collections/generic/list.cs,9c3d580a8b7a8fe8

[KOZ6.0]

重複キーを登録できない問題に関しては、SortedList<TKey, TValue> の継承をあきらめるしかなさそうです。
また、複数の同一キーが存在する場合に、
(1) 追加はどの位置に行うのか（前につけるか後ろにつけるか）
(2) ChangeKey の振る舞いは？(同一キーすべて交換するのか、どれかひとつなのか、ひとつならどれを選択する？）
等のふるまいについて決定しておく必要があります。

[hqf00342]

「原点」はサンプルソースの`OriginIndex`(int)ですか？
TKey値を指定するのではなく、SortedListのインデックスのようですが、挿入のたびに原点値がどんどんずれていく気がします。

[KOZ6.0]

列挙の「起点」であって、「原点」は表現がちょっと違うような気がしますね。

Answer 1

なんだか音沙汰が無いですね。とりあえず、以下の２点

(1) foreach文で回すとその都度Reset()関数を呼ばないとインデックス値が初期化されない。
(2) SortedListベースであるため同じ座標値を登録すると重複で例外が発生してしまう。

について解消したクラスを書いてみました。
あとはメソッドを生やすなり、修正するなりしてみてください。

using System;
using System.Collections;
using System.Collections.Generic;

public class CircularList<TKey, TValue>
    : IEnumerable<KeyValuePair<TKey, TValue>>
{
    private readonly IComparer<TKey> comparer;
    private readonly List<TKey> keys;
    private readonly List<TValue> values;
    private int version;
    private int originIndex;
    private const int defaultCapacity = 4;

    public CircularList() : this(defaultCapacity, Comparer<TKey>.Default) { }
    public CircularList(int capacity) : this(capacity, Comparer<TKey>.Default) { }
    public CircularList(IComparer<TKey> comparer) : this(defaultCapacity, comparer) { }

    public CircularList(int capacity, IComparer<TKey> comparer) {
        this.comparer = comparer;
        keys = new List<TKey>(capacity);
        values = new List<TValue>(capacity);
        version = int.MaxValue;
        originIndex = 0;
    }

    public int OriginIndex {
        get {
            return originIndex;
        }
        set {
            if (value > Count || value < 0) {
                throw new ArgumentOutOfRangeException();
            }
            originIndex = value;
        }
    }

    public int Count => keys.Count;

    public TValue this[int index] {
        get {
            return values[index];
        }
        set {
            values[index] = value;
        }
    }

    public TValue[] GetValues(TKey key) {
        var r = GetRange(key);
        var array = new TValue[r.LastIndex - r.FirstIndex + 1];
        for (int i = r.FirstIndex; i <= r.LastIndex; i++) {
            array[i] = this[i];
        }
        return array;
    }

    public bool ContainsKey(TKey key) {
        return (GetIndex(key) >= 0);
    }

    public void Add(TKey key, TValue value) {
        AddCore(key, value);
        version++;
    }

    public void AddRange(IEnumerable<KeyValuePair<TKey, TValue>> keyValues) {
        foreach (var pair in keyValues) {
            AddCore(pair.Key, pair.Value);
        }
        version++;
    }

    private void AddCore(TKey key, TValue value) {
        var index = GetIndex(key);
        if (index < 0) {
            index = ~index;
        } else {
            index = GetLastIndex(key, index) + 1;
        }
        keys.Insert(index, key);
        values.Insert(index, value);
    }

    public void RemoveAt(int index) {
        RemoveCore(index);
        version++;
    }

    public void Remove(TKey key) {
        RemoveCore(key);
        version++;
    }

    private TValue RemoveCore(int index) {
        var value = values[index];
        keys.RemoveAt(index);
        values.RemoveAt(index);
        return value;
    }

    private List<TValue> RemoveCore(TKey key) {
        var removeList = new List<TValue>();
        var r = GetRange(key);
        for (var i = r.LastIndex; i >= r.FirstIndex; i--) {
            removeList.Insert(0, RemoveCore(i));
        }
        return removeList;
    }

    public void ChangeKey(TKey oldKey, TKey newKey) {
        foreach (var value in RemoveCore(oldKey)) {
            AddCore(newKey, value);
        }
        version++;
    }

    private int GetIndex(TKey key) {
        return keys.BinarySearch(key, comparer);
    }

    private struct Range
    {
        public int FirstIndex;
        public int LastIndex;
    }

    private Range GetRange(TKey key) {
        var index = GetIndex(key);
        return new Range() {
            FirstIndex = GetFirstIndex(key, index),
            LastIndex = GetLastIndex(key, index)
        };
    }

    private int GetFirstIndex(TKey key, int index) {
        if (index < 0) return 0;
        while (index > 0 &&
                comparer.Compare(keys[index - 1], key) == 0) {
            index--;
        }
        return index;
    }

    private int GetLastIndex(TKey key, int index) {
        if (index < 0) return -1;
        while (index < keys.Count - 1 &&
                comparer.Compare(keys[index + 1], key) == 0) {
            index++;
        }
        return index;
    }

    public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator() {
        return new Enumerator(this);
    }

    IEnumerator IEnumerable.GetEnumerator() {
        return new Enumerator(this);
    }

    private class Enumerator : IEnumerator<KeyValuePair<TKey, TValue>>
    {
        private readonly CircularList<TKey, TValue> owner;
        private readonly int version;
        private readonly int originIndex;
        private readonly int count;
        private int currentIndex;
        private int numberOfCall;

        public Enumerator(CircularList<TKey, TValue> owner) {
            this.owner = owner;
            version = owner.version;
            originIndex = owner.OriginIndex;
            count = owner.Count;
            Reset();
        }

        public void Reset() {
            currentIndex = originIndex - 1;
            numberOfCall = 0;
        }

        public KeyValuePair<TKey, TValue> Current {
            get {
                var key = owner.keys[currentIndex];
                var value = owner.values[currentIndex];
                return new KeyValuePair<TKey, TValue>(key, value);
            }
        }

        public void Dispose() { }

        public bool MoveNext() {
            if (owner.version != version) {
                throw new InvalidOperationException();
            }
            if (numberOfCall >= count) {
                return false;
            }
            numberOfCall++;
            currentIndex = (currentIndex + 1) % count;
            return true;
        }

        object IEnumerator.Current => Current;
    }
}

Comments

[Motch]

回答ありがとうございます。提案頂いた内容を基に自分なりに修正を加えてみます。