基本情報技術者 2009年 春期 午後 問11
次のJavaプログラムの説明及びプログラムを読んで、設問に答えよ。
〔プログラムの説明〕
ギャップバッファを利用した簡易テキストエディタである。
ギャップバッファとは、編集対象となる文字列の編集箇所に空き領域を作り、そこに文字を挿入する機構をもつバッファのことである。一般に、テキストの編集時には、文字の挿入、削除などの変更は局所的に集中することが多く、編集箇所にあらかじめ空き領域を作っておくと効率よく変更を行うことができるという利点がある。ギャップバッファ内の空き領域をギャップといい、ギャップバッファ内の文字列をテキストという。ここで、ギャップは、ギャップバッファ内に一つしか存在しない。ただし、文字の挿入によって、ギャップがない状態になる場合がある。
テキストの表示イメージとギャップバッファを図1に示す（網掛けの部分がギャップである）。
クラスGapBufferはギャップバッファの機能を実現する。このクラスの使用者は、テキストを仮想的に連続する文字列として扱うことができ、ギャップの位置やサイズを意識せずに文字の挿入や削除の処理を行う。このとき、図1①のように各文字はオフセット値（offset）で指定し、テキストの最初の文字はオフセット値0、テキストの最後の文字はオフセット値“テキストの文字数−1”で指定する。
図1②は、配列buffer内におけるテキストの物理的な表現の例である。フィールドgapOffsetとgapSizeは、それぞれギャップの先頭位置とギャップのサイズを表す。
図1②の状態から“プログラム”と“説明”の間に“の”を挿入する手順を図2に示す。
まず、“プロ”の直後に“グラム”を移動することで、ギャップを“プログラム”と“説明”の間に移動する（図2②）。ギャップの先頭に“の”を格納する（図2③）。この操作によって、ギャップのサイズは1文字分小さくなり、ギャップの先頭位置は1文字分後ろへずれる。
次に、図2③の状態から“プログラムの”の“グ”を削除する手順を図3に示す。
まず、“ラムの”を“説明”の直前に移動することで、ギャップを“プログ”と“ラムの説明”の間に移動する（図3②）。ギャップの先頭位置を1文字分前にずらし、ギャップのサイズを1文字分増やす（図3③）。
クラスGapBufferは、次のコンストラクタ及びメソッドをもつ。
(1) コンストラクタは引数initialTextで指定された文字列をテキストの初期値としてギャップバッファを生成する。ギャップは、テキストの前に作られる。
(2) メソッドinsertは、メソッドconfirmGapを呼んで引数offsetの位置にギャップを移動した上で、引数offsetで指定された位置に、引数chで指定された文字を挿入する。
(3) メソッドdeleteは、引数offsetで指定された位置にある文字を削除する。テキストがない場合は、何もしない。
(4) メソッドcharAtは、引数offsetで指定された位置の文字を返す。
(5) メソッドlengthは、テキストの文字数を返す。
(6) メソッドconfirmGapは、配列bufferにおいて引数newGapOffsetで与えられた位置に1文字以上のギャップがあるようにする。必要であればギャップを指定された位置に移動し、ギャップがない場合は、新たにギャップを作る。
なお、このクラスの各メソッドが呼び出されるとき、引数は正しいものとする。
クラスEditorは、GapBufferを利用して、簡易テキストエディタを実現する。メソッドmainに与えられた最初の引数をテキストの初期値とする。カーソルは、文字の間にあり、カーソルの位置はオフセット値で表し、フィールドcursorに保持される。例えば、図4のようにカーソルが“プロ”と“グラム”の間にあるとき、cursorの値は2である。カーソルがテキストの末尾にあるとき、cursorの値はテキストの文字数と同じであり、テキストがないとき、cursorの値は0である。
文字の入力は、外部で与えられるクラスCharReaderで行う。メソッドgetは、ターミナルから1文字ずつ読み込む。CharReaderには、次の制御文字が定義されている。制御文字以外の文字が入力されたときは、カーソルの位置に文字を挿入し、カーソルを1文字分進める。
① CharReader.MOVE_FORWARD
カーソルを1文字分進める。カーソルがテキストの末尾にあるときは、無視する。
② CharReader.MOVE_BACKWARD
カーソルを1文字分戻す。カーソルがテキストの先頭にあるときは、無視する。
③ CharReader.DELETE
カーソルの直後の1文字を削除する。カーソルがテキストの末尾にあるときは、無視する。
④ CharReader.EOF
エディタを終了する。
ギャップバッファの内容の表示は、外部で与えられるクラスDisplayで行う。メソッドoutputは、GapBufferのメソッドcharAtを呼び出してギャップバッファのテキストを取得する。
設問1：
問題文を見る プログラム中のに入れる正しい答えを、解答群の中から選べ。
aに関する解答群
ア：gapSize--
イ：gapSize++
ウ：gapSize - 1
エ：gapSize + 1
bに関する解答群
ア：buffer.length
イ：gapOffset
ウ：gapSize
エ：length()
cに関する解答群
ア：buffer.length
イ：buffer.length - gapOffset
ウ：buffer.length - gapSize
エ：buffer.length - INITIAL_GAP_SIZE
dに関する解答群
ア：CharReader
イ：Display
ウ：Editor
エ：GapBuffer
オ：Object
カ：StringBuffer
e, fに関する解答群
ア：--cursor
イ：++cursor
ウ：cursor
エ：cursor--
オ：cursor++
模範解答
a：ア、b：ウ、c：ウ、d：エ、e：ウ、f：オ
解説
解答の導き方
この問題では、ギャップバッファ（編集位置に空き領域を置き、そこへ文字を入れる仕組み）と、それを使うエディタの処理を読み解きます。配列（複数の値を順番に並べて扱う入れ物）にある文字の位置と、利用者から見た文字の位置を分けて考えるのがポイントです。
1. 空欄a：挿入後にギャップがどう変わるか
コンストラクタでは、文字列の前にギャップを作っています。その後、insertは「confirmGapでギャップを移動」してから、ギャップの先頭に文字を格納します。
「buffer[gapOffset++] = ch;」では、まずギャップの先頭位置に文字を書き込み、gapOffsetを1増やします。ギャップの先頭が1つ後ろへ移るので、ギャップの大きさは1つ小さくなります。したがって、aにはgapSizeを1減らす処理が入ります。
2. 空欄b：ギャップの後ろにある文字を探す
オフセット値（先頭から数えた位置）は、ギャップを飛ばしたテキスト上の位置です。一方、buffer内ではギャップの分だけ後ろに文字が置かれています。
offsetがgapOffsetより小さいとき、文字はギャップより前にあるので、配列上の位置はoffsetのままです。offsetがgapOffset以上なら、ギャップを越えた先にある文字なので、配列上の位置をギャップの大きさ分だけ後ろへずらします。つまり、offsetに加えるのはgapSizeです。よって、bはgapSizeです。
3. 空欄c：テキストの文字数を求める
buffer全体の要素数には、テキストの文字だけでなくギャップも含まれています。テキストの文字数は、bufferの要素数からギャップの大きさを引けば求められます。
したがって、lengthが返す値は です。gapOffsetはギャップの位置を表す値であって、ギャップの大きさではないため、引く値には使いません。
4. 空欄d：bufが扱うもの
Editorのコンストラクタでは、bufにGapBufferのオブジェクトを設定しています。また、run内ではbufに対してinsert、delete、lengthを呼び出しています。これらのメソッドをもつ型はGapBufferなので、dにはGapBufferが入ります。
5. 空欄e：カーソル直後の文字を削除する
問題文では、カーソルは文字の間にあると説明されています。例えばカーソルの位置が2なら、カーソルの直後にある文字のオフセット値も2です。
そのため、カーソル直後の文字を削除するには、deleteにcursorを渡します。テキストの末尾では削除しないよう、プログラムは先にcursorがbuf.length()より小さいことを確認しています。よって、eはcursorです。
6. 空欄f：文字を挿入し、カーソルを進める
制御文字以外の文字が入力された場合は、カーソルの位置に挿入し、カーソルを1文字分進めます。その処理に合うのがcursor++です。
ここで、Javaの後置インクリメント（変数の現在の値を使い、その変数を1増やす演算）の順序に注意します。cursorが2の場合、cursor++はまず値2を引数として渡すために使い、その評価中にcursorを3へ増やします。その後にinsertが実行され、insertにはoffsetの2が渡されます。
このように、カーソルの増加はinsertの呼出し後ではなく、insertが実行される前に起きます。これにより、文字は元のカーソル位置に入り、カーソルは挿入後の文字の次の位置になります。
誤りやすいポイント
- gapOffsetはギャップの位置、gapSizeはギャップの大きさです。名前が似ていますが、役割は異なります。
- ギャップより後ろの文字をcharAtで探すときは、配列上の位置がgapSize分だけ後ろになります。ギャップより前の文字には加算しません。
- lengthはbufferの長さそのものではありません。bufferにはギャップも含まれるため、ギャップの大きさを引きます。
- cursorは文字そのものの位置ではなく、文字と文字の間の位置です。そのため、カーソル直後の文字を削除するときのオフセット値はcursorです。
- cursor++は、増加後の値ではなく増加前の値をinsertに渡します。また、cursorが増えるのはinsertの実行前です。
FAQ
Q: ギャップがない状態でも、charAtの考え方は同じですか？
A: 同じです。ギャップがないときはgapSizeが0なので、ギャップより後ろの文字の位置に加える値も0です。
A: 同じです。ギャップがないときはgapSizeが0なので、ギャップより後ろの文字の位置に加える値も0です。
Q: deleteで、削除する位置の次にギャップを移動するのはなぜですか？
A: 削除する文字をギャップの直前に置くためです。その後、gapOffsetを1戻し、gapSizeを1増やすと、その文字がギャップに含まれ、テキストから削除された状態になります。
A: 削除する文字をギャップの直前に置くためです。その後、gapOffsetを1戻し、gapSizeを1増やすと、その文字がギャップに含まれ、テキストから削除された状態になります。
Q: cursor++の代わりに++cursorを使うと、insertに渡る値はどうなりますか？
A: 前置インクリメントでは、先にcursorを増やしてから、その値を使います。このプログラムでは、増加前のカーソル位置に挿入する必要があるため、cursor++を使っています。
A: 前置インクリメントでは、先にcursorを増やしてから、その値を使います。このプログラムでは、増加前のカーソル位置に挿入する必要があるため、cursor++を使っています。
関連キーワード: ギャップバッファ、配列、オフセット、文字列挿入、文字列削除、後置インクリメント
