/*
 * Copyright (C) 2010 Google Inc. All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * 1.  Redistributions of source code must retain the above copyright
 *     notice, this list of conditions and the following disclaimer.
 * 2.  Redistributions in binary form must reproduce the above copyright
 *     notice, this list of conditions and the following disclaimer in the
 *     documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY
 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY
 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

#ifndef IDBKeyTree_h
#define IDBKeyTree_h

#if ENABLE(INDEXED_DATABASE)

#include "IDBKey.h"
#include <wtf/AVLTree.h>
#include <wtf/Vector.h>

namespace WebCore {

template <typename ValueType>
class IDBKeyTree : public RefCounted<IDBKeyTree<ValueType> > {
public:
    static PassRefPtr<IDBKeyTree> create()
    {
        return adoptRef(new IDBKeyTree());
    }
    ~IDBKeyTree();

    ValueType* get(IDBKey* key);
    void put(IDBKey* key, ValueType* value);
    void remove(IDBKey* key);

private:
    struct TreeNode {
        RefPtr<ValueType> value;
        RefPtr<IDBKey> key;

        TreeNode* less;
        TreeNode* greater;
        int balanceFactor;
    };

    struct AVLTreeAbstractor {
        typedef TreeNode* handle;
        typedef size_t size;
        typedef IDBKey* key;

        handle get_less(handle h) { return h->less; }
        void set_less(handle h, handle lh) { h->less = lh; }
        handle get_greater(handle h) { return h->greater; }
        void set_greater(handle h, handle gh) { h->greater = gh; }
        int get_balance_factor(handle h) { return h->balanceFactor; }
        void set_balance_factor(handle h, int bf) { h->balanceFactor = bf; }

        static handle null() { return 0; }

        int compare_key_key(key va, key vb);
        int compare_key_node(key k, handle h) { return compare_key_key(k, h->key.get()); }
        int compare_node_node(handle h1, handle h2) { return compare_key_key(h1->key.get(), h2->key.get()); }
    };

    IDBKeyTree();

    typedef WTF::AVLTree<AVLTreeAbstractor> TreeType;
    TreeType m_tree;
};

template <typename ValueType>
IDBKeyTree<ValueType>::IDBKeyTree()
{
}

template <typename ValueType>
IDBKeyTree<ValueType>::~IDBKeyTree()
{
    typename TreeType::Iterator iter;
    iter.start_iter_least(m_tree);
    for (; *iter; ++iter)
        delete *iter;
    m_tree.purge();
}

template <typename ValueType>
int IDBKeyTree<ValueType>::AVLTreeAbstractor::compare_key_key(key va, key vb)
{
    if (va->type() != vb->type())
        return vb->type() - va->type();

    switch (va->type()) {
    case IDBKey::NullType:
        return 0;
    case IDBKey::NumberType:
        return vb->number() - va->number();
    case IDBKey::StringType:
        return codePointCompare(va->string(), vb->string());
    // FIXME: Handle dates.  Oh, and test this thoroughly.
    default:
        ASSERT_NOT_REACHED();
        return 0;
    }
}

template <typename ValueType>
ValueType* IDBKeyTree<ValueType>::get(IDBKey* key)
{
    TreeNode* node = m_tree.search(key);
    if (!node)
        return 0;
    return node->value.get();
}

template <typename ValueType>
void IDBKeyTree<ValueType>::put(IDBKey* key, ValueType* value)
{
    TreeNode* node = m_tree.search(key);
    if (!node) {
        node = new TreeNode();
        node->key = key;
        m_tree.insert(node);
    }
    node->value = value;
}

template <typename ValueType>
void IDBKeyTree<ValueType>::remove(IDBKey* key)
{
    TreeNode* node = m_tree.remove(key);
    if (node)
        delete node;
}

}

#endif // ENABLE(INDEXED_DATABASE)

#endif // IDBKeyTree_h