trie.hpp

/*
 * bidirectional_tree.hpp
 *
 * 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 {

template < class Key, class Value >
class trie {
	Value m_data;

	trie * m_parent;
	ext::map < Key, trie > m_children;

public:
	trie * getParent ( ) {
		return m_parent;
	}

	const trie * getParent ( ) const {
		return m_parent;
	}

	Value & getData ( ) {
		return m_data;
	}

	const Value & getData ( ) const {
		return m_data;
	}

	ext::map < Key, trie > & getChildren ( ) {
		return m_children;
	}

	const ext::map < Key, trie > & getChildren ( ) const {
		return m_children;
	}

	typedef typename ext::map < Key, trie >::const_iterator const_children_iterator;
	typedef const trie * const_child_iterator;

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

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

		std::pair < typename ext::map < Key, trie >::iterator, bool > iter = children.insert ( std::move ( key ), std::move ( value ) );
		iter.first->second.m_parent = const_cast < trie * > ( & * under );
	}

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

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

		for ( ; begin != end; ++begin )
			children.insert ( * begin ).first->second.m_parent = const_cast < trie * > ( & * under );
	}

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

	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_child_iterator root ( ) const {
		return this;
	}

	const_child_iterator parent ( ) const {
		return this->getParent ( );
	}

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

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

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

	const_children_iterator erase ( const_child_iterator under, const_children_iterator position ) {
		ext::map < Key, trie > & children = const_cast < ext::map < Key, trie > & > ( under->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_ */