#include <splay_tree_map.h>
Inheritance diagram for dsac::search_tree::SplayTreeMap< Key, Value, Compare >:
Collaboration diagram for dsac::search_tree::SplayTreeMap< Key, Value, Compare >:
Protected Types | |
| typedef TreeMap< Key, Value, Compare > | Base |
| typedef BalanceableBinaryTree::Node | Node |
 Protected Types inherited from dsac::search_tree::TreeMap< Key, Value, Compare > | |
| typedef dsac::map::AbstractMap< Key, Value > | Base |
| typedef std::pair< Entry, int > | BSTEntry |
| typedef dsac::tree::LinkedBinaryTree< BSTEntry > | TreeBase |
| typedef BalanceableBinaryTree::Node | Node |
| typedef BalanceableBinaryTree::Position | Position |
Protected Member Functions | |
| void | splay (Node *p) |
| void | rebalance_access (Node *p) |
| void | rebalance_insert (Node *p) |
| void | rebalance_delete (Node *p) |
| Protected Member Functions inherited from dsac::search_tree::TreeMap< Key, Value, Compare > | |
| virtual void | rebalance_access (Node *) |
| virtual void | rebalance_insert (Node *) |
| virtual void | rebalance_delete (Node *) |
| Key | key (Node *nd) const |
| int | aux (Node *nd) const |
| void | set_aux (Node *nd, int value) |
| bool | equals (Key a, Key b) const |
| Node * | search (Key k) const |
| abstract_iter_rep * | get_rep (const_iterator iter) const |
| Protected Member Functions inherited from dsac::map::AbstractMap< Key, Value > | |
| abstract_iter_rep * | get_rep (const_iterator iter) const |
| void | update_value (const Entry &e, const Value &v) |
Protected Attributes | |
| BalanceableBinaryTree | tree |
| Protected Attributes inherited from dsac::search_tree::TreeMap< Key, Value, Compare > | |
| BalanceableBinaryTree | tree |
| Compare | less_than |
Additional Inherited Members | |
| Public Member Functions inherited from dsac::search_tree::TreeMap< Key, Value, Compare > | |
| TreeMap () | |
| Creates an empty map. | |
| int | size () const |
| Returns the number of entries in the map. | |
| const_iterator | begin () const |
| Returns a const_iterator to first entry. | |
| const_iterator | end () const |
| Returns a const_iterator representing the end. | |
| const_iterator | find (const Key &k) const |
| Returns a const_iterator to the entry with a given key, or end() if no such entry exists. | |
| const_iterator | put (const Key &k, const Value &v) |
| const_iterator | erase (const_iterator loc) |
| Removes the entry indicated by the given iterator, and returns const_iterator to next entry in iteration order. | |
| const_iterator | lower_bound (const Key &k) const |
| Returns a const_iterator to the first entry with key greater than or equal to k, or end() if no such entry exists. | |
| const_iterator | upper_bound (const Key &k) const |
| Returns a const_iterator to the first entry with key strictly greater than k, or end() if no such entry exists. | |
| void | _dump () const |
| used for debugging only | |
| bool | empty () const |
| Returns true if the map is empty, false otherwise. | |
| bool | erase (const Key &k) |
| virtual const_iterator | erase (const_iterator loc)=0 |
| Public Member Functions inherited from dsac::map::AbstractMap< Key, Value > | |
| bool | empty () const |
| Returns true if the map is empty, false otherwise. | |
| bool | contains (const Key &k) const |
| Returns true if the map contains an entry with the given key. | |
| const Value & | at (const Key &k) const |
| bool | erase (const Key &k) |
| virtual | ~AbstractMap () |
| virtual int | size () const =0 |
| virtual const_iterator | begin () const =0 |
| virtual const_iterator | end () const =0 |
| virtual const_iterator | find (const Key &k) const =0 |
| virtual const_iterator | put (const Key &k, const Value &v)=0 |
| virtual const_iterator | erase (const_iterator loc)=0 |
| Static Public Member Functions inherited from dsac::search_tree::TreeMap< Key, Value, Compare > | |
| static void | _dumpNode (Node *p) |
| static void | _dump (Node *p, int depth) |
| Static Protected Member Functions inherited from dsac::search_tree::TreeMap< Key, Value, Compare > | |
| static Node * | successor (Node *p) |
Member Typedef Documentation
◆ Base
template<typename Key , typename Value , typename Compare = std::less<Key>>
|
protected |
◆ Node
template<typename Key , typename Value , typename Compare = std::less<Key>>
|
protected |
Member Function Documentation
◆ rebalance_access()
template<typename Key , typename Value , typename Compare = std::less<Key>>
|
inlineprotected |
Here is the call graph for this function:
◆ rebalance_delete()
template<typename Key , typename Value , typename Compare = std::less<Key>>
|
inlineprotected |
Here is the call graph for this function:
◆ rebalance_insert()
template<typename Key , typename Value , typename Compare = std::less<Key>>
|
inlineprotected |
Here is the call graph for this function:
◆ splay()
template<typename Key , typename Value , typename Compare = std::less<Key>>
|
inlineprotected |
Here is the call graph for this function:
Field Documentation
◆ tree
template<typename Key , typename Value , typename Compare = std::less<Key>>
|
protected |
The documentation for this class was generated from the following file:
- dsac/searchtree/splay_tree_map.h
