xref: /external/opencore/oscl/oscl/osclbase/src/oscl_map.h

/* ------------------------------------------------------------------
 * Copyright (C) 1998-2009 PacketVideo
 *
 * Licensed 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.
 * -------------------------------------------------------------------
 */
// -*- c++ -*-
// = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =

//                     O S C L _ M A P

// = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =

/*! \addtogroup osclbase OSCL Base
 *
 * @{
 */


/*! \file oscl_map.h
    \brief The file oscl_map.h defines the template class Oscl_Map which has a very similar API as the STL Map class (it basically provides a subset of the STL functionality).  Memory allocation is abstracted through the use of an allocator template parameter.
*/

#ifndef OSCL_MAP_H_INCLUDED
#define OSCL_MAP_H_INCLUDED

#ifndef OSCL_BASE_H_INCLUDED
#include "oscl_base.h"
#endif

#ifndef OSCL_TREE_H_INCLUDED
#include "oscl_tree.h"
#endif

#define OSCL_DISABLE_WARNING_TRUNCATE_DEBUG_MESSAGE
#include "osclconfig_compiler_warnings.h"

template <class T>
struct Oscl_Less
{
    bool operator()(const T& x, const T& y) const
    {
        return x < y ? true : false ;
    }
};

template <class V, class U>
struct Oscl_Select1st
{
    const U& operator()(const V& x) const
    {
        return x.first;
    }
};

/**
 * Oscl_Map Class.  A subset of STL::Map methods.
 * Oscl_Map is a sorted associative container that associates objects of type Key with objects of type T.
 * It is also a unique associative container, meaning that no two elements have the same key.  Oscl_Map
 * uses the key to speed lookup, insertion, and deletion of elements.  It is often superior to all other
 * containers when you need to lookup an element by key value.  Due to the underlying tree structure,
 * inserts and erases can be performed in logarithmic time, where a vector would take linear time in
 * some cases.
 */

template < class Key, class T, class Alloc, class Compare = Oscl_Less<Key> >
class Oscl_Map
{

    public:
        typedef Key key_type;
        typedef Compare key_compare;
        typedef Oscl_Pair<const Key, T> value_type;
        typedef Oscl_Map<Key, T, Alloc, Compare> self;

    private:
        typedef Oscl_Rb_Tree < key_type, value_type,
        Oscl_Select1st<value_type, key_type>,
        key_compare, Alloc > rep_type;
        rep_type t;  // red-black tree representing map

    public:
        typedef typename rep_type::pointer pointer;
        typedef typename rep_type::reference reference;
        typedef typename rep_type::const_reference const_reference;
        typedef typename rep_type::iterator iterator;
        typedef typename rep_type::const_iterator const_iterator;
        typedef typename rep_type::size_type size_type;

        class value_compare
        {
                friend class Oscl_Map<Key, T, Alloc, Compare>;
            protected :
                Compare comp;
                value_compare(Compare c) : comp(c) {}
            public:
                bool operator()(const value_type& x, const value_type& y) const
                {
                    return comp(x.first, y.first);
                }
        };

    public:

        /**
         * Creates an empty map using comp as the key compare object
         */
        Oscl_Map(const Compare& comp = Compare()) : t(comp) {}
//    Oscl_Map(const value_type* first, const value_type* last,
//        const Compare& comp = Compare()) : t(first, last, comp, false) {}

        /**
         * Oscl_Map copy constructor
         */
        Oscl_Map(const self& x) : t(x.t) {}
        /**
         * Oscl_Map assignment operator
         */
        self& operator=(const self& x)
        {
            t = x.t;
            return *this;
        }
        /**
         * Returns the key compare object used by the map
         */
        key_compare key_comp() const
        {
            return t.key_comp();
        }
        /**
         * Returns the value compare object used by the map
         */
        value_compare value_comp() const
        {
            return value_compare(t.key_comp());
        }
        /**
         * Returns an iterator pointing to the beginning of the map
         */
        iterator begin()
        {
            return t.begin();
        }
        /**
         * Returns a const iterator pointing to the beginning of the map
         */
        const_iterator begin() const
        {
            return t.begin();
        }
        /**
         * Returns an iterator pointing to the end of the map.
         */
        iterator end()
        {
            return t.end();
        }
        /**
         * Returns a const iterator pointing to the end of the map.
         */
        const_iterator end() const
        {
            return t.end();
        }
        /**
         * Returns true if map size is 0
         */
        bool empty() const
        {
            return t.empty();
        }
        /**
         * Returns the size of the map
         */
        size_type size() const
        {
            return t.size();
        }
        /**
         * Returns the maximum possible size of the map
         */
        size_type max_size() const
        {
            return t.max_size();
        }
        /**
         * Returns a reference to the object that is associated with a particular key.
         * If the map does not already contain such an object, operator[] inserts the default object value_type().
         */
        T& operator[](const key_type& k)
        {
            return (*((insert(value_type(k, T()))).first)).second;
        }
//    void swap(map<Key, T, Compare>& x) { t.swap(x.t); }


        typedef Oscl_Pair<iterator, bool> pair_iterator_bool;
        /**
         * Inserts x into the map
         */
        pair_iterator_bool insert(const value_type& x)
        {
            return t.insert_unique(x);
        }
        /**
         * Inserts x into the map using position as a hint as to where it should be inserted
         */
        iterator insert(iterator position, const value_type& x)
        {
            return t.insert_unique(position, x);
        }
        /**
         * Inserts the range [first,last) into the map
         */
        void insert(const value_type* first, const value_type* last)
        {
            t.insert_unique(first, last);
        }
        /**
         * Erases the element pointed to by position
         */
        void erase(iterator position)
        {
            t.erase(position);
        }
        /**
         * Erases the element with key x
         */
        size_type erase(const key_type& x)
        {
            return t.erase(x);
        }
        /**
         * Erases all elements in the range [first,last)
         */
        void erase(iterator first, iterator last)
        {
            t.erase(first, last);
        }
        /**
         * Erases all elements
         */
        void clear()
        {
            t.clear();
        }
        /**
         * Finds an element whose key is x
         */
        iterator find(const key_type& x)
        {
            return t.find(x);
        }
        /**
         * Finds an element whose key is x
         */
        const_iterator find(const key_type& x) const
        {
            return t.find(x);
        }
        /**
         * Returns the number of elements with key x.  For map this will either be 0 or 1.
         */
        size_type count(const key_type& x) const
        {
            return t.count(x);
        }
        /**
         * Finds the first element whose key is not less than x
         */
        iterator lower_bound(const key_type& x)
        {
            return t.lower_bound(x);
        }
        /**
         * Finds the first element whose key is not less than x
         */
        const_iterator lower_bound(const key_type& x) const
        {
            return t.lower_bound(x);
        }
        /**
         * Finds the first element whose key is not greater than x
         */
        iterator upper_bound(const key_type& x)
        {
            return t.upper_bound(x);
        }
        /**
         * Finds the first element whose key is not greater than x
         */
        const_iterator upper_bound(const key_type& x) const
        {
            return t.upper_bound(x);
        }
        typedef Oscl_Pair<iterator, iterator> pair_iterator_iterator;
        /**
         * Finds a range containing all elements whose key is x
         */
        pair_iterator_iterator equal_range(const key_type& x)
        {
            return t.equal_range(x);
        }
        typedef Oscl_Pair<const_iterator, const_iterator> pair_citerator_citerator;
        /**
         * Finds a range containing all elements whose key is x
         */
        pair_citerator_citerator equal_range(const key_type& x) const
        {
            return t.equal_range(x);
        }

    private:

};

//template <class Key, class T, class Compare>
//inline bool operator==(const map<Key, T, Compare>& x,
//                       const map<Key, T, Compare>& y) {
//    return x.size() == y.size() && equal(x.begin(), x.end(), y.begin());
//}

//template <class Key, class T, class Compare>
//inline bool operator<(const map<Key, T, Compare>& x,
//                      const map<Key, T, Compare>& y) {
//    return lexicographical_compare(x.begin(), x.end(), y.begin(), y.end());
//}


/*! @} */


#endif