ft_containers/incs/map.hpp

/* ************************************************************************** */
/*                                                                            */
/*                                                        :::      ::::::::   */
/*   map.hpp                                            :+:      :+:    :+:   */
/*                                                    +:+ +:+         +:+     */
/*   By: paulohl <pohl@student.42.fr>               +#+  +:+       +#+        */
/*                                                +#+#+#+#+#+   +#+           */
/*   Created: 2021/11/18 11:05:42 by paulohl           #+#    #+#             */
/*   Updated: 2022/01/19 14:55:51 by pohl             ###   ########.fr       */
/*                                                                            */
/* ************************************************************************** */

#ifndef MAP_HPP
# define MAP_HPP


#include <unistd.h>


# include <fstream>
# include "Node.hpp"
# include "map_iterator.hpp"
# include "map_reverse_iterator.hpp"
# include "pair.hpp"

namespace ft
{

template< typename Key, typename T, typename Cmp = std::less<Key>,
	typename Allocator = std::allocator<pair<const Key, T> > >
class map
{

// Member types
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<Key, T, Cmp>				iterator;
	typedef const_map_iterator<Key, T, Cmp>			const_iterator;
	typedef map_reverse_iterator<Key, T, Cmp>		reverse_iterator;
	typedef map_reverse_iterator<Key, T, Cmp>		const_reverse_iterator;

private:

	typedef Node<Key, T, Cmp>	node;

// Member class
public:

	class value_compare
	{

	public:

		typedef bool		result_type;
		typedef value_type	first_argument_type;
		typedef value_type	second_argument_type;

	protected:

		Cmp	comp;

		value_compare( Cmp c ): comp(c) { return ; }

	public:

		bool operator()( const value_type& lhs, const value_type& rhs ) const
		{
			return comp(lhs, rhs);
		}

	};

public:

	// Default constructor
	explicit map( const key_compare &cmp = key_compare(),
			const Allocator &alloc = Allocator() ):
		_root(NULL), _comparator(cmp), _pairAlloc(alloc), _size(0)
	{
		return ;
	}
	// Iterator constructor
	template< class InputIt >
	map( InputIt first, InputIt last,
			const Cmp& cmp = Cmp(),
			const Allocator& alloc = Allocator() ):
		_root(NULL), _comparator(cmp), _pairAlloc(alloc), _size(0)
	{
		pair<Key, T> pair;
		while (first != last)
		{
			pair = *first;
			this->insert(*first);
			first++;
		}
		return ;
	}
	// Copy constructor
	map( const map& other ): _root(NULL)
	{
		*this = other;
	}
	// Destructor
	~map( void )
	{
		return ;
	}

	// Assignation operator
	map	&operator=( const map &rhs )
	{
		this->_pairAlloc = rhs._pairAlloc;
		this->_comparator = rhs._comparator;
		this->clear();
		this->_size = rhs._size;
		this->_root = rhs._root->clone();
		return *this;
	}

	allocator_type	get_pairAlloc( void ) const { return _pairAlloc; }

	// Element access
	mapped_type			&at( const key_type &key )
	{
		return *this[key];
	}
	const mapped_type	&at( const key_type &key ) const
	{
		return *this[key];
	}
	mapped_type			&operator[]( const key_type &key )
	{
		value_type	tmp = ft::make_pair(key, mapped_type());

		return (this->insert(tmp).first)->second;
	}

	// Iterator operations
	iterator				begin( void )
	{
		node	*begin_node = _root->minimum();

		if (begin_node)
			return iterator(begin_node);
		return iterator(NULL, true);
	}
	const_iterator			begin( void ) const
	{
		node	*begin_node = _root->minimum();

		if (begin_node)
			return const_iterator(begin_node);
		return const_iterator(NULL, true);
	}
	iterator				end( void )
	{
		return iterator(_root->maximum(), true);
	}
	const_iterator			end( void ) const
	{
		return const_iterator(_root->maximum(), true);
	}
	reverse_iterator		rbegin( void )
	{
		return reverse_iterator(_root->minimum());
	}
	const_reverse_iterator	rbegin( void ) const
	{
		return const_reverse_iterator(_root->minimum());
	}
	reverse_iterator		rend( void )
	{
		return reverse_iterator(_root->maximum(), true);
	}
	const_reverse_iterator	rend( void ) const
	{
		return const_reverse_iterator(_root->maximum(), true);
	}

	// Capacity
	bool		empty( void ) const { return _size == 0; }
	size_type	size( void ) const { return _size; }
	size_type	max_size( void ) const { return _nodeAlloc.max_size(); }

	// Modifiers
	void						clear ( void )
	{
		if (this->_root)
			this->_root->clear();
		this->_root = NULL;
		this->_size = 0;
	}
	pair<iterator, bool>	insert( const value_type &value )
	{
		node	*newNode = _nodeAlloc.allocate(1);
		node	*insertedPlace = NULL;

		newNode->assign(node(value));
		insertedPlace = insertNode(newNode, _root);
		this->printTree();
		if (newNode == insertedPlace)
		{
			this->_size++;
			return ft::make_pair(iterator(insertedPlace), true);
		}
		_nodeAlloc.deallocate(newNode, 1);
		return ft::make_pair(iterator(insertedPlace), false);
	}
	iterator					insert( iterator hint, const value_type &value);
	template< typename InputIt >
	void						insert( InputIt first, InputIt last )
	{
		while (first != last)
		{
			this->insert(*first);
			first++;
		}
	}
	void						erase( iterator pos )
	{
		node	*to_delete = pos.getNode();
		node	*tmp;

		if (to_delete->getLeftChild() == NULL)
			transplant(to_delete, to_delete->getRightChild());
		else if (to_delete->getRightChild() == NULL)
			transplant(to_delete, to_delete->getLeftChild());
		else
		{
			tmp = to_delete->minimum();
			if (tmp->getParent() != to_delete)
			{
				transplant(tmp, tmp->getRightChild());
				tmp->setRightChild(to_delete->getRightChild());
				tmp->getRightChild()->setParent(tmp);
			}
			transplant(to_delete, tmp);
			if (tmp != to_delete->getLeftChild())
			{
				tmp->setLeftChild(to_delete->getLeftChild());
				tmp->getLeftChild()->setParent(tmp);
			}
			if (tmp != to_delete->getRightChild())
			{
				tmp->setRightChild(to_delete->getRightChild());
				tmp->getRightChild()->setParent(tmp);
			}
		}
		tmp = to_delete->getParent();
		_pairAlloc.destroy(&to_delete->getPair());
		_nodeAlloc.deallocate(to_delete, 1);
		to_delete = NULL;
		this->_size--;
		while (tmp)
		{
			correctInbalance(tmp);
			tmp = tmp->getParent();
		}
	}
	void						erase( iterator first, iterator last )
	{
		while (first != last)
		{
			/* std::cout << "To delete: " << first->first << std::endl; */
			this->erase(first++);
			/* printTree(); */
			/* read(0, NULL, 2); */
		}
	}
	size_type					erase( const key_type &key )
	{
		iterator	to_erase = find(key);

		if (to_erase == this->end())
			return (0);
		erase(to_erase);
		return (1);
	}
	void						swap( map &other )
	{
		node			tmp_root = other._root;
		key_compare		tmp_comparator = other._comparator;
		allocator_type	tmp_pairAlloc = other._pairAlloc;
		size_type		tmp_size = other._size;

		other._root = this->_root;
		other._comparator = this->_comparator;
		other._pairAlloc = this->_pairAlloc;
		other._size = this->_size;
		this->_root = tmp_root;
		this->_comparator = tmp_comparator;
		this->_pairAlloc = tmp_pairAlloc;
		this->_size = tmp_size;
	}

	// Lookup
	size_type		count( const key_type &key )
	{
		return find(key) == end() ? 0 : 1;
	}
	iterator		find( const key_type &key )
	{
		node *tmp = findNode(key);
		if (!tmp)
			return iterator(this->maximum(), true);
		else
			return iterator(tmp);
	}
	const_iterator	find( const key_type &key ) const
	{
		node *tmp = findNode(key);
		if (!tmp)
			return iterator(this->maximum(), true);
		else
			return iterator(tmp);
	}
	pair<iterator, iterator>	equal_range( const key_type &key )
	{
		return ft::make_pair(lower_bound(key), upper_bound(key));
	}
	pair<const_iterator, const_iterator>	equal_range( const key_type &key ) const
	{
		return ft::make_pair(lower_bound(key), upper_bound(key));
	}
	iterator		lower_bound( const key_type &key )
	{
		node	*lower_bound_node = _root->lower_bound(key);

		if (lower_bound_node)
			return iterator(lower_bound_node);
		return iterator(lower_bound_node, true);
	}
	const_iterator	lower_bound( const key_type &key ) const
	{
		node	*lower_bound_node = _root->lower_bound(key);

		if (lower_bound_node)
			return const_iterator(lower_bound_node);
		return const_iterator(lower_bound_node, true);
	}
	iterator		upper_bound( const key_type &key )
	{
		node	*upper_bound_node = _root->upper_bound(key);

		if (upper_bound_node)
			return iterator(upper_bound_node);
		return iterator(upper_bound_node, true);
	}
	const_iterator	upper_bound( const key_type &key ) const
	{
		node	*upper_bound_node = _root->upper_bound(key);

		if (upper_bound_node)
			return const_iterator(upper_bound_node);
		return const_iterator(upper_bound_node, true);
	}

	// Observers
	key_compare		key_comp( void ) const { return _comparator; }
	value_compare	value_comp( void ) const { return value_compare(); }

	// Non-member functions
	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 != *rhs_it)
				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 != *rhs_it)
				return *lhs_it < *rhs_it;
			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);
	}

	// Debug
	void	printTree( void ) const
	{
		std::ofstream	myfile;

		myfile.open("tree_visualisation.mmd", std::ios::out);
		myfile << "flowchart TD" << std::endl;
		if (_root)
			traverseTree(this->_root, myfile);
		else
			myfile << "Empty tree" << std::endl;
		myfile.close();
		/* std::cout << "Printed tree in ./tree_visualisation.mmd" << std::endl; */
	}

private:

	node	*findNode( const key_type &key )
	{
		node	*result = _root;

		while (result && result->getKey() != key)
		{
			if (_comparator(key, result->getKey()))
				result = result->getLeftChild();
			else
				result = result->getRightChild();
		}
		return result;
	}
	node	*insertNode( node *to_insert, node *current_node = NULL )
	{
		if (!to_insert)
			return NULL;
		if (!_root)
		{
			_root = to_insert;
			return _root;
		}
		if (!current_node)
			current_node = _root;
		if (_comparator(to_insert->getKey(), current_node->getKey()))
		{
			if (current_node->getLeftChild())
				current_node = insertNode(to_insert, current_node->getLeftChild());
			else
				current_node = current_node->insertChild(to_insert, map::left);
		}
		else if (_comparator(current_node->getKey(), to_insert->getKey()))
		{
			if (current_node->getRightChild())
				current_node = insertNode(to_insert, current_node->getRightChild());
			else
				current_node = current_node->insertChild(to_insert, map::right);
		}
		correctInbalance(current_node);
		return current_node;
	}
	void	correctInbalance( node *node )
	{
		this->printTree();
		int	inbalance = node->getBalance();
		int	side;

		if (inbalance > 1 || inbalance < -1)
		{
			side = inbalance < 0 ? map::left : map::right;
			if ((inbalance ^ node->getChild(side)->getBalance()) < 0) // are this node and its child the same sign
				rotate(node->getChild(side), side);
			rotate(node, 1 - side);
		}
		if (node->getParent())
			correctInbalance(node->getParent());
	}
	void	rotate( node *hinge, int	side )
	{
		node	*other = hinge->getChild(1 - side);

		hinge->setChild(other->getChild(side), 1 - side);
		if (other->getChild(side))
			other->getChild(side)->setParent(hinge);
		other->setParent(hinge->getParent());
		if (hinge->getParent() == NULL)
			_root = other;
		else if (hinge->getParent()->getLeftChild() == hinge)
			hinge->getParent()->setLeftChild(other);
		else
			hinge->getParent()->setRightChild(other);
		other->setChild(hinge, side);
		hinge->setParent(other);
	}
	void	transplant( node *original, node *replacement )
	{
		if (original->getParent() == NULL)
			this->_root = replacement;
		else if (original == original->getParent()->getLeftChild())
			original->getParent()->setLeftChild(replacement);
		else
			original->getParent()->setRightChild(replacement);
		if (replacement != NULL)
			replacement->setParent(original->getParent());
	}
	void	traverseTree( node *node, std::ofstream &file) const
	{
		file << node << "(" << node->getKey() << " - " << node->getBalance() << ")" << std::endl;
		if (node->getParent())
			file << node << "-->" << node->getParent() << std::endl;
		if (node->getLeftChild())
		{
			file << node << "-.->" << node->getLeftChild() << std::endl;
			traverseTree(node->getLeftChild(), file);
		}
		if (node->getRightChild())
		{
			file << node << "==>" << node->getRightChild() << std::endl;
			traverseTree(node->getRightChild(), file);
		}
	}

private:

	node					*_root;
	key_compare				_comparator;
	allocator_type			_pairAlloc;
	size_type				_size;
	std::allocator<node>	_nodeAlloc;

	const static int	right = 0;
	const static int	left = 1;

};

}

#endif