I am having a bit of trouble writting a
private void fixExcess(int i)
method of a B-Tree I am attempting to create.
The function works after a private void looseAdd(Comparable element) has been preformed, if the number of data variables is greater than the max allowed.
The way it should work would be to split the node (array) in question in half, taking the middle node and moving it up to the node above, and finally make the two halves into seperate nodes.
I add Comparable objects to the B-Tree by using the add method, which in turn calls the looseAdd method, and then once a looseAdd has been preformed will attempt to fix the root, if it has too many elements.
I have commented out the part where I am attempting to fix the array, in the add method, since I have a bit of a logic error in there, that needs to be fixed.
The main question is how would I go about writing this fixExcess method. I have attempted to write it a number of times, but I always loose track of all the system.arraycopy calls.
Any help anyone could offer me on this would be greatly appreciated.
The code I have so far is below:
code:
public class ComparableBTreeSet
{
private static int min = 1;
private static int max = 2 * min;
private int dataCount;
private int subsetCount;
Comparable[] data = new Comparable[max + 1];
ComparableBTreeSet[] subset = new ComparableBTreeSet[max + 2];
public static void main(String args[])
{
ComparableBTreeSet b = new ComparableBTreeSet();
for (int i = 0; i < 8 ; i++ )
{
System.out.print("Please enter some data ("+(8-i)+" more): ");
String temp = SavitchIn.readLine();
b.add((Comparable)temp);
}
b.print();
}
public ComparableBTreeSet()
{
dataCount = 0;
subsetCount = 0;
}
public void add(Comparable element)
{
looseAdd(element);
if (dataCount > max)
{
Comparable[] tempData = new Comparable[max + 1];
ComparableBTreeSet[] tempSubset = new ComparableBTreeSet[max+2];
System.arraycopy(data, 0, tempData, 0, max+1);
System.arraycopy(subset, 0, tempSubset, 0, max+2);
data = new Comparable[max + 1];
subset = new ComparableBTreeSet[max + 2];
ComparableBTreeSet tempNode = new ComparableBTreeSet();
tempNode.data = tempData;
tempNode.subset = tempSubset;
tempNode.dataCount = dataCount;
tempNode.subsetCount = subsetCount;
subset[0] = tempNode;
dataCount = 0;
subsetCount = 1;
fixExcess(0);
}
}
private void looseAdd(Comparable element)
{
if (contains(element)){}
else
{
int placer = firstGE(element);
if (subsetCount == 0)
{
Comparable[] temp = new Comparable[dataCount-placer];
System.arraycopy(data,placer,temp,0,temp.length);
data[placer] = element;
dataCount++;
System.arraycopy(temp,0,data,placer+1,temp.length);
}
else
{
subset[placer].looseAdd(element);
if (subset[placer].dataCount > max)
{
fixExcess(placer);
}
}
}
}
private void fixExcess(int i)
{
}
private int firstGE(Comparable target)
{
for (int i = 0; i < dataCount ; i++ )
if (target.compareTo(data[i]) < 0)
return i;
return dataCount;
}
public boolean contains(Comparable target)
{
for (int i = 0 ; i < dataCount ; i++ )
if (data[i].equals(target))
return true;
for (int i = 0; i < subsetCount ; i++ )
subset[i].contains(target);
return false;
}
public void print()
{
for (int i = 0; i < dataCount ; i++ )
System.out.print(" "+data[i]+" ");
System.out.println();
for (int i = 0 ; i < subsetCount ; i++ )
subset[i].print();
}
}
[This message has been edited by WarMage (edited 05-06-2001).]
posted 05-06-2001 23:23
