- PR -

File Structure#2

1
投稿者投稿内容
NO
会議室デビュー日: 2003/03/02
投稿数: 15
投稿日時: 2003-03-16 11:20
また、分かりにくい質問ですが、HeapAreaとRecordクラスをテストしたところ、この二つのクラスはちゃんと走るのですが、Distributorのクラスを使って、ファイルの読み書きをすると、infinite　loopに入ってしまいます。原因は、レコードの読み込みと書き込みにあり、HeapAreaが値を受け取らないためです。どうしたら、Heapを作ることができるのでしょうか。

このクラスが問題　ヒープが値を受け取りません。

public class Distributor {

public Distributor(String inFile, String filePref, int n, int mSize,Sortable seedRec) {
this.bSize=mSize;
this.fib = new Fibonacci(n);
this.heap= new HeapArea(this.bSize);
try{
this.inStream = new BufferedReader(new FileReader(inFile));
this.outStream=new BufferedOutputStream[n];
for(int i=0;i<n;i++){
String filename=filePref+(i+1);
this.outStream[i]= new BufferedOutputStream(new FileOutputStream(filename),this.bSize);//buffer　sizeを指定します。
}
inStream.close();
}catch(FileNotFoundException e){
}catch(IOException e){
}
this.seedRec=seedRec;
this.runs=n;

}//end of constructor

/**
* The main control flow of the replacement selection algorithm in this.
*/
public void distribute(){
try{
int[] tally =new int[this.runs];
int[] go = this.fib.next();
this.seedRec.readObject(this.inStream);//レコード読み込み
while(!this.seedRec.isSeparator(this.seedRec)){
for(int i = 0; i <this.runs ; i++){
while(go[i]-tally[i]>0){
this.heap = new HeapArea(this.bSize);//ここでsalaryの高い順に整列
this.heap.put(this.seedRec);//値を置いていく
Sortable nextItem;
Sortable outputItem = this.heap.findMax();
while(this.heap.getSize()> 0){//この部分でinfinite　loopに入ってしまいます。
if(this.heap.findMax().compareTo(outputItem)>0){
outputItem = this.heap.deleteMax();
this.seedRec.writeObject(this.outStream[i]);
if( this.inStream.ready()){// data in the input stream
nextItem = this.seedRec.createObject();
if(nextItem.compareTo(outputItem)<0||nextItem.compareTo(outputItem)==0){
this.heap.insert(nextItem);
}else{
seedRec.writeSeparator(this.outStream[bSize]);
this.heap.toss(nextItem);
}//end of else
tally[i]++;
System.out.println(tally[i]);
}//end of ready
}//end of comp
}//end of while(primary Heap size<= 0)
int n = this.heap.getSAreaSize();//secondary　areaにある値をprimary　areaへ押し上げる
this.heap.fixHeap(n);
}//end of while(go - pos)
}//end of runs
}//end of while(isSeparator)
}catch(Exception e){
e.printStackTrace();
}
}//end of distribute

ヒープのクラス　Distributorクラスがなければ上手く走る
public class HeapArea {
/**
* param size is the capacity(number of records) of the heap area.
*/
public HeapArea(int size) {
this.size = size;
this.hSize=0;
this.sSize=0;
this.inOrder = true;
getArray(this.size-1);
this.area[ 0 ] = null;
}

/**
* Insert into the primary heap, maintaining heap order.
* x the item to insert.
* exception:
* NotInOrder if the primary heap has not been established
*/
public void insert(Sortable x)throws NotInOrder{
if(!this.inOrder){
put(x);
return;
}
checkSize();
// Percolate up
int hole = ++this.hSize;
area[ 0 ] = x;
for( ; x.compareTo(area[ hole / 2 ] ) > 0; hole /= 2 )
area[ hole ] = area[ hole/2 ];
area[ hole ] = x;

}

/**
* Insert into the heap area, without maintaining heaporder.
* @param x the item to insert.
*/
public void put(Sortable x){
//checkSize();
hSize=hSize+1;
area[hSize]=x;
//this.area[++this.hSize]=x;
if(hSize>=2){
if((x.compareTo(this.area[this.hSize/2])) > 0)
this.inOrder=false;
}
}
/**
* Insert into the secondary area(without maintaining heap order.
* x the item to insert
*/
public void toss(Sortable x){
checkSize();
this.area[++this.sSize]=x;
this.inOrder=false;
}
/**
* Find the greatest item in the heap.
* ensure:
* return the greatest item.
* exception:
* Underflow if the primary heap heap is logically empty, false otherwise.
*/
public Sortable findMax()throws Underflow, NotInOrder{
if(this.isEmpty())
throw new Underflow("Empty binary heap");
if(!this.inOrder)
fixHeap();
return this.area[1];
}
/**
* Remove the greatest item from the primary heap and adjust the heap
* @return the greatest item.
* @exception:
* Underflow if the primary heap is empty, or NotInOrder if the primary
* heap has not been fixed.
*/
public Sortable deleteMax() throws Underflow, NotInOrder{
Sortable maxItem = findMax();
area[1]=area[this.hSize--];
percolateDown(1);
return maxItem;
}
/**
* Re-establish the heap order for the data collection in the area in linear time.
*/
public void fixHeap(){
for( int i = this.hSize / 2; i > 0; i-- )
percolateDown( i );
inOrder = true;
}
/**
* Re-establish the heap order for the size n at the beginning of the array
* for the items in the last n cells in linear time.
*/
public void fixHeap(int n){
if(n !=size){
if(n>=size/2){
for(int i=1;i<=sSize-n;i++)
put(area[area.length-i]);
}
hSize=n;
sSize=0;
fixHeap();
}
}


/**
* ensure:
* return true if the primary heap is logically empty, false otherwise.
*/
public boolean isEmpty(){
return hSize==0;
}
/**
* Make the entire array including the heap logically empty.
*/
public void makeEmpty(){
this.hSize=this.sSize=0;
}
/**
* @reutrn the number of node in the primary heap.
* exception:
* NotInOrder id the primary heap not been established.
*/
public int getPHeapSize()throws NotInOrder{
return this.hSize+1;

}
/**
* @return the number of nodes in the secondary storage area.
*/
public int getSAreaSize(){
return this.sSize;
}
public int getSize(){
return this.size;
}
/**
* Internal method to percolate down in the heap.
* @param hole the index at which the percolate begins.
*/
private void percolateDown(int hole){
int child;
Sortable tmp = area[hole];
for( ; hole*2 <= hSize ; hole = child){
child = hole*2;
if(child != hSize && (area[child+1].compareTo(area[child])>0))
child++;
if(area[child].compareTo(tmp)>0)
this.area[hole]=this.area[child];
else
break;
}

this.area[hole]=tmp;
}


/**
* Private method to allocate the heap array.
* Includes an extra spot for the sentinel.
* @param newMaxSize the capacity of the heap.
*/
private void getArray( int newMaxSize ){
this.area = new Sortable[ newMaxSize + 1 ];
}

/**
* Private method that doubles the heap array if full.
*/
private void checkSize( )
{
if( this.hSize == area.length - 1 )
{
Sortable [ ] oldArray = area;
this.getArray( hSize * 2 );
for( int i = 0; i < oldArray.length; i++ )
this.area[ i ] = oldArray[ i ];
}
}
private int hSize;//Number of elements in heap
private int sSize;//Number of items the secondary area
private boolean inOrder;//True if heap order is guaranteed in the primary heap
private Sortable[] area;//The array holding heap and secondary area
private int size;

}
//このクラスは出来上がり
public class Fibonacci {

public Fibonacci(int k) {
this.order=k;
init();
}
public int[] next(){
int tmp = this.array[0]; //first number of the fibonacci
for(int i=0; i < this.array.length-1 ; i++) { //add the numbers
array[i] = tmp + array[i+1];

}
this.array[array.length-1]=tmp;
return array;
}
public void display(){
for(int i=0; i<this.array.length; i++){
System.out.println(this.array[i]);
}
}
public void init(){
this.array = new int[this.order];
for(int i=1; i < this.order ; i++){
array[i]=0;
}
array[0]=1;
}
//インターフェース、Recordクラスでimplementする
public interface Sortable {

public int compareTo(Sortable obj);//return negative 0, or positive if this<,=orobj
public Sortable createObject();//the factory method
public boolean isSeparator(Sortable obj);//return true if obj is a separator record
public void readObject(Reader r)throws IOException;//to read from raw data file
public void readObject(InputStream is)throws IOException;//to read from runs
public void writeObject(OutputStream os)throws IOException;
public void writeSeparator(OutputStream os)throws IOException;
public String toString();//to a format for display
}
//レコードクラス　おかしいところはないように思われる。
public class Record implements Sortable{

private int id;
private float salary;
private String name;
public Record() {
super();
}

public Record(int id, float salary, String name) {
this.id = id;
this.salary = salary;
this.name = name;
}

public int getID(){
return this.id;
}
public float getSalary(){
return this.salary;
}
public String getName(){
return this.name;
}
public int compareTo(Sortable obj) {
Record r = (Record)obj;
return (int)(this.salary - r.salary);
}

public String toString() {
return (getID() +" "+ getSalary() +" "+ getName());
}

public void readObject(InputStream is)throws IOException{//to read from runs
DataInputStream dis = new DataInputStream(is);
this.id=dis.readInt();
this.salary=dis.readFloat();
int nameCount=dis.readInt();
this.name = DataIO.readFixedString(4,dis);
}
public void readObject(Reader r)throws IOException{
String s="";
try{
BufferedReader br = new BufferedReader(r);
s= br.readLine();
if(s==null)
return;
StringTokenizer lineTokenizer = new StringTokenizer(s);
int id = Integer.parseInt(lineTokenizer.nextToken());
float salary = Float.parseFloat(lineTokenizer.nextToken());
String name = lineTokenizer.nextToken();
}catch(IOException e){}
}
public boolean isSeparator(Sortable obj){
Record rd=(Record)obj;
return (rd.salary == -1);
}

public void writeObject(OutputStream os) throws IOException {
DataOutputStream dos = new DataOutputStream(os);
try {
dos.writeInt(this.id);
dos.writeFloat(this.salary);
dos.write(this.name.length());
dos.writeChars(this.name);
} catch (Exception e) {
//throw e;
}
}

public void writeSeparator(OutputStream os)throws IOException{
DataOutputStream dos = new DataOutputStream(os);
String s = "|";
try {
dos.writeInt(-1);
dos.writeFloat(-1);
dos.write(-1);
dos.writeChars(s);
dos.flush();
} catch (Exception e) {
//throw e;
}

}
public Sortable createObject(){//the factory method
return new Record(this.id,this.salary,this.name);
}
}
1

スキルアップ／キャリアアップ（JOB@IT）