Claw  1.7.3
avl.hpp
Go to the documentation of this file.
00001 /*
00002   CLAW - a C++ Library Absolutely Wonderful
00003 
00004   CLAW is a free library without any particular aim but being useful to 
00005   anyone.
00006 
00007   Copyright (C) 2005-2011 Julien Jorge
00008 
00009   This library is free software; you can redistribute it and/or
00010   modify it under the terms of the GNU Lesser General Public
00011   License as published by the Free Software Foundation; either
00012   version 2.1 of the License, or (at your option) any later version.
00013 
00014   This library is distributed in the hope that it will be useful,
00015   but WITHOUT ANY WARRANTY; without even the implied warranty of
00016   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00017   Lesser General Public License for more details.
00018 
00019   You should have received a copy of the GNU Lesser General Public
00020   License along with this library; if not, write to the Free Software
00021   Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
00022 
00023   contact: julien.jorge@gamned.org
00024 */
00030 #ifndef __CLAW_AVL_HPP__
00031 #define __CLAW_AVL_HPP__
00032 
00033 #include <claw/avl_base.hpp>
00034 
00035 namespace claw
00036 {
00037   //---------------------------------------------------------------------------
00042   template < class K, class Comp = std::less<K> >
00043   class avl
00044   {
00045   private:
00047     typedef avl_base<K, Comp> impl_type;
00048 
00049   public:
00051     typedef K value_type;
00052 
00054     typedef K key_type;
00055 
00057     typedef K referent_type;
00058 
00060     typedef Comp key_less;
00061 
00063     typedef const K& const_reference;
00064 
00066     typedef typename impl_type::avl_const_iterator const_iterator;
00067 
00068   public:
00069     avl();
00070     explicit avl( const avl<K, Comp>& that );
00071     template<typename InputIterator>
00072     avl( InputIterator first, InputIterator last );
00073 
00074     void insert( const K& key );
00075     template<typename InputIterator>
00076     void insert( InputIterator first, InputIterator last );
00077 
00078     void erase( const K& key );
00079     void clear();
00080 
00081     unsigned int size() const;
00082     bool empty() const;
00083 
00084     const_iterator begin() const;
00085     const_iterator end() const;
00086     const_iterator find( const K& key ) const;
00087     const_iterator find_nearest_greater( const K& key ) const;
00088     const_iterator find_nearest_lower( const K& key ) const;
00089     const_iterator lower_bound() const;
00090     const_iterator upper_bound() const;
00091 
00092     avl<K, Comp>& operator=( const avl<K, Comp>& that );
00093     bool operator==( const avl<K, Comp>& that ) const;
00094     bool operator!=( const avl<K, Comp>& that ) const;
00095     bool operator<( const avl<K, Comp>& that ) const;
00096     bool operator>( const avl<K, Comp>& that ) const;
00097     bool operator<=( const avl<K, Comp>& that ) const;
00098     bool operator>=( const avl<K, Comp>& that ) const;
00099 
00100   private:
00102     impl_type m_tree;
00103 
00104   }; // class avl
00105 } // namespace claw
00106 
00107 #include <claw/impl/avl.tpp>
00108 
00109 #endif // __CLAW_AVL_HPP__