diff options
| -rw-r--r-- | TODO.md | 1 | ||||
| -rw-r--r-- | src/main.hh | 2 | ||||
| -rw-r--r-- | src/priority_queue.hh | 94 | ||||
| -rw-r--r-- | src/skill.cc | 4 | ||||
| -rw-r--r-- | src/vector.hh | 16 |
5 files changed, 102 insertions, 15 deletions
@@ -1,5 +1,4 @@ ## TODO NEXT -- priority_queue (?) - TCreature - TPlayer - TNonPlayer diff --git a/src/main.hh b/src/main.hh index ad4f3ca..0b0993c 100644 --- a/src/main.hh +++ b/src/main.hh @@ -10,6 +10,8 @@ #include <stdlib.h> #include <string.h> +#include <algorithm> + typedef uint8_t uint8; typedef uint16_t uint16; typedef uint32_t uint32; diff --git a/src/priority_queue.hh b/src/priority_queue.hh new file mode 100644 index 0000000..b48353e --- /dev/null +++ b/src/priority_queue.hh @@ -0,0 +1,94 @@ +#ifndef TIBIA_PRIORITY_QUEUE_HH_ +#define TIBIA_PRIORITY_QUEUE_HH_ 1 + +#include "main.hh" +#include "vector.hh" + +template<typename K, typename T> +struct priority_queue_entry{ + K Key; + T Data; +}; + +template<typename K, typename T> +struct priority_queue{ + // REGULAR FUNCTIONS + // ========================================================================= + priority_queue(int capacity, int increment){ + Entry = new vector<priority_queue_entry<K, T>>(1, capacity, increment); + Entries = 0; + } + + // TODO(fusion): Probably missing some inlined destructor? + + void insert(K Key, T *Data){ + this->Entries += 1; + int CurrentIndex = this->Entries; + *this->Entry->at(CurrentIndex) = {Key, *Data}; + while(CurrentIndex > 1){ + int ParentIndex = CurrentIndex / 2; + priority_queue_entry<K, T> *Current = this->Entry->at(CurrentIndex); + priority_queue_entry<K, T> *Parent = this->Entry->at(ParentIndex); + if(Parent->Key <= Current->Key) + break; + std::swap(*Current, *Parent); + CurrentIndex = ParentIndex; + } + } + + void deleteMin(void){ + if(this->Entries < 1){ + error("priority_queue::deleteMin: Warteschlange ist leer.\n"); + return; + } + + if(this->Entries > 1){ + int CurrentIndex = 1; + int LastIndex = this->Entries; + std::swap(*this->Entry->at(CurrentIndex), + *this->Entry->at(LastIndex)); + + // TODO(fusion): This may be an oversight but the decompiled version + // checks in the loop below would INCLUDE `LastIndex`, which I assume + // is a bug? The first and last elements were just swapped and what + // was the first element in the queue is now at the end and should be + // considered "removed". + while(1){ + int SmallestIndex = CurrentIndex * 2; + if(SmallestIndex >= LastIndex){ + break; + } + + priority_queue_entry<K, T> *Smallest = this->Entry->at(SmallestIndex); + if((SmallestIndex + 1) < LastIndex){ + priority_queue_entry<K, T> *Other = this->Entry->at(SmallestIndex + 1); + if(Other->Key < Smallest->Key){ + Smallest = Other; + SmallestIndex += 1; + } + } + + priority_queue_entry<K, T> *Current = this->Entry->at(CurrentIndex); + if(Current->Key <= Smallest->Key){ + break; + } + + std::swap(*Current, *Smallest); + CurrentIndex = SmallestIndex; + } + } + + this->Entries -= 1; + } + + // DATA + // ========================================================================= + vector<priority_queue_entry<K, T>> *Entry; + int Entries; +}; + +// TODO(fusion): We only use this structure two global queues: +// priority_queue<uint32, uint32> ToDoQueue(5000, 1000); +// priority_queue<uint32, TAttackWave*> AttackWaveQueue(100, 100); + +#endif //TIBIA_PRIORITY_QUEUE_HH_ diff --git a/src/skill.cc b/src/skill.cc index ba060a3..909c787 100644 --- a/src/skill.cc +++ b/src/skill.cc @@ -1166,9 +1166,7 @@ bool TSkillBase::SetSkills(int Race){ // types of creatures. int NumSkills = RaceData[Race].Skills; for(int i = 0; i < NumSkills; i += 1){ - // TODO(fusion): We'd need to implement the `vector` container being used - // across the codebase. - //TSkillData *SkillData = RaceData[Race].Skill(i); + TSkillData *SkillData = RaceData[Race].Skill.at(i); // BUG(fusion): We don't check if `Skill` is valid? Could be NULL. We // don't seem to set all `Skill` fields either so there is something diff --git a/src/vector.hh b/src/vector.hh index 5c59d2c..044ffe1 100644 --- a/src/vector.hh +++ b/src/vector.hh @@ -39,7 +39,9 @@ struct vector{ } } - T *operator(int index){ + // TODO(fusion): Probably missing some inlined destructor? + + T *at(int index){ // TODO(fusion): This is probably not the best way to achieve this. while(index < this->start){ @@ -56,11 +58,7 @@ struct vector{ // TODO(fusion): Do we actually need to swap elements here? I'm // assuming some non-trivial structures that would invoke their // destructors when `this->entry` gets deleted just below. - { - T tmp = entry[new_index]; - entry[new_index] = this->entry[old_index]; - this->entry[old_index] = tmp; - } + std::swap(entry[new_index], this->entry[old_index]); } if(this->entry != NULL){ @@ -83,11 +81,7 @@ struct vector{ int new_index = old_index; // TODO(fusion): Same as above. - { - T tmp = entry[new_index]; - entry[new_index] = this->entry[old_index]; - this->entry[old_index] = tmp; - } + std::swap(entry[new_index], this->entry[old_index]); } if(this->entry != NULL){ |