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.

634 lines
16 KiB

/* ************************************************************************** */
/* */
/* ::: :::::::: */
/* map.hpp :+: :+: :+: */
/* +:+ +:+ +:+ */
/* By: frdescam <marvin@42.fr> +#+ +:+ +#+ */
/* +#+#+#+#+#+ +#+ */
/* Created: 2021/11/12 18:20:31 by frdescam #+# #+# */
/* Updated: 2021/11/12 18:30:40 by frdescam ### ########.fr */
/* */
/* ************************************************************************** */
#ifndef MAP_HPP
#define MAP_HPP
#include <memory>
#include <limits>
#include <stddef.h>
#include <string>
#include <iostream>
#include "map_utils.hpp"
namespace ft {
template < class Key,
class T,
class Compare = std::less<Key>,
class Alloc = std::allocator<ft::pair<const Key,T> >
> class map
{
public:
typedef Key key_type;
typedef T mapped_type;
typedef ft::pair<const key_type,mapped_type> value_type;
typedef s_tree<value_type> Node;
typedef Compare key_compare;
typedef Alloc allocator_type;
typedef value_type& reference;
typedef const value_type& const_reference;
typedef value_type* pointer;
typedef const value_type* const_pointer;
typedef ft::map_iterator< Key, T > iterator;
typedef ft::map_iterator< Key, T, true > const_iterator;
typedef ft::map_reverse_iterator<iterator> reverse_iterator;
typedef ft::map_reverse_iterator<const_iterator> const_reverse_iterator;
typedef ptrdiff_t difference_type;
typedef size_t size_type;
// ITERATORS
iterator begin() {
Node *n = _mapTree;
while (n && n->left)
n = n->left;
return iterator(n, &_mapTree);
}
iterator end() { return iterator(NULL, &_mapTree); }
const_iterator begin() const {
Node *n = _mapTree;
while (n && n->left)
n = n->left;
return const_iterator(n, &_mapTree);
}
const_iterator end() const { return const_iterator(NULL, &_mapTree);}
reverse_iterator rbegin() {return reverse_iterator(this->end());}
reverse_iterator rend() { return reverse_iterator(this->begin());}
const_reverse_iterator rbegin() const {return const_reverse_iterator(this->end());}
const_reverse_iterator rend() const { return const_reverse_iterator(this->begin());}
// BEGIN IMPLEMENTATION
// Constructs an empty container, with no elements.
explicit map (const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type())
: _keyCmp(comp), _allocTp(alloc), _size(0), _mapTree(NULL)
{
/* NOP */
}
// Constructs a container with as many elements as the range [first,last),
// with each element constructed from its corresponding element in that range.
template <class InputIterator>
map (InputIterator first, InputIterator last, const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type())
: _keyCmp(comp), _allocTp(alloc), _size(0), _mapTree(NULL)
{
for (;first != last; ++first )
insertValueIteratif(make_pair(first->first, first->second));
}
// Constructs a container with a copy of each of the elements in x.
map (const map& x) : _keyCmp(x.key_comp()), _allocTp(x.get_allocator()), _size(0), _mapTree(NULL)
{
const_iterator it = x.begin(); // <- problem on est ds une infinite loop car x n'a pas été rempli correctement et que (x._mapTree == x._mapTree->left)
const_iterator end = x.end();
this->insert(it,end);
}
~map()
{
deleteTree(_mapTree);
}
// Copy container content
// Assigns new contents to the container, replacing its current content.
map& operator= (const map& x)
{
std::cout << "Map operator=" << std::endl;
iterator it = x.begin();
iterator end = x.end();
this->clear();
this->insert(/* x.begin() */it,/* x.end() */end);
return (*this);
}
// CAPACITY:
bool empty() const { return _size ? false : true;}
size_type size() const { return _size;}
size_type max_size() const { return _allocTp.max_size(); }
// ELEMENT ACCESS:
mapped_type& operator[] (const key_type& k) {
return (*((this->insert(make_pair(k,mapped_type()))).first)).second;
}
// MODIFIERS:
pair<iterator,bool> insert (const value_type& val) {
return insertValueIteratif(val);
}
iterator insert (iterator position, const value_type& val) {
static_cast<void>(position);
return insert(val).first;
}
template <class InputIterator>
void insert (InputIterator first, InputIterator last) {
for (; first != last; ++first)
insert(*first);
}
void erase (iterator position) {
deleteValue(position->first);
}
size_type erase (const key_type& k) {
Node* node = NULL;
if ((node = nodeExist(_mapTree, k))){
erase(iterator(node, &_mapTree));
// std::cout << "smt erased\n";
return 1;
}
// std::cout << "nothong erased\n";
return 0;
}
void erase (iterator first, iterator last) {
while (first != last) {
iterator tmp = first++;
erase(tmp);
}
}
// Exchanges the content of the container by the content of x, which is another map of the same type. Sizes may differ.
void swap (map& x) {
size_type size_tmp = x._size;
key_compare keyCmp_tmp = x._keyCmp;
allocator_type allocTp_tmp = x._allocTp;
Node *mapTree_tmp = x._mapTree;
x._size = _size;
x._keyCmp = _keyCmp;
x._allocTp = _allocTp;
x._mapTree = _mapTree;
_size = size_tmp;
_keyCmp = keyCmp_tmp;
_allocTp = allocTp_tmp;
_mapTree = mapTree_tmp;
}
void clear() {
if (_size)
deleteTree(_mapTree);
_mapTree = NULL;
_size = 0;
}
// Returns a copy of the comparison object used by the container to compare keys.
key_compare key_comp() const {
return key_compare();
}
// Returns a comparison object that can be used to compare two elements to get whether the key of the first one goes before the second.
iterator find (const key_type& k) {
Node *node = nodeExist(_mapTree, k);
return node ? iterator(node, &_mapTree) : iterator(NULL, &_mapTree);
}
const_iterator find (const key_type& k) const {
return find(k);
}
size_type count (const key_type& k) const {
const_iterator it = begin();
const_iterator it_end = end();
while (it != it_end) {
if (it->first == k)
return 1;
++it;
}
return 0;
}
// Returns an iterator pointing to the first element in the container whose key is not considered to go before k (i.e., either it is equivalent or goes after).
iterator lower_bound (const key_type& k) {
iterator it = begin();
iterator it_end = end();
while (it != it_end && key_compare()(it->first, k))
++it;
return(it);
}
const_iterator lower_bound (const key_type& k) const {
return lower_bound(k);
}
// Returns an iterator pointing to the first element in the container whose key is considered to go after k.
iterator upper_bound (const key_type& k) { //PAS BON : L'IT RETOURNÉ FONCTIONNE QUE SI LA VALEUR DONNÉE EST DS LA MAP
iterator it = begin();
iterator it_end = end();
while (it != it_end && key_compare()(it->first, k))
++it;
return(it);
}
const_iterator upper_bound (const key_type& k) const {
return upper_bound(k);
}
// Returns the bounds of a range that includes all the elements in the container which have a key equivalent to k.
pair<const_iterator,const_iterator> equal_range (const key_type& k) const {
return ft::make_pair(lower_bound(k), upper_bound(k));
}
pair<iterator,iterator> equal_range (const key_type& k) {
return ft::make_pair(lower_bound(k), upper_bound(k));
}
// Returns a copy of the allocator object associated with the map.
allocator_type get_allocator() const {
return allocator_type();
}
// to erase
Key getStr() { return _mapTree->myPair.first;}
Node* nodeExist(Node *tree, const key_type& k) {
static_cast<void>(tree);
Node* start = getLowest(_mapTree);
while (start && start != NULL) {
if (k == start->myPair.first)
return start;
if (k < start->myPair.first)
start = start->left;
else start = start->right;
}
return NULL;
}
void deltree(Node *tree) {
if (tree) {
if (tree->left != _mapTree)
deltree(tree->left);
if (tree->right != _mapTree)
deltree(tree->right);
delete (tree);
}
delete (_mapTree);
}
Node *getTree(){return _mapTree;}
private:
key_compare _keyCmp;
allocator_type _allocTp;
size_type _size;
Node *_mapTree;
// TYPE DEFINI SPECIFIQUEMENT POUR L'ALLOCATION DE NOEUDS
typename allocator_type::template rebind<Node>::other _alloc_node;
Node* createNode(const value_type& val)
{
Node* node = _alloc_node.allocate(1);
_allocTp.construct(&node->myPair, val);
node->parent = node->left = node->right = NULL;
node->color = E_RED;
return node;
}
Node *insertBST_iteratif(Node *&root, Node *&ptr) {
Node *node = root;
while (node)
if (ptr->myPair.first > node->myPair.first) {
if (!node->right) {
_size++;
node->right = ptr;
ptr->parent = node;
return ptr;
}
node = node->right;
}
else if (ptr->myPair.first < node->myPair.first) {
if (!node->left) {
_size++;
node->left = ptr;
ptr->parent = node;
return ptr;
}
node = node->left;
}
else
return node;
_size++;
ptr->color = E_BLACK;
return (root = ptr);
}
pair<iterator,bool> insertValueIteratif(const value_type& val) {
Node *ptr = createNode(val);
Node *to_return;
pair<iterator,bool> toReturnPair;
if (ptr == (to_return = insertBST_iteratif(_mapTree, ptr))){
fixInsertRBTree(ptr);
toReturnPair.second = true;
}
else {
_alloc_node.destroy(ptr);
_alloc_node.deallocate(ptr, sizeof(Node));
toReturnPair.second = false;
}
toReturnPair.first = iterator(to_return, &_mapTree);
return (toReturnPair);
}
Node* getLowest(Node* node) {
Node* ptr = node;
if (ptr)
while (ptr->left != NULL)
ptr = ptr->left;
return ptr;
}
Node* getHighest(Node* node) {
Node* ptr = node;
if (ptr)
while (ptr->right != NULL)
ptr = ptr->right;
return ptr;
}
void setColor(Node* node, int color) {
if (node == NULL)
return;
node->color = color;
}
void rotateLeft(Node* n)
{
if (!n || !n->right) {
std::cout << "il n'y a pas de fils droit from(leftrotate)\n";
return ;
}
n->right->parent = n->parent;
if (n->parent == NULL)
_mapTree = n->right;
else if (n->parent->right == n)
n->parent->right = n->right;
else
n->parent->left = n->right;
n->parent = n->right;
if (n->right && n->right->left)
n->right->left->parent = n;
if (n->right)
n->right = n->right->left;
n->parent->left = n;
}
void rotateRight(Node* n)
{
if (!n | !n->left) {
std::cout << "il n'y a pas de fils gauche from(rightrotate)\n";
return ;
}
n->left->parent = n->parent;
if (n->parent == NULL)
_mapTree = n->left;
else if (n->parent->right == n)
n->parent->right = n->left;
else
n->parent->left = n->left;
n->parent = n->left;
if (n->left && n->left->right)
n->left->right->parent = n;
if (n->left)
n->left = n->left->right;
n->parent->right = n;
return ;
}
void fixInsertRBTree(Node* ptr) {
Node *parent = NULL;
Node *grandparent = NULL;
while (ptr != _mapTree && getColor(ptr) == E_RED && getColor(ptr->parent) == E_RED) {
parent = ptr->parent;
grandparent = parent->parent;
if (parent == grandparent->left) {
Node *uncle = grandparent->right;
if (getColor(uncle) == E_RED) {
setColor(uncle, E_BLACK);
setColor(parent, E_BLACK);
setColor(grandparent, E_RED);
ptr = grandparent;
} else {
if (ptr == parent->right) {
rotateLeft(parent);
ptr = parent;
parent = ptr->parent;
}
rotateRight(grandparent);
std::swap(parent->color, grandparent->color);
ptr = parent;
}
} else {
Node *uncle = grandparent->left;
if (getColor(uncle) == E_RED) {
setColor(uncle, E_BLACK);
setColor(parent, E_BLACK);
setColor(grandparent, E_RED);
ptr = grandparent;
} else {
if (ptr == parent->left) {
rotateRight(parent);
ptr = parent;
parent = ptr->parent;
}
rotateLeft(grandparent);
std::swap(parent->color, grandparent->color);
ptr = parent;
}
}
}
setColor(_mapTree, E_BLACK);
}
void fixDeleteRBTree(Node *&node) {
if (node == NULL)
return;
if (node == _mapTree) {
if (!node->left && !node->right)
{
delete(_mapTree);
_mapTree = NULL;
}
else if (!node->left)
{
Node *child_right = node->right;
child_right->parent = NULL;
delete(_mapTree);
_mapTree = child_right;
setColor(_mapTree, E_BLACK);
}
else if (!node->right) {
Node *child_left = node->left;
child_left->parent = NULL;
delete(_mapTree);
_mapTree = child_left;
setColor(_mapTree, E_BLACK);
}
}
if (getColor(node) == E_RED || getColor(node->left) == E_RED || getColor(node->right) == E_RED) {
Node *child = node->left != NULL ? node->left : node->right;
if (node == node->parent->left) {
node->parent->left = child;
if (child != NULL)
child->parent = node->parent;
setColor(child, E_BLACK);
delete (node);
} else {
node->parent->right = child;
if (child != NULL)
child->parent = node->parent;
setColor(child, E_BLACK);
delete (node);
}
} else {
Node *sibling = NULL;
Node *parent = NULL;
Node *ptr = node;
setColor(ptr, E_DOUBLE_BLACK);
while (ptr != _mapTree && getColor(ptr) == E_DOUBLE_BLACK) {
parent = ptr->parent;
if (ptr == parent->left) {
sibling = parent->right;
if (getColor(sibling) == E_RED) {
setColor(sibling, E_BLACK);
setColor(parent, E_RED);
rotateLeft(parent);
} else {
if (getColor(sibling->left) == E_BLACK && getColor(sibling->right) == E_BLACK) {
setColor(sibling, E_RED);
if(getColor(parent) == E_RED)
setColor(parent, E_BLACK);
else
setColor(parent, E_DOUBLE_BLACK);
ptr = parent;
} else {
if (getColor(sibling->right) == E_BLACK) {
setColor(sibling->left, E_BLACK);
setColor(sibling, E_RED);
rotateRight(sibling);
sibling = parent->right;
}
setColor(sibling, parent->color);
setColor(parent, E_BLACK);
setColor(sibling->right, E_BLACK);
rotateLeft(parent);
break;
}
}
} else {
sibling = parent->left;
if (getColor(sibling) == E_RED) {
setColor(sibling, E_BLACK);
setColor(parent, E_RED);
rotateRight(parent);
} else {
if (getColor(sibling->left) == E_BLACK && getColor(sibling->right) == E_BLACK) {
setColor(sibling, E_RED);
if (getColor(parent) == E_RED)
setColor(parent, E_BLACK);
else
setColor(parent, E_DOUBLE_BLACK);
ptr = parent;
} else {
if (getColor(sibling->left) == E_BLACK) {
setColor(sibling->right, E_BLACK);
setColor(sibling, E_RED);
rotateLeft(sibling);
sibling = parent->left;
}
setColor(sibling, parent->color);
setColor(parent, E_BLACK);
setColor(sibling->left, E_BLACK);
rotateRight(parent);
break;
}
}
}
}
if (node == node->parent->left)
node->parent->left = NULL;
else
node->parent->right = NULL;
delete(node);
setColor(_mapTree, E_BLACK);
}
}
Node* deleteBST(Node *node, const key_type& val) {
if (node == NULL)
return node;
if (val < node->myPair.first)
return deleteBST(node->left, val);
if (val > node->myPair.first)
return deleteBST(node->right, val);
if (node->left == NULL || node->right == NULL)
return node;
Node *temp = getLowest(node->right);
_allocTp.construct(&node->myPair, temp->myPair);
return deleteBST(node->right, temp->myPair.first);
}
void deleteValue(const key_type& val) {
Node *node;
if ((node = deleteBST(_mapTree, val)))
--_size;
fixDeleteRBTree(node);
}
void deleteTree(Node *ptr)
{
if (ptr)
{
deleteTree(ptr->left);
deleteTree(ptr->right);
delete ptr;
}
}
int getColor(Node *&node) {
if (node == NULL)
return E_BLACK;
return (node->color);
}
Node *getRoot(Node *n)
{
while ( n->parent )
n = n->parent;
return n;
}
};
template<typename Key, typename T>
std::ostream& operator <<(std::ostream &o, ft::map<Key, T> &x) { o << x.getStr() << std::endl; return o;}
}
#endif