TreeNode.h

Go to the documentation of this file.

// Copyright 2014 Sensics, Inc.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

#ifndef INCLUDED_TreeNode_h_GUID_EEC6C5AF_332A_4780_55C2_D794B3BF5106
#define INCLUDED_TreeNode_h_GUID_EEC6C5AF_332A_4780_55C2_D794B3BF5106

// Internal Includes
#include <osvr/Util/TreeNode_fwd.h>

// Library/third-party includes
#include <boost/noncopyable.hpp>
#include <boost/operators.hpp>
#include <boost/assert.hpp>

// Standard includes
#include <string>
#include <vector>
#include <algorithm>
#include <stdexcept>

namespace osvr {
namespace util {
    namespace tree {
        struct NoSuchChild : std::runtime_error {
            NoSuchChild(std::string const &name)
                : std::runtime_error("No child found with the name " + name) {}
        };
        template <typename ValueType>
        class TreeNode : boost::noncopyable,
                         boost::operators<TreeNode<ValueType> > {
          public:
            typedef TreeNode<ValueType> type;

            typedef typename TreeNodePointer<ValueType>::type ptr_type;

            typedef type *parent_ptr_type;

            typedef ValueType value_type;

            static type &create(TreeNode &parent, std::string const &name);

            static type &create(TreeNode &parent, std::string const &name,
                                value_type const &val);

            static ptr_type createRoot();

            static ptr_type createRoot(value_type const &val);

            type &getOrCreateChildByName(std::string const &name);

            type const &getChildByName(std::string const &name) const;

            std::string const &getName() const;

            bool isRoot() const;

            parent_ptr_type getParent() const;

            bool hasChildren() const;

            size_t numChildren() const;

            value_type &value() { return m_value; }

            value_type const &value() const { return m_value; }

            template <typename F> void visitChildren(F &visitor) {
                typedef typename ChildList::size_type size_type;
                for (size_type i = 0; i < m_children.size(); ++i) {
                    visitor(*(m_children[i]));
                }
            }

            template <typename F> void visitConstChildren(F &visitor) const {
                for (auto const &node : m_children) {
                    visitor(const_cast<type const &>(*node));
                }
            }

            template <typename F> void visitChildren(F &visitor) const {
                visitConstChildren(visitor);
            }

            bool operator==(const type &x) const { return this == &x; }

          private:
            typedef type *weak_ptr_type;

            TreeNode(type &parent, std::string const &name);

            TreeNode(type &parent, std::string const &name,
                     value_type const &val);

            TreeNode();

            explicit TreeNode(value_type const &val);

            weak_ptr_type m_getChildByName(std::string const &name) const;

            void m_addChild(ptr_type const &child);

            value_type m_value;

            typedef std::vector<ptr_type> ChildList;
            ChildList m_children;

            std::string const m_name;

            parent_ptr_type m_parent;
        };

        template <typename ValueType>
        inline TreeNode<ValueType> &
        TreeNode<ValueType>::create(TreeNode<ValueType> &parent,
                                    std::string const &name) {
            if (parent.m_getChildByName(name)) {
                throw std::logic_error(
                    "Can't create a child with the same name as "
                    "an existing child!");
            }
            ptr_type ret(new TreeNode(parent, name));
            parent.m_addChild(ret);
            return *ret;
        }

        template <typename ValueType>
        inline TreeNode<ValueType> &
        TreeNode<ValueType>::create(TreeNode<ValueType> &parent,
                                    std::string const &name,
                                    ValueType const &val) {
            if (parent.m_getChildByName(name)) {
                throw std::logic_error(
                    "Can't create a child with the same name as "
                    "an existing child!");
            }
            ptr_type ret(new TreeNode(parent, name, val));
            parent.m_addChild(ret);
            return *ret;
        }

        template <typename ValueType>
        inline typename TreeNode<ValueType>::ptr_type
        TreeNode<ValueType>::createRoot() {
            ptr_type ret(new TreeNode());
            return ret;
        }

        template <typename ValueType>
        inline typename TreeNode<ValueType>::ptr_type
        TreeNode<ValueType>::createRoot(ValueType const &val) {
            ptr_type ret(new TreeNode(val));
            return ret;
        }

        template <typename ValueType>
        inline TreeNode<ValueType> &
        TreeNode<ValueType>::getOrCreateChildByName(std::string const &name) {
            weak_ptr_type child = m_getChildByName(name);
            if (child != nullptr) {
                return *child;
            }
            return TreeNode::create(*this, name);
        }

        template <typename ValueType>
        inline TreeNode<ValueType> const &
        TreeNode<ValueType>::getChildByName(std::string const &name) const {
            weak_ptr_type child = m_getChildByName(name);
            if (child != nullptr) {
                return *child;
            }
            throw NoSuchChild(name);
        }

        template <typename ValueType>
        inline std::string const &TreeNode<ValueType>::getName() const {
            return m_name;
        }

        template <typename ValueType>
        inline bool TreeNode<ValueType>::isRoot() const {
            BOOST_ASSERT_MSG(
                (getParent() == nullptr) == m_name.empty(),
                "The root and only the root should have an empty name "
                "and no parent!");
            return getParent() == nullptr;
        }

        template <typename ValueType>
        inline typename TreeNode<ValueType>::parent_ptr_type
        TreeNode<ValueType>::getParent() const {
            return m_parent;
        }

        template <typename ValueType>
        inline bool TreeNode<ValueType>::hasChildren() const {
            return !m_children.empty();
        }

        template <typename ValueType>
        inline size_t TreeNode<ValueType>::numChildren() const {
            BOOST_ASSERT_MSG((m_children.size() != 0) == hasChildren(),
                             "hasChildren should return true iff size != 0!");
            return m_children.size();
        }

        template <typename ValueType>
        inline typename TreeNode<ValueType>::weak_ptr_type
        TreeNode<ValueType>::m_getChildByName(std::string const &name) const {
            auto it = std::find_if(
                begin(m_children), end(m_children),
                [&](ptr_type const &n) { return n->getName() == name; });
            weak_ptr_type ret = nullptr;
            if (it != end(m_children)) {
                ret = (*it).get();
            }
            return ret;
        }

        template <typename ValueType>
        inline void TreeNode<ValueType>::m_addChild(
            typename TreeNode<ValueType>::ptr_type const &child) {
            m_children.push_back(child);
        }

        template <typename ValueType>
        inline TreeNode<ValueType>::TreeNode(TreeNode<ValueType> &parent,
                                             std::string const &name)
            : m_value(), m_children(), m_name(name), m_parent(&parent) {
            if (m_name.empty()) {
                throw std::logic_error(
                    "Can't create a named tree node with an empty name!");
            }
        }

        template <typename ValueType>
        inline TreeNode<ValueType>::TreeNode(TreeNode<ValueType> &parent,
                                             std::string const &name,
                                             ValueType const &val)
            : m_value(val), m_children(), m_name(name), m_parent(&parent) {
            if (m_name.empty()) {
                throw std::logic_error(
                    "Can't create a named tree node with an empty name!");
            }
        }

        template <typename ValueType>
        inline TreeNode<ValueType>::TreeNode()
            : m_value(), m_children(), m_name(), m_parent(nullptr) {
        }

        template <typename ValueType>
        inline TreeNode<ValueType>::TreeNode(ValueType const &val)
            : m_value(val), m_children(), m_name(), m_parent(nullptr) {
        }

    } // namespace tree
} // namespace util
} // namespace osvr

#endif // INCLUDED_TreeNode_h_GUID_EEC6C5AF_332A_4780_55C2_D794B3BF5106