1 ////////////////////////////////////////////////////////////////////////////////
3 // Copyright 2010 - 2017, Paul Beckingham, Federico Hernandez.
5 // Permission is hereby granted, free of charge, to any person obtaining a copy
6 // of this software and associated documentation files (the "Software"), to deal
7 // in the Software without restriction, including without limitation the rights
8 // to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
9 // copies of the Software, and to permit persons to whom the Software is
10 // furnished to do so, subject to the following conditions:
12 // The above copyright notice and this permission notice shall be included
13 // in all copies or substantial portions of the Software.
15 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
16 // OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
17 // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
18 // THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
19 // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
20 // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
23 // http://www.opensource.org/licenses/mit-license.php
25 ////////////////////////////////////////////////////////////////////////////////
35 ////////////////////////////////////////////////////////////////////////////////
36 // - Tree, Branch and Node are synonymous.
37 // - A Tree may contain any number of branches.
38 // - A Branch may contain any number of name/value pairs, unique by name.
39 // - The destructor will delete all branches recursively.
40 // - Tree::enumerate is a snapshot, and is invalidated by modification.
41 // - Branch sequence is preserved.
42 void Tree::addBranch (std::shared_ptr <Tree> branch)
45 throw "Failed to allocate memory for parse tree.";
47 _branches.push_back (branch);
50 ////////////////////////////////////////////////////////////////////////////////
51 void Tree::removeBranch (std::shared_ptr <Tree> branch)
53 for (auto i = _branches.begin (); i != _branches.end (); ++i)
63 ////////////////////////////////////////////////////////////////////////////////
64 void Tree::removeAllBranches ()
66 _branches.erase (_branches.begin (), _branches.end ());
69 ////////////////////////////////////////////////////////////////////////////////
70 void Tree::replaceBranch (std::shared_ptr <Tree> from, std::shared_ptr <Tree> to)
72 for (unsigned int i = 0; i < _branches.size (); ++i)
74 if (_branches[i] == from)
82 ////////////////////////////////////////////////////////////////////////////////
83 // Accessor for attributes.
84 void Tree::attribute (const std::string& name, const std::string& value)
86 _attributes[name] = value;
89 ////////////////////////////////////////////////////////////////////////////////
90 // Accessor for attributes.
91 void Tree::attribute (const std::string& name, const int value)
93 _attributes[name] = format (value);
96 ////////////////////////////////////////////////////////////////////////////////
97 // Accessor for attributes.
98 void Tree::attribute (const std::string& name, const double value)
100 _attributes[name] = format (value, 1, 8);
103 ////////////////////////////////////////////////////////////////////////////////
104 // Accessor for attributes.
105 std::string Tree::attribute (const std::string& name)
107 // Prevent autovivification.
108 auto i = _attributes.find (name);
109 if (i != _attributes.end ())
115 ////////////////////////////////////////////////////////////////////////////////
116 void Tree::removeAttribute (const std::string& name)
118 _attributes.erase (name);
121 ////////////////////////////////////////////////////////////////////////////////
122 // Recursively builds a list of std::shared_ptr <Tree> objects, left to right,
123 // depth first. The reason for the depth-first enumeration is that a client may
124 // wish to traverse the tree and delete nodes. With a depth-first iteration,
125 // this is a safe mechanism, and a node pointer will never be dereferenced after
126 // it has been deleted.
127 void Tree::enumerate (std::vector <std::shared_ptr <Tree>>& all) const
129 for (auto& i : _branches)
136 ////////////////////////////////////////////////////////////////////////////////
137 bool Tree::hasTag (const std::string& tag) const
139 return std::find (_tags.begin (), _tags.end (), tag) != _tags.end ();
142 ////////////////////////////////////////////////////////////////////////////////
143 void Tree::tag (const std::string& tag)
146 _tags.push_back (tag);
149 ////////////////////////////////////////////////////////////////////////////////
150 void Tree::unTag (const std::string& tag)
152 auto i = std::find (_tags.begin (), _tags.end (), tag);
153 if (i != _tags.end ())
157 ////////////////////////////////////////////////////////////////////////////////
158 int Tree::countTags () const
160 return _tags.size ();
163 ////////////////////////////////////////////////////////////////////////////////
164 int Tree::count () const
169 // Recurse and count the branches.
170 for (auto& i : _branches)
171 total += i->count ();
176 ////////////////////////////////////////////////////////////////////////////////
177 std::shared_ptr <Tree> Tree::find (const std::string& path)
179 std::vector <std::string> elements = split (path, '/');
181 // Must start at the trunk.
182 auto cursor = std::make_shared <Tree> (*this);
183 auto it = elements.begin ();
184 if (cursor->_name != *it)
187 // Perhaps the trunk is what is needed?
188 if (elements.size () == 1)
191 // Now look for the next branch.
192 for (++it; it != elements.end (); ++it)
196 // If the cursor has a branch that matches *it, proceed.
197 for (auto i = cursor->_branches.begin (); i != cursor->_branches.end (); ++i)
199 if ((*i)->_name == *it)
214 ////////////////////////////////////////////////////////////////////////////////
215 std::string Tree::dumpNode (
216 const std::shared_ptr <Tree> t,
219 std::stringstream out;
222 for (int i = 0; i < depth; ++i)
226 // Useful for debugging tree node new/delete errors.
227 // << std::hex << t << " "
228 << "\033[1m" << t->_name << "\033[0m";
232 for (auto& a : t->_attributes)
237 atts += a.first + "='\033[33m" + a.second + "\033[0m'";
245 for (auto& tag : t->_tags)
250 tags += "\033[32m" + tag + "\033[0m";
257 // Recurse for branches.
258 for (auto& b : t->_branches)
259 out << dumpNode (b, depth + 1);
264 ////////////////////////////////////////////////////////////////////////////////
265 std::string Tree::dump () const
267 std::stringstream out;
268 out << "Tree (" << count () << " nodes)\n"
269 << dumpNode (std::make_shared <Tree> (*this), 1);
274 ////////////////////////////////////////////////////////////////////////////////