Use a std::list to store the beings (nodes).

4 files changed, 69 insertions, 140 deletions

diff --git a/src/being.cpp b/src/being.cpp
index 4404854a..65eb707e 100644
--- a/src/being.cpp
+++ b/src/being.cpp
@@ -27,8 +27,8 @@
 #include "being.h"
 
 NODE *player_node = NULL;
-NODE *head = NULL; // First node of the list
-unsigned int b_count = 0; // Number of beings in the list
+
+std::list<NODE*> beings;
 
 
 PATH_NODE::PATH_NODE(unsigned short x, unsigned short y):
@@ -47,7 +47,6 @@ PATH_NODE *calculate_path(
 
 NODE::NODE():
     id(0), job(0),
-    next(NULL),
     action(0), frame(0),
     path(NULL),
     speech(NULL), speech_time(0),
@@ -61,147 +60,79 @@ NODE::NODE():
     speech_color = makecol(0, 0, 0);
 }
 
-NODE *get_head() {
-  return head;
-}
-
-unsigned int get_count() {
-    return b_count;
-}
-
 void empty() {
-    NODE *node = head;
-    NODE *next;
-    while(node) {
-        next = node->next;
-        delete node;
-        node = next;
+    std::list<NODE*>::iterator i;
+    for (i = beings.begin(); i != beings.end(); i++) {
+        delete (*i);
     }
-    b_count = 0;
-    head = NULL;
+    beings.clear();
 }
 
 void add_node(NODE *node) {
-    NODE *temp = head;
-    if(temp) {
-        while(temp->next)
-            temp = temp->next;
-        temp->next = node;
-    } else head = node;
-    b_count++;
+    beings.push_back(node);
 }
 
 void remove_node(unsigned int id) {
-    unsigned int temp;
-    NODE *node_old, *node_new;
-    node_old = head;
-    node_new = NULL;
-    while (node_old) {
-        temp = get_id(node_old);
-        if (temp==id) {
-            if (node_new==NULL) {
-                head = node_old->next;
-                delete node_old;
-                b_count--;
-                return;
-            } else {
-                node_new->next = node_old->next;
-                delete node_old;
-                b_count--;
-                return;
-            }
-        } else {
-            node_new = node_old;
-            node_old = node_old->next;
+    std::list<NODE*>::iterator i;
+    for (i = beings.begin(); i != beings.end(); i++) {
+        if ((*i)->id == id) {
+            delete (*i);
+            beings.erase(i);
+            return;
         }
     }
 }
 
-unsigned int get_id(NODE *node) {
-    return node->id;
-}
-
 unsigned int find_npc(unsigned short x, unsigned short y) {
-    NODE *node = head;
-    while (node) {
+    std::list<NODE*>::iterator i;
+    for (i = beings.begin(); i != beings.end(); i++) {
+        NODE *node = (*i);
         // Check if is a NPC (only low job ids)
-        if ((node->job >= 46) && (node->job <= 125)) {
-            if ((get_x(node->coordinates) == x) &&
-                    (get_y(node->coordinates) == y))
-            {
-                return node->id;
-            }
-            else {
-                node = node->next;
-            }
-        } else {
-            node = node->next;
+        if (node->job >= 46 && node->job <= 125 &&
+                get_x(node->coordinates) == x &&
+                get_y(node->coordinates) == y)
+        {
+            return node->id;
         }
     }
     return 0;
 }
 
 unsigned int find_monster(unsigned short x, unsigned short y) {
-    NODE *node = head;
-    while (node) {
+    std::list<NODE*>::iterator i;
+    for (i = beings.begin(); i != beings.end(); i++) {
+        NODE *node = (*i);
         // Check if is a MONSTER
-        if (node->job > 200) {
-            if (get_x(node->coordinates) == x &&
-                    get_y(node->coordinates) == y)
-            {
-                return node->id;
-            }
+        if (node->job > 200 &&
+                get_x(node->coordinates) == x &&
+                get_y(node->coordinates) == y)
+        {
+            return node->id;
         }
-        node = node->next;
     }
     return 0;
 }
 
 NODE *find_node(unsigned int id) {
-    NODE *node = head;
-    while (node) {
+    std::list<NODE*>::iterator i;
+    for (i = beings.begin(); i != beings.end(); i++) {
+        NODE *node = (*i);
         if (node->id == id) {
             return node;
         }
-        else {
-            node = node->next;
-        }
-        return NULL;
     }
+    return NULL;
 }
 
-void sort() {
-    NODE *p, *q, *r, *s, *temp;
-    s = NULL;
-
-    // Bubble sort
-    while (s != head->next) {
-        r = p = head;
-        q = p->next;
-
-        while (p != s) {
-            if (get_y(p->coordinates) > get_y(q->coordinates)) {
-                if (p == head) {
-                    temp = q->next;
-                    q->next = p;
-                    p->next = temp;
-                    head = q;
-                    r = q;
-                } else {
-                    temp = q->next;
-                    q->next = p;
-                    p->next = temp;
-                    r->next = q;
-                    r = q;
-                }
-            } else {
-                r = p;
-                p = p->next;
-            }
-            q = p->next;
-            if (q == s) s = p;
+class NODE_Compare {
+    public:
+        bool operator() (const NODE *a, const NODE *b) const {
+            return get_y(a->coordinates) < get_y(b->coordinates);
         }
-    }
+};
+
+void sort() {
+    beings.sort(NODE_Compare());
 }
 
 void empty_path(NODE *node) {
diff --git a/src/being.h b/src/being.h
index a64e41e2..17572951 100644
--- a/src/being.h
+++ b/src/being.h
@@ -25,6 +25,7 @@
 #define _TMW_BEING_H
 
 #include "./net/protocol.h"
+#include <list>
 
 #define ACTION_NODE  0
 //#define PLAYER_NODE  1
@@ -50,7 +51,6 @@ struct NODE {
     unsigned int id;
     short job;
     char coordinates[3];
-    NODE *next;
     unsigned char type;
     unsigned char action;
     unsigned char frame;
@@ -70,9 +70,6 @@ struct NODE {
 /** Removes all beings from the list */
 void empty();
 
-/** Returns the first node of the list */
-NODE *get_head();
-
 /** Add a node to the list */
 void add_node(NODE *node);
 
@@ -82,16 +79,10 @@ NODE *find_node(unsigned int id);
 /** Remove a node */
 void remove_node(unsigned int id);
 
-/** Returns number of beings in the list */
-unsigned int get_count();
-
 PATH_NODE *calculate_path(
         unsigned short src_x, unsigned short src_y,
         unsigned short dest_x, unsigned short dest_y);
 
-/** Returns the id of a being in the list */
-unsigned int get_id(NODE *node);
-
 /** Find a NPC id based on its coordinates */
 unsigned int find_npc(unsigned short x, unsigned short y);
 
@@ -106,4 +97,6 @@ void empty_path(NODE *node);
 
 extern NODE *player_node;
 
+extern std::list<NODE*> beings;
+
 #endif
diff --git a/src/graphic/graphic.cpp b/src/graphic/graphic.cpp
index 92acd9be..3640bde0 100644
--- a/src/graphic/graphic.cpp
+++ b/src/graphic/graphic.cpp
@@ -261,8 +261,10 @@ void GraphicEngine::refresh() {
     }
         
     // Draw nodes
-    NODE *node = get_head();
-    while (node) {
+    std::list<NODE*>::iterator beingIterator = beings.begin();
+    while (beingIterator != beings.end()) {
+        NODE *node = (*beingIterator);
+
         unsigned short x = get_x(node->coordinates);
         unsigned short y = get_y(node->coordinates);
         unsigned char dir = get_direction(node->coordinates) / 2;
@@ -392,12 +394,11 @@ void GraphicEngine::refresh() {
         }
         
         if (node->action == MONSTER_DEAD && node->frame >= 20) {
-            NODE *temp = node;
-            node = node->next;
-            remove_node(temp->id);
+            delete node;
+            beingIterator = beings.erase(beingIterator);
         }
         else {
-            node = node->next;
+            beingIterator++;
         }
 
         // nodes are ordered so if the next node y is > then the
@@ -422,8 +423,10 @@ void GraphicEngine::refresh() {
     }
     
     // Draw player speech
-    node = get_head();
-    while (node) {
+    beingIterator = beings.begin();
+    while (beingIterator != beings.end()) {
+        NODE *node = (*beingIterator);
+
         if (node->speech != NULL) {
             if (node->speech_color == makecol(255, 255, 255)) {
                 textprintf_centre_ex(buffer, font,
@@ -445,8 +448,9 @@ void GraphicEngine::refresh() {
                 free(node->speech);
                 node->speech = NULL;
             }
-        }       
-        node = node->next;
+        }
+
+        beingIterator++;
     }
 
     set_trans_blender(0, 0, 0, 110);
diff --git a/src/map.cpp b/src/map.cpp
index 0687dd53..ec796768 100644
--- a/src/map.cpp
+++ b/src/map.cpp
@@ -52,16 +52,17 @@ void set_walk(short x_c, short y_c, bool walkable) {
 }
 
 bool get_walk(short x_c, short y_c) {
-	bool ret = (tiled_map.tiles[x_c][y_c].data[3] & 0x0002)>0;
-	if(ret==true) {
-    NODE *node = get_head();
-		while(node && ret==true) {
-			if(get_x(node->coordinates)==x_c && get_y(node->coordinates)==y_c)
-				ret = false;
-			node = node->next;
-		}
-		return ret;
-	} else return false;
+    bool ret = (tiled_map.tiles[x_c][y_c].data[3] & 0x0002)>0;
+    if (ret == true) {
+        std::list<NODE*>::iterator i = beings.begin();
+        while (i != beings.end() && ret == true) {
+            NODE *node = (*i);
+            if (get_x(node->coordinates)==x_c && get_y(node->coordinates)==y_c)
+                ret = false;
+            i++;
+        }
+        return ret;
+    } else return false;
 }
 
 unsigned char get_path_walk(unsigned short x, unsigned short y) {