src/libshared/src/Tree.cpp

   1 ////////////////////////////////////////////////////////////////////////////////
   2 //
   3 // Copyright 2010 - 2017, Paul Beckingham, Federico Hernandez.
   4 //
   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:
  11 //
  12 // The above copyright notice and this permission notice shall be included
  13 // in all copies or substantial portions of the Software.
  14 //
  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
  21 // SOFTWARE.
  22 //
  23 // http://www.opensource.org/licenses/mit-license.php
  24 //
  25 ////////////////////////////////////////////////////////////////////////////////
  26
  27 #include <cmake.h>
  28 #include <Tree.h>
  29 #include <algorithm>
  30 #include <iostream>
  31 #include <sstream>
  32 #include <shared.h>
  33 #include <format.h>
  34
  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)
  43 {
  44   if (! branch)
  45     throw "Failed to allocate memory for parse tree.";
  46
  47   _branches.push_back (branch);
  48 }
  49
  50 ////////////////////////////////////////////////////////////////////////////////
  51 void Tree::removeBranch (std::shared_ptr <Tree> branch)
  52 {
  53   for (auto i = _branches.begin (); i != _branches.end (); ++i)
  54   {
  55     if (branch == *i)
  56     {
  57       _branches.erase (i);
  58       return;
  59     }
  60   }
  61 }
  62
  63 ////////////////////////////////////////////////////////////////////////////////
  64 void Tree::removeAllBranches ()
  65 {
  66   _branches.erase (_branches.begin (), _branches.end ());
  67 }
  68
  69 ////////////////////////////////////////////////////////////////////////////////
  70 void Tree::replaceBranch (std::shared_ptr <Tree> from, std::shared_ptr <Tree> to)
  71 {
  72   for (unsigned int i = 0; i < _branches.size (); ++i)
  73   {
  74     if (_branches[i] == from)
  75     {
  76       _branches[i] = to;
  77       return;
  78     }
  79   }
  80 }
  81
  82 ////////////////////////////////////////////////////////////////////////////////
  83 // Accessor for attributes.
  84 void Tree::attribute (const std::string& name, const std::string& value)
  85 {
  86   _attributes[name] = value;
  87 }
  88
  89 ////////////////////////////////////////////////////////////////////////////////
  90 // Accessor for attributes.
  91 void Tree::attribute (const std::string& name, const int value)
  92 {
  93   _attributes[name] = format (value);
  94 }
  95
  96 ////////////////////////////////////////////////////////////////////////////////
  97 // Accessor for attributes.
  98 void Tree::attribute (const std::string& name, const double value)
  99 {
 100   _attributes[name] = format (value, 1, 8);
 101 }
 102
 103 ////////////////////////////////////////////////////////////////////////////////
 104 // Accessor for attributes.
 105 std::string Tree::attribute (const std::string& name)
 106 {
 107   // Prevent autovivification.
 108   auto i = _attributes.find (name);
 109   if (i != _attributes.end ())
 110     return i->second;
 111
 112   return "";
 113 }
 114
 115 ////////////////////////////////////////////////////////////////////////////////
 116 void Tree::removeAttribute (const std::string& name)
 117 {
 118   _attributes.erase (name);
 119 }
 120
 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
 128 {
 129   for (auto& i : _branches)
 130   {
 131     i->enumerate (all);
 132     all.push_back (i);
 133   }
 134 }
 135
 136 ////////////////////////////////////////////////////////////////////////////////
 137 bool Tree::hasTag (const std::string& tag) const
 138 {
 139   return std::find (_tags.begin (), _tags.end (), tag) != _tags.end ();
 140 }
 141
 142 ////////////////////////////////////////////////////////////////////////////////
 143 void Tree::tag (const std::string& tag)
 144 {
 145   if (! hasTag (tag))
 146     _tags.push_back (tag);
 147 }
 148
 149 ////////////////////////////////////////////////////////////////////////////////
 150 void Tree::unTag (const std::string& tag)
 151 {
 152   auto i = std::find (_tags.begin (), _tags.end (), tag);
 153   if (i != _tags.end ())
 154     _tags.erase (i);
 155 }
 156
 157 ////////////////////////////////////////////////////////////////////////////////
 158 int Tree::countTags () const
 159 {
 160   return _tags.size ();
 161 }
 162
 163 ////////////////////////////////////////////////////////////////////////////////
 164 int Tree::count () const
 165 {
 166   // This branch.
 167   int total = 1;
 168
 169   // Recurse and count the branches.
 170   for (auto& i : _branches)
 171     total += i->count ();
 172
 173   return total;
 174 }
 175
 176 ////////////////////////////////////////////////////////////////////////////////
 177 std::shared_ptr <Tree> Tree::find (const std::string& path)
 178 {
 179   std::vector <std::string> elements = split (path, '/');
 180
 181   // Must start at the trunk.
 182   auto cursor = std::make_shared <Tree> (*this);
 183   auto it = elements.begin ();
 184   if (cursor->_name != *it)
 185     return nullptr;
 186
 187   // Perhaps the trunk is what is needed?
 188   if (elements.size () == 1)
 189     return cursor;
 190
 191   // Now look for the next branch.
 192   for (++it; it != elements.end (); ++it)
 193   {
 194     bool found = false;
 195
 196     // If the cursor has a branch that matches *it, proceed.
 197     for (auto i = cursor->_branches.begin (); i != cursor->_branches.end (); ++i)
 198     {
 199       if ((*i)->_name == *it)
 200       {
 201         cursor = *i;
 202         found = true;
 203         break;
 204       }
 205     }
 206
 207     if (! found)
 208       return nullptr;
 209   }
 210
 211   return cursor;
 212 }
 213
 214 ////////////////////////////////////////////////////////////////////////////////
 215 std::string Tree::dumpNode (
 216   const std::shared_ptr <Tree> t,
 217   int depth) const
 218 {
 219   std::stringstream out;
 220
 221   // Dump node
 222   for (int i = 0; i < depth; ++i)
 223     out << "  ";
 224
 225   out
 226       // Useful for debugging tree node new/delete errors.
 227       // << std::hex << t << " "
 228       << "\033[1m" << t->_name << "\033[0m";
 229
 230   // Dump attributes.
 231   std::string atts;
 232   for (auto& a : t->_attributes)
 233   {
 234     if (atts != "")
 235       atts += ' ';
 236
 237     atts += a.first + "='\033[33m" + a.second + "\033[0m'";
 238   }
 239
 240   if (atts.length ())
 241     out << ' ' << atts;
 242
 243   // Dump tags.
 244   std::string tags;
 245   for (auto& tag : t->_tags)
 246   {
 247     if (tags.length ())
 248       tags += ' ';
 249
 250     tags += "\033[32m" + tag + "\033[0m";
 251   }
 252
 253   if (tags.length ())
 254     out << ' ' << tags;
 255   out << '\n';
 256
 257   // Recurse for branches.
 258   for (auto& b : t->_branches)
 259     out << dumpNode (b, depth + 1);
 260
 261   return out.str ();
 262 }
 263
 264 ////////////////////////////////////////////////////////////////////////////////
 265 std::string Tree::dump () const
 266 {
 267   std::stringstream out;
 268   out << "Tree (" << count () << " nodes)\n"
 269       << dumpNode (std::make_shared <Tree> (*this), 1);
 270
 271   return out.str ();
 272 }
 273
 274 ////////////////////////////////////////////////////////////////////////////////
 275