ext/OGDF/ogdf/fileformats/DinoXmlParser.h

   1 /*
   2  * $Revision: 2564 $
   3  *
   4  * last checkin:
   5  *   $Author: gutwenger $
   6  *   $Date: 2012-07-07 00:03:48 +0200 (Sa, 07. Jul 2012) $
   7  ***************************************************************/
   8
   9 /** \file
  10  * \brief Contains the struct declarations XmlAttributeObject, XmlTagObject
  11  * and the class DinoXmlParser.
  12  *
  13  * \author Dino Ahr
  14  *
  15  * \par License:
  16  * This file is part of the Open Graph Drawing Framework (OGDF).
  17  *
  18  * \par
  19  * Copyright (C)<br>
  20  * See README.txt in the root directory of the OGDF installation for details.
  21  *
  22  * \par
  23  * This program is free software; you can redistribute it and/or
  24  * modify it under the terms of the GNU General Public License
  25  * Version 2 or 3 as published by the Free Software Foundation;
  26  * see the file LICENSE.txt included in the packaging of this file
  27  * for details.
  28  *
  29  * \par
  30  * This program is distributed in the hope that it will be useful,
  31  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  32  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  33  * GNU General Public License for more details.
  34  *
  35  * \par
  36  * You should have received a copy of the GNU General Public
  37  * License along with this program; if not, write to the Free
  38  * Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  39  * Boston, MA 02110-1301, USA.
  40  *
  41  * \see  http://www.gnu.org/copyleft/gpl.html
  42  ***************************************************************/
  43
  44 #ifdef _MSC_VER
  45 #pragma once
  46 #endif
  47
  48 #ifndef OGDF_DINO_XML_PARSER_H
  49 #define OGDF_DINO_XML_PARSER_H
  50
  51 #include <ogdf/basic/Stack.h>
  52 #include <ogdf/basic/String.h>
  53 #include <ogdf/basic/Hashing.h>
  54 #include <ogdf/basic/GraphAttributes.h>
  55 #include <ogdf/fileformats/DinoXmlScanner.h>
  56
  57
  58
  59 namespace ogdf {
  60
  61         //---------------------------------------------------------
  62         // H a s h e d S t r i n g
  63         //---------------------------------------------------------
  64
  65         typedef HashElement<String,int> HashedString;
  66
  67         //---------------------------------------------------------
  68         // X m l A t t r i b u t e O b j e c t
  69         //---------------------------------------------------------
  70         /** This struct represents an attribute associated to a tag.
  71          */
  72         struct OGDF_EXPORT XmlAttributeObject {
  73
  74                 /** Contains the name of the attribute, i.e.
  75                  *  for <A attr1="value1"> ... </A> it contains "attr1"
  76                  */
  77                 HashedString *m_pAttributeName;
  78
  79                 /** Contains the value assigned to this attribute without qoutes, i.e.
  80                  *  for <A attr1="value1"> ... </A> it contains "value1" and not "\"value1\"".
  81                  */
  82                 HashedString *m_pAttributeValue;
  83
  84                 /** Pointer to the next attribute and 0 if this is the only attribute. */
  85                 XmlAttributeObject *m_pNextAttribute;
  86
  87                 /** Constructor */
  88                 XmlAttributeObject(HashedString *name, HashedString *value) :
  89                         m_pAttributeName(name),
  90                         m_pAttributeValue(value),
  91                         m_pNextAttribute(0)
  92                         {};
  93
  94                 /** Destructor; will be performed in destroyParseTree(). */
  95                 ~XmlAttributeObject(){};
  96
  97                 /** Flag denotes whether attribute is valid or not. */
  98                 bool m_valid;
  99
 100                 /** Getter. */
 101                 const String& getName() const {
 102                         return m_pAttributeName->key();
 103                 }
 104
 105                 const String& getValue() const {
 106                         return m_pAttributeValue->key();
 107                 }
 108
 109                 const bool& valid() const {
 110                         return m_valid;
 111                 }
 112
 113                 /** Setter. */
 114                 void setValid() {
 115                         m_valid = true;
 116                 }
 117
 118                 void setInvalid() {
 119                         m_valid = false;
 120                 }
 121
 122                 // Overloaded new and delete operators
 123                 OGDF_NEW_DELETE
 124
 125         }; // struct XmlAttributeObject
 126
 127         //---------------------------------------------------------
 128         // X m l T a g O b j e c t
 129         //---------------------------------------------------------
 130         /** This struct represents a node in the XML parse tree.
 131          */
 132         struct OGDF_EXPORT XmlTagObject {
 133
 134                 /** The identifier of the tag,
 135                  *i.e. for <A> the identifier is "A"
 136                  */
 137                 HashedString *m_pTagName;
 138
 139                 /** Pointer to the first attribute;
 140                  *  if there is more than one attribute these are linked by
 141                  * m_pNextAttribute in struct XmlAttributeObject
 142                  */
 143                 XmlAttributeObject *m_pFirstAttribute;
 144
 145                 /** Contains the characters inbetween the start tag and the end tag,
 146                  *  i.e. for <A attr1=... attr2=...> lala </A> it contains " lala "
 147                  */
 148                 HashedString *m_pTagValue;
 149
 150                 /** Contains the pointer to the first son tag object,
 151                  *  i.e. for <A> <B> ... </B> <C> ... </C> </A> it contains a pointer
 152                  *  to the object representing B
 153                  *  The other children of A are reachable via m_pBrother of the first son,
 154                  *  i.e. the variable m_pBrother of the object representing B contains a
 155                  * pointer to the object representing C
 156                  */
 157                 XmlTagObject *m_pFirstSon;
 158
 159                 /** Contains the pointer to a brother tag object or 0 if this
 160                  *  object is the only child
 161                  */
 162                 XmlTagObject *m_pBrother;
 163
 164                 /** Constructor */
 165                 XmlTagObject(HashedString *name) :
 166                         m_pTagName(name),
 167                         m_pFirstAttribute(0),
 168                         m_pTagValue(0),
 169                         m_pFirstSon(0),
 170                         m_pBrother(0),
 171                         m_valid(0)
 172                         {};
 173
 174                 /** Destructor; will be performed in destroyParseTree(). */
 175                 ~XmlTagObject(){};
 176
 177                 /** Flag denotes whether attribute is valid or not. */
 178                 mutable bool m_valid;
 179
 180                 /** integer value for the depth in the xml parse tree */
 181                 int m_depth;
 182
 183                 /** integer value that stores the line number
 184                  *  of the tag in the parsed xml document */
 185                  int m_line;
 186
 187                 public:
 188
 189                 /**Checks if currentNode is leaf in the parse tree.
 190                  * Returns true if list of sons is empty.
 191                  * Returns false otherwise.
 192                  *
 193                  * NEW
 194                  */
 195                 bool isLeaf() const;
 196
 197                 /**Searches for a son with tag name sonsName.
 198                  * Returns the son via the referenced pointer son.
 199                  * Returns true if son is found.
 200                  * Returns false, otherwise, son is set to NULL.
 201                  *
 202                  * NEW
 203                  */
 204                 bool findSonXmlTagObjectByName( const String sonsName,
 205                                                                                 XmlTagObject *&son) const;
 206
 207                 /**Searches for sons with tag name sonsName.
 208                  * Returns the sons via a list with pointers to the sons.
 209                  * Returns true if at least one son was found.
 210                  * Returns false otherwise, sons is set to NULL.
 211                  *
 212                  * NEW
 213                  */
 214                 bool findSonXmlTagObjectByName( const String sonsName,
 215                                                                                 List<XmlTagObject*> &sons) const;
 216
 217                 /**Searches for sons of father which names are inequal to those
 218                  * in list sonsNames.
 219                  * Returns true if at least one son of father is found whose name
 220                  * doesn't match one in sonsNames.
 221                  * Returns false otherwise.
 222                  *
 223                  * NEW
 224                  */
 225                 bool hasMoreSonXmlTagObject(const List<String> &sonNamesToIgnore) const;
 226
 227                 /**Searches for an attribute with name name.
 228                  *
 229                  * NEW
 230                  */
 231                 bool findXmlAttributeObjectByName(
 232                         const String attName,
 233                         XmlAttributeObject*& attribute) const;
 234
 235                 /**Checks if currentTag owns at least one attribute.
 236                  * Returns true if list of attributes isn't empty.
 237                  * Returns false otherwise.
 238                  *
 239                  * NEW
 240                  */
 241                 bool isAttributeLess() const;
 242
 243                 /** Getter. */
 244                 const bool& valid() const {
 245                         return m_valid;
 246                 }
 247
 248                 const String& getName() const {
 249                         return m_pTagName->key();
 250                 }
 251
 252                 const String& getValue() const {
 253                         return m_pTagValue->key();
 254                 }
 255
 256                 /** Setter. */
 257                 void setValid() const {
 258                         m_valid = true;
 259                 }
 260
 261                 void setInvalid() {
 262                         m_valid = false;
 263                 }
 264
 265                 /* get for depth of xml-tag-object */
 266                 const int& getDepth() const {
 267                         return m_depth;
 268                 }
 269
 270                 /* setter for new depth */
 271                 void setDepth(int newDepth){
 272                         m_depth = newDepth;
 273                 }
 274
 275
 276                 /* get for line of xml-tag-object */
 277                 const int& getLine() const {
 278                         return m_line;
 279                 }
 280
 281                 /* setter for line */
 282                 void setLine(int line) {
 283                         m_line = line;
 284                 }
 285
 286                 // Overloaded new and delete operators
 287                 OGDF_NEW_DELETE
 288
 289         }; // struct XmlTagObject
 290
 291         //---------------------------------------------------------
 292         // D i n o X m l P a r s e r
 293         //---------------------------------------------------------
 294         /** This class parses the XML input file and builds up a
 295          *  parse tree with linked elements XMLTagObject and
 296          *  XMLAttributeObject. The class DinoXmlScanner is used to
 297          *  get the token for the parse process.
 298          */
 299          class OGDF_EXPORT DinoXmlParser {
 300
 301                  friend ostream &operator<<(ostream&, const DinoXmlParser &);
 302
 303          private:
 304
 305                 /** Pointer to the root element of the parse tree. */
 306                 XmlTagObject *m_pRootTag;
 307
 308                 /** Pointer to the scanner. */
 309                 DinoXmlScanner *m_pScanner;
 310
 311                 /** Hash table for storing names of TagObjects and
 312                  *  AttributeObjects in an efficient manner.
 313                  *  The key element is String.
 314                  *  The info element is int.
 315                  */
 316                 Hashing<String,int> m_hashTable;
 317
 318                 /** The info element of the hash table is simply an integer
 319                  * number which is incremented for each new element (starting at 0).
 320                  * The value m_hashTableInfoIndex - 1 is the last used index.
 321                  */
 322                 int m_hashTableInfoIndex;
 323
 324                 /** Recursion depth of parse(). */
 325                 int m_recursionDepth;
 326                 /** stack for checking correctness of correspondent closing tags */
 327                 Stack<String> m_tagObserver;
 328
 329
 330         public:
 331
 332                 /** Constructor.
 333                  *  Inside the constructor the scanner is generated.
 334                  */
 335                 DinoXmlParser(const char *fileName);
 336
 337                 /** Destructor; destroys the parse tree. */
 338                 ~DinoXmlParser();
 339
 340                 /** Creates a new hash element and inserts it into the hash table.
 341                  */
 342                 void addNewHashElement(const String &key, int info){
 343                         OGDF_ASSERT(info >= m_hashTableInfoIndex)
 344                         m_hashTable.fastInsert(key, info);
 345                         m_hashTableInfoIndex = info + 1;
 346                 }
 347
 348                 /** Creates the parse tree and anchors it in m_pRootTag.
 349                  *  TODO: Should return a value to indicate if success.
 350                  */
 351                 void createParseTree();
 352
 353                 /** Allows (non modifying) access to the parse tree. */
 354                 const XmlTagObject &getRootTag() const {
 355                         return *m_pRootTag;
 356                 }
 357
 358                 /** Traverses the parseTree starting at startTag using the path
 359                  * description in path, which contains the infoIndices of the tags
 360                  * which have to be traversed.
 361                  * If the XmlTagObject associated to the last infoIndex in the path is
 362                  * found, it is returned via targetTag and the return value is true
 363                  * If the XmlTagObject is not found the return value is false.
 364                  */
 365                 bool traversePath(
 366                         const XmlTagObject &startTag,
 367                         const Array<int> &infoIndexPath,
 368                         const XmlTagObject *&targetTag) const;
 369
 370                 /** Searches for a specific son (identified by sonInfoIndex)
 371                  *  of father.
 372                  *  Returns the son via the referenced pointer son.
 373                  *  Returns true if son is found.
 374                  *  Returns false otherwise, son is set to NULL.
 375                  */
 376                 bool findSonXmlTagObject(
 377                         const XmlTagObject &father,
 378                         int sonInfoIndex,
 379                         const XmlTagObject *&son) const;
 380
 381                 /** Searches for a specific brother (identified by brotherInfoIndex)
 382                  *  of current.
 383                  *  Returns the brother via the referenced pointer brother.
 384                  *  Returns true if brother is found.
 385                  *  Returns false otherwise, brother is set to NULL.
 386                  */
 387                 bool findBrotherXmlTagObject(
 388                         const XmlTagObject &currentTag,
 389                         int brotherInfoIndex,
 390                         const XmlTagObject *&brother) const;
 391
 392                 /** Searches for a specific attribute (identified by attributeInfoIndex)
 393                  *  of current.
 394                  *  Returns the attribute via the referenced pointer attribute.
 395                  *  Returns true if attribute is found.
 396                  *  Returns false otherwise, attribute is set to NULL.
 397                  */
 398                 bool findXmlAttributeObject(
 399                         const XmlTagObject &currentTag,
 400                         int attributeInfoIndex,
 401                         const XmlAttributeObject *&attribute) const;
 402
 403                 /** Returns line number of the most recently read line of
 404                  *  the input file.
 405                  */
 406                 inline int getInputFileLineCounter() const {
 407                         return m_pScanner->getInputFileLineCounter();
 408                 }
 409
 410                 /** Prints the content of the hash table to os. */
 411                 void printHashTable(ostream &os);
 412
 413         private:
 414
 415                 /** Destroys the parse tree appended to root. */
 416                 void destroyParseTree(XmlTagObject *root);
 417
 418                 /** Parses the token stream provided by the scanner until a complete
 419                  *  XmlTagObject is identified which will be returned.
 420                  *  This function is likely to be called recursively
 421                  * due to the recursive structure of XML documents.
 422                  */
 423                 XmlTagObject* parse();
 424
 425                 /** Append attributeObject to list of attributes of tagObject. */
 426                 void appendAttributeObject(
 427                         XmlTagObject *tagObject,
 428                         XmlAttributeObject *attributeObject);
 429
 430                 /** Appends sonTagObject to the list of sons of currentTagObject. */
 431                 void appendSonTagObject(
 432                         XmlTagObject *currentTagObject,
 433                         XmlTagObject *sonTagObject);
 434
 435                 /** Returns the hash element for the given string.
 436                  *  If the key str is not contained in the table yet, it is
 437                  *  inserted together with a new info index and the new
 438                  *  hash element is returned.
 439                  *  If the key str exists, the associated hash element is returned.
 440                  */
 441                 HashedString *hashString(const String &str);
 442
 443                 /** Prints the given XmlTagObject and its children recursively.
 444                  *  The parameter indent is used as indentation value.
 445                  */
 446                 void printXmlTagObjectTree(
 447                         ostream &os,
 448                         const XmlTagObject &rootObject,
 449                         int indent = 0) const;
 450
 451                 /** Little helper that prints nOfSpaces space characters. */
 452                 void printSpaces(ostream &os, int nOfSpaces) const;
 453
 454         }; // class DinoXmlParser
 455
 456         /** Output operator for DinoXmlParser. */
 457         ostream &operator<<(ostream &os, const DinoXmlParser &parser);
 458
 459 } // end namespace ogdf
 460
 461 #endif