Closed Thread Icon

Preserved Topic: Java B-Tree fixExcess Problem (Page 1 of 1) Pages that link to <a href="https://ozoneasylum.com/backlink?for=20933" title="Pages that link to Preserved Topic: Java B-Tree fixExcess Problem (Page 1 of 1)" rel="nofollow" >Preserved Topic: Java B-Tree fixExcess Problem <span class="small">(Page 1 of 1)</span>\

 
WarMage
Maniac (V) Mad Scientist

From: Rochester, New York, USA
Insane since: May 2000

posted posted 05-06-2001 23:23

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).]

WarMage
Maniac (V) Mad Scientist

From: Rochester, New York, USA
Insane since: May 2000

posted posted 05-07-2001 22:30

NM, I figured it out, BTW anyone want to tell me what OWL means? I had someone write that to me the other day.

butcher
Paranoid (IV) Inmate

From: New Jersey, USA
Insane since: Oct 2000

posted posted 05-07-2001 22:47

Mage

First of all, I don't know what OWL stands for, and it's not in this rather comprehensive list at this link, kindly provided by Bitdamaged in another forum.

Second of all, I think you are the only other person in this Asylum that is fluent in Java. You are the only one who ever posts answers to my Java questions. (Thanks BTW)

WarMage
Maniac (V) Mad Scientist

From: Rochester, New York, USA
Insane since: May 2000

posted posted 05-07-2001 23:15

Thanks for the link on the OWL, I didn't think i would get a meaning out of it, someone just attempting to confuse me...Butcher, your a java person, so I am not the only one.

I am sure there are other Java people in here somewhere... right? plz?

-mage-

p.s. I will post the complete BTree for all of your use in a couple of days, reason being if it gets out now, I am bound to get the repercussion of, "You stole that, I saw it online, some WarMage person wrote that"... Don't want to have to go on and explain that mess. Not saying people want my code just that the < .0000000001% chance of it happening is worth the precausion, of not posting it here.

« BackwardsOnwards »

Show Forum Drop Down Menu