SCI: Replaced vertex list used for dijkstra algo by Common::List; got rid of include/list.h

svn-id: r38829

2 files changed, 16 insertions, 128 deletions

diff --git a/engines/sci/engine/kpathing.cpp b/engines/sci/engine/kpathing.cpp
index 510d831686..45bd19a32d 100644
--- a/engines/sci/engine/kpathing.cpp
+++ b/engines/sci/engine/kpathing.cpp
@@ -29,7 +29,6 @@
 
 #include "sci/include/engine.h"
 #include "sci/engine/aatree.h"
-#include "sci/include/list.h"
 #include "sci/gfx/gfx_widgets.h"
 
 #include "common/list.h"
@@ -111,9 +110,6 @@ struct Vertex {
 		Vertex *cle_prev;	// previous element
 	} entries;
 
-	// Dijkstra list entry
-	LIST_ENTRY(Vertex) dijkstra;	// TODO: Convert this
-
 	// Distance from starting vertex
 	float dist;
 
@@ -1379,13 +1375,12 @@ static void dijkstra(PathfindingState *s) {
 	// Parameters: (PathfindingState *) s: The pathfinding state
 	// Returns   : (void)
 	Polygon *polygon;
+
 	// Vertices of which the shortest path is known
-	LIST_HEAD(done_head, Vertex) done;
-	// The remaining vertices
-	LIST_HEAD(remain_head, Vertex) remain;
+	VertexList done;
 
-	LIST_INIT(remain);
-	LIST_INIT(done);
+	// The remaining vertices
+	VertexList remain;
 
 	// Start out with all vertices in set remain
 	for (PolygonList::iterator it = s->polygons.begin(); it != s->polygons.end(); ++it) {
@@ -1393,7 +1388,7 @@ static void dijkstra(PathfindingState *s) {
 		Vertex *vertex;
 
 		CLIST_FOREACH(vertex, &polygon->vertices, entries) {
-			LIST_INSERT_HEAD(&remain, vertex, dijkstra);
+			remain.push_front(vertex);
 		}
 	}
 
@@ -1401,14 +1396,16 @@ static void dijkstra(PathfindingState *s) {
 
 	// Loop until we find vertex_end
 	while (1) {
-		int i;
-		Vertex *vertex, *vertex_min = 0;
-		float min = HUGE_DISTANCE;
-
 		// Find vertex at shortest distance from set done
-		LIST_FOREACH(vertex, &remain, dijkstra) {
+		VertexList::iterator it;
+		VertexList::iterator vertex_min_it = remain.end();
+		Vertex *vertex_min = 0;
+		float min = HUGE_DISTANCE;
+		for (it = remain.begin(); it != remain.end(); ++it) {
+			Vertex *vertex = *it;
 			if (vertex->dist < min) {
-				vertex_min = vertex;
+				vertex_min_it = it;
+				vertex_min = *vertex_min_it;
 				min = vertex->dist;
 			}
 		}
@@ -1423,10 +1420,10 @@ static void dijkstra(PathfindingState *s) {
 			return;
 
 		// Move vertex from set remain to set done
-		LIST_REMOVE(vertex_min, dijkstra);
-		LIST_INSERT_HEAD(&done, vertex_min, dijkstra);
+		done.push_front(vertex_min);
+		remain.erase(vertex_min_it);
 
-		for (i = 0; i < s->vertices; i++) {
+		for (int i = 0; i < s->vertices; i++) {
 			// Adjust upper bound for all vertices that are visible from vertex_min
 			if (IS_VISIBLE(s, vertex_min->idx, i)) {
 				float new_dist;
diff --git a/engines/sci/include/list.h b/engines/sci/include/list.h
deleted file mode 100644
index 73a605c74c..0000000000
--- a/engines/sci/include/list.h
+++ /dev/null
@@ -1,109 +0,0 @@
-/* ScummVM - Graphic Adventure Engine
- *
- * ScummVM is the legal property of its developers, whose names
- * are too numerous to list here. Please refer to the COPYRIGHT
- * file distributed with this source distribution.
- *
- * This program is free software; you can redistribute it and/or
- * modify it under the terms of the GNU General Public License
- * as published by the Free Software Foundation; either version 2
- * of the License, or (at your option) any later version.
-
- * This program is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
- * GNU General Public License for more details.
-
- * You should have received a copy of the GNU General Public License
- * along with this program; if not, write to the Free Software
- * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
- *
- * $URL$
- * $Id$
- *
- */
-
-/*
- * Copyright (c) 1991, 1993
- *	The Regents of the University of California.  All rights reserved.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * are met:
- * 1. Redistributions of source code must retain the above copyright
- *    notice, this list of conditions and the following disclaimer.
- * 2. Redistributions in binary form must reproduce the above copyright
- *    notice, this list of conditions and the following disclaimer in the
- *    documentation and/or other materials provided with the distribution.
- * 3. Neither the name of the University nor the names of its contributors
- *    may be used to endorse or promote products derived from this software
- *    without specific prior written permission.
- *
- * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
- * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
- * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
- * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
- * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
- * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
- * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
- * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
- * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
- * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
- * SUCH DAMAGE.
- *
- *	@(#)queue.h	8.5 (Berkeley) 8/20/94
- */
-
-/* 2006-04-21 Modified by Walter van Niftrik. */
-
-#ifndef _SCI_LIST_H
-#define _SCI_LIST_H
-
-#include "common/scummsys.h"
-
-namespace Sci {
-
-/* List definitions. */
-#define LIST_HEAD(name, type)						\
-struct name {								\
-	type *lh_first;	/* first element */			\
-}
-
-#define LIST_ENTRY(type)						\
-struct {								\
-	type *le_next;	/* next element */			\
-	type **le_prev;	/* address of previous next element */	\
-}
-
-#define LIST_INIT(head) do {						\
-	(head).lh_first = NULL;					\
-} while (0)
-
-#define LIST_INSERT_HEAD(head, elm, field) do {				\
-	if (((elm)->field.le_next = (head)->lh_first) != NULL)		\
-		(head)->lh_first->field.le_prev = &(elm)->field.le_next;\
-	(head)->lh_first = (elm);					\
-	(elm)->field.le_prev = &(head)->lh_first;			\
-} while (0)
-
-#define LIST_REMOVE(elm, field) do {					\
-	if ((elm)->field.le_next != NULL)				\
-		(elm)->field.le_next->field.le_prev =			\
-		    (elm)->field.le_prev;				\
-	*(elm)->field.le_prev = (elm)->field.le_next;			\
-} while (0)
-
-#define LIST_FOREACH(var, head, field)					\
-	for ((var) = ((head)->lh_first);				\
-		(var);							\
-		(var) = ((var)->field.le_next))
-
-/* List access methods. */
-#define LIST_EMPTY(head)		((head)->lh_first == NULL)
-#define LIST_FIRST(head)		((head)->lh_first)
-#define LIST_NEXT(elm, field)		((elm)->field.le_next)
-
-
-} // End of namespace Sci
-
-#endif /* !_SCI_LIST_H */