/*
* BBoom.java - Joris van Rantwijk
* in026 Inleiding databeheer
*
* B+ boom.
*/
import java.io.RandomAccessFile;
import java.io.IOException;
/*
* Implementatie van een B+ boom volgens variant-4 uit het dictaat.
*
* De interne knopen worden opgeslagen in een indexfile. Elke knoop
* komt in een aparte pagina in de file. De eerste pagina van de indexfile
* heeft een afwijkend formaat: hierin staat eerst de hoogte van de boom,
* en daarna het paginanummer van de wortel van de boom.
* Een interne knoop kan maximaal 2*k opvolgers hebben. Voor elke opvolger
* worden twee getallen opgeslagen: de grootste sleutelwaarde van de
* opvolger en het paginanummer van de opvolger. Als de verwijzing naar
* een opvolger niet in gebruik is (de knoop bevat vrije ruimte) dan staan
* beide getallen op -1.
* De verwijzingen naar opvolgers zijn gesorteerd op oplopende
* sleutelwaarde; de ongebruikte verwijzingen komen als laatste.
* Of de opvolger een interne of een externe knoop is, kan worden bepaald
* aan de hand van de boomhoogte.
*
* De externe knopen (bladeren) worden opgeslagen in de recordfile.
* Elke knoop komt in een aparte pagina in de file. Elke pagina
* bevat maximaal bucketsize records. Een vrije positie binnen de pagina
* wordt aangegeven met een sleutelwaarde van -1.
* De records in een pagina zijn gesorteerd op oplopende sleutelwaarde;
* de vrije posities komen als laatste.
* In elke pagina staat achter de records ook een getal dat verwijst naar
* de volgende pagina. We doen daar in dit voorbeeld niets mee, maar het kan
* worden gebruikt voor het sequentieel doorlopen van het bestand.
*
* Bij het verwijderen van records moeten pagina's soms samengevoegd worden.
* Hierdoor kunnen vrije pagina's ontstaan. Dit kan zowel in de index als
* in de recordfile gebeuren. In beide files houden we een gelinkte lijst
* van vrije pagina's bij, door aan het begin van elke vrije pagina een
* verwijzing naar de volgende vrije pagina op te nemen. In een aparte file
* bewaren we dan een verwijzing naar de eerste vrije pagina van elke file.
*/
//===========================================================================
// Class BBoom
// Implementatie van B+ boom (variant-4).
//===========================================================================
public class BBoom extends BestandsOrganisatie
{
// De gebruikte files.
private RandomAccessFile ifile;
private RandomAccessFile rfile;
private RandomAccessFile vfile;
// De omvang van een pagina in bytes.
private final static int PAGESIZE = 1024;
// Het maximale aantal records per pagina.
private int bucketsize;
private int k = PAGESIZE / 16; // Orde van de boom.
private int h; // De boomhoogte
private int root; // Het paginanummer van de wortel
private int ifree; // Eerste vrije indexpagina
private int rfree; // Eerste vrije recordpagina
// Construeer een BBoom object.
// Gebruik de gegeven filenaam, en het gegeven recordtype.
//-----------------------------------------------------------------------
public BBoom(String filenaam, Class recordType)
throws IOException
{
int i;
this.recordType = recordType;
this.recordLen = Record.newRecord(recordType).getRecordlen();
// Bereken de bucketsize (het aantal records dat in een pagina past).
bucketsize = (PAGESIZE - 4) / recordLen;
// Open de benodigde files. Als de files nog niet bestaan,
// worden er automatisch lege files aangemaakt.
ifile = new RandomAccessFile(filenaam + "i", "rw");
rfile = new RandomAccessFile(filenaam + "r", "rw");
vfile = new RandomAccessFile(filenaam + "v", "rw");
// Controleer de lengte van de indexfile.
if (ifile.length() == 0) {
// Het bestand bevat nog geen gegevens. Initialiseer het bestand
// door het aanmaken van een index bestaande uit alleen een
// wortelknoop, en een lege recordpagina.
h = 1;
root = 1;
ifree = -1;
rfree = -1;
// Schrijf eerste pagina van indexfile.
ifile.seek(0);
ifile.writeInt(h);
ifile.writeInt(root);
diskaccess++;
// Schrijf wortelpagina.
ifile.seek(PAGESIZE);
ifile.writeInt(0);
ifile.writeInt(0);
for (i = 1; i < 2*k; i++) {
ifile.writeInt(-1);
ifile.writeInt(-1);
}
diskaccess++;
// Schrijf lege recordpagina.
Record r = Record.newRecord(recordType);
rfile.seek(0);
for (i = 0; i < bucketsize; i++)
r.write(rfile);
rfile.writeInt(-1);
diskaccess++;
} else {
// Lees alvast de boomhoogte en wortellocatie.
ifile.seek(0);
h = ifile.readInt();
root = ifile.readInt();
// Lees de verwijzingen naar ketens van vrije pagina's.
vfile.seek(0);
ifree = vfile.readInt();
rfree = vfile.readInt();
}
}
// Sluit het bestand.
//-----------------------------------------------------------------------
public void close() throws IOException
{
// Schrijf de (mogelijk gewijzigde) verwijzingen naar vrije pagina's.
vfile.seek(0);
vfile.writeInt(ifree);
vfile.writeInt(rfree);
// Sluit alle files.
ifile.close();
rfile.close();
vfile.close();
}
// Alloceer een pagina in de indexfile.
// Hergebruik een vrije pagina als dat mogelijk is, voeg anders een
// pagina toe aan het eind van de file.
//-----------------------------------------------------------------------
private int allocPageI() throws IOException
{
int p;
if (ifree != -1) {
p = ifree;
ifile.seek(ifree * PAGESIZE);
ifree = ifile.readInt();
} else {
p = (int) ((ifile.length() + PAGESIZE - 1) / PAGESIZE);
}
return (p);
}
// Alloceer een pagina in de recordfile.
// Hergebruik een vrije pagina als dat mogelijk is, voeg anders een
// pagina toe aan het eind van de file.
//-----------------------------------------------------------------------
private int allocPageR() throws IOException
{
int p;
if (rfree != -1) {
p = rfree;
rfile.seek(rfree * PAGESIZE);
rfree = rfile.readInt();
} else {
p = (int) ((rfile.length() + PAGESIZE - 1) / PAGESIZE);
}
return (p);
}
// Geef een pagina uit de indexfile vrij door hem toe te voegen
// aan de lijst van vrije pagina's.
//-----------------------------------------------------------------------
private void freePageI(int p) throws IOException
{
ifile.seek(p * PAGESIZE);
ifile.writeInt(ifree);
ifree = p;
}
// Geef een pagina uit de recordfile vrij door hem toe te voegen
// aan de lijst van vrije pagina's.
//-----------------------------------------------------------------------
private void freePageR(int p) throws IOException
{
rfile.seek(p * PAGESIZE);
rfile.writeInt(rfree);
rfree = p;
}
// Zoek het record met sleutelwaarde <key>.
// Geef de positie van het record in de rfile terug.
// Als het record niet wordt gevonden, geef -1.
//-----------------------------------------------------------------------
private int findRecord(int key) throws IOException
{
Record r = Record.newRecord(recordType);
int i, j, d, p, a, b;
// Begin met zoeken bij de wortel van de boom.
p = root;
j = -1;
// Loop van boven naar beneden door alle niveau's van de boom.
for (d = 0; d < h; d++) {
ifile.seek(p * PAGESIZE);
diskaccess++;
// Doorloop de interne knoop met paginanummer p.
// Zoek de eerste opvolger waarvan de max.sleutelw >= key.
for (i = 0; i < 2*k; i++) {
// Lees max.sleutelw en verwijzing.
a = ifile.readInt();
b = ifile.readInt();
// Bewaar laatste geldige verwijzing.
if (b != -1) j = b;
// Kijk of dit de opvolger is die we zoeken.
if (a >= key) break;
}
// j bevat nu het paginanummer van de gekozen opvolger.
// Bekijk deze opvolger in de volgende ronde.
p = j;
}
// p bevat nu het paginanummer van de recordpagina waarin
// het record zich moet bevinden.
rfile.seek(p * PAGESIZE);
diskaccess++;
for (i = 0; i < bucketsize; i++) {
r.read(rfile);
if (r.key == key) {
// Hoera! We hebben het record gevonden.
// Geef de positie terug.
return (p * PAGESIZE + i * recordLen);
}
}
// We hebben het record niet gevonden.
return (-1);
}
// Voeg het record <r> toe aan een pagina in de recordfile.
// In p[0] staat het nummer van de pagina, in v[0] staat de hoogste
// sleutelwaarde van de pagina.
// Als de pagina vol is, moet hij eerst gesplitst worden. In dat geval,
// geven we in v[0] de hoogste sleutelwaarde van de eerste pagina, in
// p[0] het nummer van de 1e pagina, in v[1] de hoogste sleutelwaarde
// van de tweede pagina en in p[1] het nummer van de tweede pagina.
// Als er geen splitsing nodig was geven we in v[0] de hoogste sleutel
// van de pagina, p[0] blijft ongewijzigd, v[1] = -1 en p[1] = -1.
//-----------------------------------------------------------------------
private void insertExternal(Record r, int p[], int[] v)
throws IOException
{
Record[] pag = new Record[bucketsize + 1];
Record t = Record.newRecord(recordType);
int i, next;
// Lees de pagina in het geheugen.
rfile.seek(p[0] * PAGESIZE);
for (i = 0; i < bucketsize; i++) {
pag[i] = Record.newRecord(recordType);
pag[i].read(rfile);
}
next = rfile.readInt();
diskaccess++;
// Schuif de records op om plaats te maken voor het nieuwe record.
for (i = bucketsize;
i > 0 && (pag[i-1].key == -1 || pag[i-1].key > r.key);
i--)
pag[i] = pag[i-1];
// Voeg het nieuwe record tussen.
pag[i] = r;
// Pas eventueel de maximale sleutelwaarde aan.
if (r.key > v[0]) v[0] = r.key;
// Bepaal of een splitsing nodig is.
if (pag[bucketsize].key != -1) {
// De pagina is te vol :-( splits hem in twee pagina's.
// In de oude pagina komt de eerste helft van de records,
// in de nieuwe pagina de tweede helft van de records.
p[1] = allocPageR();
v[1] = v[0];
v[0] = pag[bucketsize / 2].key;
// Schrijf de eerste helft van de records.
rfile.seek(p[0] * PAGESIZE);
for (i = 0; i <= bucketsize / 2; i++)
pag[i].write(rfile);
// Vul aan met ongeldige records.
for (i = bucketsize / 2 + 1; i < bucketsize; i++)
t.write(rfile);
// Schrijf verwijzing naar de nieuwe pagina.
rfile.write(p[1]);
diskaccess++;
// Schrijf de tweede helft van de records.
rfile.seek(p[1] * PAGESIZE);
for (i = bucketsize / 2 + 1; i <= bucketsize; i++)
pag[i].write(rfile);
// Vul aan met ongeldige records.
for (i = 0; i < bucketsize / 2; i++)
t.write(rfile);
// Schrijf verwijzing naar de volgende pagina.
rfile.writeInt(next);
diskaccess++;
} else {
// Er is geen splitsing nodig.
p[1] = -1;
v[1] = -1;
// Schrijf de pagina terug naar de record file.
rfile.seek(p[0] * PAGESIZE);
for (i = 0; i < bucketsize; i++)
pag[i].write(rfile);
// Schrijf verwijzing naar de volgende pagina.
rfile.writeInt(next);
diskaccess++;
}
}
// Voeg het record r toe aan de subboom waarvan p[0] de wortel is.
// De grootste sleutelwaarde in de knoop p[0] is v[0]. We bevinden
// ons op diepte d in de boom.
// Misschien moet de knoop gesplitst worden. In dat geval geven we
// in v[0] de hoogste sleutelwaarde van de 1e deelknoop, in p[0] het
// pagina nummer van de 1e knoop, in v[1] de hoogste sleutelwaarde van
// de 2e knoop, in p[1] het paginanummer van de 2e knoop.
// Als er geen splitsing nodig was geven we in v[0] de hoogste sleutel
// van de knoop, p[0] is ongewijzigd en v[1] = -1 en p[1] = -1.
//-----------------------------------------------------------------------
private void insertInternal(Record r, int[] p, int[] v, int d)
throws IOException
{
boolean change = false;
int[] opvv = new int[2*k + 1];
int[] opvp = new int[2*k + 1];
int[] newp = new int[2];
int[] newv = new int[2];
int i, j;
// Lees de knoop in het geheugen.
ifile.seek(p[0] * PAGESIZE);
for (i = 0; i < 2*k; i++) {
opvv[i] = ifile.readInt();
opvp[i] = ifile.readInt();
}
diskaccess++;
opvv[2*k] = -1;
opvp[2*k] = -1;
// Bepaal in welke opvolger het record moet worden toegevoegd.
j = -1;
for (i = 0; i < 2*k; i++) {
// Bewaar de laatste geldige verwijzing.
if (opvv[i] != -1) j = i;
// Is dit de juiste opvolger ?
if (opvv[i] >= r.key) break;
}
// j bevat nu het nummer van de gekozen opvolger.
newp[0] = opvp[j];
newv[0] = opvv[j];
// Voeg het record toe in de gekozen opvolger.
// Als we onder in de boom zijn, is de opvolger een recordpagina.
if (d == h)
insertExternal(r, newp, newv);
else
insertInternal(r, newp, newv, d + 1);
// Pas eventueel de maximale sleutelwaarde aan.
if (r.key > v[0]) v[0] = r.key;
// Ga na of de opvolgerknoop gesplitst is.
if (newp[1] != -1) {
// De opvolger is gesplitst, de nieuwe opvolgerknoop moet
// worden toegevoegd in deze knoop.
// Schuif de opvolgers op in de array.
for (i = 2*k - 1; i > j; i--) {
opvp[i+1] = opvp[i];
opvv[i+1] = opvv[i];
}
// Wijzig de waarden van de gesplitste opvolger, voeg de
// nieuwe opvolger tussen.
opvp[j] = newp[0];
opvv[j] = newv[0];
opvp[j+1] = newp[1];
opvv[j+1] = newv[1];
// De inhoud van deze pagina is gewijzigd.
change = true;
} else {
// Er was geen splitsing in de opvolger.
if (newp[0] != opvp[j] || newv[0] != opvv[j]) {
// De gegevens van de opvolger zijn gewijzigd.
// Registreer de veranderingen in deze knoop.
opvp[j] = newp[0];
opvv[j] = newv[0];
change = true;
}
}
// Bepaal of een splitsing nodig is.
if (opvp[2*k] != -1) {
// De knoop is te vol. Splits hem in twee knopen.
// In de oude knoop komt de eerste helft van de opvolgers,
// de andere helft komt in een nieuwe knoop.
p[1] = allocPageI();
v[1] = v[0];
v[0] = opvv[k];
// Schrijf de eerste helft van de opvolgers.
ifile.seek(p[0] * PAGESIZE);
for (i = 0; i <= k; i++) {
ifile.writeInt(opvv[i]);
ifile.writeInt(opvp[i]);
}
// Vul aan met lege verwijzingen.
for (i = k+1; i < 2*k; i++) {
ifile.writeInt(-1);
ifile.writeInt(-1);
}
diskaccess++;
// Schrijf de tweede helft van de opvolgers.
ifile.seek(p[1] * PAGESIZE);
for (i = k + 1; i <= 2*k; i++) {
ifile.writeInt(opvv[i]);
ifile.writeInt(opvp[i]);
}
// Vul aan met lege verwijzingen.
for (i = 0; i < k; i++) {
ifile.writeInt(-1);
ifile.writeInt(-1);
}
diskaccess++;
} else {
// Er is geen splitsing nodig.
p[1] = -1;
v[1] = -1;
// Schrijf de knoop alleen als er veranderingen waren.
if (change) {
ifile.seek(p[0] * PAGESIZE);
for (i = 0; i < 2*k; i++) {
ifile.writeInt(opvv[i]);
ifile.writeInt(opvp[i]);
}
diskaccess++;
}
}
}
// Probeer de twee record pagina's p[0] en p[1] samen te voegen.
// Als dit niet mogelijk is, zorg er dan in elk geval voor dat beide
// pagina's ongeveer evenveel records bevatten. v[0] en v[1] bevatten de
// hoogste sleutelwaardes, deze moeten eventueel gewijzigd worden.
// Na samenvoegen geven we p[1] = -1 en v[1] = -1 terug.
//-----------------------------------------------------------------------
private void joinExternal(int[] p, int[] v) throws IOException
{
Record[] rec = new Record[2*bucketsize];
Record t = Record.newRecord(recordType);
int next1, next2, nrec;
int i;
// Lees de records uit beide pagina's en stop ze bij elkaar.
// Tel het aantal records.
nrec = 0;
rfile.seek(p[0] * PAGESIZE);
for (i = 0; i < bucketsize; i++) {
Record r = Record.newRecord(recordType);
r.read(rfile);
if (r.key != -1) {
rec[nrec] = r;
nrec++;
}
}
next1 = rfile.readInt();
diskaccess++;
rfile.seek(p[1] * PAGESIZE);
for (i = 0; i < bucketsize; i++) {
Record r = Record.newRecord(recordType);
r.read(rfile);
if (r.key != -1) {
rec[nrec] = r;
nrec++;
}
}
next2 = rfile.readInt();
diskaccess++;
// Bepaal of alle records in 1 pagina passen.
if (nrec <= bucketsize) {
// Stop alle records in 1 pagina.
rfile.seek(p[0] * PAGESIZE);
for (i = 0; i < nrec; i++)
rec[i].write(rfile);
for (i = nrec; i < bucketsize; i++)
t.write(rfile);
rfile.writeInt(next2);
// Geef de andere pagina vrij.
freePageR(p[1]);
// Update de administratie van de aanroepende functie.
v[0] = rec[nrec-1].key;
p[1] = -1;
v[1] = -1;
} else {
// Verdeel de records netjes over 2 pagina's.
// In de 1e pagina komen nrec/2 records.
rfile.seek(p[0] * PAGESIZE);
for (i = 0; i < nrec/2; i++)
rec[i].write(rfile);
for (i = nrec/2; i < bucketsize; i++)
t.write(rfile);
rfile.writeInt(next1);
diskaccess++;
// In de 2e pagina knoop komt de rest.
rfile.seek(p[1] * PAGESIZE);
for (i = nrec/2; i < nrec; i++)
rec[i].write(rfile);
for (i = nrec - nrec/2; i < bucketsize; i++)
t.write(rfile);
rfile.writeInt(next2);
diskaccess++;
// Update de administratie van de aanroepende functie.
v[0] = rec[nrec/2-1].key;
v[1] = rec[nrec-1].key;
}
}
// Probeer de twee interne knopen p[0] en p[1] samen te voegen.
// Als dit niet mogelijk is, zorg er dan in elk geval voor dat beide
// knopen ongeveer evenveel opvolgers hebben. v[0] en v[1] bevatten de
// hoogste sleutelwaardes, deze moeten eventueel gewijzigd worden.
// Na samenvoegen geven we p[1] = -1 en v[1] = -1 terug.
//-----------------------------------------------------------------------
private void joinInternal(int[] p, int[] v) throws IOException
{
int[] opvv = new int[2*2*k];
int[] opvp = new int[2*2*k];
int nopv;
int i;
// Lees de opvolgers van beide knopen en stop ze bij elkaar.
// Tel het totaal aantal opvolgers.
nopv = 0;
ifile.seek(p[0] * PAGESIZE);
for (i = 0; i < 2*k; i++) {
int a = ifile.readInt();
int b = ifile.readInt();
if (a != -1) {
opvv[nopv] = a;
opvp[nopv] = b;
nopv++;
}
}
diskaccess++;
ifile.seek(p[1] * PAGESIZE);
for (i = 0; i < 2*k; i++) {
int a = ifile.readInt();
int b = ifile.readInt();
if (a != -1) {
opvv[nopv] = a;
opvp[nopv] = b;
nopv++;
}
}
diskaccess++;
// Bepaal of de opvolgers in 1 knoop passen.
if (nopv <= 2*k) {
// Stop alle opvolgers in 1 knoop.
ifile.seek(p[0] * PAGESIZE);
for (i = 0; i < nopv; i++) {
ifile.writeInt(opvv[i]);
ifile.writeInt(opvp[i]);
}
for (i = nopv; i < 2*k; i++) {
ifile.writeInt(-1);
ifile.writeInt(-1);
}
diskaccess++;
// Geef de andere knoop vrij.
freePageI(p[1]);
// Update de administratie van de aanroepende functie.
v[0] = opvv[nopv-1];
p[1] = -1;
v[1] = -1;
} else {
// Verdeel de opvolgers netjes over twee knopen.
// In de eerste knoop komen nopv/2 opvolgers.
ifile.seek(p[0] * PAGESIZE);
for (i = 0; i < nopv/2; i++) {
ifile.writeInt(opvv[i]);
ifile.writeInt(opvp[i]);
}
for (i = nopv/2; i < 2*k; i++) {
ifile.writeInt(-1);
ifile.writeInt(-1);
}
diskaccess++;
// In de tweede knoop komt de rest.
ifile.seek(p[1] * PAGESIZE);
for (i = nopv/2; i < nopv; i++) {
ifile.writeInt(opvv[i]);
ifile.writeInt(opvp[i]);
}
for (i = nopv - nopv/2; i < 2*k; i++) {
ifile.writeInt(-1);
ifile.writeInt(-1);
}
diskaccess++;
// Update de administratie van de aanroepende functie.
v[0] = opvv[nopv/2-1];
v[1] = opvv[nopv-1];
}
}
// Verwijder het record met sleute key uit een pagina in de recordfile.
// Geef true als de pagina na de verwijdering minder dan halfvol is.
// Geef een exceptie als het record niet in de opgegeven pagina zit.
//-----------------------------------------------------------------------
private boolean removeExternal(int key, int p)
throws Exception, IOException
{
Record[] pag = new Record[bucketsize];
Record t = Record.newRecord(recordType);
int i, next;
// Lees de pagina in het geheugen.
rfile.seek(p * PAGESIZE);
for (i = 0; i < bucketsize; i++) {
pag[i] = Record.newRecord(recordType);
pag[i].read(rfile);
}
next = rfile.readInt();
diskaccess++;
// Zoek het record dat we moeten verwijderen.
for (i = 0; i < bucketsize; i++)
if (pag[i].key == key) break;
if (i == bucketsize) {
// Het record bevindt zich niet in de pagina.
throw new Exception("Record niet gevonden");
}
// Verwijder het record, en schuif de volgende records een plaats op.
while (i+1 < bucketsize) {
pag[i] = pag[i+1];
i++;
}
pag[bucketsize-1] = t;
// Schrijf de pagina terug naar de record file.
rfile.seek(p * PAGESIZE);
for (i = 0; i < bucketsize; i++)
pag[i].write(rfile);
// Schrijf verwijzing naar de volgende pagina.
rfile.writeInt(next);
diskaccess++;
// Geef aan de aanroeper door of deze pagina nu voor minder dan de
// helft vol is.
return (pag[(bucketsize-1)/2].key == -1);
}
// Verwijder het record met sleutel key uit de subboom waarvan p de
// wortel is. We bevinden ons op diepte d in de boom.
// Geef een exceptie als het record niet gevonden wordt.
//-----------------------------------------------------------------------
private boolean removeInternal(int key, int p, int d)
throws Exception, IOException
{
int[] opvv = new int[2*k];
int[] opvp = new int[2*k];
int[] newp = new int[2];
int[] newv = new int[2];
boolean needjoin;
int i, j;
// Lees de knoop in het geheugen.
ifile.seek(p * PAGESIZE);
for (i = 0; i < 2*k; i++) {
opvv[i] = ifile.readInt();
opvp[i] = ifile.readInt();
}
diskaccess++;
// Bepaal in welke subboom het record zich moet bevinden.
j = -1;
for (i = 0; i < 2*k; i++) {
// Bewaar de laatste geldige verwijzing.
if (opvv[i] != -1) j = i;
// Is dit de juiste opvolger ?
if (opvv[i] >= key) break;
}
// j bevat nu het nummer van de gekozen opvolger.
// Als we onder in de boom zijn, is de opvolger een externe knoop.
if (d == h)
needjoin = removeExternal(key, opvp[j]);
else
needjoin = removeInternal(key, opvp[j], d + 1);
// Als de opvolger nog minstens halfvol is, hoeven we verder
// niets te veranderen.
if (!needjoin)
return false;
// De opvolger is voor minder dan de helft vol. Om de minimale
// vullingsgraad te herstellen, combineren we hem met een andere
// opvolger.
if (j > 0) {
// Combineer de opvolger met zijn linker buurman.
newp[0] = opvp[j-1];
newv[0] = opvv[j-1];
newp[1] = opvp[j];
newv[1] = opvv[j];
if (d == h)
joinExternal(newp, newv);
else
joinInternal(newp, newv);
opvp[j-1] = newp[0];
opvv[j-1] = newv[0];
opvp[j] = newp[1];
opvv[j] = newv[1];
// Als de twee opvolgers samengevoegd zijn, schuiven we de
// volgende opvolgers een plaats op.
if (opvp[j] == -1) {
for (i = j; i+1 < 2*k; i++) {
opvp[i] = opvp[i+1];
opvv[i] = opvv[i+1];
}
opvp[2*k-1] = -1;
opvv[2*k-1] = -1;
}
} else if (opvp[j+1] != -1) {
// Combineer de opvolger met zijn rechter buurman.
newp[0] = opvp[j];
newv[0] = opvv[j];
newp[1] = opvp[j+1];
newv[1] = opvv[j+1];
if (d == h)
joinExternal(newp, newv);
else
joinInternal(newp, newv);
opvp[j] = newp[0];
opvv[j] = newv[0];
opvp[j+1] = newp[1];
opvv[j+1] = newv[1];
// Als de twee opvolgers samengevoegd zijn, schuiven we de
// volgende opvolgers een plaats op.
if (opvp[j+1] == -1) {
for (i = j+1; i+1 < 2*k; i++) {
opvp[i] = opvp[i+1];
opvv[i] = opvv[i+1];
}
opvp[2*k-1] = -1;
opvv[2*k-1] = -1;
}
}
// Schrijf de knoop terug naar de index file.
ifile.seek(p * PAGESIZE);
for (i = 0; i < 2*k; i++) {
ifile.writeInt(opvv[i]);
ifile.writeInt(opvp[i]);
}
diskaccess++;
// Geef aan de aanroeper door of deze knoop nu voor minder dan de
// helft vol is.
return (opvp[k-1] == -1);
}
// Voeg het record r toe.
//-----------------------------------------------------------------------
public void insert(Record r) throws Exception, IOException
{
int[] newp = new int[2];
int[] newv = new int[2];
int i;
// Controleer of het record nog niet bestaat.
if ( findRecord(r.key) != -1 ) {
// Het record bestaat al, geef een exceptie.
throw new Exception("Record bestaat al");
}
// Voeg het record toe aan de boom.
newp[0] = root;
newv[0] = 0; // Deze waarde is niet van belang.
insertInternal(r, newp, newv, 1);
// Ga na of de wortel gesplitst is.
if (newp[1] != -1) {
// De wortel van de boom is gesplitst.
// Maak een nieuwe wortelknoop.
// Alloceer een nieuwe wortelpagina,
// verhoog de diepte van de boom.
root = allocPageI();
h++;
// Schrijf naar de nieuwe wortelpagina verwijzingen naar de
// twee knopen die uit de oude wortel zijn ontstaan.
ifile.seek(root * PAGESIZE);
ifile.writeInt(newv[0]);
ifile.writeInt(newp[0]);
ifile.writeInt(newv[1]);
ifile.writeInt(newp[1]);
// Vul aan met lege verwijzingen.
for (i = 2; i < 2*k; i++) {
ifile.writeInt(-1);
ifile.writeInt(-1);
}
diskaccess++;
// Update eerste pagina van indexfile.
ifile.seek(0);
ifile.writeInt(h);
ifile.writeInt(root);
diskaccess++;
}
}
// Vervang een bestaand record door r.
//-----------------------------------------------------------------------
public void update(Record r) throws Exception, IOException
{
int p;
// Bepaal de positie van het record.
p = findRecord(r.key);
if (p == -1) {
// Het record bestaat niet, geef een exceptie.
throw new Exception("Record niet gevonden");
}
// Overschrijf het record met <r>.
rfile.seek(p);
r.write(rfile);
diskaccess++;
}
// Zoek het record met de sleutel key.
//-----------------------------------------------------------------------
public Record retrieve(int key) throws IOException
{
Record r = Record.newRecord(recordType);
int p;
// Bepaal de positie van het record.
p = findRecord(key);
if (p == -1) {
// Het record bestaat niet, geef null terug.
return null;
}
// Lees het record.
rfile.seek(p);
r.read(rfile);
diskaccess++;
// Geef het record terug.
return r;
}
// Verwijder het record met de sleutel key.
//-----------------------------------------------------------------------
public void delete(int key) throws Exception, IOException
{
int[] opvp = new int[2*k];
int[] opvv = new int[2*k];
boolean b;
int i;
// Verwijder het record uit de boom.
b = removeInternal(key, root, 1);
if ( b && h > 1 ) {
// Als de wortel slechts 1 interne knoop als opvolger heeft,
// kan deze opvolger de nieuwe wortel worden.
// Lees de wortelpagina.
ifile.seek(root * PAGESIZE);
for (i = 0; i < 2*k; i++) {
opvv[i] = ifile.readInt();
opvp[i] = ifile.readInt();
}
diskaccess++;
if (opvp[1] == -1) {
// De wortel heeft slechts 1 opvolger.
// Verwijder de oude wortelpagina.
freePageI(root);
// De opvolger van de oude wortel wordt de nieuwe wortel.
// De hoogte van de boom vermindert daardoor.
root = opvp[0];
h--;
// Update eerste pagina van indexfile.
ifile.seek(0);
ifile.writeInt(h);
ifile.writeInt(root);
diskaccess++;
}
}
}
}
//===========================================================================
// End
//===========================================================================