From 0840f434541b57fbd6d3c9d7b2a8b127cc680912 Mon Sep 17 00:00:00 2001 From: Adrian Kummerlaender Date: Wed, 1 Oct 2014 20:30:08 +0200 Subject: Moved child pointers to OperatorNode class * access was restricted by declaring them private and offering member methods such as "hasChildren" * only OperatorNode instances have children, there is no reason for wasting space by keeping empty pointers around in all other instances * this enabled the removal of all nullptr comparisons from tree construction * changed "Tree::addNode" factory method template to return a pointer to the type of the constructed node instance instead of a plain node pointer --- src/nodes.cc | 36 +++++++++++++++++++++++++++++++----- src/nodes.h | 21 +++++++++++++-------- src/tree.cc | 60 +++++++++++++++++++++++++++++++++++++++--------------------- src/tree.h | 4 ++-- 4 files changed, 85 insertions(+), 36 deletions(-) diff --git a/src/nodes.cc b/src/nodes.cc index 256a609..dd003c4 100644 --- a/src/nodes.cc +++ b/src/nodes.cc @@ -4,11 +4,20 @@ #include "exceptions.h" #include +#include #include #include namespace SimpleParser { +bool Node::hasChildren() const { + return false; +} + +bool Node::isParentOf(Node*const) const { + return false; +} + OperandNode::OperandNode(double value): value_{value} { } @@ -31,20 +40,20 @@ OperatorNode::OperatorNode(TokenType token): double OperatorNode::solve() const { switch ( this->operator_ ) { case TokenType::OPERATOR_PLUS: { - return this->leftChild->solve() + this->rightChild->solve(); + return this->left_->solve() + this->right_->solve(); } case TokenType::OPERATOR_MINUS: { - return this->leftChild->solve() - this->rightChild->solve(); + return this->left_->solve() - this->right_->solve(); } case TokenType::OPERATOR_MULTIPLY: { - return this->leftChild->solve() * this->rightChild->solve(); + return this->left_->solve() * this->right_->solve(); } case TokenType::OPERATOR_DIVIDE: { - return this->leftChild->solve() / this->rightChild->solve(); + return this->left_->solve() / this->right_->solve(); } case TokenType::OPERATOR_POWER: { return std::pow( - this->leftChild->solve(), this->rightChild->solve() + this->left_->solve(), this->right_->solve() ); } default: { @@ -76,10 +85,27 @@ std::string OperatorNode::print() const { } } +bool OperatorNode::hasChildren() const { + return this->right_ != nullptr && + this->left_ != nullptr; +} + +bool OperatorNode::isParentOf(Node*const node) const { + return this->right_ == node || + this->left_ == node; +} + TokenType OperatorNode::token() const { return this->operator_; } +void OperatorNode::setChildren(Node*const right, Node*const left) { + assert(right != nullptr && left != nullptr); + + this->right_ = right; + this->left_ = left; +} + ConstantNode::ConstantNode( const std::string& identifier, const ConstantMap* constants diff --git a/src/nodes.h b/src/nodes.h index 9559722..95bf772 100644 --- a/src/nodes.h +++ b/src/nodes.h @@ -13,11 +13,10 @@ class Node { public: virtual ~Node() {}; - virtual double solve() const = 0; - virtual std::string print() const = 0; - - Node* leftChild; - Node* rightChild; + virtual double solve() const = 0; + virtual std::string print() const = 0; + virtual bool hasChildren() const; + virtual bool isParentOf(Node*const) const; }; @@ -25,15 +24,21 @@ class OperatorNode: public Node { public: explicit OperatorNode(TokenType); - TokenType token() const; + virtual double solve() const; + virtual std::string print() const; + virtual bool hasChildren() const; + virtual bool isParentOf(Node*const) const; - virtual double solve() const; - virtual std::string print() const; + TokenType token() const; + void setChildren(Node*const, Node*const); private: const TokenType operator_; + Node* right_; + Node* left_; + }; class OperandNode: public Node { diff --git a/src/tree.cc b/src/tree.cc index ab227e4..419a05c 100644 --- a/src/tree.cc +++ b/src/tree.cc @@ -61,13 +61,11 @@ std::string Tree::print() const { << node->print() << "\"]; "; - if ( node->rightChild != nullptr && - node->leftChild != nullptr ) { + if ( node->hasChildren() ) { std::size_t childIndex{}; for ( auto&& child : this->node_collection_ ) { - if ( child.get() == node->leftChild || - child.get() == node->rightChild ) { + if ( node->isParentOf(child.get()) ) { out << "\"node" << nodeIndex << "\" -> \"node" @@ -87,15 +85,20 @@ std::string Tree::print() const { return out.str(); } -template -Node* Tree::addNode(Args&&... args) { +template < + typename Type, + typename... Args +> +typename std::add_pointer::type Tree::addNode(Args&&... args) { this->node_collection_.emplace_back( - std::make_unique( + std::make_unique( std::forward(args)... ) ); - return this->node_collection_.back().get(); + return static_cast::type>( + this->node_collection_.back().get() + ); } Node* Tree::buildTree(const std::string& term) { @@ -129,9 +132,16 @@ Node* Tree::buildTree(const std::string& term) { this->addNode(elementToken) ); } else { - Node*const currOperator = popNode(operators); - currOperator->rightChild = popNode(operands); - currOperator->leftChild = popNode(operands); + OperatorNode*const currOperator( + static_cast( + popNode(operators) + ) + ); + + currOperator->setChildren( + popNode(operands), + popNode(operands) + ); operands.push(currOperator); @@ -147,17 +157,21 @@ Node* Tree::buildTree(const std::string& term) { switch ( determineToken(subElements.front()) ) { case TokenType::VALUE_NUMBER: case TokenType::OPERATOR_MINUS: { - operands.push(this->addNode( - stringToDouble(subElements.front()) - )); + operands.push( + this->addNode( + stringToDouble(subElements.front()) + ) + ); break; } case TokenType::VALUE_IDENTIFIER: { - operands.push(this->addNode( - subElements.front(), - this->constants_ - )); + operands.push( + this->addNode( + subElements.front(), + this->constants_ + ) + ); break; } @@ -175,11 +189,15 @@ Node* Tree::buildTree(const std::string& term) { while ( !operators.empty() ) { OperatorNode*const currOperator( - static_cast(popNode(operators)) + static_cast( + popNode(operators) + ) ); - currOperator->rightChild = popNode(operands); - currOperator->leftChild = popNode(operands); + currOperator->setChildren( + popNode(operands), + popNode(operands) + ); operands.push(currOperator); } diff --git a/src/tree.h b/src/tree.h index e2eb7a6..1b673a2 100644 --- a/src/tree.h +++ b/src/tree.h @@ -18,8 +18,8 @@ class Tree { std::string print() const; private: - template - Node* addNode(Args&&... args); + template + typename std::add_pointer::type addNode(Args&&... args); Node* buildTree(const std::string&); -- cgit v1.2.3