1 /* Boost.Flyweight example of a composite design.
2 *
3 * Copyright 2006-2014 Joaquin M Lopez Munoz.
4 * Distributed under the Boost Software License, Version 1.0.
5 * (See accompanying file LICENSE_1_0.txt or copy at
6 * http://www.boost.org/LICENSE_1_0.txt)
7 *
8 * See http://www.boost.org/libs/flyweight for library home page.
9 */
10
11 #include <boost/flyweight.hpp>
12 #include <boost/functional/hash.hpp>
13 #include <boost/tokenizer.hpp>
14 #include <boost/variant.hpp>
15 #include <boost/variant/apply_visitor.hpp>
16 #include <boost/variant/recursive_wrapper.hpp>
17 #include <iostream>
18 #include <stdexcept>
19 #include <string>
20 #include <vector>
21
22 using namespace boost::flyweights;
23
24 /* A node of a lisp-like list can be modeled as a boost::variant of
25 * 1. A string (primitive node)
26 * 2. A vector of nodes (embedded list)
27 * To save space, 2 is stored as a vector of flyweights.
28 * As is usual with recursive data structures, a node can be thought
29 * of also as a list. To close the flyweight circle, the final
30 * type list is a flyweight wrapper, so that the final structure can
31 * be described as follows in BNF-like style:
32 *
33 * list ::= flyweight<list_impl>
34 * list_impl ::= std::string | std::vector<list>
35 */
36
37 struct list_elems;
38
39 typedef boost::variant<
40 std::string,
41 boost::recursive_wrapper<list_elems>
42 > list_impl;
43
44 struct list_elems:std::vector<flyweight<list_impl> >{};
45
46 typedef flyweight<list_impl> list;
47
48 /* list_impl must be hashable to be used by flyweight: If a
49 * node is a std::string, its hash resolves to that of the string;
50 * if it is a vector of flyweight nodes, we combine their corresponding
51 * hash values. As hashing a flyweight does not involve actually hashing
52 * its pointed-to value, the resulting computation does not recursively
53 * descend down the entire data structure.
54 */
55
56 struct list_hasher:boost::static_visitor<std::size_t>
57 {
operator ()list_hasher58 std::size_t operator()(const std::string& str)const
59 {
60 boost::hash<std::string> h;
61 return h(str);
62 }
63
operator ()list_hasher64 std::size_t operator()(const list_elems& elms)const
65 {
66 std::size_t res=0;
67 for(list_elems::const_iterator it=elms.begin(),it_end=elms.end();
68 it!=it_end;++it){
69 boost::hash_combine(res,*it);
70 }
71 return res;
72 }
73 };
74
75 #if defined(BOOST_NO_ARGUMENT_DEPENDENT_LOOKUP)
76 namespace boost{
77 #endif
78
hash_value(const list_impl & limpl)79 std::size_t hash_value(const list_impl& limpl)
80 {
81 return boost::apply_visitor(list_hasher(),limpl);
82 }
83
84 #if defined(BOOST_NO_ARGUMENT_DEPENDENT_LOOKUP)
85 } /* namespace boost */
86 #endif
87
88 /* basic pretty printer with indentation according to the nesting level */
89
90 struct list_pretty_printer:boost::static_visitor<>
91 {
list_pretty_printerlist_pretty_printer92 list_pretty_printer():nest(0){}
93
operator ()list_pretty_printer94 void operator()(const std::string& str)
95 {
96 indent();
97 std::cout<<str<<"\n";
98 }
99
operator ()list_pretty_printer100 void operator()(const boost::recursive_wrapper<list_elems>& elmsw)
101 {
102 indent();
103 std::cout<<"(\n";
104 ++nest;
105 const list_elems& elms=elmsw.get();
106 for(list_elems::const_iterator it=elms.begin(),it_end=elms.end();
107 it!=it_end;++it){
108 boost::apply_visitor(*this,it->get());
109 }
110 --nest;
111 indent();
112 std::cout<<")\n";
113 }
114
115 private:
indentlist_pretty_printer116 void indent()const
117 {
118 for(int i=nest;i--;)std::cout<<" ";
119 }
120
121 int nest;
122 };
123
pretty_print(const list & l)124 void pretty_print(const list& l)
125 {
126 list_pretty_printer pp;
127 boost::apply_visitor(pp,l.get());
128 }
129
130 /* list parser */
131
132 template<typename InputIterator>
parse_list(InputIterator & first,InputIterator last,int nest)133 list parse_list(InputIterator& first,InputIterator last,int nest)
134 {
135 list_elems elms;
136 while(first!=last){
137 std::string str=*first++;
138 if(str=="("){
139 elms.push_back(parse_list(first,last,nest+1));
140 }
141 else if(str==")"){
142 if(nest==0)throw std::runtime_error("unmatched )");
143 return list(elms);
144 }
145 else{
146 elms.push_back(list(str));
147 }
148 }
149 if(nest!=0)throw std::runtime_error("unmatched (");
150 return list(elms);
151 }
152
parse_list(const std::string str)153 list parse_list(const std::string str)
154 {
155 typedef boost::tokenizer<boost::char_separator<char> > tokenizer;
156 tokenizer tok(str,boost::char_separator<char>(" ","()"));
157 tokenizer::iterator begin=tok.begin();
158 return parse_list(begin,tok.end(),0);
159 }
160
main()161 int main()
162 {
163 std::cout<<"enter list: ";
164 std::string str;
165 std::getline(std::cin,str);
166 try{
167 pretty_print(parse_list(str));
168 }
169 catch(const std::exception& e){
170 std::cout<<"error: "<<e.what()<<"\n";
171 }
172
173 return 0;
174 }
175