配列に基づいて一般的なサイズ変更循環バッファーを作成しました。これは、この特定のケースが発生するまでテストでうまく機能していました。
- 頭 == 尾と
- 配列全体が要素で満たされている
配列のサイズが通常どおりに変更され、 head = 0 、 tail = new position to insert が配置され、すべてがうまくいくことを期待していました。しかし、これは私が出力として得ているものです:
adding : e
head : 5 tail : 5 , size : 12
a b c d e f g h i j k l
adding : f
resizing array to size: 24
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException
at java.lang.System.arraycopy(Native Method)
at ResizingCircularArray.resize(ResizingCircularArray.java:16)
at ResizingCircularArray.enqueue(ResizingCircularArray.java:33)
at ResizingCircularArray.main(ResizingCircularArray.java:105)
おそらく些細なことですが、重要なことですが、それが何であるかを突き止めることはできません。誰か助けてくれませんか？
注:
head > 次のデキューが行われる
位置 tail > 次のエンキューが行われる位置
編集: ns47731 の提案に従って、arraycopy 行を からsystem.arraycopy(arr, head, tempArr, 0, size);に変更しましたSystem.arraycopy(arr, 0, tempArr, 0, size);。これにより、例外の問題は解決されますが、ロジックにエラーが発生します。これは以下で明らかです。
43.dequeing : f
head : 13 tail : 20 , size : 7
null null null null null null null null null null null null null g h i j k l m null null null null
44.dequeing : g
resizing array to size: 12
head : 0 tail : 6 , size : 6
null null null null null null null null null null null null
つまり、データ部分g h i j k l mがドロップされています。
問題は System.arraycopy() 自体にあり、循環配列ではなく線形配列用に設計されていることに気付いたので、循環配列で動作する単純なバージョンを自分用に作成しました。
private void arrayCopy(E[] srcArr , int srcpos , E[] destArr , int destpos , int length){
for(int index = 0 ; index < length ; index++){
destArr[index] = srcArr[head++];
if(head == srcArr.length){
head = (head % srcArr.length);
}
}
}
後で例外ケースを追加する必要がありますが、これは一般的に機能します。
変更されたコード
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
class ResizingCircularArray<E> {
private int head = 0;
private int tail = 0;
private int size = 0; // a measure of non-null elements in the array
private E[] arr;
// Modified version of System.arraycopy() to work with circular array.
private void arrayCopy(E[] srcArr , int srcpos , E[] destArr , int destpos , int length){
for(int index = 0 ; index < length ; index++){
destArr[index] = srcArr[head++];
if(head == srcArr.length){
head = (head % srcArr.length);
}
}
}
private void resize() {
System.out.println("resizing array to size: " + 2 * size);
@SuppressWarnings("unchecked")
E[] tempArr = (E[]) new Object[2 * size];
arrayCopy(arr, head, tempArr, 0, size);
head = 0;
tail = size; // tail point to where the NEXT element will land
arr = tempArr;
}
@SuppressWarnings("unchecked")
public ResizingCircularArray() {
arr = (E[]) new Object[3];
}
public void enqueue(E item) {
if (item == null)
throw new NullPointerException(
" adding null values is not allowed ");
if (size == arr.length) {
resize();
}
if (tail == arr.length) {
// going round
tail = (tail % arr.length);
}
arr[tail++] = item;
size++;
System.out.println("head : " + head + " tail : " + tail + " , size : "
+ size);
}
public E dequeue() {
if (!(size > 0))
throw new java.util.NoSuchElementException("size is negative");
E item = arr[head];
arr[head++] = null;
if (head == (arr.length)) {
head = (head % arr.length); // =0
}
--size;
if (size == arr.length / 4) {
resize();
}
System.out.println("head : " + head + " tail : " + tail + " , size : "
+ size);
return item;
}
public boolean isEmpty() {
return size == 0;
}
public E sample(int offset) {
if (offset < 0)
throw new java.lang.IllegalArgumentException(
"provided offset is out of bounds");
return arr[head + offset];
/*
* NOTE : the check for (head+offset)>tail as pointed out by sos will
* work in case of linear array , Not in case of Circular array because
* when tail comes around in a circle , tail will be < than head and the
* above check will create trouble
*/
}
public int size() {
return size;
}
public void display() {
for (E item : arr)
System.out.print(item + " ");
System.out.println("\n");
}
public static void main(String[] args) {
ResizingCircularArray<String> r = new ResizingCircularArray<String>();
String line = null;
String[] segment, parsed;
boolean endFlag = false;
int count = 0;
try (BufferedReader is = new BufferedReader(new FileReader(
"CircArrayPoints.txt"))) {
line = is.readLine();
segment = line.trim().split(";");
System.out.println("total commands : " + segment.length);
for (int i = 0; !segment[i].equals("stop") && !endFlag; i++) {
parsed = segment[i].split(" ");
count++;
switch (parsed[0]) {
case "enq":
System.out.println(count+ ".adding : " + parsed[1]);
r.enqueue(parsed[1]);
r.display();
break;
case "deq":
if (r.isEmpty()) {
System.out.println("Empty queue");
endFlag = true;
break;
}
// print after checking isEmpty() to make sure
// sample(0) doesn't call null etc
System.out.println(count+ ".dequeing : " + r.sample(0));
r.dequeue();
r.display();
break;
case "disp":
r.display();
break;
default:
break;
}
}
} catch (IOException e) {
e.printStackTrace();
}
}
}
ファイル: CircArrayPoints.txt
enq a;enq b;enq c;enq d;enq e;enq f;enq g;enq h;enq i;enq j;enq k;enq l;deq;deq;deq;deq;deq;enq a;enq b;enq c;enq d;enq e;enq f;enq g;enq h;enq i;enq j;enq k;enq l;enq m;deq;deq;deq;deq;deq;deq;deq;deq;deq;deq;deq;deq;deq;deq;deq;deq;deq;disp;stop