123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174 |
- /* 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;
- }
|