Changeset 876 for code/branches/core2/src/orxonox/core/Identifier.cc

Timestamp:

Mar 10, 2008, 12:27:30 AM (16 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) )

File:

• code/branches/core2/src/orxonox/core/Identifier.cc (modified) (11 diffs)

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() << " ";