jchjava
diff --git a/‎include/react/common/TopoQueue.h‎
Lines changed: 24 additions & 21 deletions b/‎include/react/common/TopoQueue.h‎
Lines changed: 24 additions & 21 deletions
diff --git a/‎include/react/propagation/TopoSortEngine.h‎
Lines changed: 1 addition & 1 deletion b/‎include/react/propagation/TopoSortEngine.h‎
Lines changed: 1 addition & 1 deletion
diff --git a/‎src/react/propagation/TopoSortEngine.cpp‎
Lines changed: 12 additions & 12 deletions b/‎src/react/propagation/TopoSortEngine.cpp‎
Lines changed: 12 additions & 12 deletions
@@ -24,40 +24,43 @@ template <typename T>
 class TopoQueue
 {
 public:
-    static bool LevelOrderOp(const T* lhs, const T* rhs)
-    {
-        return lhs->Level > rhs->Level;
-    }
+    using DataT = std::vector<T*>;
 
     void Push(T* node)
     {
         data_.push_back(node);
-        std::push_heap(data_.begin(), data_.end(), LevelOrderOp);
     }
 
-    void Pop()
+    bool FetchNext()
     {
-        std::pop_heap(data_.begin(), data_.end(), LevelOrderOp);
-        data_.pop_back();
-    }
+        next_.clear();
 
-    T* Top() const
-    {
-        return data_.front();
-    }
+        minLevel_ = INT_MAX;
+        for (const auto& e : data_)
+            if (minLevel_ > e->Level)
+                minLevel_ = e->Level;
 
-    bool Empty() const
-    {
-        return data_.empty();
-    }
+        auto p = std::partition(data_.begin(), data_.end(), CompFunctor{ minLevel_ });
 
-    void Invalidate()
-    {
-        std::make_heap(data_.begin(), data_.end(), LevelOrderOp);
+        next_.insert(next_.end(), p, data_.end());
+        data_.resize(std::distance(data_.begin(), p));
+
+        return !next_.empty();
     }
 
+    const DataT& NextNodes() const  { return next_; }
+
 private:
-    std::vector<T*>    data_;
+    struct CompFunctor
+    {
+        CompFunctor(int level) : Level{ level } {}
+        bool operator()(T* x) { return x->Level != Level; }
+        const int Level;
+    };
+
+    DataT   next_;
+    DataT   data_;
+    int     minLevel_ = INT_MAX;
 };
 
 ///////////////////////////////////////////////////////////////////////////////////////////////////
 
@@ -68,7 +68,7 @@ class ParNode : public IReactiveNode
     int             Level = 0;
     int             NewLevel = 0;
     atomic<bool>    Collected = false;
-    int             Weight = 1;
+    uint            Weight = 1;
 
     NodeVector<ParNode>     Successors;
     InvalidateMutexT        InvalidateMutex;
 
@@ -60,21 +60,21 @@ template class EngineBase<ParNode,DefaultQueueableTurn<ExclusiveTurn>>;
 template <typename TTurn>
 void SeqEngineBase<TTurn>::OnTurnPropagate(TTurn& turn)
 {
-    while (!scheduledNodes_.Empty())
+    while (scheduledNodes_.FetchNext())
     {
-        auto node = scheduledNodes_.Top();
-        scheduledNodes_.Pop();
-
-        if (node->Level < node->NewLevel)
+        for (auto* curNode : scheduledNodes_.NextNodes())
         {
-            node->Level = node->NewLevel;
-            invalidateSuccessors(*node);
-            scheduledNodes_.Push(node);
-            continue;
-        }
+            if (curNode->Level < curNode->NewLevel)
+            {
+                curNode->Level = curNode->NewLevel;
+                invalidateSuccessors(*curNode);
+                scheduledNodes_.Push(curNode);
+                continue;
+            }
 
-        node->Queued = false;
-        node->Tick(&turn);
+            curNode->Queued = false;
+            curNode->Tick(&turn);
+        }
     }
 }