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
22using 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
37struct list_elems;
38
39typedef boost::variant<
40 std::string,
41 boost::recursive_wrapper<list_elems>
42> list_impl;
43
44struct list_elems:std::vector<flyweight<list_impl> >{};
45
46typedef 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
56struct list_hasher:boost::static_visitor<std::size_t>
57{
58 std::size_t operator()(const std::string& str)const
59 {
60 boost::hash<std::string> h;
61 return h(str);
62 }
63
64 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(seed&: res,v: *it);
70 }
71 return res;
72 }
73};
74
75#if defined(BOOST_NO_ARGUMENT_DEPENDENT_LOOKUP)
76namespace boost{
77#endif
78
79std::size_t hash_value(const list_impl& limpl)
80{
81 return boost::apply_visitor(visitor: list_hasher(),visitable: 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
90struct list_pretty_printer:boost::static_visitor<>
91{
92 list_pretty_printer():nest(0){}
93
94 void operator()(const std::string& str)
95 {
96 indent();
97 std::cout<<str<<"\n";
98 }
99
100 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(visitor&: *this,visitable: it->get());
109 }
110 --nest;
111 indent();
112 std::cout<<")\n";
113 }
114
115private:
116 void indent()const
117 {
118 for(int i=nest;i--;)std::cout<<" ";
119 }
120
121 int nest;
122};
123
124void pretty_print(const list& l)
125{
126 list_pretty_printer pp;
127 boost::apply_visitor(visitor&: pp,visitable: l.get());
128}
129
130/* list parser */
131
132template<typename InputIterator>
133list 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(x: list(str));
147 }
148 }
149 if(nest!=0)throw std::runtime_error("unmatched (");
150 return list(elms);
151}
152
153list 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(first&: begin,last: tok.end(),nest: 0);
159}
160
161int main()
162{
163 std::cout<<"enter list: ";
164 std::string str;
165 std::getline(is&: std::cin,str&: str);
166 try{
167 pretty_print(l: parse_list(str));
168 }
169 catch(const std::exception& e){
170 std::cout<<"error: "<<e.what()<<"\n";
171 }
172
173 return 0;
174}
175

source code of boost/libs/flyweight/example/composite.cpp