Pythonで循環リスト(circular list; 初期位置リセット可)を作る

いい感じの循環リストがなさそうなので作ってみようというメモ

環境・事前準備

Windows10 64bit
- WSL2
- Docker Desktop 4.17.0 (99724)
- jupyter
  - python 3.10

循環リストとは

[a,b,c] というリストが有ったときに最後まで辿ったらまた最初に戻るようなリストである。あえて図を描くと下のようになる。

graph LR;
  a --> b;
  b --> c;
c --> a;

きっかけは、クロック周期の再現に良いんじゃないかと探していた。

よくあるやり方

itertools.cycle(*iterable*) https://docs.python.org/ja/3/library/itertools.html#itertools.cycle
- 破壊的かつ常に元のコピーを保持するのでメモリ増える。最大2倍？
- 初期位置リセットできない
collections.deque.rotate https://docs.python.org/3/library/collections.html#collections.deque
- 元のコピーは保持しないようなのでメモリが増える心配はない
  - ただし、元のリストに対してd.append(d.popleft())と言う処理をしているので破壊的ではある
- 初期位置にリセットできない

今回は、単純なHEAD位置をもったリストにすればリセット可能で破壊的でもないのが作れそうなのでやってみる

iterableとiteratorの違い

pythonのリストっぽいオブジェクトにはiterableとiteratorの2種類がある。

iterable
- iter(iterable)関数でiteratorになるオブジェクト。
- 代表例：list
- special method のdef __iter__(self)をもつ
- 厳密でないが判定方法は、抽象クラスを使って、isinstance(*iterable_obj*, collections.abc.Iterable ( collections.abc.Iterable )でできる
iterator
- next(iterator)関数で次の要素を取り出せる。
- special method のdef __iter__(self) と def __next__(self) をもつ。つまりiterableでもある。
- 判定方法は同じように、isinstance(*iterator_obj*, collections.abc.Iterator)( collections.abc.Iterator )でできる。ちなみに、IterableでもTrueになる。

※他にも非同期版(aiter)もある

CircularList Classを自作する

以上を踏まえて新しい循環リストを作る。求める機能は以下とする。

next()関数使っても要素は削除されないようにする、つまり、Iterableオブジェクトにする。
ただし、iteratorのように使えたほうが良いのでnext()でシフトして循環していくイテレータを生成するジェネレータを持たせる。
シフト・循環はHead位置を保持して再現する。これだと配列操作はいらないので基本的に処理は軽い。

cl = CircularList(['a', 'b'])
g = cl.generator_for_circ() # Head=0
next(g) # a, Head <- 1
next(g) # b, Head <- 0
next(g) # a, Head <- 1

循環をresetできる機能を追加する
- Headを0にすればいい

cl = CircularList(['a', 'b'])
g = cl.generator_for_circ() # Head=0
next(g) # a, Head <- 1
cl.reset() # Head <- 0 ※実際には再開するとstep分足されるのでその分引く必要あり
next(g) # a, Head <- 1

できたコードは以下である。

メモ代わりの解説

listから継承してもいいが、破壊的な配列操作のオーバーライドとHeadの処理が大変なのであえて抽象クラスIterableから継承してる。
Iterableの継承だと__iter__(self)の記述が必須になる。今回は、iter(self._l)をそのまま返して従来のイテレータの使い方もできるようにしている。
headは中身が見えるgetだけで、書き換えできないように@propertyの設定にしている。
__repr__の設定で、リストの中身が見えるように。
def circ_iterator(self, step=1)で循環リスト用のイテレータを作るジェネレータにしている。基本的にはHead位置の値を返してyieldで止まる。次のループでHeadが更新されることに注意。
indexでアクセスできる（l[0]）ようにsubscratable(__getitem__(self, idx:int))を設定。
- 逆に、値の書き換え（assigment）はできないように__setitem__(self, idx, v)は設定してない
リストの長さ(len())を取れるように__len__(self)を設定している。__iter__の設定だけでは実は返されず、TypeError: object of type * has no len()　になる。