/**
 *    Copyright (C) 2014 MongoDB Inc.
 *
 *    This program is free software: you can redistribute it and/or  modify
 *    it under the terms of the GNU Affero General Public License, version 3,
 *    as published by the Free Software Foundation.
 *
 *    This program is distributed in the hope that it will be useful,
 *    but WITHOUT ANY WARRANTY; without even the implied warranty of
 *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *    GNU Affero General Public License for more details.
 *
 *    You should have received a copy of the GNU Affero General Public License
 *    along with this program.  If not, see <http://www.gnu.org/licenses/>.
 *
 *    As a special exception, the copyright holders give permission to link the
 *    code of portions of this program with the OpenSSL library under certain
 *    conditions as described in each individual source file and distribute
 *    linked combinations including the program with the OpenSSL library. You
 *    must comply with the GNU Affero General Public License in all respects for
 *    all of the code used other than as permitted herein. If you modify file(s)
 *    with this exception, you may extend this exception to your version of the
 *    file(s), but you are not obligated to do so. If you do not wish to do so,
 *    delete this exception statement from your version. If you delete this
 *    exception statement from all source files in the program, then also delete
 *    it in the license file.
 */

#include "mongo/bson/ordering.h"
#include "mongo/db/catalog/head_manager.h"
#include "mongo/db/jsobj.h"
#include "mongo/db/operation_context.h"
#include "mongo/db/record_id.h"
#include "mongo/db/storage/record_store.h"

#pragma once

namespace mongo {

class BSONObjBuilder;
class BucketDeletionNotification;
class SortedDataBuilderInterface;

/**
 * This interface is a work in progress.  Notes below:
 *
 * This interface began as the SortedDataInterface, a way to hide the fact that there were two
 * on-disk formats for the btree.  With the introduction of other storage engines, this
 * interface was generalized to provide access to sorted data.  Specifically:
 *
 * 1. Many other storage engines provide different Btree(-ish) implementations.  This interface
 * could allow those interfaces to avoid storing btree buckets in an already sorted structure.
 *
 * TODO: See if there is actually a performance gain.
 *
 * 2. The existing btree implementation is written to assume that if it modifies a record it is
 * modifying the underlying record.  This interface is an attempt to work around that.
 *
 * TODO: See if this actually works.
 */
class SortedDataInterface {
public:
    virtual ~SortedDataInterface() {}

    //
    // Data changes
    //

    /**
     * Return a bulk builder for 'this' index.
     *
     * Implementations can assume that 'this' index outlives its bulk
     * builder.
     *
     * @param txn the transaction under which keys are added to 'this' index
     * @param dupsAllowed true if duplicate keys are allowed, and false
     *        otherwise
     *
     * @return caller takes ownership
     */
    virtual SortedDataBuilderInterface* getBulkBuilder(OperationContext* txn, bool dupsAllowed) = 0;

    /**
     * Insert an entry into the index with the specified key and RecordId.
     *
     * @param txn the transaction under which the insert takes place
     * @param dupsAllowed true if duplicate keys are allowed, and false
     *        otherwise
     *
     * @return Status::OK() if the insert succeeded,
     *
     *         ErrorCodes::DuplicateKey if 'key' already exists in 'this' index
     *         at a RecordId other than 'loc' and duplicates were not allowed
     */
    virtual Status insert(OperationContext* txn,
                          const BSONObj& key,
                          const RecordId& loc,
                          bool dupsAllowed) = 0;

    /**
     * Remove the entry from the index with the specified key and RecordId.
     *
     * @param txn the transaction under which the remove takes place
     * @param dupsAllowed true if duplicate keys are allowed, and false
     *        otherwise
     */
    virtual void unindex(OperationContext* txn,
                         const BSONObj& key,
                         const RecordId& loc,
                         bool dupsAllowed) = 0;

    /**
     * Return ErrorCodes::DuplicateKey if 'key' already exists in 'this'
     * index at a RecordId other than 'loc', and Status::OK() otherwise.
     *
     * @param txn the transaction under which this operation takes place
     *
     * TODO: Hide this by exposing an update method?
     */
    virtual Status dupKeyCheck(OperationContext* txn, const BSONObj& key, const RecordId& loc) = 0;

    //
    // Information about the tree
    //

    /**
     * 'output' is used to store results of validate when 'full' is true.
     * If 'full' is false, 'output' may be NULL.
     *
     * TODO: expose full set of args for testing?
     */
    virtual void fullValidate(OperationContext* txn,
                              bool full,
                              long long* numKeysOut,
                              BSONObjBuilder* output) const = 0;

    virtual bool appendCustomStats(OperationContext* txn,
                                   BSONObjBuilder* output,
                                   double scale) const = 0;


    /**
     * Return the number of bytes consumed by 'this' index.
     *
     * @param txn the transaction under which this operation takes place
     *
     * @see IndexAccessMethod::getSpaceUsedBytes
     */
    virtual long long getSpaceUsedBytes(OperationContext* txn) const = 0;

    /**
     * Return true if 'this' index is empty, and false otherwise.
     */
    virtual bool isEmpty(OperationContext* txn) = 0;

    /**
     * Attempt to bring the entirety of 'this' index into memory.
     *
     * If the underlying storage engine does not support the operation,
     * returns ErrorCodes::CommandNotSupported
     *
     * @return Status::OK()
     */
    virtual Status touch(OperationContext* txn) const {
        return Status(ErrorCodes::CommandNotSupported,
                      "this storage engine does not support touch");
    }

    /**
     * Return the number of entries in 'this' index.
     *
     * The default implementation should be overridden with a more
     * efficient one if at all possible.
     */
    virtual long long numEntries(OperationContext* txn) const {
        long long x = -1;
        fullValidate(txn, false, &x, NULL);
        return x;
    }

    /**
     * Navigation
     *
     * A cursor is tied to a transaction, such as the OperationContext or a WriteUnitOfWork
     * inside that context. Any cursor acquired inside a transaction is invalid outside
     * of that transaction, instead use the savePosition() and restorePosition() methods
     * reestablish the cursor.
     */
    class Cursor {
    public:
        virtual ~Cursor() {}

        /**
         * Return the direction of 'this' cursor.
         *
         * @return +1 for a forward cursor or -1 for a reverse cursor
         */
        virtual int getDirection() const = 0;

        /**
         * Return true if 'this' forward (reverse) cursor is positioned
         * past the end (before the beginning) of the index, and false otherwise.
         */
        virtual bool isEOF() const = 0;

        /**
         * Return true if 'this' cursor and the 'other' cursor are positioned at
         * the same key and RecordId, or if both cursors are at EOF. Otherwise,
         * this function returns false.
         *
         * Implementations should prohibit the comparison of cursors associated
         * with different indices.
         */
        virtual bool pointsToSamePlaceAs(const Cursor& other) const = 0;

        /**
         * Position 'this' forward (reverse) cursor either at the entry or
         * immediately after (or immediately before) the specified key and RecordId.
         * The cursor should be positioned at EOF if no such entry exists.
         *
         * @return true if the entry (key, RecordId) exists within the index,
         *         and false otherwise
         */
        virtual bool locate(const BSONObj& key, const RecordId& loc) = 0;

        /**
     * Position 'this' forward (reverse) cursor at the first (last) entry
     * with the specified key.  The cursor should be positioned at EOF or at
     * the entry immediately after (before) the specified key if no such
     * entry exists.
         */
        virtual void seekExact(const BSONObj& key) {
            (void)locate(key, getDirection() == 1 ? RecordId::min() : RecordId::max());
        }

        /**
         * Position 'this' forward (reverse) cursor either at the next
         * (previous) occurrence of a particular key or immediately after
         * (or immediately before).
         *
         * @see SortedDataInterface::customLocate
         */
        virtual void advanceTo(const BSONObj& keyPrefix,
                               int prefixLen,
                               bool prefixExclusive,
                               const std::vector<const BSONElement*>& keySuffix,
                               const std::vector<bool>& suffixInclusive) = 0;

        /**
         * Position 'this' forward (reverse) cursor either at the first
         * (last) occurrence of a particular key or immediately after
         * (or immediately before). The key is a typical BSONObj,
         * represented by the specified parameters in the following way:
         *
         * The first 'prefixLen' elements of 'keyPrefix' followed by
         * the last 'keySuffix.size() - prefixLen' elements of 'keySuffix'.
         *
         * e.g.
         *
         *  Suppose that
         *
         *      keyPrefix = { "" : 1, "" : 2 }
         *      prefixLen = 1
         *      prefixExclusive = false
         *      keySuffix = [ IGNORED; { "" : 5 } ]
         *      suffixInclusive = [ IGNORED; false ]
         *
         *      ==> represented key is { "" : 1, "" : 5 }
         *          with the exclusive byte set on the second field
         *
         *  Suppose that
         *
         *      keyPrefix = { "" : 1, "" : 2 }
         *      prefixLen = 1
         *      prefixExclusive = true
         *      keySuffix = IGNORED
         *      suffixInclusive = IGNORED
         *
         *      ==> represented key is { "" : 1 }
         *          with the exclusive byte set on the first field
         *
         * @param prefixExclusive true if 'this' forward (reverse) cursor
         *        should be positioned immediately after (immediately
         *        before) the represented key, and false otherwise
         *
         * @param suffixInclusive an element of the vector is false if
         *        'this' forward (reverse) cursor should be positioned
         *        immediately after (immediately before) the represented
         *        key, and true otherwise
         *
         * Implementations should prohibit callers from specifying
         * 'prefixLen = 0' when 'prefixExclusive = true'.
         *
         * @see IndexEntryComparison::makeQueryObject
         */
        virtual void customLocate(const BSONObj& keyPrefix,
                                  int prefixLen,
                                  bool prefixExclusive,
                                  const std::vector<const BSONElement*>& keySuffix,
                                  const std::vector<bool>& suffixInclusive) = 0;

        /**
         * Return the key associated with the current position of 'this' cursor.
         */
        virtual BSONObj getKey() const = 0;

        /**
         * Return the RecordId associated with the current position of 'this' cursor.
         */
        virtual RecordId getRecordId() const = 0;

        /**
         * Position 'this' forward (reverse) cursor at the next (preceding) entry
         * in the index. A cursor positioned at EOF should remain at EOF when advanced.
         */
        virtual void advance() = 0;

        //
        // Saving and restoring state
        //

        /**
         * Save the entry in the index (i.e. its key and RecordId) of where
         * 'this' cursor is currently positioned.
         *
         * Implementations can assume that no operations other than delete
         * or restorePosition() will be called on 'this' cursor after its
         * position has been saved.
         */
        virtual void savePosition() = 0;

        /**
         * Restore 'this' cursor to the previously saved entry in the index.
         *
         * Implementations should have the same behavior as calling locate()
         * with the saved key and RecordId.
         */
        virtual void restorePosition(OperationContext* txn) = 0;
    };

    /**
     * Return a cursor over 'this' index. The cursor need not be positioned
     * at any particular entry.
     *
     * Implementations can assume that locate() is called on the cursor
     * before it gets used.
     *
     * Implementations can assume that 'this' index outlives all cursors
     * it produces.
     *
     * @param txn the transaction to which the cursor is tied
     * @param direction the direction of the cursor.
     *        +1 for a forward cursor or -1 for a reverse cursor.
     *
     * @return caller takes ownership
     */
    virtual Cursor* newCursor(OperationContext* txn, int direction) const = 0;

    //
    // Index creation
    //

    virtual Status initAsEmpty(OperationContext* txn) = 0;
};

/**
 * A version-hiding wrapper around the bulk builder for the Btree.
 */
class SortedDataBuilderInterface {
public:
    virtual ~SortedDataBuilderInterface() {}

    /**
     * Adds 'key' to intermediate storage.
     *
     * 'key' must be > or >= the last key passed to this function (depends on _dupsAllowed).  If
     * this is violated an error Status (ErrorCodes::InternalError) will be returned.
     */
    virtual Status addKey(const BSONObj& key, const RecordId& loc) = 0;

    /**
     * Do any necessary work to finish building the tree.
     *
     * The default implementation may be used if no commit phase is necessary because addKey
     * always leaves the tree in a valid state.
     *
     * This is called outside of any WriteUnitOfWork to allow implementations to split this up
     * into multiple units.
     */
    virtual void commit(bool mayInterrupt) {}
};

}  // namespace mongo
