diff options
Diffstat (limited to 'qlparser/qtnode.hh')
-rw-r--r-- | qlparser/qtnode.hh | 503 |
1 files changed, 503 insertions, 0 deletions
diff --git a/qlparser/qtnode.hh b/qlparser/qtnode.hh new file mode 100644 index 0000000..53a038e --- /dev/null +++ b/qlparser/qtnode.hh @@ -0,0 +1,503 @@ +#ifndef _QTNODE_ +#define _QTNODE_ + +#ifndef CPPSTDLIB +#include <vector.h> // STL<ToolKit> +#include <list.h> // STL<ToolKit> +#include <ospace/string.h> // STL<ToolKit> +#else +#include <vector> +#include <list> +#include <string> +#endif + +#include "raslib/rmdebug.hh" +#include "raslib/sinterval.hh" +#include "qlparser/parseinfo.hh" +#include "qlparser/qtdata.hh" + +// define used in lots of qlparser files to indent output +#ifdef CPPSTDLIB +#define SPACE_STR(numSpace) std::string(numSpace,' ') +#else +#define SPACE_STR(numSpace) std::string(' ',numSpace) +#endif + +class QtOperation; // forward declarations of subclasses of QtNode +class Type; +class QtTypeElement; + +/* +* This file is part of rasdaman community. +* +* Rasdaman community is free software: you can redistribute it and/or modify +* it under the terms of the GNU General Public License as published by +* the Free Software Foundation, either version 3 of the License, or +* (at your option) any later version. +* +* Rasdaman community is distributed in the hope that it will be useful, +* but WITHOUT ANY WARRANTY; without even the implied warranty of +* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +* GNU General Public License for more details. +* +* You should have received a copy of the GNU General Public License +* along with rasdaman community. If not, see <http://www.gnu.org/licenses/>. +* +* Copyright 2003, 2004, 2005, 2006, 2007, 2008, 2009 Peter Baumann / +rasdaman GmbH. +* +* For more information please see <http://www.rasdaman.org> +* or contact Peter Baumann via <baumann@rasdaman.com>. +*/ +/************************************************************* + * + * + * COMMENTS: + * + ************************************************************/ + + +//@ManMemo: Module: {\bf qlparser} + +/** + + The class QtNode is the common super class of all node + classes of the query tree. It provides a reference to its + parent node in the tree. The parent of root is null. + +*/ + + +class QtNode +{ + public: + /// list of QtData pointers + typedef std::vector<QtData*> QtDataList; + + /// struct containing dimension and triming information + struct QtTrimElement + { + r_Dimension dimension; + r_Sinterval interval; + bool intervalFlag; + }; + + /// list of QtTrimData structures + typedef std::vector<QtTrimElement*> QtTrimList; + + /// list of QtNode pointers + typedef std::list<QtNode*> QtNodeList; + + enum QtNodeType + { + QT_UNDEFINED_NODE, + QT_MDD_ACCESS, + QT_OPERATION_ITERATOR, + QT_SELECTION_ITERATOR, + QT_JOIN_ITERATOR, + QT_UPDATE, + QT_INSERT, + QT_DELETE, + QT_COMMAND, + QT_PLUS, + QT_MINUS, + QT_MULT, + QT_DIV, + QT_OR, + QT_AND, + QT_XOR, + QT_IS, + QT_EQUAL, + QT_NOT_EQUAL, + QT_LESS, + QT_LESS_EQUAL, + QT_NOT, + QT_SQRT, +// added by CStancuMara + QT_EXECUTE, + QT_ONC_STREAM, + QT_ITERATOR, + QT_OPERATION, + QT_BINARY_OPERATION, + QT_BINARY_INDUCE, + QT_GROUP_ITERATOR, + QT_IDENT, + QT_NARY_OPERATION, + QT_UNARY_OPERATION, + QT_CONDENSE, + QT_UNARY_INDUCE, + +//************** + QT_ABS, QT_EXP, QT_LOG, QT_LN, QT_SIN, QT_COS, + QT_TAN, QT_SINH, QT_COSH, QT_TANH, QT_ARCSIN, + QT_ARCCOS, QT_ARCTAN, + QT_REALPART, + QT_IMAGINARPART, + QT_CAST, +//************** + + QT_CSE_ROOT, + QT_DOMAIN_OPERATION, + QT_ALL, + QT_SOME, + QT_COUNTCELLS, + QT_ADDCELLS, + QT_AVGCELLS, + QT_MINCELLS, + QT_MAXCELLS, + QT_MDD_VAR, + QT_MDD_STREAM, + QT_CONST, + QT_DOT, + QT_CONVERSION, + QT_OID, + QT_INTERVALOP, + QT_MINTERVALOP, + QT_POINTOP, + QT_LO, + QT_HI, + QT_SDOM, + QT_SHIFT, + QT_EXTEND, + //QT_MINTERVAL_SELECT, + QT_MARRAYOP, + QT_CONDENSEOP, + QT_SCALE, + QT_OVERLAY, + QT_BIT, + QT_PYRAMID, + QT_LAST_NODE_TYPE + }; + + + + enum QtAreaType + { + QT_AREA_MDD, + QT_AREA_SCALAR + }; + + enum QtChildType + { + QT_DIRECT_CHILDS, + QT_LEAF_NODES, + QT_ALL_NODES + }; + + /// list of QtOperation pointers + typedef std::vector<QtOperation*> QtOperationList; + + /// default constructor + QtNode(); + + /// constructor getting a pointer to the parent + QtNode( QtNode* node ); + + /// destructor + virtual ~QtNode(); + + /// returns weather class b is a subtype of class a + bool subtype( enum QtNodeType a, enum QtNodeType b ); + + /// return childs of the node + virtual QtNodeList* getChilds( QtChildType flag ); + /** + The method allows different retrieval of the subtree nodes. Dependent on the content of {\tt flag} + one of the following semantics is used: + {\tt DIRECT_CHILDS} - A list of all direct child nodes of the current node is returned. + {\tt LEAF_NODES } - A list of all leaf nodes of the subtree with the current node as root is returned. + {\tt ALL_NODES } - A list of all nodes of the subtree with the current node as root is returned. + The nodes in the result list have a special order. Every node comes before its parent node in + the result list. + */ + + /// return childs of a certain class + QtNodeList* getChild( const QtNodeType node, QtChildType flag = QT_DIRECT_CHILDS ); + /** + The method allows to specify the class of childs to be considered according to method {\tt getChilds}. + By default, just direct childs are considered + */ + + /// test if the two nodes have an equal meaning in a subtree + virtual bool equalMeaning( QtNode* node ); + + /** + The method checks, if the two nodes have an equal meaning in a subtree. + {\tt equalMeaning()} depends on the type of the node and the information in the node. + For unary and binary operators the method {\tt equalMeaning()} is invoked on the input nodes. + */ + + /// creates a unique name for a common subexpression + virtual std::string getSpelling(); + + /** + The method creates a unique name for common subexpressions by concatenating operators + and variables in the subtree of the common subexpression. + */ + + /// test if the edge to the parent node is of type mdd or atomic + virtual QtAreaType getAreaType(); + /** + The method tests if the edge to the parent node belongs to a multidimensional or + atomic area. + */ + + /// simplifies the tree + virtual void simplify(); + /** + The method evaluates constant expressions. + */ + + /// optimizes the tree +// virtual void rewriteOps(); + /** + The method applies some algebraic rules: + + \begin{verbatim} + some( x or y ) -> some( x ) or some( y ) + all ( x and y ) -> all ( x ) and all ( y ) + all() or some() -> some() or all() + some() and all() -> all() and some() + \end{verbatim} + + Further, a left deep tree is produced (for +,*):: + + \begin{verbatim} + (T1 o T2) + (T3 o T4) -> ((T1 o T2) o T3) o T4 + \end{verbatim} + + The method has to be supplied top-down in the query tree. + */ + + /// optimizes the tree +// virtual void sortAssociativeOps(); + /** + Operators of commutative binary operations are ordered in a + unique sequence. + */ + + /// check idempetency rules +// virtual void checkIdempotency(); + /** + The method applies idempotency rules on binary operations. + The method is supplied bottom-up in the query tree. + */ + + /// prints the tree + virtual void printTree( int tab, std::ostream& s = std::cout, QtChildType mode = QT_ALL_NODES )=0; + + /// prints the algebraic expression + virtual void printAlgebraicExpression( std::ostream& s = std::cout )=0; + + //@Man: Read/Write methods + //@{ + /// + + /// + inline virtual void setInput( QtOperation* inputOld, QtOperation* inputNew); + /// + inline QtNode* getParent() const; + /// + inline void setParent( QtNode* node ); + /// + inline const ParseInfo& getParseInfo(); + /// + inline void setParseInfo( const ParseInfo &info ); + + /// + //@} + + /// methods for identification of nodes + inline virtual const QtNodeType getNodeType() const; + /** + The method allows you to differ between the different node types. + */ + + /// method for pre optimizations (basically load optimization) + //virtual void preOptimize(){}; + /** + {\em Load Optimization} + The method is invoked through the whole query tree. The information of + every triming and projection node is collected and stored in a {\tt QtTrimList} + structure which is passed down. While collecting the information consistency + of the data is checked. At the leafs, which are load operations, the structure + is converted to a minterval object and stored in the leaf node. + The list is dynamically created in the node which is on top of an operation subtree + and deleted where the information is stored or dropped. + + Defined empty to do nothing in case it is not defined for a subclass. + */ + + /// returns the QtNodeType parent of the argument (do not use for the root) + enum QtNodeType getQtNodeTypeParent(enum QtNodeType); + + /// number of QtNodeTypes + static const int QtNodes; + + /// the root of the inheritance tree + static const QtNodeType QtRoot; + + /// the inheritance relations list + static const QtNodeType QtInheritance[][2]; + + + protected: + /// attribute for parser info + ParseInfo parseInfo; + + private: + /// pointer to its parent + QtNode* parent; + + /// attribute for identification of nodes + static const QtNodeType nodeType; + + /// (base_class, derived_class) pair + struct QtNodePair { + enum QtNodeType base, deriv; + }; + + + ///operator overload for QtNodePair struct + friend bool operator<( const QtNodePair a, const QtNodePair b); + + /// starting point of elements having node as base class + static int child_range[]; + + /// sets up the child_range[] array + void set_child_range(const QtNodePair *arr); + + /// minim and maxim labels to determine subtypes + static int minim[], maxim[]; + + /// keeps track if SetMinMax was already called + static bool MinMaxDone; + + /// sets minim and maxim values for each QtNodeType + void SetMinMax(); + + /// sets min max values once child_range is set up, for subtree with x as root + void num_node (const QtNodePair *arr, enum QtNodeType x); + +}; + + + + +//@ManMemo: Module: {\bf qlparser} + +/** + + The class encapsulates type information. It additionally + can hold a name in order to be identifyable in a list. + + The type is specified by {\tt dataType} and {\tt type}. + This is necessary because not all types are supported by + subclasses of \Ref{Type}, e.g. not all types are persistent ones. + + In case of QT_MDD and QT_COMPLEX, further type information + can be optained from {\tt type}. + +*/ + +class QtTypeElement +{ + public: + /// + QtTypeElement(); + + /// + QtTypeElement( const QtDataType initDataType, const char* initName = NULL ); + + /// + QtTypeElement( const Type* initType, const char* initName = NULL ); + + /// + QtTypeElement( const QtTypeElement& typeElement ); + + /// + ~QtTypeElement(); + + /// assignment: cleanup + copy + const QtTypeElement& operator= ( const QtTypeElement& ); + + //@Man: Read/Write methods + //@{ + /// + /// + void setDataType( const QtDataType newDataType ); + /// + void setType( const Type* newType ); + /// + inline void setName( const char* newName ); + /// + inline const QtDataType getDataType() const; + /// + inline const Type* getType() const; + /// + inline const char* getName() const; + /// + inline bool isBaseType() const; + /// + inline bool isInteger() const; + /// + //@} + /// + + /// print type + void printStatus( std::ostream& s = std::cout ) const; + + private: + /// + QtDataType dataType; + + /// + const Type* type; + + /// + char* name; +}; + + + +//@ManMemo: Module: {\bf qlparser} + +/** + + The class encapsulates a tuple of \Ref{QtTypeElement} + objects. + +*/ + +class QtTypeTuple +{ + public: + /// + QtTypeTuple( unsigned int length = 0 ); + + /// concatenate type tuple + void concat( const QtTypeTuple& typeTuple ); + + /// concatenate type element + void concat( const QtTypeElement& typeElement ); + + /// + std::vector<QtTypeElement> tuple; + + /// print type + void printStatus( std::ostream& s = std::cout ) const; +}; + +#include "qlparser/qtnode.icc" + +#endif + + + + + + + + + + |