Thread portable class Gate portable class Timer class Pool class Terimber 2.0 About C++

Downloads Products & Services Support Clients Open Source About Home / Open source / Terimber 2.0 map.h Go to the documentation of this file. /* * The Software License * ================================================================================= * Copyright (c) 2003-.The Terimber Corporation. All rights reserved. * ================================================================================= * Redistributions of source code must retain the above copyright notice, * this list of conditions and the following disclaimer. * 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. * The end-user documentation included with the redistribution, if any, * must include the following acknowledgment: * "This product includes software developed by the Terimber Corporation." * ================================================================================= * THIS SOFTWARE IS PROVIDED "AS IS" AND ANY EXPRESSED 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 THE TERIMBER CORPORATION 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 _terimber_map_h_ #define _terimber_map_h_ #include "base/memory.h" BEGIN_TERIMBER_NAMESPACE #pragma pack(4) template< class T > class less { public: inline bool operator()( const T& first, const T& second ) const; }; template < class T1, class T2 > class pair { public: pair< T1, T2 >(); pair< T1, T2 >( const T1& v1, const T2& v2 ); pair< T1, T2 >(const pair< T1, T2 >& x); inline bool operator==(const pair< T1, T2 >& x) const; inline bool operator<(const pair< T1, T2 >& x) const; inline bool operator!=(const pair< T1, T2 >& x) const; T1 first; T2 second; }; template < class K, class T, class Pr = less< K >, bool M = false > class base_map { public: class iterator; class const_iterator; friend class const_iterator; friend class iterator; typedef bool redblack; #define c_red true #define c_black false typedef bool nodetype; #define t_head true #define t_leaf false class _node; class _node_ { public: _node_() : _left(0), _parent(0), _right(0), _color(c_red), _type(t_leaf) { } _node* _left; _node* _parent; _node* _right; redblack _color; nodetype _type; }; class _node : public _node_ { public: _node() : _node_() { } K _key; T _value; inline static _node* _max( _node* p ) { while (p->_right->_type != t_head) p = p->_right; return p; } inline static _node* _min(_node* p) { while (p->_left->_type != t_head) p = p->_left; return p; } }; protected: explicit base_map< K, T, Pr, M >(const Pr& pr = Pr() ); base_map< K, T, Pr, M >(const base_map< K, T, Pr, M >& x); ~base_map< K, T, Pr, M >(); public: class const_iterator { public: typedef std::bidirectional_iterator_tag iterator_category; typedef size_t size_type; typedef T* pointer; typedef const T* const_pointer; typedef T& reference; typedef const T& const_reference; typedef T value_type; typedef size_t difference_type; inline const_iterator() : _ptr(0) { } inline const_iterator(_node* p ) : _ptr(p) { } inline const_iterator(const iterator& x) : _ptr(x._ptr) { } inline const T& operator*() const { return _ptr->_value; } inline const T* operator->() const { return &_ptr->_value; } inline const_iterator& operator++() { _inc(); return *this; } inline const_iterator operator++(int) { const_iterator tmp = *this; _inc(); return tmp; } inline const_iterator& operator--() { _dec(); return *this; } inline const_iterator operator--(int) { const_iterator tmp = *this; _dec(); return tmp; } inline bool operator==(const const_iterator& x) const { return _ptr == x._ptr; } inline bool operator!=(const const_iterator& x) const { return _ptr != x._ptr; } inline const K& key() const { return _ptr->_key; } inline void _dec() { if (_ptr->_type == t_head) _ptr = _ptr->_right; else if (_ptr->_left->_type != t_head) _ptr = _node::_max(_ptr->_left); else { _node* p; while ((p = _ptr->_parent)->_type != t_head && _ptr == p->_left) _ptr = p; if (p->_type != t_head) _ptr = p; } } inline void _inc() { if (_ptr->_type == t_head) //; ??? _ptr = _ptr->_left; else if (_ptr->_right->_type != t_head) _ptr = _node::_min(_ptr->_right); else { _node* p; while ((p = _ptr->_parent)->_type != t_head && _ptr == p->_right) _ptr = p; _ptr = p; } } inline _node* left() const { return _ptr->_left; } inline _node* right() const { return _ptr->_right; } inline _node* parent() const { return _ptr->_parent; } inline _node* node() const { return _ptr; } protected: _node* _ptr; }; class iterator : public const_iterator { public: inline iterator() {} inline iterator( _node* p ) : const_iterator(p) { } inline T& operator*() const { return this->_ptr->_value; } inline T* operator->() const { return &this->_ptr->_value; } inline iterator& operator++() { this->_inc(); return *this; } inline iterator operator++(int) { iterator tmp = *this; this->_inc(); return tmp; } inline iterator& operator--() { this->_dec(); return *this; } inline iterator operator--(int) { iterator tmp = *this; this->_dec(); return tmp; } inline bool operator==(const iterator& x) const { return this->_ptr == x._ptr; } inline bool operator!=(const iterator& x) const { return this->_ptr != x._ptr; } }; inline const Pr& comp() const; inline TYPENAME base_map< K, T, Pr, M >::iterator begin(); inline TYPENAME base_map< K, T, Pr, M >::const_iterator begin() const; inline TYPENAME base_map< K, T, Pr, M >::iterator end(); inline TYPENAME base_map< K, T, Pr, M >::const_iterator end() const; inline size_t size() const; inline bool empty() const; inline TYPENAME base_map< K, T, Pr, M >::iterator find( const K& k ); inline TYPENAME base_map< K, T, Pr, M >::const_iterator find( const K& k ) const; typedef pair< iterator, iterator > pairii_t; typedef pair< const_iterator, const_iterator > paircc_t; inline TYPENAME base_map< K, T, Pr, M >::iterator lower_bound( const K& k ); inline TYPENAME base_map< K, T, Pr, M >::const_iterator lower_bound( const K& k ) const; inline TYPENAME base_map< K, T, Pr, M >::iterator upper_bound( const K& k ); inline TYPENAME base_map< K, T, Pr, M >::const_iterator upper_bound( const K& k ) const; inline pairii_t equal_range( const K& k ); inline paircc_t equal_range( const K& k ) const; inline void clear(); typedef pair< iterator, bool > pairib_t; protected: inline TYPENAME base_map< K, T, Pr, M >::iterator _insert( bool left, TYPENAME base_map< K, T, Pr, M >::_node* w, TYPENAME base_map< K, T, Pr, M >::_node* n, const K& k, const T& v ); inline TYPENAME base_map< K, T, Pr, M >::iterator _erase( iterator w, TYPENAME base_map< K, T, Pr, M >::_node*& e ); inline TYPENAME base_map< K, T, Pr, M >::_node* _lbound( const K& k ) const; inline TYPENAME base_map< K, T, Pr, M >::_node* _ubound( const K& k ) const; inline TYPENAME base_map< K, T, Pr, M >::_node*& lmost(); inline TYPENAME base_map< K, T, Pr, M >::_node*& lmost() const; inline TYPENAME base_map< K, T, Pr, M >::_node*& rmost(); inline TYPENAME base_map< K, T, Pr, M >::_node*& rmost() const; inline TYPENAME base_map< K, T, Pr, M >::_node*& root(); inline TYPENAME base_map< K, T, Pr, M >::_node*& root() const; inline TYPENAME base_map< K, T, Pr, M >::_node* head(); inline TYPENAME base_map< K, T, Pr, M >::_node* head() const; inline void _lrotate( TYPENAME base_map< K, T, Pr, M >::_node* x ); inline void _rrotate( TYPENAME base_map< K, T, Pr, M >::_node* x ); inline void _consval( T* p, const T& v ); inline void _conskey( K* p, const K& k ); inline void _destval( T* p ); inline void _destkey( K* p ); Pr key_compare; TYPENAME base_map< K, T, Pr, M >::_node_ _head; size_t _size; }; template < class K, class T, class A = byte_allocator, class Pr = less< K >, bool M = false > class _map : public base_map< K, T, Pr, M > { _map< K, T, A, Pr, M >& operator=(const _map< K, T, A, Pr, M >& x); public: explicit _map< K, T, A, Pr, M >(const Pr& pr = Pr() ); _map< K, T, A, Pr, M >(const _map< K, T, A, Pr, M >& x ); ~_map< K, T, A, Pr, M >(); inline void assign( A& allocator_, const _map< K, T, A, Pr, M >& x ); /* inline TYPENAME _map< K, T, A, Pr, M >::iterator insert( A& allocator_, //!< external allocator const K& k, //!< key const T& v //!< value ); */ inline TYPENAME _map< K, T, A, Pr, M >::pairib_t insert( A& allocator_, const K& k, const T& v ); inline TYPENAME _map< K, T, A, Pr, M >::iterator erase( TYPENAME _map< K, T, A, Pr, M >::iterator p ); inline TYPENAME _map< K, T, A, Pr, M >::iterator erase( node_allocator< TYPENAME base_map< K, T, Pr, M >::_node >& allocator_, TYPENAME _map< K, T, A, Pr, M >::iterator p ); inline void erase( const K& k ); inline void erase( node_allocator< TYPENAME base_map< K, T, Pr, M >::_node >& allocator_, const K& k ); inline TYPENAME _map< K, T, A, Pr, M >::iterator erase( TYPENAME _map< K, T, A, Pr, M >::iterator first, TYPENAME _map< K, T, A, Pr, M >::iterator last ); inline TYPENAME _map< K, T, A, Pr, M >::iterator erase( node_allocator< TYPENAME base_map< K, T, Pr, M >::_node >& allocator_, TYPENAME _map< K, T, A, Pr, M >::iterator first, TYPENAME _map< K, T, A, Pr, M >::iterator last ); protected: inline void _erase( TYPENAME _map< K, T, A, Pr, M >::_node* x ); inline void _erase( node_allocator< TYPENAME base_map< K, T, Pr, M >::_node >& allocator_, TYPENAME _map< K, T, A, Pr, M >::_node* x ); inline TYPENAME _map< K, T, A, Pr, M >::iterator _insert( A& _allocator, bool left, TYPENAME _map< K, T, A, Pr, M >::_node* w, const K& k, const T& v ); inline TYPENAME _map< K, T, A, Pr, M >::_node* _buynode( byte_allocator& _allocator, TYPENAME _map< K, T, A, Pr, M >::_node* p, TYPENAME _map< K, T, A, Pr, M >::redblack c, TYPENAME _map< K, T, A, Pr, M >::nodetype t ); inline TYPENAME _map< K, T, A, Pr, M >::_node* _buynode( node_allocator< TYPENAME base_map< K, T, Pr, M >::_node >& _allocator, TYPENAME _map< K, T, A, Pr, M >::_node* p, TYPENAME _map< K, T, A, Pr, M >::redblack c, TYPENAME _map< K, T, A, Pr, M >::nodetype t ); inline void _freenode( node_allocator< TYPENAME base_map< K, T, Pr, M >::_node >& _allocator, TYPENAME _map< K, T, A, Pr, M >::_node* s ); }; template < class K, class T, class Pr = less< K >, bool M = false > class map : public base_map< K, T, Pr, M > { public: explicit map< K, T, Pr, M >( const Pr& pr = Pr(), size_t size = os_def_size ); map< K, T, Pr, M >(const map< K, T, Pr, M >& x); ~map< K, T, Pr, M >(); map< K, T, Pr, M >& operator=(const map< K, T, Pr, M >& x); /* inline TYPENAME map< K, T, Pr, M >::iterator insert( const K& k, //!< key const T& v //!< value ); */ inline TYPENAME map< K, T, Pr, M >::pairib_t insert( const K& k, const T& v ); inline TYPENAME map< K, T, Pr, M >::iterator erase( TYPENAME map< K, T, Pr, M >::iterator p ); inline void erase( const K& k ); inline void clear(); protected: inline TYPENAME map< K, T, Pr, M >::iterator erase( TYPENAME map< K, T, Pr, M >::iterator first, TYPENAME map< K, T, Pr, M >::iterator last ); inline void _erase( TYPENAME map< K, T, Pr, M >::_node* x ); inline TYPENAME map< K, T, Pr, M >::iterator _insert( bool left, TYPENAME map< K, T, Pr, M >::_node* w, const K& k, const T& v ); inline TYPENAME map< K, T, Pr, M >::_node* _buynode( TYPENAME map< K, T, Pr, M >::_node* p, TYPENAME map< K, T, Pr, M >::redblack c, TYPENAME map< K, T, Pr, M >::nodetype t ); inline void _freenode( TYPENAME map< K, T, Pr, M >::_node* s ); node_allocator< TYPENAME base_map< K, T, Pr, M >::_node > _allocator; }; #pragma pack() END_TERIMBER_NAMESPACE #endif // _terimber_map_h_

© Copyright Terimber 2003-.