Author: elecharny
Date: Thu Jun 14 15:47:37 2012
New Revision: 1350300
URL: http://svn.apache.org/viewvc?rev=1350300&view=rev
Log:
o Added the results for the insertion/deletion in a page
o Added some first methods in the Page interface
Added:
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/InsertResult.java
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/ModifyResult.java
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/SplitResult.java
Modified:
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Page.java
Added:
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/InsertResult.java
URL:
http://svn.apache.org/viewvc/labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/InsertResult.java?rev=1350300&view=auto
==============================================================================
---
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/InsertResult.java
(added)
+++
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/InsertResult.java
Thu Jun 14 15:47:37 2012
@@ -0,0 +1,34 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ *
+ */
+package org.apache.mavibot.btree;
+
+/**
+ * The result of an insert operation. This is just a container that stores
either
+ * the new pivot that has been extracted after a page split, or a modified
page if
+ * the child page hasn't been split.
+ *
+ * @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>
+ */
+interface InsertResult<K, V>
+{
+}
Added:
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/ModifyResult.java
URL:
http://svn.apache.org/viewvc/labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/ModifyResult.java?rev=1350300&view=auto
==============================================================================
---
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/ModifyResult.java
(added)
+++
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/ModifyResult.java
Thu Jun 14 15:47:37 2012
@@ -0,0 +1,53 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ *
+ */
+package org.apache.mavibot.btree;
+
+/**
+ * The result of an insert operation, when the child has not been split. It
contains the
+ * reference to the modified page.
+ *
+ * @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>
+ */
+/* No qualifier */ class ModifyResult<K, V> implements InsertResult<K, V>
+{
+ /** The modified page reference */
+ protected Page<K, V> modifiedPage;
+
+ /**
+ * The default constructor for ModifyResult.
+ * @param modifiedPage
+ */
+ public ModifyResult( Page<K, V> modifiedPage )
+ {
+ this.modifiedPage = modifiedPage;
+ }
+
+
+ /**
+ * @return the modifiedPage
+ */
+ public Page<K, V> getModifiedPage()
+ {
+ return modifiedPage;
+ }
+}
Modified:
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Page.java
URL:
http://svn.apache.org/viewvc/labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Page.java?rev=1350300&r1=1350299&r2=1350300&view=diff
==============================================================================
--- labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Page.java
(original)
+++ labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/Page.java
Thu Jun 14 15:47:37 2012
@@ -29,4 +29,28 @@ package org.apache.mavibot.btree;
*/
public interface Page<K, V>
{
+ /**
+ * @return The number of keys present in this page
+ */
+ long getNbElems();
+
+
+ /**
+ * Insert the given key and value into this page. We first find the place
were to
+ * inject the <K,V> into the tree, by recursively browsing the pages :<br/>
+ * <ul>
+ * <li>If the index is below zero, the key is present in the Page : we
modify the
+ * value and return</li>
+ * <li>If the page is a node, we have to go down to the right child
page</li>
+ * <li>If the page is a leaf, we insert the new <K,V> element into the
page, and if
+ * the Page is full, we split it and propagate the new pivot up into the
tree</li>
+ * </ul>
+ * <p>
+ *
+ * @param revision The new revision for the modified pages
+ * @param key Inserted key
+ * @param value Inserted value
+ * @return Either a modified Page or an Overflow element if the Page was
full
+ */
+ InsertResult<K, V> insert( long revision, K key, V value );
}
Added:
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/SplitResult.java
URL:
http://svn.apache.org/viewvc/labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/SplitResult.java?rev=1350300&view=auto
==============================================================================
---
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/SplitResult.java
(added)
+++
labs/mavibot/trunk/mavibot/src/main/java/org/apache/mavibot/btree/SplitResult.java
Thu Jun 14 15:47:37 2012
@@ -0,0 +1,79 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ *
+ */
+package org.apache.mavibot.btree;
+
+/**
+ * The result of an insert operation, when the page has been split. It contains
+ * the new pivotal value, plus the reference on the two new pages.
+ *
+ * @param <K> The type for the Key
+ * @param <V> The type for the stored value
+
+ * @author <a href="mailto:[email protected]";>Apache Directory
Project</a>
+ */
+/* No qualifier */ class SplitResult<K, V> implements InsertResult<K, V>
+{
+ /** The left child */
+ protected Page<K, V> leftPage;
+
+ /** The right child */
+ protected Page<K, V> rightPage;
+
+ /** The key pivot */
+ protected K pivot;
+
+ /**
+ * The default constructor for SplitResult.
+ * @param modifiedPage
+ */
+ public SplitResult( K pivot, Page<K, V> leftPage, Page<K, V> rightPage )
+ {
+ this.pivot = pivot;
+ this.leftPage = leftPage;
+ this.rightPage = rightPage;
+ }
+
+
+ /**
+ * @return the leftPage
+ */
+ public Page<K, V> getLeftPage()
+ {
+ return leftPage;
+ }
+
+
+ /**
+ * @return the rightPage
+ */
+ public Page<K, V> getRightPage()
+ {
+ return rightPage;
+ }
+
+
+ /**
+ * @return the pivot
+ */
+ public K getPivot()
+ {
+ return pivot;
+ }
+}
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
