- Moved Zone and Animation to List<>.

- Removed any reference to Node from codebase.

svn-id: r26452

11 files changed, 92 insertions, 154 deletions

diff --git a/engines/parallaction/animation.cpp b/engines/parallaction/animation.cpp
index 83977617e6..3d7e0a6190 100644
--- a/engines/parallaction/animation.cpp
+++ b/engines/parallaction/animation.cpp
@@ -63,18 +63,14 @@ char	_localNames[10][10];
 
 Animation *Parallaction::findAnimation(const char *name) {
 
-	Animation *v4 = (Animation*)_animations._next;
-
-	while (v4) {
-		if (!scumm_stricmp(name, v4->_label._text)) return v4;
-		v4 = (Animation*)v4->_next;
-	}
+	for (AnimationList::iterator it = _animations.begin(); it != _animations.end(); it++)
+		if (!scumm_stricmp((*it)->_label._text, name)) return *it;
 
 	return NULL;
 }
 
 
-Animation *Parallaction::parseAnimation(Script& script, Node *list, char *name) {
+Animation *Parallaction::parseAnimation(Script& script, AnimationList &list, char *name) {
 //	printf("parseAnimation(%s)\n", name);
 
 	Animation *vD0 = new Animation;
@@ -82,7 +78,7 @@ Animation *Parallaction::parseAnimation(Script& script, Node *list, char *name)
 	vD0->_label._text = (char*)malloc(strlen(name)+1);
 	strcpy(vD0->_label._text, name);
 
-	addNode(list, vD0);
+	list.push_front(vD0);
 
 	fillBuffers(script, true);
 	while (scumm_stricmp(_tokens[0], "endanimation")) {
@@ -151,14 +147,7 @@ Animation *Parallaction::parseAnimation(Script& script, Node *list, char *name)
 
 
 void Parallaction::freeAnimations() {
-	Animation *v4 = (Animation*)_animations._next;
-
-	while (v4) {
-		Animation *v = (Animation*)v4->_next;
-		delete v4;
-		v4 = (Animation*)v;
-	}
-
+	_animations.clear();
 	return;
 }
 
@@ -167,12 +156,13 @@ void Parallaction::freeAnimations() {
 void jobDisplayAnimations(void *parm, Job *j) {
 //	printf("jobDisplayAnimations()...\n");
 
-	Animation *v18 = (Animation*)_vm->_animations._next;
 	StaticCnv v14;
 
 	uint16 _si = 0;
 
-	for ( ; v18; v18 = (Animation*)v18->_next) {
+	for (AnimationList::iterator it = _vm->_animations.begin(); it != _vm->_animations.end(); it++) {
+
+		Animation *v18 = *it;
 
 		if ((v18->_flags & kFlagsActive) && ((v18->_flags & kFlagsRemove) == 0))   {
 			v14._width = v18->width();
@@ -211,9 +201,9 @@ void jobDisplayAnimations(void *parm, Job *j) {
 void jobEraseAnimations(void *arg_0, Job *j) {
 	debugC(3, kDebugJobs, "jobEraseAnimations");
 
-	Animation *a = (Animation*)_vm->_animations._next;
+	for (AnimationList::iterator it = _vm->_animations.begin(); it != _vm->_animations.end(); it++) {
 
-	for (; a; a=(Animation*)a->_next) {
+		Animation *a = *it;
 
 		if (((a->_flags & kFlagsActive) == 0) && ((a->_flags & kFlagsRemove) == 0)) continue;
 
@@ -460,12 +450,13 @@ void jobRunScripts(void *parm, Job *j) {
 
 	static uint16 modCounter = 0;
 
-	Animation *a = (Animation*)_vm->_animations._next;
-
 	StaticCnv v18;
 
-	if (a->_flags & kFlagsCharacter) a->_z = a->_top + a->height();
-	for ( ; a; a = (Animation*)a->_next) {
+	for (AnimationList::iterator it = _vm->_animations.begin(); it != _vm->_animations.end(); it++) {
+
+		Animation *a = *it;
+
+		if (a->_flags & kFlagsCharacter) a->_z = a->_top + a->height();
 
 		if ((a->_flags & kFlagsActing) == 0) continue;
 		InstructionList::iterator inst = a->_program->_ip;
@@ -628,36 +619,15 @@ void wrapLocalVar(LocalVariable *local) {
 	return;
 }
 
+int compareAnimationZ(const AnimationPointer &a1, const AnimationPointer &a2) {
+	if (a1->_z == a2->_z) return 0;
+	return (a1->_z < a2->_z ? -1 : 1);
+}
 
 
 void Parallaction::sortAnimations() {
-	Node v14;
-
 	_char._ani._z = _char._ani.height() + _char._ani._top;
-
-	Animation *vC = (Animation*)_animations._next;
-	Node *v8;
-	Animation *v4;
-
-	while (vC) {
-
-		v8 = &v14;
-
-		while ((v8->_next != NULL) && (vC->_z >= ((Animation*)(v8->_next))->_z)) {
-			v8 = v8->_next;
-		}
-
-		v4 = (Animation*)vC->_next;
-
-		addNode(v8, vC);
-
-		vC = v4;
-	}
-
-	_animations._prev = v14._prev;
-	_animations._next = v14._next;
-	_animations._next->_prev = &_animations;
-
+	_animations.sort(compareAnimationZ);
 	return;
 }
 
diff --git a/engines/parallaction/callables.cpp b/engines/parallaction/callables.cpp
index 570e1c0ea3..9117bbf686 100644
--- a/engines/parallaction/callables.cpp
+++ b/engines/parallaction/callables.cpp
@@ -403,7 +403,7 @@ void _c_finito(void *parm) {
 	}
 
 	// this code saves main character animation from being removed from the following code
-	removeNode(&_vm->_char._ani);
+	_vm->_animations.remove(&_vm->_char._ani);
 	_vm->_locationNames[0][0] = '\0';
 	_vm->_numLocations = 0;
 	_commandFlags = 0;
@@ -412,18 +412,16 @@ void _c_finito(void *parm) {
 	_engineFlags |= kEngineQuit;
 
 	// TODO (LIST): this sequence should be just _zones.clear()
-	_vm->freeZones(_vm->_zones._next);
-	_vm->_zones._next = NULL;
+	_vm->freeZones();
 
 	// TODO (LIST): this sequence should be just _animations.clear()
 	_vm->freeAnimations();
-	_vm->_animations._next = NULL;
 
 	// this dangerous flag can now be cleared
 	_engineFlags &= ~kEngineQuit;
 
 	// main character animation is restored
-	addNode(&_vm->_animations, &_vm->_char._ani);
+	_vm->_animations.push_front(&_vm->_char._ani);
 	_score = 0;
 
 	return;
diff --git a/engines/parallaction/commands.h b/engines/parallaction/commands.h
index 35ad6c15f3..91410218b9 100644
--- a/engines/parallaction/commands.h
+++ b/engines/parallaction/commands.h
@@ -63,7 +63,7 @@ union CommandData {
 	}
 };
 
-struct Command : public Node {
+struct Command {
 	uint16			_id;
 	CommandData 	u;
 	uint32			_flagsOn;
diff --git a/engines/parallaction/defs.h b/engines/parallaction/defs.h
index 37495e8f46..9e877db457 100644
--- a/engines/parallaction/defs.h
+++ b/engines/parallaction/defs.h
@@ -28,21 +28,6 @@
 
 namespace Parallaction {
 
-// TODO (LIST): this struct won't be used anymore as soon as List<> is enforced throughout the code.
-struct Node {
-	Node*	_prev;
-	Node*	_next;
-
-	Node() {
-		_prev = 0;
-		_next = 0;
-	}
-
-	virtual ~Node() {
-
-	}
-};
-
 template <class T>
 class ManagedList : public Common::List<T> {
 
@@ -84,6 +69,31 @@ public:
 		else
 			Common_List::insert(it, element);
 	}
+
+	// FIXME: this routine is a copy of the sort routine that can be found in common/func.cpp
+	// That wasn't usable because the 'less than' operator was hardcoded. Any comments or
+	// suggestions are welcome.
+	void sort(CompareFunction compare) {
+		iterator first = Common_List::begin();
+		iterator last = Common_List::end();
+
+		if (first == last)
+			return;
+
+		// Simple selection sort
+		iterator i(first);
+		for (; i != last; ++i) {
+			iterator minElem(i);
+			iterator j(i);
+			++j;
+			for (; j != last; ++j)
+				if (compare(*j, *minElem) < 0)
+					minElem = j;
+			if (minElem != i)
+				SWAP(*minElem, *i);
+		}
+	}
+
 };
 
 } // namespace Parallaction
@@ -94,3 +104,4 @@ public:
 
 
 
+
diff --git a/engines/parallaction/location.cpp b/engines/parallaction/location.cpp
index a59c2bbd26..8066c65afd 100644
--- a/engines/parallaction/location.cpp
+++ b/engines/parallaction/location.cpp
@@ -35,8 +35,6 @@ namespace Parallaction {
 
 void resolveLocationForwards();
 void switchBackground(const char* background, const char* mask);
-void parseWalkNodes(Script &script, Node *list);
-
 
 
 
@@ -142,13 +140,13 @@ void Parallaction::parseLocation(const char *filename) {
 			_location._endComment = parseComment(*_locationScript);
 		}
 		if (!scumm_stricmp(_tokens[0], "ZONE")) {
-			parseZone(*_locationScript, &_zones, _tokens[1]);
+			parseZone(*_locationScript, _zones, _tokens[1]);
 		}
 		if (!scumm_stricmp(_tokens[0], "NODES")) {
 			parseWalkNodes(*_locationScript, _location._walkNodes);
 		}
 		if (!scumm_stricmp(_tokens[0], "ANIMATION")) {
-			parseAnimation(*_locationScript, &_animations, _tokens[1]);
+			parseAnimation(*_locationScript, _animations, _tokens[1]);
 		}
 		if (!scumm_stricmp(_tokens[0], "SOUND")) {
 			strcpy(_soundFile, _tokens[1]);
@@ -193,15 +191,10 @@ void Parallaction::freeLocation() {
 	// TODO (LIST): helperNode should be rendered useless by the use of a Common::List<>
 	// to store Zones and Animations. Right now, it holds a list of Zones to be preserved
 	// but that'll pretty meaningless with a single list approach.
-	helperNode._prev = helperNode._next = NULL;
-	freeZones(_zones._next);
-	_zones._next = helperNode._next;
-	_zones._prev = helperNode._prev;
+	freeZones();
 	debugC(7, kDebugLocation, "freeLocation: zones freed");
 
 	freeAnimations();
-	_animations._next = 0;
-	_animations._prev = 0;
 	debugC(7, kDebugLocation, "freeLocation: animations freed");
 
 	if (_location._comment) {
@@ -334,7 +327,7 @@ void Parallaction::changeLocation(char *location) {
 		debugC(2, kDebugLocation, "changeLocation: changed cursor");
 	}
 
-	removeNode(&_char._ani);
+	_animations.remove(&_char._ani);
 	debugC(2, kDebugLocation, "changeLocation: removed character from the animation list");
 
 	freeLocation();
@@ -367,7 +360,7 @@ void Parallaction::changeLocation(char *location) {
 		}
 	}
 
-	addNode(&_animations, &_char._ani);
+	_animations.push_front(&_char._ani);
 	debugC(2, kDebugLocation, "changeLocation: new character added to the animation list");
 
 	strcpy(_saveData1, list[0].c_str());
diff --git a/engines/parallaction/parallaction.cpp b/engines/parallaction/parallaction.cpp
index 58ee2dcd78..490ca38e31 100644
--- a/engines/parallaction/parallaction.cpp
+++ b/engines/parallaction/parallaction.cpp
@@ -198,7 +198,7 @@ int Parallaction::init() {
 
 	initInventory();
 
-	addNode(&_animations, &_vm->_char._ani);
+	_animations.push_front(&_vm->_char._ani);
 	_gfx = new Gfx(this);
 
 	int midiDriver = MidiDriver::detectMusicDriver(MDT_MIDI | MDT_ADLIB | MDT_PREFER_MIDI);
@@ -805,35 +805,6 @@ void Parallaction::changeCharacter(const char *name) {
 	return;
 }
 
-// TODO (LIST): this routine will be removed
-void addNode(Node *list, Node *n) {
-
-	Node *v4 = list->_next;
-
-	if (v4 != NULL) {
-		v4->_prev = n;
-	}
-
-	n->_next = v4;
-	list->_next = n;
-	n->_prev = list;
-
-	return;
-}
-
-// TODO (LIST): this routine will be removed
-void removeNode(Node *n) {
-
-	Node *v4 = n->_next;
-	if (v4 != NULL) {
-		v4->_prev = n->_prev;
-	}
-
-	n->_prev->_next = n->_next;
-
-	return;
-}
-
 /*
 	helper function to provide *descending* ordering of the job list
 	(higher priorities values comes first in the list)
diff --git a/engines/parallaction/parallaction.h b/engines/parallaction/parallaction.h
index 8786998eea..0a63ee9380 100644
--- a/engines/parallaction/parallaction.h
+++ b/engines/parallaction/parallaction.h
@@ -200,11 +200,6 @@ extern const char 	*_minidrkiName;
 
 void waitUntilLeftClick();
 
-void addNode(Node *list, Node *n);
-void removeNode(Node *n);
-
-
-
 
 void jobRemovePickedItem(void*, Job *j);
 void jobDisplayDroppedItem(void*, Job *j);
@@ -321,7 +316,7 @@ public:
 	Zone 		*findZone(const char *name);
 	Zone   		*hitZone(uint32 type, uint16 x, uint16 y);
 	uint16		runZone(Zone*);
-	void 		freeZones(Node *list);
+	void 		freeZones();
 
 	void 		runDialogue(SpeakData*);
 
@@ -371,8 +366,8 @@ public:
 
 	Common::Point	_mousePos;
 
-	Node 	_zones;
-	Node 	_animations;
+	ZoneList 		_zones;
+	AnimationList 	_animations;
 
 protected:		// data
 
@@ -404,8 +399,6 @@ protected:		// data
 
 	JobList		_jobs;
 
-	Node 		helperNode;			// used for freeZones: to be removed
-
 protected:		// members
 	bool detectGame(void);
 
@@ -435,13 +428,13 @@ protected:		// members
 	void 		switchBackground(const char* background, const char* mask);
 	void 		freeLocation();
 
-	void		parseZone(Script &script, Node *list, char *name);
+	void		parseZone(Script &script, ZoneList &list, char *name);
 	void		parseZoneTypeBlock(Script &script, Zone *z);
 	void 		parseWalkNodes(Script& script, WalkNodeList &list);
 	void 		displayCharacterComment(ExamineData *data);
 	void 		displayItemComment(ExamineData *data);
 
-	Animation * parseAnimation(Script &script, Node *list, char *name);
+	Animation * parseAnimation(Script &script, AnimationList &list, char *name);
 	void		parseScriptLine(Instruction *inst, Animation *a, LocalVariable *locals);
 	void		loadProgram(Animation *a, char *filename);
 	LValue		getLValue(Instruction *inst, char *str, LocalVariable *locals, Animation *a);
diff --git a/engines/parallaction/saveload.cpp b/engines/parallaction/saveload.cpp
index 284ac9402c..db1cd636b0 100644
--- a/engines/parallaction/saveload.cpp
+++ b/engines/parallaction/saveload.cpp
@@ -87,8 +87,7 @@ void Parallaction::doLoadGame(uint16 slot) {
 	// need to invoke freeZones here with kEngineQuit set, because the
 	// call in changeLocation preserve certain zones.
 	_engineFlags |= kEngineQuit;
-	freeZones(_zones._next);
-	_zones._next = NULL;
+	freeZones();
 	_engineFlags &= ~kEngineQuit;
 
 	_numLocations = atoi(s);
diff --git a/engines/parallaction/walk.cpp b/engines/parallaction/walk.cpp
index 8ed3d61757..4910bc07ba 100644
--- a/engines/parallaction/walk.cpp
+++ b/engines/parallaction/walk.cpp
@@ -181,6 +181,9 @@ WalkNodeList *PathBuilder::buildPath(uint16 x, uint16 y) {
 	buildSubPath(pos, stop);
 	_list->insert(_list->begin(), _subPath.begin(), _subPath.end());
 
+	for (WalkNodeList::iterator it = _list->begin(); it != _list->end(); it++)
+		printf("node (%i, %i)\n", (*it)->_x, (*it)->_y);
+
 	delete v44;
 	return _list;
 }
diff --git a/engines/parallaction/zone.cpp b/engines/parallaction/zone.cpp
index 85e6f8edc9..ebf2136f05 100644
--- a/engines/parallaction/zone.cpp
+++ b/engines/parallaction/zone.cpp
@@ -34,12 +34,8 @@ namespace Parallaction {
 
 Zone *Parallaction::findZone(const char *name) {
 
-	Zone *v4 = (Zone*)_zones._next;
-
-	while (v4) {
-		if (!scumm_stricmp(name, v4->_label._text)) return v4;
-		v4 = (Zone*)v4->_next;
-	}
+	for (ZoneList::iterator it = _zones.begin(); it != _zones.end(); it++)
+		if (!scumm_stricmp((*it)->_label._text, name)) return *it;
 
 	return findAnimation(name);
 }
@@ -47,7 +43,7 @@ Zone *Parallaction::findZone(const char *name) {
 
 
 
-void Parallaction::parseZone(Script &script, Node *list, char *name) {
+void Parallaction::parseZone(Script &script, ZoneList &list, char *name) {
 //	printf("parseZone(%s)", name);
 
 	if (findZone(name)) {
@@ -62,7 +58,7 @@ void Parallaction::parseZone(Script &script, Node *list, char *name) {
 	z->_label._text = (char*)malloc(strlen(name)+1);
 	strcpy(z->_label._text, name);
 
-	addNode(list, z);
+	list.push_front(z);
 
 	fillBuffers(script, true);
 	while (scumm_stricmp(_tokens[0], "endzone")) {
@@ -112,13 +108,14 @@ void Parallaction::parseZone(Script &script, Node *list, char *name) {
 	return;
 }
 
-void Parallaction::freeZones(Node *list) {
+void Parallaction::freeZones() {
 	debugC(1, kDebugLocation, "freeZones: kEngineQuit = %i", _engineFlags & kEngineQuit);
 
-	Zone *z = (Zone*)list;
-	Zone *v8 = NULL;
+	ZoneList::iterator it = _zones.begin();
 
-	for (; z; ) {
+	while ( it != _zones.end() ) {
+
+		Zone* z = *it;
 
 		// WORKAROUND: this huge condition is needed because we made TypeData a collection of structs
 		// instead of an union. So, merge->_obj1 and get->_icon were just aliases in the original engine,
@@ -132,16 +129,12 @@ void Parallaction::freeZones(Node *list) {
 
 			debugC(1, kDebugLocation, "freeZones preserving zone '%s'", z->_label._text);
 
-			v8 = (Zone*)z->_next;
-			removeNode(z);					// HelperNode holds a list of zones to be preserved. There's code in freeLocation to deal with this too.
-			addNode(&helperNode, z);		// Can't we simply delete the other zones in the list and keep the good ones?
-			z = v8;
-			continue;
-		}
+			it++;
+
+		} else
+
+			it = _zones.erase(it);
 
-		Zone *z2 = (Zone*)z->_next;
-		delete z;
-		z = z2;
 	}
 
 	return;
@@ -514,11 +507,12 @@ Zone *Parallaction::hitZone(uint32 type, uint16 x, uint16 y) {
 
 	uint16 _di = y;
 	uint16 _si = x;
-	Zone *z = (Zone*)_zones._next;
 
-	for (; z; z = (Zone*)z->_next) {
+	for (ZoneList::iterator it = _zones.begin(); it != _zones.end(); it++) {
 //		printf("Zone name: %s", z->_name);
 
+		Zone *z = *it;
+
 		if (z->_flags & kFlagsRemove) continue;
 
 		Common::Rect r;
@@ -573,10 +567,11 @@ Zone *Parallaction::hitZone(uint32 type, uint16 x, uint16 y) {
 
 	}
 
-	Animation *a = (Animation*)_animations._next;
 
 	int16 _a, _b, _c, _d, _e, _f;
-	for (; a; a = (Animation*)a->_next) {
+	for (AnimationList::iterator it = _animations.begin(); it != _animations.end(); it++) {
+
+		Animation *a = *it;
 
 		_a = (a->_flags & kFlagsActive) ? 1 : 0;															   // _a: active Animation
 		_e = ((_si >= a->_left + a->width()) || (_si <= a->_left)) ? 0 : 1;		// _e: horizontal range
diff --git a/engines/parallaction/zone.h b/engines/parallaction/zone.h
index 7689f216a4..1a0a616624 100644
--- a/engines/parallaction/zone.h
+++ b/engines/parallaction/zone.h
@@ -189,7 +189,7 @@ struct Label {
 	}
 };
 
-struct Zone : public Node {
+struct Zone {
 	int16 			_left;
 	int16			_top;
 	int16			_right;
@@ -212,6 +212,9 @@ struct Zone : public Node {
 	virtual uint16 height() const;
 };
 
+typedef Zone* ZonePointer;
+typedef ManagedList<ZonePointer> ZoneList;
+
 struct LocalVariable {
 	int16		_value;
 	int16		_min;
@@ -243,7 +246,7 @@ enum InstructionFlags {
 
 struct Animation;
 
-struct Instruction : public Node {
+struct Instruction {
 	uint32	_index;
 	uint32	_flags;
 	struct {
@@ -302,6 +305,8 @@ struct Animation : public Zone  {
 	byte* getFrameData(uint32 index) const;
 };
 
+typedef Animation* AnimationPointer;
+typedef ManagedList<AnimationPointer> AnimationList;
 
 void	dropItem(uint16 v);
 int16	pickupItem(Zone *z);