[5181] | 1 | /* |
---|
| 2 | * ORXONOX - the hottest 3D action shooter ever to exist |
---|
| 3 | * > www.orxonox.net < |
---|
| 4 | * |
---|
| 5 | * |
---|
| 6 | * License notice: |
---|
| 7 | * |
---|
| 8 | * This program is free software; you can redistribute it and/or |
---|
| 9 | * modify it under the terms of the GNU General Public License |
---|
| 10 | * as published by the Free Software Foundation; either version 2 |
---|
| 11 | * of the License, or (at your option) any later version. |
---|
| 12 | * |
---|
| 13 | * This program is distributed in the hope that it will be useful, |
---|
| 14 | * but WITHOUT ANY WARRANTY; without even the implied warranty of |
---|
| 15 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
---|
| 16 | * GNU General Public License for more details. |
---|
| 17 | * |
---|
| 18 | * You should have received a copy of the GNU General Public License |
---|
| 19 | * along with this program; if not, write to the Free Software |
---|
| 20 | * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. |
---|
| 21 | * |
---|
| 22 | * Author: |
---|
| 23 | * Fabian 'x3n' Landau |
---|
| 24 | * Co-authors: |
---|
| 25 | * ... |
---|
| 26 | * |
---|
| 27 | */ |
---|
| 28 | |
---|
| 29 | /** |
---|
| 30 | @file ClassTreeMask.cc |
---|
| 31 | @brief Implementation of the ClassTreeMask, ClassTreeMaskNode and ClassTreeMaskIterator classes. |
---|
| 32 | */ |
---|
| 33 | |
---|
| 34 | #include "ClassTreeMask.h" |
---|
| 35 | #include "Identifier.h" |
---|
| 36 | #include "BaseObject.h" |
---|
| 37 | |
---|
| 38 | namespace orxonox |
---|
| 39 | { |
---|
| 40 | // ############################### |
---|
| 41 | // ### ClassTreeMaskNode ### |
---|
| 42 | // ############################### |
---|
| 43 | /** |
---|
| 44 | @brief Constructor: Creates the node, sets the subclass and the rule. |
---|
| 45 | @param subclass The subclass the rule refers to |
---|
| 46 | @param bIncluded The rule: included (true) or excluded (false) |
---|
| 47 | */ |
---|
| 48 | ClassTreeMaskNode::ClassTreeMaskNode(const Identifier* subclass, bool bIncluded) |
---|
| 49 | { |
---|
| 50 | this->subclass_ = subclass; |
---|
| 51 | this->bIncluded_ = bIncluded; |
---|
| 52 | } |
---|
| 53 | |
---|
| 54 | /** |
---|
| 55 | @brief Destructor: Deletes all subnodes. |
---|
| 56 | */ |
---|
| 57 | ClassTreeMaskNode::~ClassTreeMaskNode() |
---|
| 58 | { |
---|
| 59 | // Go through the list of all subnodes and delete them |
---|
| 60 | this->deleteAllSubnodes(); |
---|
| 61 | } |
---|
| 62 | |
---|
| 63 | /** |
---|
| 64 | @brief Sets the rule for the node to "included". |
---|
| 65 | @param overwrite True = overwrite previously added rules for inheriting classes |
---|
| 66 | */ |
---|
| 67 | void ClassTreeMaskNode::include(bool overwrite) |
---|
| 68 | { |
---|
| 69 | this->setIncluded(true, overwrite); |
---|
| 70 | } |
---|
| 71 | |
---|
| 72 | /** |
---|
| 73 | @brief Sets the rule for the node to "excluded". |
---|
| 74 | @param overwrite True = overwrite previously added rules for inheriting classes |
---|
| 75 | */ |
---|
| 76 | void ClassTreeMaskNode::exclude(bool overwrite) |
---|
| 77 | { |
---|
| 78 | this->setIncluded(false, overwrite); |
---|
| 79 | } |
---|
| 80 | |
---|
| 81 | /** |
---|
| 82 | @brief Sets the rule for the node to a given value and erases all following rules. |
---|
| 83 | @param bIncluded The rule: included (true) or excluded (false) |
---|
| 84 | @param overwrite True = overwrite previously added rules for inheriting classes |
---|
| 85 | */ |
---|
| 86 | void ClassTreeMaskNode::setIncluded(bool bIncluded, bool overwrite) |
---|
| 87 | { |
---|
| 88 | if (overwrite) |
---|
| 89 | this->deleteAllSubnodes(); |
---|
| 90 | |
---|
| 91 | this->bIncluded_ = bIncluded; |
---|
| 92 | } |
---|
| 93 | |
---|
| 94 | /** |
---|
| 95 | @brief Adds a new subnode to the list of subnodes. |
---|
| 96 | @param subnode The new subnode |
---|
| 97 | */ |
---|
| 98 | void ClassTreeMaskNode::addSubnode(ClassTreeMaskNode* subnode) |
---|
| 99 | { |
---|
| 100 | this->subnodes_.insert(this->subnodes_.end(), subnode); |
---|
| 101 | } |
---|
| 102 | |
---|
| 103 | /** |
---|
| 104 | @brief Deletes all subnodes of this node. |
---|
| 105 | */ |
---|
| 106 | void ClassTreeMaskNode::deleteAllSubnodes() |
---|
| 107 | { |
---|
| 108 | // Go through the list of all subnodes and delete them |
---|
| 109 | for (std::list<ClassTreeMaskNode*>::iterator it = this->subnodes_.begin(); it != this->subnodes_.end(); ) |
---|
| 110 | delete (*(it++)); |
---|
| 111 | |
---|
| 112 | // Clear the list |
---|
| 113 | this->subnodes_.clear(); |
---|
| 114 | } |
---|
| 115 | |
---|
| 116 | |
---|
| 117 | // ############################### |
---|
| 118 | // ### ClassTreeMaskIterator ### |
---|
| 119 | // ############################### |
---|
| 120 | /** |
---|
| 121 | @brief Constructor: Initializes the iterator by creating a helper-list with the root-node and putting it to the stack. |
---|
| 122 | @param node The root-node |
---|
| 123 | */ |
---|
| 124 | ClassTreeMaskIterator::ClassTreeMaskIterator(ClassTreeMaskNode* node) |
---|
| 125 | { |
---|
| 126 | // Create a list and put the root-note into it |
---|
| 127 | std::list<ClassTreeMaskNode*>::iterator it = this->rootlist_.insert(this->rootlist_.end(), node); |
---|
| 128 | |
---|
| 129 | // Put the iterator to the only element of the list and the corresponding end()-iterator on the stack |
---|
| 130 | this->nodes_.push(std::pair<std::list<ClassTreeMaskNode*>::iterator, std::list<ClassTreeMaskNode*>::iterator>(it, this->rootlist_.end())); |
---|
| 131 | } |
---|
| 132 | |
---|
| 133 | /** |
---|
| 134 | @brief Destructor: Does nothing. |
---|
| 135 | */ |
---|
| 136 | ClassTreeMaskIterator::~ClassTreeMaskIterator() |
---|
| 137 | { |
---|
| 138 | } |
---|
| 139 | |
---|
| 140 | /** |
---|
| 141 | @brief Iterates through the rule-tree. |
---|
| 142 | @return A reference to the iterator itself |
---|
| 143 | */ |
---|
| 144 | const ClassTreeMaskIterator& ClassTreeMaskIterator::operator++() |
---|
| 145 | { |
---|
| 146 | // Check if the actual node has subnodes |
---|
| 147 | if ((*this->nodes_.top().first)->subnodes_.begin() != (*this->nodes_.top().first)->subnodes_.end()) |
---|
| 148 | { |
---|
| 149 | // Yes it has: Push an iterator, pointing at the first subnode, on the stack |
---|
| 150 | this->nodes_.push(std::pair<std::list<ClassTreeMaskNode*>::iterator, std::list<ClassTreeMaskNode*>::iterator>((*this->nodes_.top().first)->subnodes_.begin(), (*this->nodes_.top().first)->subnodes_.end())); |
---|
| 151 | } |
---|
| 152 | else |
---|
| 153 | { |
---|
| 154 | // No subnodes, meaning we reached a leaf: Go to the next node |
---|
| 155 | do |
---|
| 156 | { |
---|
| 157 | // Iterate one step in the current list |
---|
| 158 | ++this->nodes_.top().first; |
---|
| 159 | |
---|
| 160 | // Check if we reached the end of the list (the second item in the stored pair always represents the end) |
---|
| 161 | if (this->nodes_.top().first == this->nodes_.top().second) |
---|
| 162 | { |
---|
| 163 | // Yes we've reached the end: Pop the list-iterator from the stack |
---|
| 164 | this->nodes_.pop(); |
---|
| 165 | |
---|
| 166 | // Continue with the loop, meaning: Try to iterate through the previous list |
---|
| 167 | continue; |
---|
| 168 | } |
---|
| 169 | |
---|
| 170 | // If we reached this point, we aren't yet at the end of the list: Leave the loop |
---|
| 171 | break; |
---|
| 172 | } while (!this->nodes_.empty()); // Stop looping if the stack is empty, meaning: We've iterated to the end |
---|
| 173 | } |
---|
| 174 | |
---|
| 175 | // Finally return a reference to the iterator itself |
---|
| 176 | return *this; |
---|
| 177 | } |
---|
| 178 | |
---|
| 179 | /** |
---|
| 180 | @brief Returns a pointer to the ClassTreeMaskNode whereon the iterator points. |
---|
| 181 | @return The pointer to the node |
---|
| 182 | */ |
---|
| 183 | ClassTreeMaskNode* ClassTreeMaskIterator::operator*() const |
---|
| 184 | { |
---|
| 185 | return (*this->nodes_.top().first); |
---|
| 186 | } |
---|
| 187 | |
---|
| 188 | /** |
---|
| 189 | @brief Returns a pointer to the ClassTreeMaskNode whereon the iterator points. |
---|
| 190 | @return The pointer to the node |
---|
| 191 | */ |
---|
| 192 | ClassTreeMaskNode* ClassTreeMaskIterator::operator->() const |
---|
| 193 | { |
---|
| 194 | return (*this->nodes_.top().first); |
---|
| 195 | } |
---|
| 196 | |
---|
| 197 | /** |
---|
| 198 | @brief Returns true if the stack is empty, meaning we've reached the end of the tree. |
---|
| 199 | @return True if we've reached the end of the tree |
---|
| 200 | */ |
---|
| 201 | ClassTreeMaskIterator::operator bool() const |
---|
| 202 | { |
---|
| 203 | return (!this->nodes_.empty()); |
---|
| 204 | } |
---|
| 205 | |
---|
| 206 | /** |
---|
| 207 | @brief Compares the current node with the given one and returns true if they match. |
---|
| 208 | @param compare The node to compare with |
---|
| 209 | @return The result of the comparison (true if they match) |
---|
| 210 | */ |
---|
| 211 | bool ClassTreeMaskIterator::operator==(ClassTreeMaskNode* compare) const |
---|
| 212 | { |
---|
| 213 | if (!this->nodes_.empty()) |
---|
| 214 | return ((*this->nodes_.top().first) == compare); |
---|
| 215 | else |
---|
| 216 | return (compare == 0); |
---|
| 217 | } |
---|
| 218 | |
---|
| 219 | /** |
---|
| 220 | @brief Compares the current node with the given one and returns true if they don't match. |
---|
| 221 | @param compare The node to compare with |
---|
| 222 | @return The result of the comparison (true if they don't match) |
---|
| 223 | */ |
---|
| 224 | bool ClassTreeMaskIterator::operator!=(ClassTreeMaskNode* compare) const |
---|
| 225 | { |
---|
| 226 | if (!this->nodes_.empty()) |
---|
| 227 | return ((*this->nodes_.top().first) != compare); |
---|
| 228 | else |
---|
| 229 | return (compare != 0); |
---|
| 230 | } |
---|
| 231 | |
---|
| 232 | |
---|
| 233 | // ############################### |
---|
| 234 | // ### ClassTreeMask ### |
---|
| 235 | // ############################### |
---|
| 236 | /** |
---|
| 237 | @brief Constructor: Adds the root-node of the tree with the first rule ("include everything"). |
---|
| 238 | */ |
---|
| 239 | ClassTreeMask::ClassTreeMask() |
---|
| 240 | { |
---|
| 241 | this->root_ = new ClassTreeMaskNode(ClassIdentifier<BaseObject>::getIdentifier(), true); |
---|
| 242 | } |
---|
| 243 | |
---|
| 244 | /** |
---|
| 245 | @brief Copyconstructor: Adds the root-node of the tree with the first rule ("include everything") and adds all rules from the other mask. |
---|
| 246 | @param other The other mask |
---|
| 247 | */ |
---|
| 248 | ClassTreeMask::ClassTreeMask(const ClassTreeMask& other) |
---|
| 249 | { |
---|
| 250 | this->root_ = new ClassTreeMaskNode(ClassIdentifier<BaseObject>::getIdentifier(), true); |
---|
| 251 | for (ClassTreeMaskIterator it = other.root_; it; ++it) |
---|
| 252 | this->add(it->getClass(), it->isIncluded(), false); |
---|
| 253 | } |
---|
| 254 | |
---|
| 255 | /** |
---|
| 256 | @brief Destructor: Deletes the root node (which will delete all subnodes too). |
---|
| 257 | */ |
---|
| 258 | ClassTreeMask::~ClassTreeMask() |
---|
| 259 | { |
---|
| 260 | delete this->root_; |
---|
| 261 | } |
---|
| 262 | |
---|
| 263 | /** |
---|
| 264 | @brief Adds a new "include" rule for a given subclass to the mask. |
---|
| 265 | @param subclass The subclass |
---|
| 266 | @param overwrite True = overwrite previously added rules for inheriting classes |
---|
| 267 | @param clean True = clean the tree after adding the new rule |
---|
| 268 | */ |
---|
| 269 | void ClassTreeMask::include(const Identifier* subclass, bool overwrite, bool clean) |
---|
| 270 | { |
---|
| 271 | this->add(subclass, true, overwrite, clean); |
---|
| 272 | } |
---|
| 273 | |
---|
| 274 | /** |
---|
| 275 | @brief Adds a new "exclude" rule for a given subclass to the mask. |
---|
| 276 | @param subclass The subclass |
---|
| 277 | @param overwrite True = overwrite previously added rules for inheriting classes |
---|
| 278 | @param clean True = clean the tree after adding the new rule |
---|
| 279 | */ |
---|
| 280 | void ClassTreeMask::exclude(const Identifier* subclass, bool overwrite, bool clean) |
---|
| 281 | { |
---|
| 282 | this->add(subclass, false, overwrite, clean); |
---|
| 283 | } |
---|
| 284 | |
---|
| 285 | /** |
---|
| 286 | @brief Adds a new rule for a given subclass to the mask. |
---|
| 287 | @param subclass The subclass |
---|
| 288 | @param bInclude The rule: include (true) or exclude (false) |
---|
| 289 | @param overwrite True = overwrite previously added rules for inheriting classes |
---|
| 290 | @param clean True = clean the tree after adding the new rule |
---|
| 291 | */ |
---|
| 292 | void ClassTreeMask::add(const Identifier* subclass, bool bInclude, bool overwrite, bool clean) |
---|
| 293 | { |
---|
| 294 | // Check if the given subclass is a child of our root-class |
---|
| 295 | if (subclass->isA(this->root_->getClass())) |
---|
| 296 | { |
---|
| 297 | // Yes it is: Just add the rule to the three |
---|
| 298 | this->add(this->root_, subclass, bInclude, overwrite); |
---|
| 299 | } |
---|
| 300 | else |
---|
| 301 | { |
---|
| 302 | // No it's not: Search for classes inheriting from the given class and add the rules for them |
---|
| 303 | for (std::set<const Identifier*>::const_iterator it = subclass->getDirectChildrenBegin(); it != subclass->getDirectChildrenEnd(); ++it) |
---|
| 304 | if ((*it)->isA(this->root_->getClass())) |
---|
| 305 | if (overwrite || (!this->nodeExists(*it))) // If we don't want to overwrite, only add nodes that don't already exist |
---|
| 306 | this->add(this->root_, *it, bInclude, overwrite); |
---|
| 307 | } |
---|
| 308 | |
---|
| 309 | // Clean the rule-tree |
---|
| 310 | if (clean) |
---|
| 311 | this->clean(); |
---|
| 312 | } |
---|
| 313 | |
---|
| 314 | /** |
---|
| 315 | @brief Adds a new rule for a given subclass to a node of the internal rule-tree (recursive function). |
---|
| 316 | @param node The node |
---|
| 317 | @param subclass The subclass |
---|
| 318 | @param bInclude The rule: include (true) or exclude (false) |
---|
| 319 | @param overwrite True = overwrite previously added rules for inheriting classes |
---|
| 320 | */ |
---|
| 321 | void ClassTreeMask::add(ClassTreeMaskNode* node, const Identifier* subclass, bool bInclude, bool overwrite) |
---|
| 322 | { |
---|
| 323 | // Check if the current node contains exactly the subclass we want to add |
---|
| 324 | if (subclass == node->getClass()) |
---|
| 325 | { |
---|
| 326 | // We're at the right place, just change the mask and return |
---|
| 327 | node->setIncluded(bInclude, overwrite); |
---|
| 328 | return; |
---|
| 329 | } |
---|
| 330 | else if (subclass->isA(node->getClass())) |
---|
| 331 | { |
---|
| 332 | // Search for an already existing node, containing the subclass we want to add |
---|
| 333 | for (std::list<ClassTreeMaskNode*>::iterator it = node->subnodes_.begin(); it != node->subnodes_.end(); ++it) |
---|
| 334 | { |
---|
| 335 | if (subclass->isA((*it)->getClass())) |
---|
| 336 | { |
---|
| 337 | // We've found an existing node -> delegate the work with a recursive function-call and return |
---|
| 338 | this->add(*it, subclass, bInclude, overwrite); |
---|
| 339 | return; |
---|
| 340 | } |
---|
| 341 | } |
---|
| 342 | |
---|
| 343 | // There is no existing node satisfying our needs -> we create a new node |
---|
| 344 | ClassTreeMaskNode* newnode = new ClassTreeMaskNode(subclass, bInclude); |
---|
| 345 | |
---|
| 346 | // Search for nodes that should actually be subnodes of our new node and erase them |
---|
| 347 | for (std::list<ClassTreeMaskNode*>::iterator it = node->subnodes_.begin(); it != node->subnodes_.end(); ) |
---|
| 348 | { |
---|
| 349 | if ((*it)->getClass()->isChildOf(subclass)) |
---|
| 350 | { |
---|
| 351 | // We've found a subnode: add it to the new node and erase it from the current node |
---|
| 352 | if (!overwrite) |
---|
| 353 | newnode->addSubnode(*it); |
---|
| 354 | else |
---|
| 355 | delete (*it); |
---|
| 356 | |
---|
| 357 | node->subnodes_.erase(it++); |
---|
| 358 | } |
---|
| 359 | else |
---|
| 360 | { |
---|
| 361 | ++it; |
---|
| 362 | } |
---|
| 363 | } |
---|
| 364 | |
---|
| 365 | // Finally add the new node as a subnode to the current node |
---|
| 366 | node->addSubnode(newnode); |
---|
| 367 | } |
---|
| 368 | } |
---|
| 369 | |
---|
| 370 | /** |
---|
| 371 | @brief Adds a new "include" rule for a single subclass. The new rule doesn't change the mask for inheriting classes. |
---|
| 372 | @param subclass The subclass |
---|
| 373 | @param clean True = clean the tree after adding the new rule |
---|
| 374 | */ |
---|
| 375 | void ClassTreeMask::includeSingle(const Identifier* subclass, bool clean) |
---|
| 376 | { |
---|
| 377 | this->addSingle(subclass, true, clean); |
---|
| 378 | } |
---|
| 379 | |
---|
| 380 | /** |
---|
| 381 | @brief Adds a new "exclude" rule for a single subclass. The new rule doesn't change the mask for inheriting classes. |
---|
| 382 | @param subclass The subclass |
---|
| 383 | @param clean True = clean the tree after adding the new rule |
---|
| 384 | */ |
---|
| 385 | void ClassTreeMask::excludeSingle(const Identifier* subclass, bool clean) |
---|
| 386 | { |
---|
| 387 | this->addSingle(subclass, false, clean); |
---|
| 388 | } |
---|
| 389 | |
---|
| 390 | /** |
---|
| 391 | @brief Adds a new rule for a single subclass. The new rule doesn't change the mask for inheriting classes. |
---|
| 392 | @param bInclude The rule: include (true) or exclude (false) |
---|
| 393 | @param subclass The subclass |
---|
| 394 | @param clean True = clean the tree after adding the new rule |
---|
| 395 | */ |
---|
| 396 | void ClassTreeMask::addSingle(const Identifier* subclass, bool bInclude, bool clean) |
---|
| 397 | { |
---|
| 398 | for (std::set<const Identifier*>::const_iterator it = subclass->getDirectChildrenBegin(); it != subclass->getDirectChildrenEnd(); ++it) |
---|
| 399 | this->add(*it, this->isIncluded(*it), false, false); |
---|
| 400 | |
---|
| 401 | this->add(subclass, bInclude, false, clean); |
---|
| 402 | } |
---|
| 403 | |
---|
| 404 | /** |
---|
| 405 | @brief Resets the mask to "include everything". |
---|
| 406 | */ |
---|
| 407 | void ClassTreeMask::reset() |
---|
| 408 | { |
---|
| 409 | delete this->root_; |
---|
| 410 | this->root_ = new ClassTreeMaskNode(ClassIdentifier<BaseObject>::getIdentifier(), true); |
---|
| 411 | } |
---|
| 412 | |
---|
| 413 | /** |
---|
| 414 | @brief Tells if a given subclass is included or not. |
---|
| 415 | @param subclass The subclass |
---|
| 416 | @return Included (true) or excluded (false) |
---|
| 417 | */ |
---|
| 418 | bool ClassTreeMask::isIncluded(const Identifier* subclass) const |
---|
| 419 | { |
---|
| 420 | return this->isIncluded(this->root_, subclass); |
---|
| 421 | } |
---|
| 422 | |
---|
| 423 | /** |
---|
| 424 | @brief Tells if a given subclass of a node in the rule-tree is included or not (recursive function). |
---|
| 425 | @param node The node |
---|
| 426 | @param subclass The subclass |
---|
| 427 | @return Included (true) or excluded (false) |
---|
| 428 | */ |
---|
| 429 | bool ClassTreeMask::isIncluded(ClassTreeMaskNode* node, const Identifier* subclass) const |
---|
| 430 | { |
---|
| 431 | // Check if the searched subclass is of the same type as the class in the current node or a derivative |
---|
| 432 | if (subclass->isA(node->getClass())) |
---|
| 433 | { |
---|
| 434 | // Check for the special case |
---|
| 435 | if (subclass == node->getClass()) |
---|
| 436 | return node->isIncluded(); |
---|
| 437 | |
---|
| 438 | // Go through the list of subnodes and look for a node containing the searched subclass and delegate the request by a recursive function-call. |
---|
| 439 | for (std::list<ClassTreeMaskNode*>::iterator it = node->subnodes_.begin(); it != node->subnodes_.end(); ++it) |
---|
| 440 | if (subclass->isA((*it)->getClass())) |
---|
| 441 | return isIncluded(*it, subclass); |
---|
| 442 | |
---|
| 443 | // There is no subnode containing our class -> the rule of the current node takes in effect |
---|
| 444 | return node->isIncluded(); |
---|
| 445 | } |
---|
| 446 | else |
---|
| 447 | { |
---|
| 448 | // The class is not included in the mask: return false |
---|
| 449 | return false; |
---|
| 450 | } |
---|
| 451 | } |
---|
| 452 | |
---|
| 453 | /** |
---|
| 454 | @brief Tells if a given subclass is excluded or not. |
---|
| 455 | @param subclass The subclass |
---|
| 456 | @return The inverted rule: Excluded (true) or included (false) |
---|
| 457 | */ |
---|
| 458 | bool ClassTreeMask::isExcluded(const Identifier* subclass) const |
---|
| 459 | { |
---|
| 460 | return (!this->isIncluded(subclass)); |
---|
| 461 | } |
---|
| 462 | |
---|
| 463 | /** |
---|
| 464 | @brief Removes all unneeded rules that don't change the information of the mask. |
---|
| 465 | */ |
---|
| 466 | void ClassTreeMask::clean() |
---|
| 467 | { |
---|
| 468 | this->clean(this->root_); |
---|
| 469 | } |
---|
| 470 | |
---|
| 471 | /** |
---|
| 472 | @brief Removes all unneded rules that don't change the information of a node of a mask (recursive function). |
---|
| 473 | @param node The node |
---|
| 474 | */ |
---|
| 475 | void ClassTreeMask::clean(ClassTreeMaskNode* node) |
---|
| 476 | { |
---|
| 477 | // Iterate through all subnodes of the given node |
---|
| 478 | for (std::list<ClassTreeMaskNode*>::iterator it = node->subnodes_.begin(); it != node->subnodes_.end(); ) |
---|
| 479 | { |
---|
| 480 | // Recursive function-call: Clean the subnode |
---|
| 481 | this->clean(*it); |
---|
| 482 | |
---|
| 483 | // Now check if the subnode contains the same rule as the current node |
---|
| 484 | if ((*it)->isIncluded() == node->isIncluded()) |
---|
| 485 | { |
---|
| 486 | // It does: Move all subnodes of the redundant subnode to the current node |
---|
| 487 | node->subnodes_.insert(node->subnodes_.end(), (*it)->subnodes_.begin(), (*it)->subnodes_.end()); |
---|
| 488 | (*it)->subnodes_.clear(); |
---|
| 489 | |
---|
| 490 | // Remove the redundant subnode from the current node |
---|
| 491 | node->subnodes_.erase(it++); |
---|
| 492 | } |
---|
| 493 | else |
---|
| 494 | { |
---|
| 495 | // The subnode is necessary: Move on to the next subnode |
---|
| 496 | ++it; |
---|
| 497 | } |
---|
| 498 | } |
---|
| 499 | } |
---|
| 500 | |
---|
| 501 | /** |
---|
| 502 | @brief Checks if a node for the given subclass exists. |
---|
| 503 | @param subclass The Identifier of the subclass |
---|
| 504 | @return True = the node exists |
---|
| 505 | */ |
---|
| 506 | bool ClassTreeMask::nodeExists(const Identifier* subclass) |
---|
| 507 | { |
---|
| 508 | for (ClassTreeMaskIterator it = this->root_; it; ++it) |
---|
| 509 | if ((*it)->getClass() == subclass) |
---|
| 510 | return true; |
---|
| 511 | |
---|
| 512 | return false; |
---|
| 513 | } |
---|
| 514 | |
---|
| 515 | /** |
---|
| 516 | @brief Assignment operator: Adds all rules of the other mask. |
---|
| 517 | @param other The other mask |
---|
| 518 | @return A reference to the mask itself |
---|
| 519 | */ |
---|
| 520 | const ClassTreeMask& ClassTreeMask::operator=(const ClassTreeMask& other) |
---|
| 521 | { |
---|
| 522 | // Make a copy to avoid troubles with self-assignments (like A = A). |
---|
| 523 | ClassTreeMask temp(other); |
---|
| 524 | |
---|
| 525 | // Removes all current rules |
---|
| 526 | this->reset(); |
---|
| 527 | |
---|
| 528 | // Copy all rules from the other mask |
---|
| 529 | for (ClassTreeMaskIterator it = temp.root_; it; ++it) |
---|
| 530 | this->add(it->getClass(), it->isIncluded(), false, false); |
---|
| 531 | |
---|
| 532 | // Return a reference to the mask itself |
---|
| 533 | return (*this); |
---|
| 534 | } |
---|
| 535 | |
---|
| 536 | /** |
---|
| 537 | @brief Compares the mask with another mask and returns true if they represent the same logic. |
---|
| 538 | @param other The other mask |
---|
| 539 | @return True if both masks represent the same logic |
---|
| 540 | */ |
---|
| 541 | bool ClassTreeMask::operator==(const ClassTreeMask& other) const |
---|
| 542 | { |
---|
| 543 | ClassTreeMask temp1 = other; |
---|
| 544 | ClassTreeMask temp2 = (*this); |
---|
| 545 | |
---|
| 546 | temp1.clean(); |
---|
| 547 | temp2.clean(); |
---|
| 548 | |
---|
| 549 | ClassTreeMaskIterator it1 = temp1.root_; |
---|
| 550 | ClassTreeMaskIterator it2 = temp2.root_; |
---|
| 551 | |
---|
| 552 | for ( ; it1 && it2; ++it1, ++it2) |
---|
| 553 | if (it1->getClass() != it2->getClass()) |
---|
| 554 | return false; |
---|
| 555 | |
---|
| 556 | return true; |
---|
| 557 | } |
---|
| 558 | |
---|
| 559 | /** |
---|
| 560 | @brief Compares the mask with another mask and returns true if they represent different logics. |
---|
| 561 | @param other The other mask |
---|
| 562 | @return True if the masks represent different logics |
---|
| 563 | */ |
---|
| 564 | bool ClassTreeMask::operator!=(const ClassTreeMask& other) const |
---|
| 565 | { |
---|
| 566 | return (!((*this) == other)); |
---|
| 567 | } |
---|
| 568 | |
---|
| 569 | /** |
---|
| 570 | @brief Prefix operator + does nothing. |
---|
| 571 | @return A reference to the mask itself |
---|
| 572 | */ |
---|
| 573 | const ClassTreeMask& ClassTreeMask::operator+() const |
---|
| 574 | { |
---|
| 575 | return (*this); |
---|
| 576 | } |
---|
| 577 | |
---|
| 578 | /** |
---|
| 579 | @brief Prefix operator - inverts the mask. |
---|
| 580 | @return The inverted mask |
---|
| 581 | */ |
---|
| 582 | ClassTreeMask ClassTreeMask::operator-() const |
---|
| 583 | { |
---|
| 584 | return (!(*this)); |
---|
| 585 | } |
---|
| 586 | |
---|
| 587 | /** |
---|
| 588 | @brief Adds two masks in the sense of a union (all classes that are included in at least one of the masks will be included in the resulting mask too). |
---|
| 589 | @param other The mask to unite with |
---|
| 590 | @return The union |
---|
| 591 | */ |
---|
| 592 | ClassTreeMask ClassTreeMask::operator+(const ClassTreeMask& other) const |
---|
| 593 | { |
---|
| 594 | // Create a new mask |
---|
| 595 | ClassTreeMask newmask; |
---|
| 596 | |
---|
| 597 | // Add all nodes from the first mask, calculate the rule with the or-operation |
---|
| 598 | for (ClassTreeMaskIterator it = this->root_; it; ++it) |
---|
| 599 | { |
---|
| 600 | const Identifier* subclass = it->getClass(); |
---|
| 601 | newmask.add(subclass, this->isIncluded(subclass) or other.isIncluded(subclass), false, false); |
---|
| 602 | } |
---|
| 603 | |
---|
| 604 | // Add all nodes from the second mask, calculate the rule with the or-operation |
---|
| 605 | for (ClassTreeMaskIterator it = other.root_; it; ++it) |
---|
| 606 | { |
---|
| 607 | const Identifier* subclass = it->getClass(); |
---|
| 608 | newmask.add(subclass, this->isIncluded(subclass) or other.isIncluded(subclass), false, false); |
---|
| 609 | } |
---|
| 610 | |
---|
| 611 | // Drop all redundant rules |
---|
| 612 | newmask.clean(); |
---|
| 613 | |
---|
| 614 | // Return the new mask |
---|
| 615 | return newmask; |
---|
| 616 | } |
---|
| 617 | |
---|
| 618 | /** |
---|
| 619 | @brief Intersects two masks (only classes that are included in both masks will be included in the resulting mask too). |
---|
| 620 | @param other The mask to intersect with |
---|
| 621 | @return The intersection |
---|
| 622 | */ |
---|
| 623 | ClassTreeMask ClassTreeMask::operator*(const ClassTreeMask& other) const |
---|
| 624 | { |
---|
| 625 | // Create a new mask |
---|
| 626 | ClassTreeMask newmask; |
---|
| 627 | |
---|
| 628 | // Add all nodes from the first mask, calculate the rule with the and-operation |
---|
| 629 | for (ClassTreeMaskIterator it = this->root_; it; ++it) |
---|
| 630 | { |
---|
| 631 | const Identifier* subclass = it->getClass(); |
---|
| 632 | newmask.add(subclass, this->isIncluded(subclass) and other.isIncluded(subclass), false, false); |
---|
| 633 | } |
---|
| 634 | |
---|
| 635 | // Add all nodes from the second mask, calculate the rule with the and-operation |
---|
| 636 | for (ClassTreeMaskIterator it = other.root_; it; ++it) |
---|
| 637 | { |
---|
| 638 | const Identifier* subclass = it->getClass(); |
---|
| 639 | newmask.add(subclass, this->isIncluded(subclass) and other.isIncluded(subclass), false, false); |
---|
| 640 | } |
---|
| 641 | |
---|
| 642 | // Drop all redundant rules |
---|
| 643 | newmask.clean(); |
---|
| 644 | |
---|
| 645 | // Return the new mask |
---|
| 646 | return newmask; |
---|
| 647 | } |
---|
| 648 | |
---|
| 649 | /** |
---|
| 650 | @brief Removes all elements of the second mask from the first mask (all classes that are included in the first mask stay included, except those that are included in the second mask too). |
---|
| 651 | @param other The mask to subtract. |
---|
| 652 | @return The difference |
---|
| 653 | */ |
---|
| 654 | ClassTreeMask ClassTreeMask::operator-(const ClassTreeMask& other) const |
---|
| 655 | { |
---|
| 656 | return ((*this) * (!other)); |
---|
| 657 | } |
---|
| 658 | |
---|
| 659 | /** |
---|
| 660 | @brief Inverts the mask (all included classes are now excluded and vice versa). |
---|
| 661 | @return The complement |
---|
| 662 | */ |
---|
| 663 | ClassTreeMask ClassTreeMask::operator!() const |
---|
| 664 | { |
---|
| 665 | // Create a new mask |
---|
| 666 | ClassTreeMask newmask; |
---|
| 667 | |
---|
| 668 | // Add all nodes from the other mask, inverting the rules |
---|
| 669 | for (ClassTreeMaskIterator it = this->root_; it; ++it) |
---|
| 670 | { |
---|
| 671 | const Identifier* subclass = it->getClass(); |
---|
| 672 | newmask.add(subclass, !this->isIncluded(subclass), false, false); |
---|
| 673 | } |
---|
| 674 | |
---|
| 675 | // Return the new mask |
---|
| 676 | return newmask; |
---|
| 677 | } |
---|
| 678 | |
---|
| 679 | /** |
---|
| 680 | @brief Unites this mask with another mask. |
---|
| 681 | @param other The other mask |
---|
| 682 | @return A reference to the mask itself |
---|
| 683 | */ |
---|
| 684 | const ClassTreeMask& ClassTreeMask::operator+=(const ClassTreeMask& other) |
---|
| 685 | { |
---|
| 686 | (*this) = (*this) + other; |
---|
| 687 | return (*this); |
---|
| 688 | } |
---|
| 689 | |
---|
| 690 | /** |
---|
| 691 | @brief Intersects this mask with another mask. |
---|
| 692 | @param other The other mask |
---|
| 693 | @return A reference to the mask itself |
---|
| 694 | */ |
---|
| 695 | const ClassTreeMask& ClassTreeMask::operator*=(const ClassTreeMask& other) |
---|
| 696 | { |
---|
| 697 | (*this) = (*this) * other; |
---|
| 698 | return (*this); |
---|
| 699 | } |
---|
| 700 | |
---|
| 701 | /** |
---|
| 702 | @brief Subtracts another mask from this mask. |
---|
| 703 | @param other The other mask |
---|
| 704 | @return A reference to the mask itself |
---|
| 705 | */ |
---|
| 706 | const ClassTreeMask& ClassTreeMask::operator-=(const ClassTreeMask& other) |
---|
| 707 | { |
---|
| 708 | (*this) = (*this) - other; |
---|
| 709 | return (*this); |
---|
| 710 | } |
---|
| 711 | |
---|
| 712 | /** |
---|
| 713 | @brief Intersects two masks (only classes that are included in both masks will be included in the resulting mask too). |
---|
| 714 | @param other The mask to intersect with |
---|
| 715 | @return The intersection |
---|
| 716 | */ |
---|
| 717 | ClassTreeMask ClassTreeMask::operator&(const ClassTreeMask& other) const |
---|
| 718 | { |
---|
| 719 | return ((*this) * other); |
---|
| 720 | } |
---|
| 721 | |
---|
| 722 | /** |
---|
| 723 | @brief Adds two masks in the sense of a union (all classes that are included in at least one of the masks will be included in the resulting mask too). |
---|
| 724 | @param other The mask to unite with |
---|
| 725 | @return The union |
---|
| 726 | */ |
---|
| 727 | ClassTreeMask ClassTreeMask::operator|(const ClassTreeMask& other) const |
---|
| 728 | { |
---|
| 729 | return ((*this) + other); |
---|
| 730 | } |
---|
| 731 | |
---|
| 732 | /** |
---|
| 733 | @brief Joins two masks in the sense of a xor (exclusivity) operation (all classes that are included in exactly one of the masks, but not in both, will be included in the resulting mask too). |
---|
| 734 | @param other The mask to join with |
---|
| 735 | @return The result |
---|
| 736 | */ |
---|
| 737 | ClassTreeMask ClassTreeMask::operator^(const ClassTreeMask& other) const |
---|
| 738 | { |
---|
| 739 | // Create a new mask |
---|
| 740 | ClassTreeMask newmask; |
---|
| 741 | |
---|
| 742 | // Add all nodes from the first mask, calculate the rule with the xor-operation |
---|
| 743 | for (ClassTreeMaskIterator it = this->root_; it; ++it) |
---|
| 744 | { |
---|
| 745 | const Identifier* subclass = it->getClass(); |
---|
| 746 | newmask.add(subclass, this->isIncluded(subclass) xor other.isIncluded(subclass), false, false); |
---|
| 747 | } |
---|
| 748 | |
---|
| 749 | // Add all nodes from the second mask, calculate the rule with the xor-operation |
---|
| 750 | for (ClassTreeMaskIterator it = other.root_; it; ++it) |
---|
| 751 | { |
---|
| 752 | const Identifier* subclass = it->getClass(); |
---|
| 753 | newmask.add(subclass, this->isIncluded(subclass) xor other.isIncluded(subclass), false, false); |
---|
| 754 | } |
---|
| 755 | |
---|
| 756 | // Drop all redundant rules |
---|
| 757 | newmask.clean(); |
---|
| 758 | |
---|
| 759 | // Return the new mask |
---|
| 760 | return newmask; |
---|
| 761 | } |
---|
| 762 | |
---|
| 763 | /** |
---|
| 764 | @brief Inverts the mask (all included classes are now excluded and vice versa). |
---|
| 765 | @return The complement |
---|
| 766 | */ |
---|
| 767 | ClassTreeMask ClassTreeMask::operator~() const |
---|
| 768 | { |
---|
| 769 | return (!(*this)); |
---|
| 770 | } |
---|
| 771 | |
---|
| 772 | /** |
---|
| 773 | @brief Intersects this mask with another mask (and-operation) |
---|
| 774 | @param other The other mask |
---|
| 775 | @return A reference to the mask itself |
---|
| 776 | */ |
---|
| 777 | const ClassTreeMask& ClassTreeMask::operator&=(const ClassTreeMask& other) |
---|
| 778 | { |
---|
| 779 | (*this) = (*this) & other; |
---|
| 780 | return (*this); |
---|
| 781 | } |
---|
| 782 | |
---|
| 783 | /** |
---|
| 784 | @brief Unites this mask with another mask (or-operation). |
---|
| 785 | @param other The other mask |
---|
| 786 | @return A reference to the mask itself |
---|
| 787 | */ |
---|
| 788 | const ClassTreeMask& ClassTreeMask::operator|=(const ClassTreeMask& other) |
---|
| 789 | { |
---|
| 790 | (*this) = (*this) | other; |
---|
| 791 | return (*this); |
---|
| 792 | } |
---|
| 793 | |
---|
| 794 | /** |
---|
| 795 | @brief Joins this mask with another mask with a xor-operation. |
---|
| 796 | @param other The other mask |
---|
| 797 | @return A reference to the mask itself |
---|
| 798 | */ |
---|
| 799 | const ClassTreeMask& ClassTreeMask::operator^=(const ClassTreeMask& other) |
---|
| 800 | { |
---|
| 801 | (*this) = (*this) ^ other; |
---|
| 802 | return (*this); |
---|
| 803 | } |
---|
| 804 | |
---|
| 805 | /** |
---|
| 806 | @brief Converts the content of a mask into a human readable string and puts it on the ostream. |
---|
| 807 | @param out The ostream |
---|
| 808 | @param mask The mask |
---|
| 809 | @return A reference to the ostream |
---|
| 810 | */ |
---|
| 811 | std::ostream& operator<<(std::ostream& out, const ClassTreeMask& mask) |
---|
| 812 | { |
---|
| 813 | // Iterate through all rules |
---|
| 814 | for (ClassTreeMaskIterator it = mask.root_; it; ++it) |
---|
| 815 | { |
---|
| 816 | // Calculate the prefix: + means included, - means excluded |
---|
| 817 | if (it->isIncluded()) |
---|
| 818 | out << "+"; |
---|
| 819 | else |
---|
| 820 | out << "-"; |
---|
| 821 | |
---|
| 822 | // Put the name of the corresponding class on the stream |
---|
| 823 | out << it->getClass()->getName() << " "; |
---|
| 824 | } |
---|
| 825 | |
---|
| 826 | return out; |
---|
| 827 | } |
---|
| 828 | |
---|
| 829 | |
---|
| 830 | // ################################### |
---|
| 831 | // ### ClassTreeMaskObjectIterator ### |
---|
| 832 | // ################################### |
---|
| 833 | /** |
---|
| 834 | @brief Initializes the iterator from a given ClassTreeMask. |
---|
| 835 | @param mask The mask |
---|
| 836 | */ |
---|
| 837 | const ClassTreeMaskObjectIterator& ClassTreeMaskObjectIterator::operator=(const ClassTreeMask& mask) |
---|
| 838 | { |
---|
| 839 | // Clear everything, use a cleaned copy of the mask |
---|
| 840 | this->subclasses_.clear(); |
---|
| 841 | ClassTreeMask temp = mask; |
---|
| 842 | temp.clean(); |
---|
| 843 | |
---|
| 844 | // Create the subclass-list by going through the mask-tree, starting with the root-node |
---|
| 845 | this->create(temp.root_); |
---|
| 846 | |
---|
| 847 | // Move the subclass-iterator to the beginning of the subclass-list |
---|
| 848 | this->subclassIterator_ = this->subclasses_.begin(); |
---|
| 849 | |
---|
| 850 | // If there is a first subclass, move the object-iterator to the first object of this class. Else go to the end |
---|
| 851 | if (this->subclassIterator_ != this->subclasses_.end()) |
---|
| 852 | this->objectIterator_ = (*this->subclassIterator_).first->getObjects()->begin(); |
---|
| 853 | else |
---|
| 854 | this->objectIterator_ = ObjectList<BaseObject>::end(); |
---|
| 855 | |
---|
| 856 | // Check if the iterator points on a valid object. If not, go to the next object by calling ++ |
---|
| 857 | if (!this->objectIterator_ || ((*this->subclassIterator_).second && !this->objectIterator_->isExactlyA((*this->subclassIterator_).first))) |
---|
| 858 | this->operator++(); |
---|
| 859 | |
---|
| 860 | return (*this); |
---|
| 861 | } |
---|
| 862 | |
---|
| 863 | /** |
---|
| 864 | @brief Iterate to the next object (if any). |
---|
| 865 | @return The iterator itself |
---|
| 866 | */ |
---|
| 867 | const ClassTreeMaskObjectIterator& ClassTreeMaskObjectIterator::operator++() |
---|
| 868 | { |
---|
| 869 | if (this->objectIterator_) |
---|
| 870 | { |
---|
| 871 | // The iterator points on a valid object, therefore we also have a valid subclass-iterator at the moment |
---|
| 872 | do |
---|
| 873 | { |
---|
| 874 | // Go to the next object |
---|
| 875 | ++this->objectIterator_; |
---|
| 876 | |
---|
| 877 | while (!this->objectIterator_) |
---|
| 878 | { |
---|
| 879 | // We reached the end of the current objectlist - go to the next class |
---|
| 880 | ++this->subclassIterator_; |
---|
| 881 | |
---|
| 882 | // Check if there really is a next class. If yes, move the object-iterator to the first object |
---|
| 883 | if (this->subclassIterator_ != this->subclasses_.end()) |
---|
| 884 | this->objectIterator_ = (*this->subclassIterator_).first->getObjects()->begin(); |
---|
| 885 | else |
---|
| 886 | return (*this); |
---|
| 887 | } |
---|
| 888 | |
---|
| 889 | // Repeat this until we reach a valid object or the end |
---|
| 890 | } while ((*this->subclassIterator_).second && !this->objectIterator_->isExactlyA((*this->subclassIterator_).first)); |
---|
| 891 | } |
---|
| 892 | return (*this); |
---|
| 893 | } |
---|
| 894 | |
---|
| 895 | /** |
---|
| 896 | @brief Recursive function to create the Iterators subclass-list by going through the node-tree of the mask. |
---|
| 897 | @param node The current node |
---|
| 898 | */ |
---|
| 899 | void ClassTreeMaskObjectIterator::create(ClassTreeMaskNode* node) |
---|
| 900 | { |
---|
| 901 | // Add the class of this node to the list, if the class is included |
---|
| 902 | if (node->isIncluded()) |
---|
| 903 | { |
---|
| 904 | // If there are some subnodes, the bool is "true", meaning we have to check for the exact clss when iterating |
---|
| 905 | if (node->hasSubnodes()) |
---|
| 906 | this->subclasses_.insert(this->subclasses_.end(), std::pair<const Identifier*, bool>(node->getClass(), true)); |
---|
| 907 | else |
---|
| 908 | this->subclasses_.insert(this->subclasses_.end(), std::pair<const Identifier*, bool>(node->getClass(), false)); |
---|
| 909 | } |
---|
| 910 | |
---|
| 911 | // Now check if the node has subnodes |
---|
| 912 | if (node->hasSubnodes()) |
---|
| 913 | { |
---|
| 914 | // Get all _direct_ children of the nodes class |
---|
| 915 | std::set<const Identifier*> directChildren = node->getClass()->getDirectChildren(); |
---|
| 916 | |
---|
| 917 | // Iterate through all subnodes |
---|
| 918 | for (std::list<ClassTreeMaskNode*>::iterator it1 = node->subnodes_.begin(); it1 != node->subnodes_.end(); ++it1) |
---|
| 919 | { |
---|
| 920 | // Recursive call to this function with the subnode |
---|
| 921 | this->create(*it1); |
---|
| 922 | |
---|
| 923 | // Only execute the following code if the current node is included, meaning some of the subnodes might be included too |
---|
| 924 | if (node->isIncluded()) |
---|
| 925 | { |
---|
| 926 | scanChildren: // This is a label for goto |
---|
| 927 | |
---|
| 928 | // Iterate through all direct children |
---|
| 929 | for (std::set<const Identifier*>::iterator it2 = directChildren.begin(); it2 != directChildren.end(); ++it2) |
---|
| 930 | { |
---|
| 931 | // Check if the subnode (it1) is a child of the directChild (it2) |
---|
| 932 | if ((*it1)->getClass()->isA(*it2)) |
---|
| 933 | { |
---|
| 934 | // Yes it is - remove the directChild (it2) from the list, because it will already be handled by a recursive call to the create() function |
---|
| 935 | directChildren.erase(it2); |
---|
| 936 | |
---|
| 937 | // Check if the removed directChild was exactly the subnode |
---|
| 938 | if (!(*it1)->getClass()->isExactlyA(*it2)) |
---|
| 939 | { |
---|
| 940 | // No, it wasn't exactly the subnode - therefore there are some classes between |
---|
| 941 | |
---|
| 942 | // Add the previously removed directChild (it2) to the subclass-list |
---|
| 943 | this->subclasses_.insert(this->subclasses_.end(), std::pair<const Identifier*, bool>(*it2, true)); |
---|
| 944 | |
---|
| 945 | // Insert all directChildren of the directChild |
---|
| 946 | directChildren.insert((*it2)->getDirectChildrenBegin(), (*it2)->getDirectChildrenEnd()); |
---|
| 947 | |
---|
| 948 | // Restart the scan with the expanded set of directChildren |
---|
| 949 | goto scanChildren; |
---|
| 950 | } |
---|
| 951 | break; |
---|
| 952 | } |
---|
| 953 | } |
---|
| 954 | } |
---|
| 955 | } |
---|
| 956 | |
---|
| 957 | // Now add all directChildren which don't have subnodes on their own to the subclass-list |
---|
| 958 | // The bool is "false", meaning they have no subnodes and therefore need no further checks |
---|
| 959 | if (node->isIncluded()) |
---|
| 960 | for (std::set<const Identifier*>::iterator it = directChildren.begin(); it != directChildren.end(); ++it) |
---|
| 961 | this->subclasses_.insert(this->subclasses_.end(), std::pair<const Identifier*, bool>(*it, false)); |
---|
| 962 | } |
---|
| 963 | } |
---|
| 964 | } |
---|