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 <extensions/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 trie
 */
template < class Key, class Value >
class trie {
	/**
	 * \brief
	 * The value in the root node of the trie
	 */
	Value m_data;

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

	/**
	 * \brief
	 * Container of children of the root node of the trie.
	 *
	 * 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;

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

	/**
	 * \brief
	 * Inserts a subtrie into a trie.
	 *
	 * \param key the associating key for the inserted subtrie
	 * \param value a subtrie to insert
	 *
	 * \return updated position iterator pointing to the first node inserted
	 */
	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;
	}

	/**
	 * \brief
	 * Inserts a subtrie into a trie.
	 *
	 * \param key the associating key for the inserted subtrie
	 * \param value a subtrie to insert
	 *
	 * \return updated position iterator pointing to the first node inserted
	 */
	const_children_iterator insert ( Key key, const trie < Key, Value > & value ) {
		return insert ( std::move ( key ), trie < Key, Value > ( value ) );
	}

	/**
	 * \brief
	 * Inserts subtries given by range of key-value pairs at specified position.
	 *
	 * \param begin the start of the range of subtries
	 * \param end the end of the range of subtries
	 */
	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;
	}

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

	/**
	 * \brief
	 * Constructor of the trie from value to be stored in the root node and children tries.
	 *
	 * \param data the value to be stored in the root
	 * \param children map of subtries
	 */
	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;
	}

	/**
	 * \brief
	 * Constructor of the trie from value to be stored in the root node and children tries.
	 *
	 * \param data the value to be stored in the root
	 * \param children map of subtries
	 */
	trie ( const Value & data, const ext::map < Key, trie > & subtries ) : trie ( Value ( data ), ext::map < Key, trie > ( subtries ) ) {
	}

	/**
	 * \brief
	 * Constructor of the trie from value to be stored in the root node and pack of children tries.
	 *
	 * \tparam Types ... pack of types convertible to trie
	 *
	 * \param data the value to be stored in the root
	 * \param subtries ... pack of subtries
	 */
	template < typename ... Types >
	trie ( const Value & data, Types ... subtries ) : trie ( data, ext::map < Key, trie > { subtries ... } ) {
	}

	/**
	 * \brief
	 * Constructor of the trie from value to be stored in the root node and pack of children tries.
	 *
	 * \tparam Types ... pack of types convertible to trie
	 *
	 * \param data the value to be stored in the root
	 * \param subtries ... pack of subtries
	 */
	template < typename ... Types >
	trie ( Value && data, Types ... subtries ) : trie ( std::move ( data ), ext::map < Key, trie > { subtries ... } ) {
	}

	/**
	 * \brief
	 * Constructor of the trie from value to be stored in the root node and range of key-value pairs to construct nullary nodes.
	 *
	 * \param data the value to be stored in the root
	 * \param begin the iterator to the begining of key-value pairs range
	 * \param end the iterator to the end of key-value pairs range
	 */
	trie ( const Value & data, const_children_iterator begin, const_children_iterator end ) : trie ( data, ext::map < Key, trie > ( begin, end ) ) {
	}

	/**
	 * \brief
	 * Dectructor of the trie
	 */
	~trie ( ) noexcept {
	}

	/**
	 * \brief
	 * Copy constructor of the trie.
	 *
	 * \param other the other instace of the trie
	 */
	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;
	}

	/**
	 * \brief
	 * Move constructor of the trie.
	 *
	 * \param other the other instace of the trie
	 */
	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;
	}

	/**
	 * \brief
	 * Copy operator of assignment of the trie.
	 *
	 * \param other the other instace of the trie
	 *
	 * \return the assigned to instance
	 */
	trie & operator =( const trie & node ) {
		return this->operator =( trie ( node ) );
	}

	/**
	 * \brief
	 * Move operator of assignment of the trie.
	 *
	 * \param other the other instace of the trie
	 *
	 * \return the assigned to instance
	 */
	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;
	}

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

	/**
	 * \brief
	 * Getter of a children iterator to the begining of children
	 *
	 * \return iterator to the first child
	 */
	const_children_iterator begin ( ) const {
		return m_children.begin ( );
	}

	/**
	 * \brief
	 * Getter of a children iterator to the begining of children
	 *
	 * \return iterator to the first child
	 */
	children_iterator begin ( ) {
		return m_children.begin ( );
	}

	/**
	 * \brief
	 * Getter of a children iterator one after the last child
	 *
	 * \return iterator one after the last child
	 */
	const_children_iterator end ( ) const {
		return m_children.end ( );
	}

	/**
	 * \brief
	 * Getter of a children iterator one after the last child
	 *
	 * \return iterator one after the last child
	 */
	children_iterator end ( ) {
		return m_children.end ( );
	}

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

	/**
	 * \brief
	 * Erases a subtrie from a trie on given by \p position
	 *
	 * \param position the specification of position in children where to erase the subtrie
	 */
	children_iterator erase ( const_children_iterator position ) {
		ext::map < Key, trie > & children = const_cast < ext::map < Key, trie > & > ( getChildren ( ) );

		return children.erase ( position );
	}

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

	/**
	 * \brief
	 * Access value given indexes to chindren allong the selection path.
	 *
	 * \tparam Indexes ... types of child keys
	 *
	 * \param indexes actual keys
	 *
	 * \return the value in the selected node
	 */
	template < class ... Indexes >
	const Value & operator ()( Indexes ... indexes ) const {
		return this->operator ()( { ( Key ) indexes ... } );
	}

	/**
	 * \brief
	 * Access value given key to chindren allong the selection path.
	 *
	 * \param indexes list of actual keys
	 *
	 * \return the value in the selected node
	 */
	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 ( );
	}

	/**
	 * \brief
	 * Access value given indexes to chindren allong the selection path.
	 *
	 * \tparam Indexes ... types of child keys
	 *
	 * \param indexes actual keys
	 *
	 * \return the value in the selected node
	 */
	template < class ... Indexes >
	Value & operator ()( Indexes ... indexes ) {
		return this->operator ()( { ( Key ) indexes ... } );
	}

	/**
	 * \brief
	 * Access value given key to chindren allong the selection path.
	 *
	 * \param indexes list of actual keys
	 *
	 * \return the value in the selected node
	 */
	Value & operator ()( std::initializer_list < Key > indexes ) {
		trie * node = this;

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

		return node->getData ( );
	}

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

	/**
	 * \brief
	 * Helper method to traverse the trie and check all parent references are set correctly.
	 *
	 * \param node the node to test
	 *
	 * \return true if the parent child relationship of nodes is sound
	 */
	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;
	}

	/**
	 * \brief
	 * Helper method to traverse the trie and check all parent references are set correctly. Starts at root node and recursively tests all its child nodes.
	 *
	 * \param node the node to test
	 *
	 * \return true if the parent child relationship of nodes is sound
	 */
	bool checkStructure ( ) const {
		return m_parent == nullptr && checkStructure ( * this );
	}

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

	/**
	 * \brief
	 * Swap method of two tries
	 *
	 * \param first the first forward trie to swap
	 * \param second the second forward trie to swap
	 */
	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 );
	}

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

	/**
	 * \brief
	 * Three-way comparison method of forward tries.
	 *
	 * \param other the other instance to compare against
	 *
	 * \return negative if this instance is smaller than \p other instance
	 *         zero if this is equal to \p other instance
	 *         positive if this instance is bigger than \p other instance
	 */
	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 );
	}

	/**
	 * \brief
	 * Equality comparison operator.
	 *
	 * \param other the other instance to compare with
	 *
	 * \return true if this instance is equal to other instance, false othervise
	 */
	bool operator ==( const trie & other ) const {
		return compare ( other ) == 0;
	}

	/**
	 * \brief
	 * Non-equality comparison operator.
	 *
	 * \param other the other instance to compare with
	 *
	 * \return true if this instance is not equal to other instance, false othervise
	 */
	bool operator !=( const trie & other ) const {
		return compare ( other ) != 0;
	}

	/**
	 * \brief
	 * Less comparison operator.
	 *
	 * \param other the other instance to compare with
	 *
	 * \return true if this instance is smaller than other instance, false othervise
	 */
	bool operator <( const trie & other ) const {
		return compare ( other ) < 0;
	}

	/**
	 * \brief
	 * Less or equal comparison operator.
	 *
	 * \param other the other instance to compare with
	 *
	 * \return true if this instance is smaller or equal than other instance, false othervise
	 */
	bool operator <=( const trie & other ) const {
		return compare ( other ) <= 0;
	}

	/**
	 * \brief
	 * Greater comparison operator.
	 *
	 * \param other the other instance to compare with
	 *
	 * \return true if this instance is greater than other instance, false othervise
	 */
	bool operator >( const trie & other ) const {
		return compare ( other ) > 0;
	}

	/**
	 * \brief
	 * Greater or equal comparison operator.
	 *
	 * \param other the other instance to compare with
	 *
	 * \return true if this instance is greater or equal than other instance, false othervise
	 */
	bool operator >=( const trie & other ) const {
		return compare ( other ) >= 0;
	}

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

	/**
	 * \brief
	 * Internal method of printing a trie into a stream
	 *
	 * The trie is printed hierarchically. Key-value pair components are printed separated by colon.
	 *
	 * Example trie a ( k:b ( m:c ), l:b ( n:c ) ) would be printed like
	 *
	 * \-a
	 *   |
	 *   |-k:b
	 *   | |
	 *   | \-m:c
	 *   |
	 *   \-l:b
	 *     |
	 *     \-n:c
	 *
	 * \param os the stream to print to
	 *
	 * \return the changed output stream
	 */
	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:
	/**
	 * \brief
	 * Method of printing a trie into a stream
	 *
	 * The trie is printed hierarchically. Key-value pair components are printed separated by colon.
	 *
	 * Example trie a ( k:b ( m:c ), l:b ( n:c ) ) would be printed like
	 *
	 * \-a
	 *   |
	 *   |-k:b
	 *   | |
	 *   | \-m:c
	 *   |
	 *   \-l:b
	 *     |
	 *     \-n:c
	 *
	 * \param os the stream to print to
	 *
	 * \return the changed output stream
	 */
	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;
		}
	}

};

/**
 * \brief
 * Operator to print the trie to the output stream.
 *
 * \param out the output stream
 * \param trie the trie to print
 *
 * \tparam T the type of values inside the trie
 *
 * \return the output stream from the \p out
 */
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;
}

/**
 * \brief
 * Specialisation of the compare structure implementing the three-way comparison.
 *
 * \tparam T the type of values inside the trie
 */
template < class Key, class Value >
struct compare < ext::trie < Key, Value > > {

	/**
	 * \brief
	 * Implementation of the three-way comparison.
	 *
	 * \param first the left operand of the comparison
	 * \param second the right operand of the comparison
	 *
	 * \return negative value of left < right, positive value if left > right, zero if left == right
	 */
	int operator ()( const ext::trie < Key, Value > & first, const ext::trie < Key, Value > & second ) const {
		return first.compare ( second );
	}

};

/**
 * \brief
 * Overload of to_string function.
 *
 * \param value the trie to be converted to string
 *
 * \tparam T the type of values inside the trie
 *
 * \return string representation
 */
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_ */