Author: elecharny
Date: Sat Jul 28 19:58:47 2012
New Revision: 1366759
URL: http://svn.apache.org/viewvc?rev=1366759&view=rev
Log:
Removed the useless newleftMost field in the Result classes
Modified:
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/AbstractBorrowedFromSiblingResult.java
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/AbstractDeleteResult.java
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/BorrowedFromLeftResult.java
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/BorrowedFromRightResult.java
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/DeleteResult.java
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Leaf.java
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/MergedWithSiblingResult.java
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Node.java
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/RemoveResult.java
labs/mavibot/trunk/mavibot/src/test/java/org/apache/mavibot/btree/LeafTest.java
Modified:
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/AbstractBorrowedFromSiblingResult.java
URL:
http://svn.apache.org/viewvc/labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/AbstractBorrowedFromSiblingResult.java?rev=1366759&r1=1366758&r2=1366759&view=diff
==============================================================================
---
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/AbstractBorrowedFromSiblingResult.java
(original)
+++
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/AbstractBorrowedFromSiblingResult.java
Sat Jul 28 19:58:47 2012
@@ -19,6 +19,7 @@
*/
package org.apache.mavibot.btree;
+
/**
* The result of a delete operation, when the child has not been merged, and
when
* we have borrowed an element from the left sibling. It contains the
@@ -29,11 +30,12 @@ package org.apache.mavibot.btree;
* @author <a href="mailto:[email protected]";>Mavibot labs Project</a>
*/
-/* No qualifier */ abstract class AbstractBorrowedFromSiblingResult<K, V>
extends AbstractDeleteResult<K, V> implements BorrowedFromSiblingResult<K, V>
+/* No qualifier */abstract class AbstractBorrowedFromSiblingResult<K, V>
extends AbstractDeleteResult<K, V> implements
+ BorrowedFromSiblingResult<K, V>
{
/** The modified sibling reference */
private Page<K, V> modifiedSibling;
-
+
/** Tells if the sibling is the left or right one */
protected SiblingPosition position;
@@ -43,23 +45,24 @@ package org.apache.mavibot.btree;
LEFT,
RIGHT
}
-
+
+
/**
* The default constructor for RemoveResult.
*
* @param modifiedPage The modified page
* @param modifiedSibling The modified sibling
* @param removedElement The removed element (can be null if the key
wasn't present in the tree)
- * @param newLeftMost The element on the left of he current page
*/
- /* No qualifier */ AbstractBorrowedFromSiblingResult( Page<K, V>
modifiedPage, Page<K, V> modifiedSibling, Tuple<K, V> removedElement, K
newLeftMost, SiblingPosition position )
+ /* No qualifier */AbstractBorrowedFromSiblingResult( Page<K, V>
modifiedPage, Page<K, V> modifiedSibling,
+ Tuple<K, V> removedElement, SiblingPosition position )
{
- super( modifiedPage, removedElement, newLeftMost );
+ super( modifiedPage, removedElement );
this.modifiedSibling = modifiedSibling;
this.position = position;
}
-
-
+
+
/**
* {@inheritDoc}
*/
@@ -67,8 +70,8 @@ package org.apache.mavibot.btree;
{
return modifiedSibling;
}
-
-
+
+
/**
* {@inheritDoc}
*/
@@ -76,8 +79,8 @@ package org.apache.mavibot.btree;
{
return position == SiblingPosition.LEFT;
}
-
-
+
+
/**
* {@inheritDoc}
*/
@@ -85,19 +88,18 @@ package org.apache.mavibot.btree;
{
return position == SiblingPosition.RIGHT;
}
-
-
+
+
/**
* @see Object#toString()
*/
public String toString()
{
StringBuilder sb = new StringBuilder();
-
+
sb.append( "\n removed element : " ).append( getRemovedElement() );
sb.append( "\n modifiedPage : " ).append( getModifiedPage() );
sb.append( "\n modifiedSibling : " ).append( getModifiedSibling() );
- sb.append( "\n new LeftMost : " ).append( getNewLeftMost() );
return sb.toString();
}
Modified:
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/AbstractDeleteResult.java
URL:
http://svn.apache.org/viewvc/labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/AbstractDeleteResult.java?rev=1366759&r1=1366758&r2=1366759&view=diff
==============================================================================
---
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/AbstractDeleteResult.java
(original)
+++
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/AbstractDeleteResult.java
Sat Jul 28 19:58:47 2012
@@ -19,40 +19,37 @@
*/
package org.apache.mavibot.btree;
+
/**
* An abstract class to gather common elements of the DeleteResult
*
* @param <K> The type for the Key
* @param <V> The type for the stored value
- * @author <a href="mailto:[email protected]";>Mavibot labs Project</a>
+ * @author <a href="mailto:[email protected]";>Mavibot labs Project</a>
*/
-/* No qualifier */ abstract class AbstractDeleteResult<K, V> implements
DeleteResult<K, V>
+/* No qualifier */abstract class AbstractDeleteResult<K, V> implements
DeleteResult<K, V>
{
/** The modified page reference */
private Page<K, V> modifiedPage;
-
+
/** The removed element if the key was found in the tree*/
private Tuple<K, V> removedElement;
-
- /** The new leftmost element if the removed k was on position 0. Null
otherwise */
- private K newLeftMost;
-
+
+
/**
* The default constructor for AbstractDeleteResult.
*
* @param modifiedPage The modified page
* @param removedElement The removed element (can be null if the key
wasn't present in the tree)
- * @param newLeftMost The element on the left of he current page
*/
- /* No qualifier */ AbstractDeleteResult( Page<K, V> modifiedPage, Tuple<K,
V> removedElement, K newLeftMost )
+ /* No qualifier */AbstractDeleteResult( Page<K, V> modifiedPage, Tuple<K,
V> removedElement )
{
this.modifiedPage = modifiedPage;
this.removedElement = removedElement;
- this.newLeftMost = newLeftMost;
}
-
-
+
+
/**
* {@inheritDoc}
*/
@@ -72,28 +69,10 @@ package org.apache.mavibot.btree;
/**
- * @return the newLeftMost
- */
- public K getNewLeftMost()
- {
- return newLeftMost;
- }
-
-
- /**
* @param modifiedPage the modifiedPage to set
*/
- /* No qualifier */ void setModifiedPage( Page<K, V> modifiedPage )
+ /* No qualifier */void setModifiedPage( Page<K, V> modifiedPage )
{
this.modifiedPage = modifiedPage;
}
-
-
- /**
- * @param newLeftMost the newLeftMost to set
- */
- /* No qualifier */ void setNewLeftMost( K newLeftMost )
- {
- this.newLeftMost = newLeftMost;
- }
}
Modified:
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/BorrowedFromLeftResult.java
URL:
http://svn.apache.org/viewvc/labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/BorrowedFromLeftResult.java?rev=1366759&r1=1366758&r2=1366759&view=diff
==============================================================================
---
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/BorrowedFromLeftResult.java
(original)
+++
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/BorrowedFromLeftResult.java
Sat Jul 28 19:58:47 2012
@@ -19,6 +19,7 @@
*/
package org.apache.mavibot.btree;
+
/**
* The result of a delete operation, when the child has not been merged, and
when
* we have borrowed an element from the left sibling. It contains the
@@ -29,7 +30,7 @@ package org.apache.mavibot.btree;
* @author <a href="mailto:[email protected]";>Mavibot labs Project</a>
*/
-/* No qualifier */ class BorrowedFromLeftResult<K, V> extends
AbstractBorrowedFromSiblingResult<K, V>
+/* No qualifier */class BorrowedFromLeftResult<K, V> extends
AbstractBorrowedFromSiblingResult<K, V>
{
/**
* The default constructor for BorrowedFromLeftResult.
@@ -37,21 +38,21 @@ package org.apache.mavibot.btree;
* @param modifiedPage The modified page
* @param modifiedSibling The modified sibling
* @param removedElement The removed element (can be null if the key
wasn't present in the tree)
- * @param newLeftMost The element on the left of he current page
*/
- /* No qualifier */ BorrowedFromLeftResult( Page<K, V> modifiedPage,
Page<K, V> modifiedSibling, Tuple<K, V> removedElement, K newLeftMost )
+ /* No qualifier */BorrowedFromLeftResult( Page<K, V> modifiedPage, Page<K,
V> modifiedSibling,
+ Tuple<K, V> removedElement )
{
- super( modifiedPage, modifiedSibling, removedElement, newLeftMost,
AbstractBorrowedFromSiblingResult.SiblingPosition.LEFT );
+ super( modifiedPage, modifiedSibling, removedElement,
AbstractBorrowedFromSiblingResult.SiblingPosition.LEFT );
}
-
-
+
+
/**
* @see Object#toString()
*/
public String toString()
{
StringBuilder sb = new StringBuilder();
-
+
sb.append( "Borrowed from left" );
sb.append( super.toString() );
Modified:
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/BorrowedFromRightResult.java
URL:
http://svn.apache.org/viewvc/labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/BorrowedFromRightResult.java?rev=1366759&r1=1366758&r2=1366759&view=diff
==============================================================================
---
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/BorrowedFromRightResult.java
(original)
+++
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/BorrowedFromRightResult.java
Sat Jul 28 19:58:47 2012
@@ -19,6 +19,7 @@
*/
package org.apache.mavibot.btree;
+
/**
* The result of a delete operation, when the child has not been merged. It
contains the
* reference to the modified page, and the removed element.
@@ -26,9 +27,9 @@ package org.apache.mavibot.btree;
* @param <K> The type for the Key
* @param <V> The type for the stored value
- * @author <a href="mailto:[email protected]";>Mavibot labs Project</a>
+ * @author <a href="mailto:[email protected]";>Mavibot labs Project</a>
*/
-/* No qualifier */ class BorrowedFromRightResult<K, V> extends
AbstractBorrowedFromSiblingResult<K, V>
+/* No qualifier */class BorrowedFromRightResult<K, V> extends
AbstractBorrowedFromSiblingResult<K, V>
{
/**
* The default constructor for BorrowedFromRightResult.
@@ -36,21 +37,21 @@ package org.apache.mavibot.btree;
* @param modifiedPage The modified page
* @param modifiedSibling The modified sibling
* @param removedElement The removed element (can be null if the key
wasn't present in the tree)
- * @param newLeftMost The element on the left of he current page
*/
- /* No qualifier */ BorrowedFromRightResult( Page<K, V> modifiedPage,
Page<K, V> modifiedSibling, Tuple<K, V> removedElement, K newLeftMost )
+ /* No qualifier */BorrowedFromRightResult( Page<K, V> modifiedPage,
Page<K, V> modifiedSibling,
+ Tuple<K, V> removedElement )
{
- super( modifiedPage, modifiedSibling, removedElement, newLeftMost,
AbstractBorrowedFromSiblingResult.SiblingPosition.RIGHT );
+ super( modifiedPage, modifiedSibling, removedElement,
AbstractBorrowedFromSiblingResult.SiblingPosition.RIGHT );
}
-
-
+
+
/**
* @see Object#toString()
*/
public String toString()
{
StringBuilder sb = new StringBuilder();
-
+
sb.append( "Borrowed from right" );
sb.append( super.toString() );
Modified:
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/DeleteResult.java
URL:
http://svn.apache.org/viewvc/labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/DeleteResult.java?rev=1366759&r1=1366758&r2=1366759&view=diff
==============================================================================
---
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/DeleteResult.java
(original)
+++
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/DeleteResult.java
Sat Jul 28 19:58:47 2012
@@ -19,6 +19,7 @@
*/
package org.apache.mavibot.btree;
+
/**
* The result of an delete operation.
*
@@ -39,11 +40,4 @@ interface DeleteResult<K, V>
* @return the removed element
*/
Tuple<K, V> getRemovedElement();
-
-
- /**
- * @return the leftmost element for this btree
- * @return
- */
- K getNewLeftMost();
}
Modified:
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Leaf.java
URL:
http://svn.apache.org/viewvc/labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Leaf.java?rev=1366759&r1=1366758&r2=1366759&view=diff
==============================================================================
--- labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Leaf.java
(original)
+++ labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Leaf.java
Sat Jul 28 19:58:47 2012
@@ -19,8 +19,10 @@
*/
package org.apache.mavibot.btree;
+
import java.util.LinkedList;
+
/**
* A MVCC Leaf. It stores the keys and values. It does not have any children.
*
@@ -33,29 +35,30 @@ public class Leaf<K, V> extends Abstract
{
/** Values associated with keys */
protected V[] values;
-
-
+
+
/**
* Empty constructor
*/
- /* No qualifier */ Leaf( BTree<K, V> btree )
+ /* No qualifier */Leaf( BTree<K, V> btree )
{
super( btree );
}
-
-
+
+
/**
* Internal constructor used to create Page instance used when a page is
being copied or overflow
*/
- @SuppressWarnings("unchecked") // Cannot create an array of generic objects
+ @SuppressWarnings("unchecked")
+ // Cannot create an array of generic objects
private Leaf( BTree<K, V> btree, long revision, int nbElems )
{
super( btree, revision, nbElems );
- this.values = (V[])new Object[nbElems];
+ this.values = ( V[] ) new Object[nbElems];
}
-
-
+
+
/**
* {@inheritDoc}
*/
@@ -68,23 +71,23 @@ public class Leaf<K, V> extends Abstract
{
// We already have the key in the page : replace the value
// into a copy of this page, unless the page has already be copied
- int index = - ( pos + 1 );
-
+ int index = -( pos + 1 );
+
// Replace the existing value in a copy of the current page
InsertResult<K, V> result = replaceElement( revision, key, value,
index );
-
+
return result;
}
-
+
// The key is not present in the leaf. We have to add it in the page
if ( nbElems < btree.pageSize )
{
// The current page is not full, it can contain the added element.
// We insert it into a copied page and return the result
Page<K, V> modifiedPage = addElement( revision, key, value, pos );
-
+
InsertResult<K, V> result = new ModifyResult<K, V>( modifiedPage,
null );
-
+
return result;
}
else
@@ -92,12 +95,12 @@ public class Leaf<K, V> extends Abstract
// The Page is already full : we split it and return the overflow
element,
// after having created two pages.
InsertResult<K, V> result = addAndSplit( revision, key, value, pos
);
-
+
return result;
}
}
-
-
+
+
/**
* {@inheritDoc}
*/
@@ -110,16 +113,16 @@ public class Leaf<K, V> extends Abstract
// Empty leaf
return NotPresentResult.NOT_PRESENT;
}
-
+
// Find the key in the page
int pos = findPos( key );
-
+
if ( pos >= 0 )
{
// Not found : return the not present result.
return NotPresentResult.NOT_PRESENT;
}
-
+
int index = -( pos + 1 );
// If the parent is null, then this page is the root page.
@@ -127,29 +130,29 @@ public class Leaf<K, V> extends Abstract
{
// Just remove the entry if it's present
DeleteResult<K, V> result = removeElement( revision, index );
-
+
return result;
}
else
{
// The current page is not the root. Check if the leaf has more
than N/2
// elements
- int halfSize = btree.pageSize/2;
-
+ int halfSize = btree.pageSize / 2;
+
if ( nbElems == halfSize )
{
// We have to find a sibling now, and either borrow an entry
from it
// if it has more than N/2 elements, or to merge the two pages.
// Check in both next and previous page, if they have the same
parent
// and select the biggest page with the same parent to borrow
an element.
- int siblingPos = selectSibling( (Node<K, V>)parent, parentPos
);
- Leaf<K, V> sibling = (Leaf<K, V>)((Node<K,
V>)parent).children[siblingPos];
-
+ int siblingPos = selectSibling( ( Node<K, V> ) parent,
parentPos );
+ Leaf<K, V> sibling = ( Leaf<K, V> ) ( ( Node<K, V> ) parent
).children[siblingPos];
+
if ( sibling.getNbElems() == halfSize )
{
// We will merge the current page with its sibling
- DeleteResult<K, V> result = mergeWithSibling( revision,
sibling, ( siblingPos < parentPos), index );
-
+ DeleteResult<K, V> result = mergeWithSibling( revision,
sibling, ( siblingPos < parentPos ), index );
+
return result;
}
else
@@ -158,14 +161,14 @@ public class Leaf<K, V> extends Abstract
if ( siblingPos < parentPos )
{
DeleteResult<K, V> result = borrowFromLeft( revision,
sibling, index );
-
+
return result;
}
else
{
// Borrow from the right sibling
DeleteResult<K, V> result = borrowFromRight( revision,
sibling, index );
-
+
return result;
}
}
@@ -177,13 +180,13 @@ public class Leaf<K, V> extends Abstract
// we return the new pivot (it will replace any instance of
the removed
// key in its parents)
DeleteResult<K, V> result = removeElement( revision, index );
-
+
return result;
}
}
}
-
-
+
+
/**
* Merge the sibling with the current leaf, after having removed the
element in the page.
*
@@ -199,7 +202,7 @@ public class Leaf<K, V> extends Abstract
// as we merge two pages that contain N/2 elements minus the one we
remove
Leaf<K, V> newLeaf = new Leaf<K, V>( btree, revision, btree.pageSize -
1 );
Tuple<K, V> removedElement = new Tuple<K, V>( keys[pos], values[pos] );
-
+
if ( isLeft )
{
// The sibling is on the left
@@ -210,7 +213,7 @@ public class Leaf<K, V> extends Abstract
// Copy all the elements from the page up to the deletion position
System.arraycopy( keys, 0, newLeaf.keys, sibling.nbElems, pos );
System.arraycopy( values, 0, newLeaf.values, sibling.nbElems, pos
);
-
+
// And copy the remaining elements after the deletion point
System.arraycopy( keys, pos + 1, newLeaf.keys, sibling.nbElems +
pos, nbElems - pos - 1 );
System.arraycopy( values, pos + 1, newLeaf.values, sibling.nbElems
+ pos, nbElems - pos - 1 );
@@ -232,12 +235,12 @@ public class Leaf<K, V> extends Abstract
}
// And create the result
- DeleteResult<K, V> result = new MergedWithSiblingResult<K, V>(
newLeaf, removedElement, newLeaf.keys[0] );
-
+ DeleteResult<K, V> result = new MergedWithSiblingResult<K, V>(
newLeaf, removedElement );
+
return result;
}
-
-
+
+
/**
* Borrow an element from the left sibling, creating a new sibling with one
* less element and creating a new page where the element to remove has
been
@@ -252,36 +255,36 @@ public class Leaf<K, V> extends Abstract
{
// The sibling is on the left, borrow the rightmost element
K siblingKey = sibling.keys[sibling.getNbElems() - 1];
- V siblingValue = sibling.values[sibling.getNbElems() - 1 ];
-
+ V siblingValue = sibling.values[sibling.getNbElems() - 1];
+
// Create the new sibling, with one less element at the end
- Leaf<K, V> newSibling = (Leaf<K, V>)sibling.copy( revision,
sibling.getNbElems() - 1 );
+ Leaf<K, V> newSibling = ( Leaf<K, V> ) sibling.copy( revision,
sibling.getNbElems() - 1 );
// Create the new page and add the new element at the beginning
// First copy the current page, with the same size
Leaf<K, V> newLeaf = new Leaf<K, V>( btree, revision, nbElems );
-
+
// Insert the borrowed element
newLeaf.keys[0] = siblingKey;
newLeaf.values[0] = siblingValue;
-
+
// Copy the keys and the values up to the insertion position,
System.arraycopy( keys, 0, newLeaf.keys, 1, pos );
System.arraycopy( values, 0, newLeaf.values, 1, pos );
-
+
// And copy the remaining elements
System.arraycopy( keys, pos + 1, newLeaf.keys, pos + 1, keys.length -
pos - 1 );
System.arraycopy( values, pos + 1, newLeaf.values, pos + 1,
values.length - pos - 1 );
-
+
// Create the result
Tuple<K, V> removedElement = new Tuple<K, V>( keys[pos], values[pos] );
- DeleteResult<K, V> result = new BorrowedFromLeftResult<K, V>( newLeaf,
newSibling, removedElement, siblingKey );
-
+ DeleteResult<K, V> result = new BorrowedFromLeftResult<K, V>( newLeaf,
newSibling, removedElement );
+
return result;
}
-
-
+
+
/**
* Borrow an element from the right sibling, creating a new sibling with
one
* less element and creating a new page where the element to remove has
been
@@ -297,7 +300,7 @@ public class Leaf<K, V> extends Abstract
// The sibling is on the left, borrow the rightmost element
K siblingKey = sibling.keys[0];
V siblingValue = sibling.values[0];
-
+
// Create the new sibling
Leaf<K, V> newSibling = new Leaf<K, V>( btree, revision,
sibling.getNbElems() - 1 );
@@ -308,28 +311,28 @@ public class Leaf<K, V> extends Abstract
// Create the new page and add the new element at the end
// First copy the current page, with the same size
Leaf<K, V> newLeaf = new Leaf<K, V>( btree, revision, nbElems );
-
+
// Insert the borrowed element at the end
newLeaf.keys[nbElems - 1] = siblingKey;
newLeaf.values[nbElems - 1] = siblingValue;
-
+
// Copy the keys and the values up to the deletion position,
System.arraycopy( keys, 0, newLeaf.keys, 0, pos );
System.arraycopy( values, 0, newLeaf.values, 0, pos );
-
+
// And copy the remaining elements
System.arraycopy( keys, pos + 1, newLeaf.keys, pos, keys.length - pos
- 1 );
System.arraycopy( values, pos + 1, newLeaf.values, pos, values.length
- pos - 1 );
-
+
// Create the result
Tuple<K, V> removedElement = new Tuple<K, V>( keys[pos], values[pos] );
- DeleteResult<K, V> result = new BorrowedFromRightResult<K, V>(
newLeaf, newSibling, removedElement, newLeaf.keys[0] );
-
+ DeleteResult<K, V> result = new BorrowedFromRightResult<K, V>(
newLeaf, newSibling, removedElement );
+
return result;
}
-
-
+
+
/**
* Remove the element at a given position.
*
@@ -337,16 +340,14 @@ public class Leaf<K, V> extends Abstract
* @param pos The position into the page of the element to remove
* @return The modified page with the <K,V> element added
*/
- private DeleteResult<K, V> removeElement( long revision,int pos )
+ private DeleteResult<K, V> removeElement( long revision, int pos )
{
// First copy the current page, but remove one element in the copied
page
Leaf<K, V> newLeaf = new Leaf<K, V>( btree, revision, nbElems - 1 );
-
+
// Get the removed element
Tuple<K, V> removedElement = new Tuple<K, V>( keys[pos], values[pos] );
-
- K newLeftMost = null;
-
+
// Deal with the special case of an page with only one element by
skipping
// the copy, as we won't have any remaining element in the page
if ( nbElems > 1 )
@@ -354,20 +355,15 @@ public class Leaf<K, V> extends Abstract
// Copy the keys and the values up to the insertion position
System.arraycopy( keys, 0, newLeaf.keys, 0, pos );
System.arraycopy( values, 0, newLeaf.values, 0, pos );
-
+
// And copy the elements after the position
- System.arraycopy( keys, pos + 1, newLeaf.keys, pos, keys.length -
pos - 1 );
+ System.arraycopy( keys, pos + 1, newLeaf.keys, pos, keys.length -
pos - 1 );
System.arraycopy( values, pos + 1, newLeaf.values, pos,
values.length - pos - 1 );
-
- if ( pos == 0 )
- {
- newLeftMost = newLeaf.keys[0];
- }
}
-
+
// Create the result
- DeleteResult<K, V> result = new RemoveResult<K, V>( newLeaf,
removedElement, newLeftMost );
-
+ DeleteResult<K, V> result = new RemoveResult<K, V>( newLeaf,
removedElement );
+
return result;
}
@@ -378,18 +374,18 @@ public class Leaf<K, V> extends Abstract
public V find( K key )
{
int pos = findPos( key );
-
+
if ( pos < 0 )
{
- return values[- ( pos + 1 ) ];
+ return values[-( pos + 1 )];
}
else
{
return null;
}
}
-
-
+
+
/**
* {@inheritDoc}
*/
@@ -397,11 +393,11 @@ public class Leaf<K, V> extends Abstract
{
int pos = findPos( key );
Cursor<K, V> cursor = null;
-
+
if ( pos < 0 )
{
- int index = - ( pos + 1 );
-
+ int index = -( pos + 1 );
+
// The first element has been found. Create the cursor
stack.push( new ParentPos<K, V>( this, index ) );
@@ -420,42 +416,42 @@ public class Leaf<K, V> extends Abstract
{
// Not found : return a null cursor
stack.push( new ParentPos<K, V>( this, -1 ) );
-
+
return new Cursor<K, V>( transaction, stack );
}
}
-
+
return cursor;
}
-
-
+
+
/**
* {@inheritDoc}
*/
- public Cursor<K, V> browse( Transaction<K, V> transaction,
LinkedList<ParentPos<K, V>> stack )
+ public Cursor<K, V> browse( Transaction<K, V> transaction,
LinkedList<ParentPos<K, V>> stack )
{
int pos = 0;
Cursor<K, V> cursor = null;
-
+
if ( nbElems == 0 )
{
// The tree is empty, it's the root, we have nothing to return
stack.push( new ParentPos<K, V>( null, -1 ) );
-
+
return new Cursor<K, V>( transaction, stack );
}
else
{
// Start at the beginning of the page
stack.push( new ParentPos<K, V>( this, pos ) );
-
+
cursor = new Cursor<K, V>( transaction, stack );
}
-
+
return cursor;
}
-
-
+
+
/**
* Copy the current page and all of the keys, values and children, if it's
not a leaf.
*
@@ -474,7 +470,7 @@ public class Leaf<K, V> extends Abstract
return newLeaf;
}
-
+
/**
* Copy the current page if needed, and replace the value at the position
we have found the key.
*
@@ -487,24 +483,24 @@ public class Leaf<K, V> extends Abstract
private InsertResult<K, V> replaceElement( long revision, K key, V value,
int pos )
{
Leaf<K, V> newLeaf = this;
-
+
if ( this.revision != revision )
{
// The page hasn't been modified yet, we need to copy it first
- newLeaf = (Leaf<K, V>)copy( revision, nbElems );
+ newLeaf = ( Leaf<K, V> ) copy( revision, nbElems );
}
-
+
// Now we can inject the value
V oldValue = newLeaf.values[pos];
newLeaf.values[pos] = value;
-
+
// Create the result
InsertResult<K, V> result = new ModifyResult<K, V>( newLeaf, oldValue
);
-
+
return result;
}
-
-
+
+
/**
* Add a new <K, V> into a copy of the current page at a given position.
We return the
* modified page. The new page will have one more element than the current
page.
@@ -519,7 +515,7 @@ public class Leaf<K, V> extends Abstract
{
// First copy the current page, but add one element in the copied page
Leaf<K, V> newLeaf = new Leaf<K, V>( btree, revision, nbElems + 1 );
-
+
// Deal with the special case of an empty page
if ( nbElems == 0 )
{
@@ -531,11 +527,11 @@ public class Leaf<K, V> extends Abstract
// Copy the keys and the values up to the insertion position
System.arraycopy( keys, 0, newLeaf.keys, 0, pos );
System.arraycopy( values, 0, newLeaf.values, 0, pos );
-
+
// Add the new element
newLeaf.keys[pos] = key;
newLeaf.values[pos] = value;
-
+
// And copy the remaining elements
System.arraycopy( keys, pos, newLeaf.keys, pos + 1, keys.length -
pos );
System.arraycopy( values, pos, newLeaf.values, pos + 1,
values.length - pos );
@@ -543,8 +539,8 @@ public class Leaf<K, V> extends Abstract
return newLeaf;
}
-
-
+
+
/**
* Split a full page into two new pages, a left, a right and a pivot
element. The new pages will
* each contains half of the original elements. <br/>
@@ -565,7 +561,7 @@ public class Leaf<K, V> extends Abstract
int middle = btree.pageSize >> 1;
Leaf<K, V> leftLeaf = null;
Leaf<K, V> rightLeaf = null;
-
+
// Determinate where to store the new value
if ( pos <= middle )
{
@@ -575,11 +571,11 @@ public class Leaf<K, V> extends Abstract
// Copy the keys and the values up to the insertion position
System.arraycopy( keys, 0, leftLeaf.keys, 0, pos );
System.arraycopy( values, 0, leftLeaf.values, 0, pos );
-
+
// Add the new element
leftLeaf.keys[pos] = key;
leftLeaf.values[pos] = value;
-
+
// And copy the remaining elements
System.arraycopy( keys, pos, leftLeaf.keys, pos + 1, middle - pos
);
System.arraycopy( values, pos, leftLeaf.values, pos + 1, middle -
pos );
@@ -602,32 +598,32 @@ public class Leaf<K, V> extends Abstract
// Now, create the right page
rightLeaf = new Leaf<K, V>( btree, revision, middle + 1 );
-
+
int rightPos = pos - middle;
// Copy the keys and the values up to the insertion position
System.arraycopy( keys, middle, rightLeaf.keys, 0, rightPos );
System.arraycopy( values, middle, rightLeaf.values, 0, rightPos );
-
+
// Add the new element
rightLeaf.keys[rightPos] = key;
rightLeaf.values[rightPos] = value;
-
+
// And copy the remaining elements
System.arraycopy( keys, pos, rightLeaf.keys, rightPos + 1, nbElems
- pos );
- System.arraycopy( values, pos, rightLeaf.values, rightPos + 1,
nbElems -pos );
+ System.arraycopy( values, pos, rightLeaf.values, rightPos + 1,
nbElems - pos );
}
-
+
// Get the pivot
K pivot = rightLeaf.keys[0];
-
+
// Create the result
InsertResult<K, V> result = new SplitResult<K, V>( pivot, leftLeaf,
rightLeaf );
-
+
return result;
}
-
-
+
+
/**
* {@inheritDoc}
*/
@@ -635,8 +631,8 @@ public class Leaf<K, V> extends Abstract
{
return new Tuple<K, V>( keys[0], values[0] );
}
-
-
+
+
/**
* {@inheritDoc}
*/
@@ -652,16 +648,16 @@ public class Leaf<K, V> extends Abstract
public String toString()
{
StringBuilder sb = new StringBuilder();
-
+
sb.append( "Leaf[" );
sb.append( super.toString() );
- sb.append ( "] -> {" );
-
+ sb.append( "] -> {" );
+
if ( nbElems > 0 )
{
boolean isFirst = true;
-
+
for ( int i = 0; i < nbElems; i++ )
{
if ( isFirst )
@@ -672,30 +668,30 @@ public class Leaf<K, V> extends Abstract
{
sb.append( ", " );
}
-
+
sb.append( "<" ).append( keys[i] ).append( "," ).append(
values[i] ).append( ">" );
}
}
-
+
sb.append( "}" );
-
+
return sb.toString();
}
-
-
+
+
/**
* {@inheritDoc}
*/
public String dumpPage( String tabs )
{
StringBuilder sb = new StringBuilder();
-
+
sb.append( tabs );
-
+
if ( nbElems > 0 )
{
boolean isFirst = true;
-
+
for ( int i = 0; i < nbElems; i++ )
{
if ( isFirst )
@@ -706,13 +702,13 @@ public class Leaf<K, V> extends Abstract
{
sb.append( ", " );
}
-
+
sb.append( "<" ).append( keys[i] ).append( "," ).append(
values[i] ).append( ">" );
}
}
-
+
sb.append( "\n" );
-
+
return sb.toString();
}
}
Modified:
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/MergedWithSiblingResult.java
URL:
http://svn.apache.org/viewvc/labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/MergedWithSiblingResult.java?rev=1366759&r1=1366758&r2=1366759&view=diff
==============================================================================
---
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/MergedWithSiblingResult.java
(original)
+++
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/MergedWithSiblingResult.java
Sat Jul 28 19:58:47 2012
@@ -19,6 +19,7 @@
*/
package org.apache.mavibot.btree;
+
/**
* The result of a delete operation, when the child has not been merged. It
contains the
* reference to the modified page, and the removed element.
@@ -28,32 +29,30 @@ package org.apache.mavibot.btree;
* @author <a href="mailto:[email protected]";>Mavibot labs Project</a>
*/
-/* No qualifier */ class MergedWithSiblingResult<K, V> extends
AbstractDeleteResult<K, V>
+/* No qualifier */class MergedWithSiblingResult<K, V> extends
AbstractDeleteResult<K, V>
{
/**
* The default constructor for RemoveResult.
*
* @param modifiedPage The modified page
* @param removedElement The removed element (can be null if the key
wasn't present in the tree)
- * @param newLeftMost The element on the left of he current page
*/
- /* No qualifier */ MergedWithSiblingResult( Page<K, V> modifiedPage,
Tuple<K, V> removedElement, K newLeftMost )
+ /* No qualifier */MergedWithSiblingResult( Page<K, V> modifiedPage,
Tuple<K, V> removedElement )
{
- super( modifiedPage, removedElement, newLeftMost );
+ super( modifiedPage, removedElement );
}
-
-
+
+
/**
* @see Object#toString()
*/
public String toString()
{
StringBuilder sb = new StringBuilder();
-
+
sb.append( "MergedWithSiblingResult" );
sb.append( "\n removed element : " ).append( getRemovedElement() );
sb.append( "\n modifiedPage : " ).append( getModifiedPage() );
- sb.append( "\n new LeftMost : " ).append( getNewLeftMost() );
return sb.toString();
}
Modified:
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Node.java
URL:
http://svn.apache.org/viewvc/labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Node.java?rev=1366759&r1=1366758&r2=1366759&view=diff
==============================================================================
--- labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Node.java
(original)
+++ labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Node.java
Sat Jul 28 19:58:47 2012
@@ -165,11 +165,9 @@ import java.util.LinkedList;
newPage.children[index] = removeResult.getModifiedPage();
}
- K newLeftMost = removeResult.getNewLeftMost();
-
- if ( ( newLeftMost != null ) && ( pos < 0 ) )
+ if ( pos < 0 )
{
- newPage.keys[index] = newLeftMost;
+ newPage.keys[index] =
removeResult.getModifiedPage().findLeftMost().getKey();
}
// Modify the result and return
@@ -197,7 +195,7 @@ import java.util.LinkedList;
if ( nbElems == 1 )
{
removeResult = new RemoveResult<K, V>(
mergedResult.getModifiedPage(),
- mergedResult.getRemovedElement(),
mergedResult.getNewLeftMost() );
+ mergedResult.getRemovedElement() );
}
else
{
@@ -285,7 +283,7 @@ import java.util.LinkedList;
// Create the result
DeleteResult<K, V> result = new BorrowedFromRightResult<K, V>(
newNode, newSibling,
- mergedResult.getRemovedElement(), siblingKey );
+ mergedResult.getRemovedElement() );
return result;
}
@@ -363,7 +361,7 @@ import java.util.LinkedList;
// Create the result
DeleteResult<K, V> result = new BorrowedFromLeftResult<K, V>( newNode,
newSibling,
- mergedResult.getRemovedElement(), newNode.findLeftMost().getKey()
);
+ mergedResult.getRemovedElement() );
return result;
}
@@ -483,7 +481,7 @@ import java.util.LinkedList;
}
// And create the result
- DeleteResult<K, V> result = new MergedWithSiblingResult<K, V>(
newNode, removedElement, newNode.keys[0] );
+ DeleteResult<K, V> result = new MergedWithSiblingResult<K, V>(
newNode, removedElement );
return result;
}
@@ -672,7 +670,7 @@ import java.util.LinkedList;
// Modify the result and return
RemoveResult<K, V> removeResult = new RemoveResult<K, V>( newPage,
- borrowedResult.getRemovedElement(),
borrowedResult.getNewLeftMost() );
+ borrowedResult.getRemovedElement() );
return removeResult;
}
@@ -690,8 +688,6 @@ import java.util.LinkedList;
// First copy the current page, but remove one element in the copied
page
Node<K, V> newNode = new Node<K, V>( btree, revision, nbElems - 1 );
- K newLeftMost = null;
-
int index = Math.abs( pos ) - 2;
//
@@ -728,11 +724,8 @@ import java.util.LinkedList;
}
}
- // Propagate the new leftmost
- newLeftMost = mergedResult.getNewLeftMost();
-
// Create the result
- RemoveResult<K, V> result = new RemoveResult<K, V>( newNode,
mergedResult.getRemovedElement(), newLeftMost );
+ RemoveResult<K, V> result = new RemoveResult<K, V>( newNode,
mergedResult.getRemovedElement() );
return result;
}
Modified:
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/RemoveResult.java
URL:
http://svn.apache.org/viewvc/labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/RemoveResult.java?rev=1366759&r1=1366758&r2=1366759&view=diff
==============================================================================
---
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/RemoveResult.java
(original)
+++
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/RemoveResult.java
Sat Jul 28 19:58:47 2012
@@ -19,6 +19,7 @@
*/
package org.apache.mavibot.btree;
+
/**
* The result of a delete operation, when the child has not been merged. It
contains the
* reference to the modified page, and the removed element.
@@ -28,32 +29,30 @@ package org.apache.mavibot.btree;
* @author <a href="mailto:[email protected]";>Mavibot labs Project</a>
*/
-/* No qualifier */ class RemoveResult<K, V> extends AbstractDeleteResult<K, V>
+/* No qualifier */class RemoveResult<K, V> extends AbstractDeleteResult<K, V>
{
/**
* The default constructor for RemoveResult.
*
* @param modifiedPage The modified page
* @param removedElement The removed element (can be null if the key
wasn't present in the tree)
- * @param newLeftMost The element on the left of he current page
*/
- /* No qualifier */ RemoveResult( Page<K, V> modifiedPage, Tuple<K, V>
removedElement, K newLeftMost )
+ /* No qualifier */RemoveResult( Page<K, V> modifiedPage, Tuple<K, V>
removedElement )
{
- super( modifiedPage, removedElement, newLeftMost );
+ super( modifiedPage, removedElement );
}
-
-
+
+
/**
* @see Object#toString()
*/
public String toString()
{
StringBuilder sb = new StringBuilder();
-
+
sb.append( "RemoveResult :" );
sb.append( "\n removed element = " ).append( getRemovedElement() );
sb.append( "\n modifiedPage = " ).append( getModifiedPage() );
- sb.append( "\n new LeftMost = " ).append( getNewLeftMost() );
return sb.toString();
}
Modified:
labs/mavibot/trunk/mavibot/src/test/java/org/apache/mavibot/btree/LeafTest.java
URL:
http://svn.apache.org/viewvc/labs/mavibot/trunk/mavibot/src/test/java/org/apache/mavibot/btree/LeafTest.java?rev=1366759&r1=1366758&r2=1366759&view=diff
==============================================================================
---
labs/mavibot/trunk/mavibot/src/test/java/org/apache/mavibot/btree/LeafTest.java
(original)
+++
labs/mavibot/trunk/mavibot/src/test/java/org/apache/mavibot/btree/LeafTest.java
Sat Jul 28 19:58:47 2012
@@ -19,15 +19,17 @@
*/
package org.apache.mavibot.btree;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertNull;
+import static org.junit.Assert.assertTrue;
+
import java.io.IOException;
import org.apache.mavibot.btree.comparator.LongComparator;
import org.junit.Before;
import org.junit.Test;
-import static org.junit.Assert.assertEquals;
-import static org.junit.Assert.assertTrue;
-import static org.junit.Assert.assertNull;
/**
* A unit test class for Leaf
@@ -37,7 +39,8 @@ import static org.junit.Assert.assertNul
public class LeafTest
{
private BTree<Long, String> btree = null;
-
+
+
/**
* Create a btree
*/
@@ -48,17 +51,17 @@ public class LeafTest
btree.setPageSize( 8 );
}
-
+
/**
* A helper method to insert elements in a Leaf
*/
private Leaf<Long, String> insert( Leaf<Long, String> leaf, long key,
String value )
{
InsertResult<Long, String> result = leaf.insert( 1L, key, value );
-
- return (Leaf<Long, String>)((ModifyResult<Long,
String>)result).getModifiedPage();
+
+ return ( Leaf<Long, String> ) ( ( ModifyResult<Long, String> ) result
).getModifiedPage();
}
-
+
/**
* Test that deleting an entry from an empty page returns a NOT_PRESENT
result
@@ -68,9 +71,9 @@ public class LeafTest
public void testDeleteFromEmptyLeaf() throws IOException
{
Leaf<Long, String> leaf = new Leaf<Long, String>( btree );
-
+
DeleteResult<Long, String> result = leaf.delete( 1L, 1L, null, -1 );
-
+
assertEquals( NotPresentResult.NOT_PRESENT, result );
}
@@ -87,9 +90,9 @@ public class LeafTest
leaf = insert( leaf, 2L, "v2" );
leaf = insert( leaf, 3L, "v3" );
leaf = insert( leaf, 4L, "v4" );
-
+
DeleteResult<Long, String> result = leaf.delete( 2L, 5L, null, -1 );
-
+
assertEquals( NotPresentResult.NOT_PRESENT, result );
}
@@ -106,18 +109,18 @@ public class LeafTest
leaf = insert( leaf, 2L, "v2" );
leaf = insert( leaf, 3L, "v3" );
leaf = insert( leaf, 4L, "v4" );
-
+
DeleteResult<Long, String> result = leaf.delete( 4L, 3L, null, -1 );
-
+
assertTrue( result instanceof RemoveResult );
-
- Tuple<Long, String> removedElement = ((RemoveResult<Long,
String>)result).getRemovedElement();
- Page<Long, String> newLeaf = ((RemoveResult<Long,
String>)result).getModifiedPage();
-
- assertEquals( Long.valueOf( 3L), removedElement.getKey() );
+
+ Tuple<Long, String> removedElement = ( ( RemoveResult<Long, String> )
result ).getRemovedElement();
+ Page<Long, String> newLeaf = ( ( RemoveResult<Long, String> ) result
).getModifiedPage();
+
+ assertEquals( Long.valueOf( 3L ), removedElement.getKey() );
assertEquals( "v3", removedElement.getValue() );
assertEquals( 3, newLeaf.getNbElems() );
-
+
assertEquals( "v1", newLeaf.find( 1L ) );
assertEquals( "v2", newLeaf.find( 2L ) );
assertNull( newLeaf.find( 3L ) );
@@ -137,19 +140,17 @@ public class LeafTest
leaf = insert( leaf, 2L, "v2" );
leaf = insert( leaf, 3L, "v3" );
leaf = insert( leaf, 4L, "v4" );
-
+
DeleteResult<Long, String> result = leaf.delete( 4L, 1L, null, -1 );
-
+
assertTrue( result instanceof RemoveResult );
-
- RemoveResult<Long, String> removeResult = (RemoveResult<Long,
String>)result;
-
+
+ RemoveResult<Long, String> removeResult = ( RemoveResult<Long, String>
) result;
+
Tuple<Long, String> removedElement = removeResult.getRemovedElement();
Page<Long, String> newLeaf = removeResult.getModifiedPage();
- Long leftMost = removeResult.getNewLeftMost();
-
- assertEquals( Long.valueOf( 2L), leftMost );
- assertEquals( Long.valueOf( 1L), removedElement.getKey() );
+
+ assertEquals( Long.valueOf( 1L ), removedElement.getKey() );
assertEquals( "v1", removedElement.getValue() );
assertEquals( 3, newLeaf.getNbElems() );
@@ -158,8 +159,8 @@ public class LeafTest
assertEquals( "v3", newLeaf.find( 3L ) );
assertEquals( "v4", newLeaf.find( 4L ) );
}
-
-
+
+
/**
* Check that deleting an element from a leaf with N/2 element works when
we borrow
* an element in a left page with more than N/2 elements
@@ -171,7 +172,7 @@ public class LeafTest
Leaf<Long, String> left = new Leaf<Long, String>( btree );
Leaf<Long, String> target = new Leaf<Long, String>( btree );
Leaf<Long, String> right = new Leaf<Long, String>( btree );
-
+
// Fill the left page
left = insert( left, 1L, "v1" );
left = insert( left, 2L, "v2" );
@@ -194,42 +195,41 @@ public class LeafTest
parent.children[0] = left;
parent.children[1] = target;
parent.children[2] = right;
-
+
// Update the parent
parent.keys[0] = 6L;
parent.keys[1] = 10L;
-
+
// Now, delete the element from the target page
DeleteResult<Long, String> result = target.delete( 2L, 7L, parent, 1 );
-
+
assertTrue( result instanceof BorrowedFromLeftResult );
-
- BorrowedFromLeftResult<Long, String> borrowed =
(BorrowedFromLeftResult<Long, String>)result;
- assertEquals( Long.valueOf( 5L ), borrowed.getNewLeftMost() );
+
+ BorrowedFromLeftResult<Long, String> borrowed = (
BorrowedFromLeftResult<Long, String> ) result;
Tuple<Long, String> removedKey = borrowed.getRemovedElement();
assertEquals( Long.valueOf( 7L ), removedKey.getKey() );
-
+
// Check the modified leaf
- Leaf<Long, String> newLeaf = (Leaf<Long,
String>)borrowed.getModifiedPage();
-
+ Leaf<Long, String> newLeaf = ( Leaf<Long, String> )
borrowed.getModifiedPage();
+
assertEquals( 4, newLeaf.nbElems );
assertEquals( Long.valueOf( 5L ), newLeaf.keys[0] );
assertEquals( Long.valueOf( 6L ), newLeaf.keys[1] );
assertEquals( Long.valueOf( 8L ), newLeaf.keys[2] );
assertEquals( Long.valueOf( 9L ), newLeaf.keys[3] );
-
+
// Check the sibling
- Leaf<Long, String> leftSibling = (Leaf<Long,
String>)borrowed.getModifiedSibling();
-
+ Leaf<Long, String> leftSibling = ( Leaf<Long, String> )
borrowed.getModifiedSibling();
+
assertEquals( 4, leftSibling.nbElems );
assertEquals( Long.valueOf( 1L ), leftSibling.keys[0] );
assertEquals( Long.valueOf( 2L ), leftSibling.keys[1] );
assertEquals( Long.valueOf( 3L ), leftSibling.keys[2] );
assertEquals( Long.valueOf( 4L ), leftSibling.keys[3] );
}
-
-
+
+
/**
* Check that deleting an element from a leaf with N/2 element works when
we borrow
* an element in a right page with more than N/2 elements
@@ -241,7 +241,7 @@ public class LeafTest
Leaf<Long, String> left = new Leaf<Long, String>( btree );
Leaf<Long, String> target = new Leaf<Long, String>( btree );
Leaf<Long, String> right = new Leaf<Long, String>( btree );
-
+
// Fill the left page
left = insert( left, 1L, "v1" );
left = insert( left, 2L, "v2" );
@@ -264,42 +264,42 @@ public class LeafTest
parent.children[0] = left;
parent.children[1] = target;
parent.children[2] = right;
-
+
// Update the parent
parent.keys[0] = 6L;
parent.keys[1] = 10L;
-
+
// Now, delete the element from the target page
DeleteResult<Long, String> result = target.delete( 2L, 7L, parent, 1 );
-
+
assertTrue( result instanceof BorrowedFromRightResult );
-
- BorrowedFromRightResult<Long, String> borrowed =
(BorrowedFromRightResult<Long, String>)result;
+
+ BorrowedFromRightResult<Long, String> borrowed = (
BorrowedFromRightResult<Long, String> ) result;
assertEquals( Long.valueOf( 11L ),
borrowed.getModifiedSibling().getKey( 0 ) );
Tuple<Long, String> removedKey = borrowed.getRemovedElement();
assertEquals( Long.valueOf( 7L ), removedKey.getKey() );
-
+
// Check the modified leaf
- Leaf<Long, String> newLeaf = (Leaf<Long,
String>)borrowed.getModifiedPage();
-
+ Leaf<Long, String> newLeaf = ( Leaf<Long, String> )
borrowed.getModifiedPage();
+
assertEquals( 4, newLeaf.nbElems );
assertEquals( Long.valueOf( 6L ), newLeaf.keys[0] );
assertEquals( Long.valueOf( 8L ), newLeaf.keys[1] );
assertEquals( Long.valueOf( 9L ), newLeaf.keys[2] );
assertEquals( Long.valueOf( 10L ), newLeaf.keys[3] );
-
+
// Check the sibling
- Leaf<Long, String> rightSibling = (Leaf<Long,
String>)borrowed.getModifiedSibling();
-
+ Leaf<Long, String> rightSibling = ( Leaf<Long, String> )
borrowed.getModifiedSibling();
+
assertEquals( 4, rightSibling.nbElems );
assertEquals( Long.valueOf( 11L ), rightSibling.keys[0] );
assertEquals( Long.valueOf( 12L ), rightSibling.keys[1] );
assertEquals( Long.valueOf( 13L ), rightSibling.keys[2] );
assertEquals( Long.valueOf( 14L ), rightSibling.keys[3] );
}
-
-
+
+
/**
* Check that deleting an element from a leaf with N/2 element works when
we merge
* it with one of its sibling, if both has N/2 elements
@@ -311,7 +311,7 @@ public class LeafTest
Leaf<Long, String> left = new Leaf<Long, String>( btree );
Leaf<Long, String> target = new Leaf<Long, String>( btree );
Leaf<Long, String> right = new Leaf<Long, String>( btree );
-
+
// Fill the left page
left = insert( left, 1L, "v1" );
left = insert( left, 2L, "v2" );
@@ -329,29 +329,28 @@ public class LeafTest
right = insert( right, 10L, "v10" );
right = insert( right, 11L, "v11" );
right = insert( right, 12L, "v12" );
-
+
parent.children[0] = left;
parent.children[1] = target;
parent.children[2] = right;
-
+
// Update the parent
parent.keys[0] = 5L;
parent.keys[1] = 9L;
-
+
// Now, delete the element from the target page
DeleteResult<Long, String> result = target.delete( 2L, 7L, parent, 1 );
-
+
assertTrue( result instanceof MergedWithSiblingResult );
-
- MergedWithSiblingResult<Long, String> merged =
(MergedWithSiblingResult<Long, String>)result;
- assertEquals( Long.valueOf( 1L ), merged.getNewLeftMost() );
+
+ MergedWithSiblingResult<Long, String> merged = (
MergedWithSiblingResult<Long, String> ) result;
Tuple<Long, String> removedKey = merged.getRemovedElement();
assertEquals( Long.valueOf( 7L ), removedKey.getKey() );
-
+
// Check the modified leaf
- Leaf<Long, String> newLeaf = (Leaf<Long,
String>)merged.getModifiedPage();
-
+ Leaf<Long, String> newLeaf = ( Leaf<Long, String> )
merged.getModifiedPage();
+
assertEquals( 7, newLeaf.nbElems );
assertEquals( Long.valueOf( 1L ), newLeaf.keys[0] );
assertEquals( Long.valueOf( 2L ), newLeaf.keys[1] );
@@ -361,8 +360,8 @@ public class LeafTest
assertEquals( Long.valueOf( 6L ), newLeaf.keys[5] );
assertEquals( Long.valueOf( 8L ), newLeaf.keys[6] );
}
-
-
+
+
/**
* Test the findPos() method
* @throws Exception
@@ -371,24 +370,25 @@ public class LeafTest
public void testFindPos() throws Exception
{
Leaf<Long, String> leaf = new Leaf<Long, String>( btree );
-
+
// Inject the values
for ( long i = 0; i < 8; i++ )
{
long value = i + i + 1;
- leaf = (Leaf<Long, String>)((ModifyResult<Long,
String>)leaf.insert( 0L, value, "V" + value )).getModifiedPage();
+ leaf = ( Leaf<Long, String> ) ( ( ModifyResult<Long, String> )
leaf.insert( 0L, value, "V" + value ) )
+ .getModifiedPage();
}
-
+
// Check the findPos() method now
for ( long i = 0; i < 17; i++ )
{
if ( i % 2 == 1 )
{
- assertEquals( - ( i/2 + 1 ), leaf.findPos( i ) );
+ assertEquals( -( i / 2 + 1 ), leaf.findPos( i ) );
}
else
{
- assertEquals( i/2, leaf.findPos( i ) );
+ assertEquals( i / 2, leaf.findPos( i ) );
}
}
}
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
