Changeset 876 for code/branches

Timestamp:

Mar 10, 2008, 12:27:30 AM (17 years ago)

Author:

landauf

Message:

std::set instead of std::list for Identifier-lists (parents, children, …) for faster accessing by key ( std::set::find(xyz) )

Location:

code/branches/core2/src/orxonox/core

Files:

• ClassTreeMask.cc (modified) (2 diffs)
• Identifier.cc (modified) (11 diffs)
• Identifier.h (modified) (8 diffs)
• OrxonoxClass.h (modified) (3 diffs)

code/branches/core2/src/orxonox/core/ClassTreeMask.cc

@@ -327 +327 @@
         {
             // No it's not: Search for classes inheriting from the given class and add the rules for them
-            for (std::list<const Identifier*>::const_iterator it = subclass->getDirectChildrenBegin(); it != subclass->getDirectChildrenEnd(); ++it)
+            for (std::set<const Identifier*>::const_iterator it = subclass->getDirectChildrenBegin(); it != subclass->getDirectChildrenEnd(); ++it)
                 if ((*it)->isA(this->root_->getClass()))
                     if (overwrite || (!this->nodeExists(*it))) // If we don't want to overwrite, only add nodes that don't already exist
@@ -422 +422 @@
     void ClassTreeMask::addSingle(const Identifier* subclass, bool bInclude, bool clean)
     {
-        for (std::list<const Identifier*>::const_iterator it = subclass->getDirectChildrenBegin(); it != subclass->getDirectChildrenEnd(); ++it)
+        for (std::set<const Identifier*>::const_iterator it = subclass->getDirectChildrenBegin(); it != subclass->getDirectChildrenEnd(); ++it)
             this->add(*it, this->isIncluded(*it), false, false);
 

code/branches/core2/src/orxonox/core/Identifier.cc

@@ -51 +51 @@
         this->factory_ = 0;
 
-        this->children_ = new std::list<const Identifier*>();
-        this->directChildren_ = new std::list<const Identifier*>();
+        this->children_ = new std::set<const Identifier*>();
+        this->directChildren_ = new std::set<const Identifier*>();
 
         // Use a static variable because the classID gets created before main() and that's why we should avoid static member variables
@@ -72 +72 @@
         @param parents A list containing all parents
     */
-    void Identifier::initialize(std::list<const Identifier*>* parents)
+    void Identifier::initialize(std::set<const Identifier*>* parents)
     {
         COUT(4) << "*** Identifier: Initialize " << this->name_ << "-Singleton." << std::endl;
@@ -83 +83 @@
 
             // Iterate through all parents
-            for (std::list<const Identifier*>::iterator it = parents->begin(); it != parents->end(); ++it)
+            for (std::set<const Identifier*>::iterator it = parents->begin(); it != parents->end(); ++it)
             {
                 // Tell the parent we're one of it's children
@@ -89 +89 @@
 
                 // Erase all parents of our parent from our direct-parent-list
-                for (std::list<const Identifier*>::const_iterator it1 = (*it)->getParents().begin(); it1 != (*it)->getParents().end(); ++it1)
+                for (std::set<const Identifier*>::const_iterator it1 = (*it)->getParents().begin(); it1 != (*it)->getParents().end(); ++it1)
                 {
                     // Search for the parent's parent in our direct-parent-list
-                    for (std::list<const Identifier*>::iterator it2 = this->directParents_.begin(); it2 != this->directParents_.end(); ++it2)
+                    for (std::set<const Identifier*>::iterator it2 = this->directParents_.begin(); it2 != this->directParents_.end(); ++it2)
                     {
                         if ((*it1) == (*it2))
@@ -105 +105 @@
 
             // Now iterate through all direct parents
-            for (std::list<const Identifier*>::iterator it = this->directParents_.begin(); it != this->directParents_.end(); ++it)
+            for (std::set<const Identifier*>::iterator it = this->directParents_.begin(); it != this->directParents_.end(); ++it)
             {
                 // Tell the parent we're one of it's direct children
@@ -149 +149 @@
     bool Identifier::isA(const Identifier* identifier) const
     {
-        return (identifier == this || this->identifierIsInList(identifier, this->parents_));
+        return (identifier == this || (this->parents_.find(identifier) != this->children_->end()));
     }
 
@@ -167 +167 @@
     bool Identifier::isChildOf(const Identifier* identifier) const
     {
-        return this->identifierIsInList(identifier, this->parents_);
+        return (this->parents_.find(identifier) != this->children_->end());
     }
 
@@ -176 +176 @@
     bool Identifier::isDirectChildOf(const Identifier* identifier) const
     {
-        return this->identifierIsInList(identifier, this->directParents_);
+        return (this->directParents_.find(identifier) != this->children_->end());
     }
 
@@ -185 +185 @@
     bool Identifier::isParentOf(const Identifier* identifier) const
     {
-        return this->identifierIsInList(identifier, *this->children_);
+        return (this->children_->find(identifier) != this->children_->end());
     }
 
@@ -194 +194 @@
     bool Identifier::isDirectParentOf(const Identifier* identifier) const
     {
-        return this->identifierIsInList(identifier, *this->directChildren_);
+        return (this->directChildren_->find(identifier) != this->children_->end());
     }
 
@@ -221 +221 @@
     }
 
-    /**
-        @brief Searches for a given identifier in a list and returns whether the identifier is in the list or not.
-        @param identifier The identifier to look for
-        @param list The list
-        @return True = the identifier is in the list
-    */
-    bool Identifier::identifierIsInList(const Identifier* identifier, const std::list<const Identifier*>& list)
-    {
-        for (std::list<const Identifier*>::const_iterator it = list.begin(); it != list.end(); ++it)
-            if (identifier == (*it))
-                return true;
-
-        return false;
-    }
-
-    std::ostream& operator<<(std::ostream& out, const std::list<const Identifier*>& list)
-    {
-        for (std::list<const Identifier*>::const_iterator it = list.begin(); it != list.end(); ++it)
+    std::ostream& operator<<(std::ostream& out, const std::set<const Identifier*>& list)
+    {
+        for (std::set<const Identifier*>::const_iterator it = list.begin(); it != list.end(); ++it)
             out << (*it)->getName() << " ";
 

code/branches/core2/src/orxonox/core/Identifier.h

@@ -52 +52 @@
 #define _Identifier_H__
 
-#include <list>
+#include <set>
 #include <map>
 #include <string>
@@ -115 +115 @@
 
             /** @brief Returns the parents of the class the Identifier belongs to. @return The list of all parents */
-            inline const std::list<const Identifier*>& getParents() const { return this->parents_; }
+            inline const std::set<const Identifier*>& getParents() const { return this->parents_; }
             /** @brief Returns the begin-iterator of the parents-list. @return The begin-iterator */
-            inline std::list<const Identifier*>::const_iterator getParentsBegin() const { return this->parents_.begin(); }
+            inline std::set<const Identifier*>::const_iterator getParentsBegin() const { return this->parents_.begin(); }
             /** @brief Returns the end-iterator of the parents-list. @return The end-iterator */
-            inline std::list<const Identifier*>::const_iterator getParentsEnd() const { return this->parents_.end(); }
+            inline std::set<const Identifier*>::const_iterator getParentsEnd() const { return this->parents_.end(); }
 
             /** @brief Returns the children of the class the Identifier belongs to. @return The list of all children */
-            inline const std::list<const Identifier*>& getChildren() const { return (*this->children_); }
+            inline const std::set<const Identifier*>& getChildren() const { return (*this->children_); }
             /** @brief Returns the begin-iterator of the children-list. @return The begin-iterator */
-            inline std::list<const Identifier*>::const_iterator getChildrenBegin() const { return this->children_->begin(); }
+            inline std::set<const Identifier*>::const_iterator getChildrenBegin() const { return this->children_->begin(); }
             /** @brief Returns the end-iterator of the children-list. @return The end-iterator */
-            inline std::list<const Identifier*>::const_iterator getChildrenEnd() const { return this->children_->end(); }
+            inline std::set<const Identifier*>::const_iterator getChildrenEnd() const { return this->children_->end(); }
 
             /** @brief Returns the direct parents of the class the Identifier belongs to. @return The list of all direct parents */
-            inline const std::list<const Identifier*>& getDirectParents() const { return this->directParents_; }
+            inline const std::set<const Identifier*>& getDirectParents() const { return this->directParents_; }
             /** @brief Returns the begin-iterator of the direct-parents-list. @return The begin-iterator */
-            inline std::list<const Identifier*>::const_iterator getDirectParentsBegin() const { return this->directParents_.begin(); }
+            inline std::set<const Identifier*>::const_iterator getDirectParentsBegin() const { return this->directParents_.begin(); }
             /** @brief Returns the end-iterator of the direct-parents-list. @return The end-iterator */
-            inline std::list<const Identifier*>::const_iterator getDirectParentsEnd() const { return this->directParents_.end(); }
+            inline std::set<const Identifier*>::const_iterator getDirectParentsEnd() const { return this->directParents_.end(); }
 
             /** @brief Returns the direct children the class the Identifier belongs to. @return The list of all direct children */
-            inline const std::list<const Identifier*>& getDirectChildren() const { return (*this->directChildren_); }
+            inline const std::set<const Identifier*>& getDirectChildren() const { return (*this->directChildren_); }
             /** @brief Returns the begin-iterator of the direct-children-list. @return The begin-iterator */
-            inline std::list<const Identifier*>::const_iterator getDirectChildrenBegin() const { return this->directChildren_->begin(); }
+            inline std::set<const Identifier*>::const_iterator getDirectChildrenBegin() const { return this->directChildren_->begin(); }
             /** @brief Returns the end-iterator of the direct-children-list. @return The end-iterator */
-            inline std::list<const Identifier*>::const_iterator getDirectChildrenEnd() const { return this->directChildren_->end(); }
+            inline std::set<const Identifier*>::const_iterator getDirectChildrenEnd() const { return this->directChildren_->end(); }
 
             /** @brief Returns true, if a branch of the class-hierarchy is being created, causing all new objects to store their parents. @return The status of the class-hierarchy creation */
@@ -159 +159 @@
             virtual XMLPortObjectContainer* getXMLPortObjectContainer(const std::string& sectionname) = 0;
             virtual void addXMLPortObjectContainer(const std::string& sectionname, XMLPortObjectContainer* container) = 0;
-
-            static bool identifierIsInList(const Identifier* identifier, const std::list<const Identifier*>& list);
 
         private:
@@ -166 +164 @@
             Identifier(const Identifier& identifier) {} // don't copy
             virtual ~Identifier();
-            void initialize(std::list<const Identifier*>* parents);
+            void initialize(std::set<const Identifier*>* parents);
 
             /** @brief Returns the children of the class the Identifier belongs to. @return The list of all children */
-            inline std::list<const Identifier*>& getChildrenIntern() const { return (*this->children_); }
+            inline std::set<const Identifier*>& getChildrenIntern() const { return (*this->children_); }
             /** @brief Returns the direct children of the class the Identifier belongs to. @return The list of all direct children */
-            inline std::list<const Identifier*>& getDirectChildrenIntern() const { return (*this->directChildren_); }
+            inline std::set<const Identifier*>& getDirectChildrenIntern() const { return (*this->directChildren_); }
 
             /**
@@ -191 +189 @@
             }
 
-            std::list<const Identifier*> parents_;                      //!< The parents of the class the Identifier belongs to
-            std::list<const Identifier*>* children_;                    //!< The children of the class the Identifier belongs to
-
-            std::list<const Identifier*> directParents_;                //!< The direct parents of the class the Identifier belongs to
-            std::list<const Identifier*>* directChildren_;              //!< The direct children of the class the Identifier belongs to
+            std::set<const Identifier*> parents_;                      //!< The parents of the class the Identifier belongs to
+            std::set<const Identifier*>* children_;                    //!< The children of the class the Identifier belongs to
+
+            std::set<const Identifier*> directParents_;                //!< The direct parents of the class the Identifier belongs to
+            std::set<const Identifier*>* directChildren_;              //!< The direct children of the class the Identifier belongs to
 
             std::string name_;                                          //!< The name of the class the Identifier belongs to
@@ -206 +204 @@
     };
 
-    std::ostream& operator<<(std::ostream& out, const std::list<const Identifier*>& list);
+    std::ostream& operator<<(std::ostream& out, const std::set<const Identifier*>& list);
 
 
@@ -231 +229 @@
 
         public:
-            ClassIdentifier<T>* registerClass(std::list<const Identifier*>* parents, const std::string& name, bool bRootClass);
+            ClassIdentifier<T>* registerClass(std::set<const Identifier*>* parents, const std::string& name, bool bRootClass);
             void addObject(T* object);
             void removeObjects() const;
@@ -273 +271 @@
     */
     template <class T>
-    ClassIdentifier<T>* ClassIdentifier<T>::registerClass(std::list<const Identifier*>* parents, const std::string& name, bool bRootClass)
+    ClassIdentifier<T>* ClassIdentifier<T>::registerClass(std::set<const Identifier*>* parents, const std::string& name, bool bRootClass)
     {
         COUT(5) << "*** ClassIdentifier: Register Class in " << name << "-Singleton." << std::endl;

code/branches/core2/src/orxonox/core/OrxonoxClass.h

@@ -37 +37 @@
 #define _OrxonoxClass_H__
 
-#include <list>
+#include <set>
 #include <string>
 
@@ -67 +67 @@
 
             /** @brief Returns the list of all parents of the object. @return The list */
-            inline std::list<const Identifier*>* getParents() const { return this->parents_; }
+            inline std::set<const Identifier*>* getParents() const { return this->parents_; }
 
             /** @brief Creates the parents-list. */
-            inline void createParents() { this->parents_ = new std::list<const Identifier*>(); }
+            inline void createParents() { this->parents_ = new std::set<const Identifier*>(); }
 
             /** @brief Returns the MetaObjectList of the object, containing a link to all ObjectLists and ObjectListElements the object is registered in. @return The list */
@@ -157 +157 @@
         private:
             Identifier* identifier_;                    //!< The Identifier of the object
-            std::list<const Identifier*>* parents_;     //!< List of all parents of the object
+            std::set<const Identifier*>* parents_;     //!< List of all parents of the object
             MetaObjectList metaList_;                   //!< MetaObjectList, containing all ObjectLists and ObjectListElements the object is registered in
     };