Cleaned up and unified various sort predicates and moved them to Trinity namespace, replaced priority queues with sorts and purged some unused code.

--HG--
branch : trunk

13 files changed, 105 insertions, 235 deletions

diff --git a/src/game/GridNotifiersImpl.h b/src/game/GridNotifiersImpl.h
index f4267ff7048..26a9c0bd328 100644
--- a/src/game/GridNotifiersImpl.h
+++ b/src/game/GridNotifiersImpl.h
@@ -450,28 +450,4 @@ void Trinity::LocalizedPacketListDo<Builder>::operator()(Player* p)
         p->SendDirectMessage((*data_list)[i]);
 }
 
-struct ObjectDistanceOrder : public std::binary_function<const WorldObject, const WorldObject, bool>
-{
-    const Unit* m_pSource;
-
-    ObjectDistanceOrder(const Unit* pSource) : m_pSource(pSource) {};
-
-    bool operator()(const WorldObject* pLeft, const WorldObject* pRight) const
-    {
-        return m_pSource->GetDistanceOrder(pLeft, pRight);
-    }
-};
-
-struct ObjectDistanceOrderReversed : public std::binary_function<const WorldObject, const WorldObject, bool>
-{
-    const Unit* m_pSource;
-
-    ObjectDistanceOrderReversed(const Unit* pSource) : m_pSource(pSource) {};
-
-    bool operator()(const WorldObject* pLeft, const WorldObject* pRight) const
-    {
-        return !m_pSource->GetDistanceOrder(pLeft, pRight);
-    }
-};
-
 #endif                                                      // TRINITY_GRIDNOTIFIERSIMPL_H
diff --git a/src/game/Object.h b/src/game/Object.h
index bda53fd655a..c5a412c3ab7 100644
--- a/src/game/Object.h
+++ b/src/game/Object.h
@@ -711,4 +711,33 @@ class WorldObject : public Object, public WorldLocation
         uint16 m_notifyflags;
         uint16 m_executed_notifies;
 };
+
+namespace Trinity
+{
+    template<class T>
+    void RandomResizeList(std::list<T> &_list, uint32 _size)
+    {
+        while (_list.size() > _size)
+        {
+            typename std::list<T>::iterator itr = _list.begin();
+            advance(itr, urand(0, _list.size() - 1));
+            _list.erase(itr);
+        }
+    }
+      
+    // Binary predicate to sort WorldObjects based on the distance to a reference WorldObject
+    class ObjectDistanceOrderPred
+    {
+        public:
+            ObjectDistanceOrderPred(const WorldObject *pRefObj, bool ascending = true) : m_refObj(pRefObj), m_ascending(ascending) {}
+            bool operator()(const WorldObject *pLeft, const WorldObject *pRight) const
+            {
+                return m_ascending ? m_refObj->GetDistanceOrder(pLeft, pRight) : !m_refObj->GetDistanceOrder(pLeft, pRight);
+            }
+        private:
+            const WorldObject *m_refObj;
+            const bool m_ascending;
+    };
+}
+
 #endif
diff --git a/src/game/Spell.cpp b/src/game/Spell.cpp
index 2883c2f3a80..4986a143247 100644
--- a/src/game/Spell.cpp
+++ b/src/game/Spell.cpp
@@ -65,55 +65,6 @@ bool IsQuestTameSpell(uint32 spellId)
         && spellproto->Effect[1] == SPELL_EFFECT_APPLY_AURA && spellproto->EffectApplyAuraName[1] == SPELL_AURA_DUMMY;
 }
 
-class PrioritizeManaUnitWraper
-{
-    public:
-        explicit PrioritizeManaUnitWraper(Unit* unit) : i_unit(unit)
-        {
-            uint32 maxmana = unit->GetMaxPower(POWER_MANA);
-            i_percent = maxmana ? unit->GetPower(POWER_MANA) * 100 / maxmana : 101;
-        }
-        Unit* getUnit() const { return i_unit; }
-        uint32 getPercent() const { return i_percent; }
-    private:
-        Unit* i_unit;
-        uint32 i_percent;
-};
-
-struct PrioritizeMana
-{
-    int operator()(PrioritizeManaUnitWraper const& x, PrioritizeManaUnitWraper const& y) const
-    {
-        return x.getPercent() > y.getPercent();
-    }
-};
-
-typedef std::priority_queue<PrioritizeManaUnitWraper, std::vector<PrioritizeManaUnitWraper>, PrioritizeMana> PrioritizeManaUnitQueue;
-
-class PrioritizeHealthUnitWraper
-{
-public:
-    explicit PrioritizeHealthUnitWraper(Unit* unit) : i_unit(unit)
-    {
-        i_percent = unit->GetHealth() * 100 / unit->GetMaxHealth();
-    }
-    Unit* getUnit() const { return i_unit; }
-    uint32 getPercent() const { return i_percent; }
-private:
-    Unit* i_unit;
-    uint32 i_percent;
-};
-
-struct PrioritizeHealth
-{
-    int operator()(PrioritizeHealthUnitWraper const& x, PrioritizeHealthUnitWraper const& y) const
-    {
-        return x.getPercent() > y.getPercent();
-    }
-};
-
-typedef std::priority_queue<PrioritizeHealthUnitWraper, std::vector<PrioritizeHealthUnitWraper>, PrioritizeHealth> PrioritizeHealthUnitQueue;
-
 SpellCastTargets::SpellCastTargets() : m_elevation(0), m_speed(0)
 {
     m_unitTarget = NULL;
@@ -1657,7 +1608,7 @@ void Spell::SearchChainTarget(std::list<Unit*> &TagUnitMap, float max_range, uin
         }
         else
         {
-            tempUnitMap.sort(TargetDistanceOrder(cur));
+            tempUnitMap.sort(Trinity::ObjectDistanceOrderPred(cur));
             next = tempUnitMap.begin();
 
             if (cur->GetDistance(*next) > CHAIN_SPELL_JUMP_RADIUS)
@@ -2476,40 +2427,26 @@ void Spell::SelectEffectTargets(uint32 i, uint32 cur)
                         break;
                     case 57669: //Replenishment (special target selection) 10 targets with lowest mana
                     {
-                        typedef std::priority_queue<PrioritizeManaUnitWraper, std::vector<PrioritizeManaUnitWraper>, PrioritizeMana> TopMana;
-                        TopMana manaUsers;
-                        for (std::list<Unit*>::iterator itr = unitList.begin() ; itr != unitList.end(); ++itr)
+                        for (std::list<Unit*>::iterator itr = unitList.begin() ; itr != unitList.end();)
                         {
-                            if ((*itr)->getPowerType() == POWER_MANA)
-                            {
-                                PrioritizeManaUnitWraper  WTarget(*itr);
-                                manaUsers.push(WTarget);
-                            }
+                            if ((*itr)->getPowerType() != POWER_MANA)
+                                itr = unitList.erase(itr);
+                            else
+                                ++itr;
                         }
-
-                        unitList.clear();
-                        while (!manaUsers.empty() && unitList.size()<10)
+                        if (unitList.size() > 10)
                         {
-                            unitList.push_back(manaUsers.top().getUnit());
-                            manaUsers.pop();
+                            unitList.sort(Trinity::PowerPctOrderPred(POWER_MANA));
+                            unitList.resize(10);
                         }
                         break;
                     }
                     case 52759: // Ancestral Awakening
                     {
-                        typedef std::priority_queue<PrioritizeHealthUnitWraper, std::vector<PrioritizeHealthUnitWraper>, PrioritizeHealth> TopHealth;
-                        TopHealth healedMembers;
-                        for (std::list<Unit*>::iterator itr = unitList.begin() ; itr != unitList.end(); ++itr)
-                        {
-                            PrioritizeHealthUnitWraper  WTarget(*itr);
-                            healedMembers.push(WTarget);
-                        }
-
-                        unitList.clear();
-                        while (!healedMembers.empty() && unitList.size()<1)
+                        if (unitList.size() > 1)
                         {
-                            unitList.push_back(healedMembers.top().getUnit());
-                            healedMembers.pop();
+                            unitList.sort(Trinity::HealthPctOrderPred());
+                            unitList.resize(1);
                         }
                         break;
                     }
@@ -2517,18 +2454,14 @@ void Spell::SelectEffectTargets(uint32 i, uint32 cur)
                 if (m_spellInfo->EffectImplicitTargetA[i] == TARGET_DEST_TARGET_ANY
                     && m_spellInfo->EffectImplicitTargetB[i] == TARGET_UNIT_AREA_ALLY_DST)// Wild Growth, Circle of Healing, Glyph of holy light target special selection
                 {
-                    typedef std::priority_queue<PrioritizeHealthUnitWraper, std::vector<PrioritizeHealthUnitWraper>, PrioritizeHealth> TopHealth;
-                    TopHealth healedMembers;
-                    for (std::list<Unit*>::iterator itr = unitList.begin() ; itr != unitList.end(); ++itr)
+                    for (std::list<Unit*>::iterator itr = unitList.begin() ; itr != unitList.end();)
                     {
-                        if ((*itr)->IsInRaidWith(m_targets.getUnitTarget()))
-                        {
-                            PrioritizeHealthUnitWraper  WTarget(*itr);
-                            healedMembers.push(WTarget);
-                        }
+                        if (!(*itr)->IsInRaidWith(m_targets.getUnitTarget()))
+                            itr = unitList.erase(itr);
+                        else
+                            ++itr;
                     }
-
-                    unitList.clear();
+                    
                     uint32 maxsize = 5;
 
                     if (m_spellInfo->SpellFamilyName == SPELLFAMILY_DRUID && m_spellInfo->SpellFamilyFlags[1] & 0x04000000) // Wild Growth
@@ -2536,11 +2469,11 @@ void Spell::SelectEffectTargets(uint32 i, uint32 cur)
 
                     if (m_spellInfo->SpellFamilyName == SPELLFAMILY_PRIEST && m_spellInfo->SpellFamilyFlags[0] & 0x10000000 && m_spellInfo->SpellIconID == 2214) // Circle of Healing
                         maxsize += m_caster->HasAura(55675) ? 1 : 0; // Glyph of Circle of Healing
-
-                    while (!healedMembers.empty() && unitList.size()<maxsize)
+                                    
+                    if (unitList.size() > maxsize)
                     {
-                        unitList.push_back(healedMembers.top().getUnit());
-                        healedMembers.pop();
+                        unitList.sort(Trinity::HealthPctOrderPred());
+                        unitList.resize(maxsize);
                     }
                 }
                 // Death Pact
@@ -6859,7 +6792,7 @@ void Spell::SelectTrajTargets()
     if (unitList.empty())
         return;
 
-    unitList.sort(TargetDistanceOrder(m_caster));
+    unitList.sort(Trinity::ObjectDistanceOrderPred(m_caster));
 
     float b = tangent(m_targets.m_elevation);
     float a = (dz - dist2d * b) / (dist2d * dist2d);
@@ -6964,81 +6897,3 @@ void Spell::SelectTrajTargets()
         m_targets.setDst(x, y, z, m_caster->GetOrientation());
     }
 }
-
-void Spell::FillRaidOrPartyTargets(UnitList &TagUnitMap, Unit* target, float radius, bool raid, bool withPets, bool withcaster)
-{
-    Player *pTarget = target->GetCharmerOrOwnerPlayerOrPlayerItself();
-    Group *pGroup = pTarget ? pTarget->GetGroup() : NULL;
-
-    if (pGroup)
-    {
-        uint8 subgroup = pTarget->GetSubGroup();
-
-        for (GroupReference *itr = pGroup->GetFirstMember(); itr != NULL; itr = itr->next())
-        {
-            Player* Target = itr->getSource();
-
-            // IsHostileTo check duel and controlled by enemy
-            if (Target && (raid || subgroup == Target->GetSubGroup())
-                && !m_caster->IsHostileTo(Target))
-            {
-                if (Target == m_caster && withcaster ||
-                    Target != m_caster && m_caster->IsWithinDistInMap(Target, radius))
-                    TagUnitMap.push_back(Target);
-
-                if (withPets)
-                    if (Pet* pet = Target->GetPet())
-                        if (pet == m_caster && withcaster ||
-                            pet != m_caster && m_caster->IsWithinDistInMap(pet, radius))
-                            TagUnitMap.push_back(pet);
-            }
-        }
-    }
-    else
-    {
-        Unit* ownerOrSelf = pTarget ? pTarget : target->GetCharmerOrOwnerOrSelf();
-        if (ownerOrSelf == m_caster && withcaster ||
-            ownerOrSelf != m_caster && m_caster->IsWithinDistInMap(ownerOrSelf, radius))
-            TagUnitMap.push_back(ownerOrSelf);
-
-        if (withPets)
-            if (Guardian* pet = ownerOrSelf->GetGuardianPet())
-                if (pet == m_caster && withcaster ||
-                    pet != m_caster && m_caster->IsWithinDistInMap(pet, radius))
-                    TagUnitMap.push_back(pet);
-    }
-}
-
-void Spell::FillRaidOrPartyManaPriorityTargets(UnitList &TagUnitMap, Unit* target, float radius, uint32 count, bool raid, bool withPets, bool withCaster)
-{
-    FillRaidOrPartyTargets(TagUnitMap,target,radius,raid,withPets,withCaster);
-
-    PrioritizeManaUnitQueue manaUsers;
-    for (UnitList::const_iterator itr = TagUnitMap.begin(); itr != TagUnitMap.end() && manaUsers.size() < count; ++itr)
-        if ((*itr)->getPowerType() == POWER_MANA && !(*itr)->isDead())
-            manaUsers.push(PrioritizeManaUnitWraper(*itr));
-
-    TagUnitMap.clear();
-    while (!manaUsers.empty())
-    {
-        TagUnitMap.push_back(manaUsers.top().getUnit());
-        manaUsers.pop();
-    }
-}
-
-void Spell::FillRaidOrPartyHealthPriorityTargets(UnitList &TagUnitMap, Unit* target, float radius, uint32 count, bool raid, bool withPets, bool withCaster)
-{
-    FillRaidOrPartyTargets(TagUnitMap,target,radius,raid,withPets,withCaster);
-
-    PrioritizeHealthUnitQueue healthQueue;
-    for (UnitList::const_iterator itr = TagUnitMap.begin(); itr != TagUnitMap.end() && healthQueue.size() < count; ++itr)
-        if (!(*itr)->isDead())
-            healthQueue.push(PrioritizeHealthUnitWraper(*itr));
-
-    TagUnitMap.clear();
-    while (!healthQueue.empty())
-    {
-        TagUnitMap.push_back(healthQueue.top().getUnit());
-        healthQueue.pop();
-    }
-}
diff --git a/src/game/Spell.h b/src/game/Spell.h
index a9f73adb13f..a987e35e65d 100644
--- a/src/game/Spell.h
+++ b/src/game/Spell.h
@@ -436,9 +436,6 @@ class Spell
         void SelectSpellTargets();
         void SelectEffectTargets(uint32 i, uint32 cur);
         void SelectTrajTargets();
-        void FillRaidOrPartyTargets(UnitList &TagUnitMap, Unit* target, float radius, bool raid, bool withPets, bool withcaster);
-        void FillRaidOrPartyManaPriorityTargets(UnitList &TagUnitMap, Unit* target, float radius, uint32 count, bool raid, bool withPets, bool withcaster);
-        void FillRaidOrPartyHealthPriorityTargets(UnitList &TagUnitMap, Unit* target, float radius, uint32 count, bool raid, bool withPets, bool withcaster);
 
         template<typename T> WorldObject* FindCorpseUsing();
 
diff --git a/src/game/ThreatManager.cpp b/src/game/ThreatManager.cpp
index fcc3b466954..52f02f0f66d 100644
--- a/src/game/ThreatManager.cpp
+++ b/src/game/ThreatManager.cpp
@@ -246,21 +246,13 @@ void ThreatContainer::modifyThreatPercent(Unit *pVictim, int32 iPercent)
 }
 
 //============================================================
-
-bool HostileReferenceSortPredicate(const HostileReference* lhs, const HostileReference* rhs)
-{
-    // std::list::sort ordering predicate must be: (Pred(x,y)&&Pred(y,x)) == false
-    return lhs->getThreat() > rhs->getThreat();             // reverse sorting
-}
-
-//============================================================
 // Check if the list is dirty and sort if necessary
 
 void ThreatContainer::update()
 {
     if (iDirty && iThreatList.size() >1)
-    {
-        iThreatList.sort(HostileReferenceSortPredicate);
+    {    
+        iThreatList.sort(Trinity::ThreatOrderPred());
     }
     iDirty = false;
 }
diff --git a/src/game/ThreatManager.h b/src/game/ThreatManager.h
index ec6c6ec1684..723a553e9d7 100644
--- a/src/game/ThreatManager.h
+++ b/src/game/ThreatManager.h
@@ -259,5 +259,21 @@ class ThreatManager
 };
 
 //=================================================
+
+namespace Trinity
+{
+    // Binary predicate for sorting HostileReferences based on threat value
+    class ThreatOrderPred
+    {
+        public:
+            ThreatOrderPred(bool ascending = false) : m_ascending(ascending) {}
+            bool operator() (const HostileReference *a, const HostileReference *b) const
+            { 
+                return m_ascending ? a->getThreat() < b->getThreat() : a->getThreat() > b->getThreat();  
+            }
+        private:
+            const bool m_ascending;
+    };
+}
 #endif
 
diff --git a/src/game/Unit.h b/src/game/Unit.h
index 980e481e8d5..567fba03370 100644
--- a/src/game/Unit.h
+++ b/src/game/Unit.h
@@ -2083,31 +2083,36 @@ class Unit : public WorldObject
 
 namespace Trinity
 {
-    template<class T>
-    void RandomResizeList(std::list<T> &_list, uint32 _size)
+    // Binary predicate for sorting Units based on percent value of a power
+    class PowerPctOrderPred
     {
-        while (_list.size() > _size)
-        {
-            typename std::list<T>::iterator itr = _list.begin();
-            advance(itr, urand(0, _list.size() - 1));
-            _list.erase(itr);
-        }
-    }
-}
-
-// binary function to sort unit based on the distance to a reference unit
-struct TargetDistanceOrder : public std::binary_function<const Unit *, const Unit *, bool>
-{
-    const Unit *me;
-
-    // pUnit: the reference unit from which the distance is computed.
-    TargetDistanceOrder(const Unit* pUnit) : me(pUnit) {};
-
-    // functor for operator "<"
-    bool operator()(const Unit* left, const Unit* right) const
+        public:
+            PowerPctOrderPred(Powers power, bool ascending = true) : m_power(power), m_ascending(ascending) {}
+            bool operator() (const Unit *a, const Unit *b) const
+            { 
+                float rA = a->GetMaxPower(m_power) ? float(a->GetPower(m_power)) / float(a->GetMaxPower(m_power)) : 0.0f;
+                float rB = b->GetMaxPower(m_power) ? float(b->GetPower(m_power)) / float(b->GetMaxPower(m_power)) : 0.0f;
+                return m_ascending ? rA < rB : rA > rB;
+            }
+        private:
+            const Powers m_power;
+            const bool m_ascending;
+    };
+      
+    // Binary predicate for sorting Units based on percent value of health
+    class HealthPctOrderPred
     {
-        return (me->GetExactDistSq(left) < me->GetExactDistSq(right));
-    }
-};
+        public:
+            HealthPctOrderPred(bool ascending = true) : m_ascending(ascending) {}
+            bool operator() (const Unit *a, const Unit *b) const
+            { 
+                float rA = a->GetMaxHealth() ? float(a->GetHealth()) / float(a->GetMaxHealth()) : 0.0f;
+                float rB = b->GetMaxHealth() ? float(b->GetHealth()) / float(b->GetMaxHealth()) : 0.0f;
+                return m_ascending ? rA < rB : rA > rB;
+            }
+        private:
+            const bool m_ascending;
+    };
+}
 
 #endif
diff --git a/src/game/UnitAI.cpp b/src/game/UnitAI.cpp
index e70df50a56e..a156ec573d9 100644
--- a/src/game/UnitAI.cpp
+++ b/src/game/UnitAI.cpp
@@ -149,7 +149,7 @@ void UnitAI::SelectTargetList(std::list<Unit*> &targetList, uint32 num, SelectAg
             targetList.push_back((*itr)->getTarget());
 
     if (targetType == SELECT_TARGET_NEAREST || targetType == SELECT_TARGET_FARTHEST)
-        targetList.sort(TargetDistanceOrder(me));
+        targetList.sort(Trinity::ObjectDistanceOrderPred(me));
 
     if (targetType == SELECT_TARGET_FARTHEST || targetType == SELECT_TARGET_BOTTOMAGGRO)
         targetList.reverse();
diff --git a/src/game/UnitAI.h b/src/game/UnitAI.h
index b45e5fad8d8..62b7090a2d0 100644
--- a/src/game/UnitAI.h
+++ b/src/game/UnitAI.h
@@ -89,7 +89,7 @@ class UnitAI
                 return NULL;
 
             if (targetType == SELECT_TARGET_NEAREST || targetType == SELECT_TARGET_FARTHEST)
-                targetList.sort(TargetDistanceOrder(me));
+                targetList.sort(Trinity::ObjectDistanceOrderPred(me));
 
             switch(targetType)
             {
diff --git a/src/scripts/kalimdor/caverns_of_time/hyjal/boss_archimonde.cpp b/src/scripts/kalimdor/caverns_of_time/hyjal/boss_archimonde.cpp
index c643660216f..8e1fa378e07 100644
--- a/src/scripts/kalimdor/caverns_of_time/hyjal/boss_archimonde.cpp
+++ b/src/scripts/kalimdor/caverns_of_time/hyjal/boss_archimonde.cpp
@@ -318,7 +318,7 @@ struct boss_archimondeAI : public hyjal_trashAI
         if (targets.empty())
             return false;
 
-        targets.sort(ObjectDistanceOrder(me));
+        targets.sort(Trinity::ObjectDistanceOrderPred(me));
         Unit *pTarget = targets.front();
         if (pTarget)
         {
diff --git a/src/scripts/outland/black_temple/boss_bloodboil.cpp b/src/scripts/outland/black_temple/boss_bloodboil.cpp
index bf948a81e2d..1093ce06cb8 100644
--- a/src/scripts/outland/black_temple/boss_bloodboil.cpp
+++ b/src/scripts/outland/black_temple/boss_bloodboil.cpp
@@ -146,7 +146,7 @@ struct boss_gurtogg_bloodboilAI : public ScriptedAI
         }
 
         //Sort the list of players
-        targets.sort(ObjectDistanceOrderReversed(me));
+        targets.sort(Trinity::ObjectDistanceOrderPred(me, false));
         //Resize so we only get top 5
         targets.resize(5);
 
diff --git a/src/scripts/outland/black_temple/boss_reliquary_of_souls.cpp b/src/scripts/outland/black_temple/boss_reliquary_of_souls.cpp
index 75dd799458c..3e019a8dc35 100644
--- a/src/scripts/outland/black_temple/boss_reliquary_of_souls.cpp
+++ b/src/scripts/outland/black_temple/boss_reliquary_of_souls.cpp
@@ -399,7 +399,7 @@ struct boss_essence_of_sufferingAI : public ScriptedAI
         }
         if (targets.empty())
             return; // No targets added for some reason. No point continuing.
-        targets.sort(ObjectDistanceOrder(me)); // Sort players by distance.
+        targets.sort(Trinity::ObjectDistanceOrderPred(me)); // Sort players by distance.
         targets.resize(1); // Only need closest target.
         Unit *pTarget = targets.front(); // Get the first target.
         if (pTarget)
diff --git a/src/scripts/outland/black_temple/boss_teron_gorefiend.cpp b/src/scripts/outland/black_temple/boss_teron_gorefiend.cpp
index a61735f0a25..4c3887e2ba3 100644
--- a/src/scripts/outland/black_temple/boss_teron_gorefiend.cpp
+++ b/src/scripts/outland/black_temple/boss_teron_gorefiend.cpp
@@ -153,7 +153,7 @@ struct mob_shadowy_constructAI : public ScriptedAI
             if (pUnit && pUnit->isAlive())
                 targets.push_back(pUnit);
         }
-        targets.sort(ObjectDistanceOrder(me));
+        targets.sort(Trinity::ObjectDistanceOrderPred(me));
         Unit *pTarget = targets.front();
         if (pTarget && me->IsWithinDistInMap(pTarget, me->GetAttackDistance(pTarget)))
         {