trie.hpp

/*
 * trie.hpp
 *
 * This file is part of Algorithms library toolkit.
 * Copyright (C) 2017 Jan Travnicek (jan.travnicek@fit.cvut.cz)

 * Algorithms library toolkit is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.

 * Algorithms library toolkit is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.

 * You should have received a copy of the GNU General Public License
 * along with Algorithms library toolkit.  If not, see <http://www.gnu.org/licenses/>.
 *
 * Created on: Jul 2, 2016
 * Author: Jan Travnicek
 */

#ifndef __TRIE_HPP_
#define __TRIE_HPP_

#include <memory>
#include <iterator>
#include <sstream>
#include <string>

#include "compare.hpp"
#include "pair.hpp"
#include "tuple.hpp"
#include "map.hpp"

namespace ext {

/**
 * \brief
 * Class introducing a trie with interface trying to be close to the interface of standard library containers.
 *
 * The trie is a hierarchical structure of nodes with parent child relationship, where the children are accessible by their keys.
 *
 * \tparam T the type of values inside nodes of the tree
 */
template < class Key, class Value >
class trie {
	/**
	 * \brief
	 * The value in the root node of the tree
	 */
	Value m_data;

	/**
	 * \brief
	 * Pointer to the parent of the node. Null pointer for root of a tree.
	 */
	trie * m_parent;

	/**
	 * \brief
	 * Container of children of the root node of the tree.
	 *
	 * The children are tries themselves, hence the subtrie of a trie is itself a trie.
	 */
	ext::map < Key, trie > m_children;

public:
	/**
	 * \brief
	 * Getter of the parent node. Null if the node is root.
	 *
	 * \return pointer to the parent node
	 */
	trie * getParent ( ) {
		return m_parent;
	}

	/**
	 * \brief
	 * Getter of the parent node. Null if the node is root.
	 *
	 * \return pointer to the parent node
	 */
	const trie * getParent ( ) const {
		return m_parent;
	}

	/**
	 * \brief
	 * Getter of the value in the root node.
	 *
	 * \return the value in the root node
	 */
	Value & getData ( ) {
		return m_data;
	}

	/**
	 * \brief
	 * Getter of the value in the root node.
	 *
	 * \return the value in the root node
	 */
	const Value & getData ( ) const {
		return m_data;
	}

	/**
	 * \brief
	 * Getter of children of the root node.
	 *
	 * \return children of the root node
	 */
	ext::map < Key, trie > & getChildren ( ) {
		return m_children;
	}

	/**
	 * \brief
	 * Getter of children of the root node.
	 *
	 * \return children of the root node
	 */
	const ext::map < Key, trie > & getChildren ( ) const {
		return m_children;
	}

	/**
	 * \brief
	 * The iterator type over children of the node
	 */
	typedef typename ext::map < Key, trie >::iterator children_iterator;

	/**
	 * \brief
	 * The iterator type over children of the node
	 */
	typedef typename ext::map < Key, trie >::const_iterator const_children_iterator;

// ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

	const_children_iterator insert ( Key key, trie < Key, Value > && value ) {
		ext::map < Key, trie > & children = const_cast < ext::map < Key, trie > & > ( getChildren ( ) );

		typename ext::map < Key, trie >::iterator iter = children.insert ( std::move ( key ), std::move ( value ) ).first;
		iter->second.m_parent = this;
		return iter;
	}

	const_children_iterator insert ( Key key, const trie < Key, Value > & value ) {
		return insert ( std::move ( key ), trie < Key, Value > ( value ) );
	}

	void insert ( const_children_iterator begin, const_children_iterator end ) {
		ext::map < Key, trie > & children = const_cast < ext::map < Key, trie > & > ( getChildren ( ) );

		for ( ; begin != end; ++begin )
			children.insert ( * begin ).first->second.m_parent = this;
	}

// ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

	trie ( Value && data, ext::map < Key, trie > && children ) : m_data ( std::move ( data ) ), m_parent ( nullptr ), m_children ( std::move ( children ) ) {
		for ( std::pair < const Key, trie > & child : m_children )
			child.second.m_parent = this;
	}

	trie ( const Value & data, const ext::map < Key, trie > & subtrees ) : trie ( Value ( data ), ext::map < Key, trie > ( subtrees ) ) {
	}

	template < typename ... Types >
	trie ( const Value & data, Types ... subtrees ) : trie ( data, ext::map < Key, trie > { subtrees ... } ) {
	}

	template < typename ... Types >
	trie ( Value && data, Types ... subtrees ) : trie ( std::move ( data ), ext::map < Key, trie > { subtrees ... } ) {
	}

	trie ( const Value & data, const_children_iterator begin, const_children_iterator end ) : trie ( data, ext::map < Key, trie > ( begin, end ) ) {
	}

	~trie ( ) noexcept {
	}

	trie ( const trie & other ) : m_data ( other.m_data ), m_parent ( other.m_parent ), m_children ( other.m_children ) {
		for ( std::pair < const Key, trie > & child : m_children )
			child.second.m_parent = this;
	}

	trie ( trie && other ) noexcept : m_data ( std::move ( other.m_data ) ), m_parent ( other.m_parent ), m_children ( std::move ( other.m_children ) ) {
		for ( std::pair < const Key, trie > & child : m_children )
			child.second.m_parent = this;
	}

	trie & operator =( const trie & node ) {
		return this->operator =( trie ( node ) );
	}

	trie & operator =( trie && node ) noexcept {
		m_data = std::move ( node.m_data );
		m_children = std::move ( node.m_children );

		for ( std::pair < const Key, trie > & child : m_children )
			child.second.m_parent = this;

		return * this;
	}

// ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

	const_children_iterator begin ( ) const {
		return m_children.begin ( );
	}

	children_iterator begin ( ) {
		return m_children.begin ( );
	}

	const_children_iterator end ( ) const {
		return m_children.end ( );
	}

	children_iterator end ( ) {
		return m_children.end ( );
	}

// ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

	const_children_iterator erase ( const_children_iterator position ) {
		ext::map < Key, trie > & children = const_cast < ext::map < Key, trie > & > ( getChildren ( ) );

		return children.erase ( position );
	}

// ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

	template < class ... Indexes >
	const Value & operator ()( Indexes ... indexes ) const {
		return this->operator ()( { ( Key ) indexes ... } );
	}

	const Value & operator ()( std::initializer_list < Key > indexes ) const {
		const trie * node = this;

		for ( Key index : indexes ) {
			node = & node->getChildren ( ).find ( index )->second;
		}

		return node->getData ( );
	}

	template < class ... Indexes >
	Value & operator ()( Indexes ... indexes ) {
		return this->operator ()( { ( Key ) indexes ... } );
	}

	Value & operator ()( std::initializer_list < Key > indexes ) {
		trie * node = this;

		for ( Key index : indexes ) {
			node = & node->getChildren ( ).find ( index )->second;
		}

		return node->getData ( );
	}

// ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

	bool checkStructure ( const trie & node ) const {
		bool sign = true;

		for ( const std::pair < const Key, trie > & child : node.getChildren ( ) )
			sign &= child.second.getParent ( ) == & node && checkStructure ( child.second );

		return sign;
	}

	bool checkStructure ( ) const {
		return m_parent == nullptr && checkStructure ( * this );
	}

// ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

	friend void swap ( trie & first, trie & second ) {
		swap ( first.m_data, second.m_data );
		swap ( first.m_children, second.m_children );
		swap ( first.m_parent, second.m_parent );
	}

// ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

	int compare ( const trie & other ) const {
		auto first = ext::tie ( this->getData ( ), this->getChildren ( ) );
		auto second = ext::tie ( other.getData ( ), other.getChildren ( ) );

		static ext::compare < decltype ( first ) > comp;

		return comp ( first, second );
	}

	bool operator ==( const trie & other ) {
		return compare ( other ) == 0;
	}

	bool operator !=( const trie & other ) {
		return compare ( other ) != 0;
	}

	bool operator <( const trie & other ) {
		return compare ( other ) < 0;
	}

	bool operator <=( const trie & other ) {
		return compare ( other ) <= 0;
	}

	bool operator >( const trie & other ) {
		return compare ( other ) > 0;
	}

	bool operator >=( const trie & other ) {
		return compare ( other ) >= 0;
	}

// ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

	std::ostream & nicePrint ( std::ostream & os ) const {
		os << "\\-";
		std::string prefix ( "  " );

		os << getData ( ) << std::endl;

		unsigned int i = 0;
		for ( const std::pair < const Key, trie < Key, Value > > & subdata : getChildren ( ) ) {
			os << prefix << "|" << std::endl;
			nicePrint ( os, subdata, prefix, i == m_children.size ( ) - 1 );
			++i;
		}
		return os;
	}

private:
	static void nicePrint ( std::ostream & os, const std::pair < const Key, trie < Key, Value > > & data, std::string prefix, const bool last ) {
		os << prefix;

		if ( last ) {
			os << "\\-";
			prefix += "  ";
		} else {
			os << "|-";
			prefix += "| ";
		}

		os << data.first << ":" << data.second.getData ( ) << std::endl;

		unsigned int i = 0;
		for ( const std::pair < const Key, trie < Key, Value > > & subdata : data.second ) {
			os << prefix << "|" << std::endl;
			nicePrint ( os, subdata, prefix, i == data.second.m_children.size ( ) - 1 );
			++i;
		}
	}

};

template < class Key, class Value >
std::ostream & operator <<( std::ostream & out, const trie < Key, Value > & t ) {
	out << "[";

	out << t.getData ( ) << ";";

	for ( typename ext::map < Key, trie < Key, Value > >::const_iterator iter = t.getChildren ( ).begin ( ); iter != t.getChildren ( ).end ( ); ++ iter) {
		if ( iter != t.getChildren ( ).begin ( ) ) {
			out << ",";
		}

		out << iter->first << ":" << iter->second;
	}

	out << "]";
	return out;
}

template < class Key, class Value >
struct compare < ext::trie < Key, Value > > {
	int operator ()( const ext::trie < Key, Value > & first, const ext::trie < Key, Value > & second ) const {
		return first.compare ( second );
	}

};

template < class Key, class Value >
std::string to_string ( const ext::trie < Key, Value > & value ) {
	std::stringstream ss;
	ss << value;
	return ss.str();
}

} /* namespace ext */

#endif /* __TRIE_HPP_ */