vs::_vs_tree< _Key, _Comp > Class Template Reference

serves as stl-like interface from node to vs_tree; handles allocations in construction and destruction. More...

#include <vs_tree.h>

Public Types
typedef _vs_tree_iterator< _Key, _Comp >	iterator
typedef _vs_tree_node< _Key, _Comp >::_Ptr_type	_Ptr_type
typedef _vs_tree_node< _Key, _Comp >::size_type	size_type
typedef _Key	value_type

Public Member Functions
	_vs_tree ()=default
	_vs_tree (const _vs_tree &_tree)
	~_vs_tree ()
iterator	begin ()
iterator	end ()
iterator	begin () const
iterator	end () const
const _Key &	top ()
iterator	find (const _Key &_x) const
	simple recursive implementation of find More...
iterator	find_subtree (const _Key &_x, const _Ptr_type &node, _Comp comp=_Comp{}) const
size_type	height () const
size_type	size () const
void	push (const _Key &_value)

Detailed Description

template<typename _Key, typename _Comp = std::less<_Key>>
class vs::_vs_tree< _Key, _Comp >

serves as stl-like interface from node to vs_tree; handles allocations in construction and destruction.

Definition at line 266 of file vs_tree.h.

Member Typedef Documentation

_Ptr_type

template<typename _Key , typename _Comp = std::less<_Key>>

typedef _vs_tree_node<_Key, _Comp>::_Ptr_type vs::_vs_tree< _Key, _Comp >::_Ptr_type

Definition at line 272 of file vs_tree.h.

iterator

template<typename _Key , typename _Comp = std::less<_Key>>

typedef _vs_tree_iterator<_Key, _Comp> vs::_vs_tree< _Key, _Comp >::iterator

Definition at line 271 of file vs_tree.h.

size_type

template<typename _Key , typename _Comp = std::less<_Key>>

typedef _vs_tree_node<_Key, _Comp>::size_type vs::_vs_tree< _Key, _Comp >::size_type

Definition at line 273 of file vs_tree.h.

value_type

template<typename _Key , typename _Comp = std::less<_Key>>

typedef _Key vs::_vs_tree< _Key, _Comp >::value_type

Definition at line 276 of file vs_tree.h.

Constructor & Destructor Documentation

_vs_tree() [1/2]

template<typename _Key , typename _Comp = std::less<_Key>>

vs::_vs_tree< _Key, _Comp >::_vs_tree ( )

default

_vs_tree() [2/2]

template<typename _Key , typename _Comp = std::less<_Key>>

vs::_vs_tree< _Key, _Comp >::_vs_tree ( const _vs_tree< _Key, _Comp > &  _tree )

inline

Definition at line 329 of file vs_tree.h.

        {
            if (_tree.head) {
                this->head = new _vs_tree_node(*(_tree.head));
                copy_subtree(this->head, _tree.head);
            }
 
        }

~_vs_tree()

template<typename _Key , typename _Comp = std::less<_Key>>

vs::_vs_tree< _Key, _Comp >::~_vs_tree ( )

inline

Definition at line 338 of file vs_tree.h.

        {
            std::cout << "deleting " << this << std::endl;
            if (head)
                delete_subtree(head);
 
            head = nullptr;
        }

Member Function Documentation

begin() [1/2]

template<typename _Key , typename _Comp = std::less<_Key>>

iterator vs::_vs_tree< _Key, _Comp >::begin ( )

inline

Definition at line 350 of file vs_tree.h.

        {
            return iterator(this->head);
        }

begin() [2/2]

template<typename _Key , typename _Comp = std::less<_Key>>

iterator vs::_vs_tree< _Key, _Comp >::begin ( ) const

inline

Definition at line 361 of file vs_tree.h.

        {
            return iterator(this->head);
        }

end() [1/2]

template<typename _Key , typename _Comp = std::less<_Key>>

iterator vs::_vs_tree< _Key, _Comp >::end ( )

inline

Definition at line 355 of file vs_tree.h.

        {
            return iterator(nullptr);
        }

end() [2/2]

template<typename _Key , typename _Comp = std::less<_Key>>

iterator vs::_vs_tree< _Key, _Comp >::end ( ) const

inline

Definition at line 366 of file vs_tree.h.

        {
            return iterator(nullptr);
        }

find()

template<typename _Key , typename _Comp = std::less<_Key>>

iterator vs::_vs_tree< _Key, _Comp >::find ( const _Key &  _x ) const

inline

simple recursive implementation of find

Definition at line 381 of file vs_tree.h.

        {
            return find_subtree(_x, head);
        }

find_subtree()

template<typename _Key , typename _Comp = std::less<_Key>>

iterator vs::_vs_tree< _Key, _Comp >::find_subtree ( const _Key &  _x, const _Ptr_type &  node, _Comp  comp = _Comp{}  ) const

inline

Definition at line 387 of file vs_tree.h.

                                                                              {}) const
        {
            if (node->value == _x)
                return iterator(node);
 
            if (comp(_x, node->value))
            {
                if (node->left)
                    return find_subtree(_x, node->left);
                else
                    return end();
            }
            else
            {
                if (node->right)
                    return find_subtree(_x, node->right);
                else
                    return end();
            }
        }

height()

template<typename _Key , typename _Comp = std::less<_Key>>

size_type vs::_vs_tree< _Key, _Comp >::height ( ) const

inline

Definition at line 409 of file vs_tree.h.

        { return _height; }

push()

template<typename _Key , typename _Comp = std::less<_Key>>

void vs::_vs_tree< _Key, _Comp >::push ( const _Key &  _value )

inline

Definition at line 419 of file vs_tree.h.

        {
            if (head)
                head = head->node_insert(_value);
            else
                head = new _vs_tree_node<_Key, _Comp>(_value);
 
            _height = head->height + 1;
            _size++;
        }

size()

template<typename _Key , typename _Comp = std::less<_Key>>

size_type vs::_vs_tree< _Key, _Comp >::size ( ) const

inline

Definition at line 413 of file vs_tree.h.

        { return _size; }

top()

template<typename _Key , typename _Comp = std::less<_Key>>

const _Key& vs::_vs_tree< _Key, _Comp >::top ( )

inline

Definition at line 372 of file vs_tree.h.

        {
            return *begin();
        }

---

The documentation for this class was generated from the following file:

• lib/include/vs_tree.h