You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
374 lines
9.1 KiB
374 lines
9.1 KiB
/* ************************************************************************** */ |
|
/* */ |
|
/* ::: :::::::: */ |
|
/* map.hpp :+: :+: :+: */ |
|
/* +:+ +:+ +:+ */ |
|
/* By: pohl <pohl@student.42.fr> +#+ +:+ +#+ */ |
|
/* +#+#+#+#+#+ +#+ */ |
|
/* Created: 2022/02/08 09:03:00 by pohl #+# #+# */ |
|
/* Updated: 2022/02/17 08:22:02 by pohl ### ########.fr */ |
|
/* */ |
|
/* ************************************************************************** */ |
|
|
|
#ifndef MAP_HPP |
|
# define MAP_HPP |
|
|
|
# include "map_tree.hpp" |
|
# include "map_iterator.hpp" |
|
# include "map_reverse_iterator.hpp" |
|
|
|
namespace ft |
|
{ |
|
|
|
template< typename Key, typename T, typename Cmp = std::less<Key>, |
|
typename Allocator = std::allocator<pair<const Key, T> > > |
|
class map |
|
{ |
|
|
|
public: |
|
|
|
typedef Key key_type; |
|
typedef T mapped_type; |
|
typedef pair<const Key, T> value_type; |
|
typedef std::size_t size_type; |
|
typedef std::ptrdiff_t difference_type; |
|
typedef Cmp key_compare; |
|
typedef Allocator allocator_type; |
|
|
|
typedef typename Allocator::reference reference; |
|
typedef typename Allocator::const_reference const_reference; |
|
typedef typename Allocator::pointer pointer; |
|
typedef typename Allocator::const_pointer const_pointer; |
|
|
|
typedef map_iterator<const Key, T, Cmp> iterator; |
|
typedef map_iterator<const Key, T, Cmp, true> const_iterator; |
|
typedef ft::map_reverse_iterator<const Key, T, Cmp> reverse_iterator; |
|
typedef ft::map_reverse_iterator<const Key, T, Cmp, true> const_reverse_iterator; |
|
|
|
typedef tree<const Key, T, Cmp, Allocator> tree_type; |
|
|
|
public: |
|
|
|
class value_compare |
|
{ |
|
|
|
public: |
|
|
|
typedef bool result_type; |
|
typedef value_type first_argument_type; |
|
typedef value_type second_argument_type; |
|
|
|
public: |
|
|
|
Cmp comp; |
|
|
|
value_compare( Cmp c = Cmp() ): comp(c) { return ; } |
|
|
|
public: |
|
|
|
bool operator()( const value_type& lhs, const value_type& rhs ) const |
|
{ |
|
return comp(lhs.first, rhs.first); |
|
} |
|
|
|
}; |
|
|
|
|
|
public: |
|
|
|
explicit map( const key_compare &cmp = key_compare(), |
|
const Allocator &alloc = Allocator() ): |
|
_comparator(cmp), _valueAlloc(alloc) |
|
{ |
|
return; |
|
} |
|
template< typename InputIt > |
|
map( InputIt first, InputIt last, const key_compare &cmp = key_compare(), |
|
const Allocator &alloc = Allocator() ): |
|
_comparator(cmp), _valueAlloc(alloc) |
|
{ |
|
this->insert(first, last); |
|
} |
|
map( const map& other ) |
|
{ |
|
this->_rbTree = other._rbTree; |
|
this->_comparator = other._comparator; |
|
this->_valueAlloc = other._valueAlloc; |
|
} |
|
~map( void ) |
|
{ |
|
} |
|
|
|
map &operator=( const map& other ) |
|
{ |
|
if (this == &other) |
|
return *this; |
|
this->_rbTree = other._rbTree; |
|
this->_comparator = other._comparator; |
|
this->_valueAlloc = other._valueAlloc; |
|
return *this; |
|
} |
|
|
|
mapped_type& operator[]( const key_type& key ) |
|
{ |
|
return (*((this->insert(ft::make_pair(key, mapped_type()))).first)).second; |
|
} |
|
mapped_type& at( const key_type& key ) |
|
{ |
|
if (this->alreadyExists(key)) |
|
throw std::out_of_range("key is out_of_range"); |
|
else |
|
return (*this)[key]; |
|
} |
|
const mapped_type& at( const key_type& key) const |
|
{ |
|
if (this->alreadyExists(key)) |
|
throw std::out_of_range("key is out_of_range"); |
|
else |
|
return (*this)[key]; |
|
} |
|
|
|
iterator begin( void ) |
|
{ |
|
return iterator(this->_rbTree.treeMinimum(), (_rbTree.size() == 0)); |
|
} |
|
iterator begin( void ) const |
|
{ |
|
return iterator(this->_rbTree.treeMinimum(), (_rbTree.size() == 0)); |
|
} |
|
iterator end( void ) |
|
{ |
|
return iterator(this->_rbTree.treeMaximum(), true); |
|
} |
|
iterator end( void ) const |
|
{ |
|
return iterator(this->_rbTree.treeMaximum(), true); |
|
} |
|
reverse_iterator rbegin( void ) |
|
{ |
|
return reverse_iterator(this->_rbTree.treeMaximum(), (_rbTree.size() == 0)); |
|
} |
|
reverse_iterator rbegin( void ) const |
|
{ |
|
return reverse_iterator(this->_rbTree.treeMaximum(), (_rbTree.size() == 0)); |
|
} |
|
reverse_iterator rend( void ) |
|
{ |
|
return reverse_iterator(this->_rbTree.treeMinimum(), true); |
|
} |
|
reverse_iterator rend( void ) const |
|
{ |
|
return reverse_iterator(this->_rbTree.treeMinimum(), true); |
|
} |
|
|
|
bool empty( void ) const { return _rbTree.size() == 0; } |
|
size_type size( void ) const { return _rbTree.size(); } |
|
size_type max_size( void ) const { return _rbTree.max_size(); } |
|
|
|
key_compare key_comp( void ) const { return this->_comparator; } |
|
value_compare value_comp() const |
|
{ |
|
return value_compare(key_comp()); |
|
} |
|
allocator_type get_allocator( void ) const { return this->_valueAlloc; } |
|
|
|
iterator find( const key_type& key ) |
|
{ |
|
node<const Key, T, Cmp, Allocator> *result = _rbTree.findNode(key); |
|
|
|
if (result->isNil()) |
|
return this->end(); |
|
return iterator(result); |
|
} |
|
const_iterator find( const key_type& key ) const |
|
{ |
|
node<const Key, T, Cmp, Allocator> *result = _rbTree.findNode(key); |
|
|
|
if (result->isNil()) |
|
return this->end(); |
|
return const_iterator(result); |
|
} |
|
size_type count( const key_type& key ) const |
|
{ |
|
if (_rbTree.findNode(key)->isNil()) |
|
return 0; |
|
return 1; |
|
} |
|
iterator lower_bound( const key_type& key ) |
|
{ |
|
node<const Key, T, Cmp, Allocator> *result = _rbTree.lower_bound(key); |
|
|
|
if (result->isNil()) |
|
return this->end(); |
|
return iterator(result); |
|
} |
|
const_iterator lower_bound( const key_type& key ) const |
|
{ |
|
node<const Key, T, Cmp, Allocator> *result = _rbTree.lower_bound(key); |
|
|
|
if (result->isNil()) |
|
return this->end(); |
|
return const_iterator(result); |
|
} |
|
iterator upper_bound( const key_type& key ) |
|
{ |
|
node<const Key, T, Cmp, Allocator> *result = _rbTree.upper_bound(key); |
|
|
|
if (result->isNil()) |
|
return this->end(); |
|
return iterator(result); |
|
} |
|
const_iterator upper_bound( const key_type& key ) const |
|
{ |
|
node<const Key, T, Cmp, Allocator> *result = _rbTree.upper_bound(key); |
|
|
|
if (result->isNil()) |
|
return this->end(); |
|
return const_iterator(result); |
|
} |
|
ft::pair<iterator, iterator> equal_range( const key_type& key ) |
|
{ |
|
return ft::make_pair(this->lower_bound(key), this->upper_bound(key)); |
|
} |
|
ft::pair<const_iterator, const_iterator> equal_range( const key_type& key ) const |
|
{ |
|
return ft::make_pair(this->lower_bound(key), this->upper_bound(key)); |
|
} |
|
|
|
ft::pair<iterator, bool> insert( const value_type& value ) |
|
{ |
|
bool wasInserted = false; |
|
iterator inserted = this->_rbTree.insertValue(value, wasInserted); |
|
|
|
return ft::make_pair(iterator(inserted), wasInserted); |
|
} |
|
iterator insert( iterator position, const value_type& value ) |
|
{ |
|
bool placeholder = false; |
|
|
|
if ((*position).first + 1 == value.first) |
|
return this->_rbTree.insertValue(position.getNode(), value, |
|
placeholder); |
|
return this->_rbTree.insertValue(value, placeholder); |
|
} |
|
template< typename InputIt > |
|
void insert( InputIt first, InputIt last ) |
|
{ |
|
bool useless; |
|
|
|
while (first != last) |
|
{ |
|
this->_rbTree.insertValue(*first, useless); |
|
first++; |
|
} |
|
} |
|
|
|
void erase( iterator position ) |
|
{ |
|
this->_rbTree.eraseNode(position.getNode()); |
|
} |
|
void erase( iterator first, iterator last ) |
|
{ |
|
while (first != last) |
|
this->_rbTree.eraseNode((first++).getNode()); |
|
} |
|
size_type erase( const key_type& key ) |
|
{ |
|
return this->_rbTree.eraseNodeFromKey(key); |
|
} |
|
|
|
void clear( void ) |
|
{ |
|
this->_rbTree.clear(); |
|
} |
|
|
|
void swap( map& other ) |
|
{ |
|
allocator_type tmp_valueAlloc = other._valueAlloc; |
|
key_compare tmp_comparator = other._comparator; |
|
|
|
other._valueAlloc = this->_valueAlloc; |
|
other._comparator = this->_comparator; |
|
this->_valueAlloc = tmp_valueAlloc; |
|
this->_comparator = tmp_comparator; |
|
this->_rbTree.swap(other._rbTree); |
|
} |
|
|
|
friend bool operator==( const map &lhs, const map &rhs ) |
|
{ |
|
iterator lhs_it = lhs.begin(); |
|
iterator lhs_ite = lhs.end(); |
|
iterator rhs_it = rhs.begin(); |
|
iterator rhs_ite = rhs.end(); |
|
|
|
while (lhs_it != lhs_ite && rhs_it != rhs_ite) |
|
{ |
|
if (lhs_it->second != rhs_it->second) |
|
return false; |
|
lhs_it++; |
|
rhs_it++; |
|
} |
|
if (lhs_it != lhs_ite || rhs_it != rhs_ite) |
|
return false; |
|
return true; |
|
} |
|
friend bool operator!=( const map &lhs, const map &rhs ) |
|
{ |
|
return !(lhs == rhs); |
|
} |
|
friend bool operator<( const map &lhs, const map &rhs ) |
|
{ |
|
iterator lhs_it = lhs.begin(); |
|
iterator lhs_ite = lhs.end(); |
|
iterator rhs_it = rhs.begin(); |
|
iterator rhs_ite = rhs.end(); |
|
|
|
while (lhs_it != lhs_ite && rhs_it != rhs_ite) |
|
{ |
|
if (lhs_it->second != rhs_it->second) |
|
return lhs_it->second < rhs_it->second; |
|
lhs_it++; |
|
rhs_it++; |
|
} |
|
if (rhs_it == rhs_ite) |
|
return false; |
|
return true; |
|
} |
|
friend bool operator>( const map &lhs, const map &rhs ) |
|
{ |
|
return rhs < lhs; |
|
} |
|
friend bool operator<=( const map &lhs, const map &rhs ) |
|
{ |
|
return !(lhs > rhs); |
|
} |
|
friend bool operator>=( const map &lhs, const map &rhs ) |
|
{ |
|
return !(lhs < rhs); |
|
} |
|
friend void swap( map &rhs, map &lhs ) |
|
{ |
|
lhs.swap(rhs); |
|
} |
|
|
|
void printTree( void ) const |
|
{ |
|
_rbTree.printTree(); |
|
} |
|
|
|
private: |
|
|
|
tree_type _rbTree; |
|
key_compare _comparator; |
|
allocator_type _valueAlloc; |
|
|
|
bool alreadyExists( const key_type& key ) const |
|
{ |
|
return _rbTree.findNode(key)->isNil(); |
|
} |
|
|
|
}; |
|
|
|
} |
|
|
|
#endif
|
|
|