/* Boost.Flyweight example of a composite design.
 *
 * Copyright 2006-2010 Joaquin M Lopez Munoz.
 * Distributed under the Boost Software License, Version 1.0.
 * (See accompanying file LICENSE_1_0.txt or copy at
 * http://www.boost.org/LICENSE_1_0.txt)
 *
 * See http://www.boost.org/libs/flyweight for library home page.
 */

#include <boost/flyweight.hpp>
#include <boost/functional/hash.hpp>
#include <boost/tokenizer.hpp>
#include <boost/variant.hpp>
#include <boost/variant/apply_visitor.hpp>
#include <boost/variant/recursive_wrapper.hpp>
#include <iostream>
#include <stdexcept>
#include <string>
#include <vector>

using namespace boost::flyweights;

/* A node of a lisp-like list can be modeled as a boost::variant of
 *   1. A string (primitive node)
 *   2. A vector of nodes (embedded list)
 * To save space, 2 is stored as a vector of flyweights.
 * As is usual with recursive data structures, a node can be thought
 * of also as a list. To close the flyweight circle, the final
 * type list is a flyweight wrapper, so that the final structure can
 * be described as follows in BNF-like style:
 *
 *   list      ::= flyweight<list_impl>
 *   list_impl ::= std::string | std::vector<list>
 */

struct list_elems;

typedef boost::variant<
  std::string,
  boost::recursive_wrapper<list_elems>  
> list_impl;

struct list_elems:std::vector<flyweight<list_impl> >{};

typedef flyweight<list_impl> list;

/* list_impl must be hashable to be used by flyweight: If a
 * node is a std::string, its hash resolves to that of the string;
 * if it is a vector of nodes, we compute the hash by combining
 * the *addresses* of the stored flyweights' associated values: this is
 * consistent because flyweight equality implies equality of reference.
 * Using this trick instead of hashing the node values themselves
 * allow us to do the computation without recursively descending down
 * through the entire data structure.
 */

struct list_hasher:boost::static_visitor<std::size_t>
{
  std::size_t operator()(const std::string& str)const
  {
    boost::hash<std::string> h;
    return h(str);
  }

  std::size_t operator()(const list_elems& elms)const
  {
    std::size_t res=0;
    for(list_elems::const_iterator it=elms.begin(),it_end=elms.end();
        it!=it_end;++it){
      const list_impl* p=&it->get();
      boost::hash_combine(res,p);
    }
    return res;
  }
};

#if defined(BOOST_NO_ARGUMENT_DEPENDENT_LOOKUP)
namespace boost{
#endif

std::size_t hash_value(const list_impl& limpl)
{
  return boost::apply_visitor(list_hasher(),limpl);
}

#if defined(BOOST_NO_ARGUMENT_DEPENDENT_LOOKUP)
} /* namespace boost */
#endif

/* basic pretty printer with indentation according to the nesting level */

struct list_pretty_printer:boost::static_visitor<>
{
  list_pretty_printer():nest(0){}

  void operator()(const std::string& str)
  {
    indent();
    std::cout<<str<<"\n";
  }

  void operator()(const boost::recursive_wrapper<list_elems>& elmsw)
  {
    indent();
    std::cout<<"(\n";
    ++nest;
    const list_elems& elms=elmsw.get();
    for(list_elems::const_iterator it=elms.begin(),it_end=elms.end();
        it!=it_end;++it){
      boost::apply_visitor(*this,it->get());
    }
    --nest;
    indent();
    std::cout<<")\n";
  }

private:
  void indent()const
  {
    for(int i=nest;i--;)std::cout<<"  ";
  }

  int nest;
};

void pretty_print(const list& l)
{
  list_pretty_printer pp;
  boost::apply_visitor(pp,l.get());
}

/* list parser */

template<typename InputIterator>
list parse_list(InputIterator& first,InputIterator last,int nest)
{
  list_elems elms;
  while(first!=last){
    std::string str=*first++;
    if(str=="("){
      elms.push_back(parse_list(first,last,nest+1));   
    }
    else if(str==")"){
      if(nest==0)throw std::runtime_error("unmatched )");
      return list(elms);
    }
    else{
      elms.push_back(list(str)); 
    }
  }
  if(nest!=0)throw std::runtime_error("unmatched (");
  return list(elms);
}

list parse_list(const std::string str)
{
  typedef boost::tokenizer<boost::char_separator<char> > tokenizer;
  tokenizer tok(str,boost::char_separator<char>(" ","()"));
  tokenizer::iterator begin=tok.begin();
  return parse_list(begin,tok.end(),0);
}

int main()
{
  std::cout<<"enter list: ";
  std::string str;
  std::getline(std::cin,str);
  try{
    pretty_print(parse_list(str));
  }
  catch(const std::exception& e){
    std::cout<<"error: "<<e.what()<<"\n";
  }

  return 0;
}