行/列の挿入/削除の問題についてさらに考えた後、有望に見えるものを思いつきました。
最初に、少なくとも 1 つの空でないセルを持つ、すべての水平インデックスとすべての垂直インデックスを含む 2 つの並べ替えられたデータ構造 (検索ツリーなど) を作成して維持します。
このテーブルの場合:
ABCDE
1
2*
3 % #
4
5 $
あなたが持っているでしょう:
- A、B、D、E - 水平インデックスを使用
- 2,3,5 - 垂直インデックスを使用
これらの A、B、D、E、2、3、5 インデックス値を、前述の 2 つの構造のある種のノード内に格納して、メモリ内のノードのアドレスを知って何かをリンクできるようにします (ここでも、ツリー ノードは完全に適合します)。 )。
各セル (空でない) には、その場所を説明するインデックス ノードへのリンクのペアがあります (ノードへのリンク/参照を示すために & を使用しています)。
- *: &2,&A
- %: &3,&B
- #: &3,&E
- $: &5,&D
テーブルを定義するにはこれで十分です。
では、行/列の挿入をどのように処理するのでしょうか? 新しい行/列インデックスをそれぞれの (水平または垂直) インデックス データ構造に挿入し、その後 (= 右または下) にインデックス値を更新します。次に、この新しい行/列 (存在する場合) に新しいセルを追加し、それらを適切なインデックス ノードにリンクします。
たとえば、行 3 と行 4 の間に行を挿入し、@ を含むセルを 4C (新しい行) に追加します。
ABCDE
1
2*
3 % #
4 @ <- new row 4
5 <- used to be row 4
6 $ <- used to be row 5
インデックス構造は次のようになります。
- A,B,C(new),D,E - 横方向のインデックスを使用
- 2,3,4(新規),6(以前は 5) - 垂直インデックスを使用
セルは、次のようにインデックス ノードにリンクされます。
- *: &2,&A - 前と同じ
- %: &3,&B - 前と同じ
- #: &3,&E - 前と同じ
- @: &4,&C - 新しいインデックス ノード 4 および C にリンクする新しいセル
- $: &6,&D - 以前は &5,&D
しかし、$ セルを見てください。以前と同じ 2 つの物理ノードを指していますが、垂直/行ノードにインデックス 5 ではなくインデックス 6 が含まれているだけです。
$ セルの下に 100 個のセル ノードがある場合、たとえば空でない 5 行のみを占めている場合、100 ではなく、行/垂直インデックス データ構造の 5 つのインデックスのみを更新する必要があります。
同様の方法で行と列を削除できます。
さて、これを便利にするには、すべてのセルをその座標で見つけられるようにする必要もあります。
そのために、すべてのキーがインデックス ノードのアドレスの組み合わせであり、値がセル データ (またはセル データ自体) の場所である、別の並べ替えられたデータ構造 (これもおそらく検索ツリー) を作成できます。
これで、セル 3B に到達したい場合は、インデックス データ構造で 3 と B のノードを見つけ、それらのアドレス &3 と &B を取得し、それらを &3*2 32 +&B に結合し、それを検索キーとして使用します。先ほど定義した 3 番目のデータ構造の % セル。(注: 2 32は、実際にはビット単位の 2 ポインター サイズであり、システムによって異なる場合があります。)
他のセルに何が起こっても、% セルのインデックスが 3B から別のものに変わっても、% のセル リンクのアドレス &3 と &B は変わりません。
これに基づいて反復を簡単に開発できます。
マージも実行可能なはずですが、私はそれに集中していません。