mavibot/src/main/java/org/apache/directory/mavibot/btree/Page.java

/*
 *  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.directory.mavibot.btree;


import java.io.IOException;

import org.apache.directory.mavibot.btree.exception.EndOfFileExceededException;
import org.apache.directory.mavibot.btree.exception.KeyNotFoundException;


/**
 * A MVCC Page interface. A Page can be either a Leaf (containing keys and values) or a Node
 * (containing keys and references to child pages).<br/>
 * A Page can be stored on disk. If so, we store the serialized value of this Page into
 * one or more {@link PageIO} (they will be linked)
 *
 * @param <K> The type for the Key
 * @param <V> The type for the stored value
 *
 * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
 */
/* No qualifier*/interface Page<K, V>
{
    /**
     * @return The number of keys present in this page
     */
    int getNbElems();


    /**
     * Inserts 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 key Inserted key
     * @param value Inserted value
     * @param revision The new revision for the modified pages
     * @return Either a modified Page or an Overflow element if the Page was full
     * @throws IOException If we have an error while trying to access the page
     */
    InsertResult<K, V> insert( K key, V value, long revision ) throws IOException;


    /**
     * Deletes the value from an entry associated with the given key in this page. We first find
     * the place were to remove the <K,V> into the tree, by recursively browsing the pages.
     * If the value is present, it will be deleted first, later if there are no other values associated with
     * this key(which can happen when duplicates are enabled), we will remove the key from the tree.
     *
     * @param revision The new revision for the modified pages
     * @param key The key to delete
     * @param value The value to delete (can be null)
     * @param parent The parent page
     * @param parentPos The position of the current page in it's parent
     * @return Either a modified Page if the key has been removed from the page, or a NotPresentResult.
     * @throws IOException If we have an error while trying to access the page
     */
    DeleteResult<K, V> delete( K key, V value, long revision /*, Page<K, V> parent, int parentPos*/ ) throws IOException;


    /**
     * Gets the value associated with the given key, if any. If we don't have
     * one, this method will throw a KeyNotFoundException.<br/>
     * Note that we may get back null if a null value has been associated
     * with the key.
     *
     * @param key The key we are looking for
     * @return The associated value, which can be null
     * @throws KeyNotFoundException If no entry with the given key can be found
     * @throws IOException If we have an error while trying to access the page
     */
    V get( K key ) throws KeyNotFoundException, IOException;


    /**
     * Gets the values associated with the given key, if any. If we don't have
     * the key, this method will throw a KeyNotFoundException.<br/>
     * Note that we may get back null if a null value has been associated
     * with the key.
     *
     * @param key The key we are looking for
     * @return The associated value, which can be null
     * @throws KeyNotFoundException If no entry with the given key can be found
     * @throws IOException If we have an error while trying to access the page
     * @throws IllegalArgumentException If duplicates are not enabled
     */
    ValueCursor<V> getValues( K key ) throws KeyNotFoundException, IOException, IllegalArgumentException;


    /**
     * Checks if the page contains the given key with the given value.
     *
     * @param key The key we are looking for
     * @param value The value associated with the given key
     * @return true if the key and value are associated with each other, false otherwise
     */
    boolean contains( K key, V value ) throws IOException;


    /**
     * Browses the tree, looking for the given key, and creates a Cursor on top
     * of the found result.
     *
     * @param key The key we are looking for.
     * @param transaction The started transaction for this operation
     * @param stack The stack of parents we go through to get to this page
     * @return A Cursor to browse the next elements
     * @throws IOException If we have an error while trying to access the page
     */
    TupleCursor<K, V> browse( K key, ReadTransaction<K, V> transaction, ParentPos<K, V>[] stack, int depth )
        throws IOException;


    /**
     * Browses the whole tree, and creates a Cursor on top of it.
     *
     * @param transaction The started transaction for this operation
     * @param stack The stack of parents we go through to get to this page
     * @return A Cursor to browse the next elements
     * @throws IOException If we have an error while trying to access the page
     */
    TupleCursor<K, V> browse( ReadTransaction<K, V> transaction, ParentPos<K, V>[] stack, int depth )
        throws EndOfFileExceededException, IOException;


    /**
     * @return the revision
     */
    long getRevision();


    /**
     * Returns the key at a given position
     *
     * @param pos The position of the key we want to retrieve
     * @return The key found at the given position
     */
    K getKey( int pos );


    /**
     * Finds the leftmost key in this page. If the page is a node, it will go
     * down in the leftmost children to recursively find the leftmost key.
     *
     * @return The leftmost key in the tree
     */
    K getLeftMostKey();


    /**
     * Finds the rightmost key in this page. If the page is a node, it will go
     * down in the rightmost children to recursively find the rightmost key.
     *
     * @return The rightmost key in the tree
     */
    K getRightMostKey();


    /**
     * Finds the leftmost element in this page. If the page is a node, it will go
     * down in the leftmost children to recursively find the leftmost element.
     *
     * @return The leftmost element in the tree
     * @throws IOException If we have an error while trying to access the page
     */
    Tuple<K, V> findLeftMost() throws IOException;


    /**
     * Finds the rightmost element in this page. If the page is a node, it will go
     * down in the rightmost children to recursively find the rightmost element.
     *
     * @return The rightmost element in the tree
     * @throws IOException If we have an error while trying to access the page
     */
    Tuple<K, V> findRightMost() throws EndOfFileExceededException, IOException;


    /**
     * Pretty-prints the tree with tabs
     * @param tabs The tabs to add in front of each node
     * @return A pretty-print dump of the tree
     */
    String dumpPage( String tabs );


    /**
     * Find the position of the given key in the page. If we have found the key,
     * we will return its position as a negative value.
     * <p/>
     * Assuming that the array is zero-indexed, the returned value will be : <br/>
     *   position = - ( position + 1)
     * <br/>
     * So for the following table of keys : <br/>
     * <pre>
     * +---+---+---+---+
     * | b | d | f | h |
     * +---+---+---+---+
     *   0   1   2   3
     * </pre>
     * looking for 'b' will return -1 (-(0+1)) and looking for 'f' will return -3 (-(2+1)).<br/>
     * Computing the real position is just a matter to get -(position++).
     * <p/>
     * If we don't find the key in the table, we will return the position of the key
     * immediately above the key we are looking for. <br/>
     * For instance, looking for :
     * <ul>
     * <li>'a' will return 0</li>
     * <li>'b' will return -1</li>
     * <li>'c' will return 1</li>
     * <li>'d' will return -2</li>
     * <li>'e' will return 2</li>
     * <li>'f' will return -3</li>
     * <li>'g' will return 3</li>
     * <li>'h' will return -4</li>
     * <li>'i' will return 4</li>
     * </ul>
     *
     *
     * @param key The key to find
     * @return The position in the page.
     */
    int findPos( K key );


    /**
     * Checks if the given key exists.
     *
     * @param key The key we are looking at
     * @return true if the key is present, false otherwise
     * @throws IOException If we have an error while trying to access the page
     */
    boolean hasKey( K key ) throws IOException;


    /**
     * Tells if the page is a leaf or not
     * @return true if the page is a leaf
     */
    boolean isLeaf();


    /**
     * Tells if the page is a node or not
     * @return true if the page is a node
     */
    boolean isNode();
}