libs/flyweight/example/composite.cpp
/* Boost.Flyweight example of a composite design.
*
* Copyright 2006-2014 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 flyweight nodes, we combine their corresponding
* hash values. As hashing a flyweight does not involve actually hashing
* its pointed-to value, the resulting computation does not recursively
* descend down 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){
boost::hash_combine(res,*it);
}
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;
}