From 316eefa41213edf0e62fa25658674047fbadae95 Mon Sep 17 00:00:00 2001
From: Sebastian Leske <sebastian.leske@sleske.name>
Date: Fri, 13 Nov 2015 08:27:07 +0100
Subject: Refactor:Remove unused file routech.c

---
 navit/CMakeLists.txt |   2 +-
 navit/Makefile.am    |   2 +-
 navit/navit.c        |   3 -
 navit/routech.c      | 578 ---------------------------------------------------
 4 files changed, 2 insertions(+), 583 deletions(-)
 delete mode 100644 navit/routech.c

diff --git a/navit/CMakeLists.txt b/navit/CMakeLists.txt
index daf8abe8d..5333c9ff4 100644
--- a/navit/CMakeLists.txt
+++ b/navit/CMakeLists.txt
@@ -8,7 +8,7 @@ include_directories( "${CMAKE_CURRENT_SOURCE_DIR}/support")
 set(NAVIT_SRC announcement.c atom.c attr.c cache.c callback.c command.c config_.c coord.c country.c data_window.c debug.c
    event.c file.c geom.c graphics.c gui.c item.c layout.c log.c main.c map.c maps.c
    linguistics.c mapset.c maptype.c menu.c messages.c bookmarks.c navit.c navit_nls.c navigation.c osd.c param.c phrase.c plugin.c popup.c
-   profile.c profile_option.c projection.c roadprofile.c route.c routech.c script.c search.c speech.c start_real.c sunriset.c transform.c track.c 
+   profile.c profile_option.c projection.c roadprofile.c route.c script.c search.c speech.c start_real.c sunriset.c transform.c track.c
    search_houseno_interpol.c util.c vehicle.c vehicleprofile.c xmlconfig.c )
 
 if(NOT USE_PLUGINS)
diff --git a/navit/Makefile.am b/navit/Makefile.am
index 94b68be7c..7115a6c6e 100644
--- a/navit/Makefile.am
+++ b/navit/Makefile.am
@@ -51,7 +51,7 @@ EXTRA_DIST = navit_shipped.xml navit.dtd
 lib@LIBNAVIT@_la_SOURCES = announcement.c atom.c attr.c cache.c callback.c command.c config_.c coord.c country.c data_window.c debug.c \
 	event.c event_glib.h file.c geom.c graphics.c gui.c item.c layout.c log.c main.c map.c maps.c \
 	linguistics.c mapset.c maptype.c menu.c messages.c bookmarks.c bookmarks.h navit.c navigation.c osd.c param.c phrase.c plugin.c popup.c \
-	profile.c profile_option.c projection.c roadprofile.c route.c routech.c search.c search_houseno_interpol.c script.c speech.c start_real.c \
+	profile.c profile_option.c projection.c roadprofile.c route.c search.c search_houseno_interpol.c script.c speech.c start_real.c \
 	transform.c track.c util.c vehicle.c vehicleprofile.c xmlconfig.c \
 	announcement.h atom.h attr.h attr_def.h cache.h callback.h color.h command.h config_.h coord.h country.h \
 	android.h data.h data_window.h data_window_int.h debug.h destination.h draw_info.h endianess.h event.h \
diff --git a/navit/navit.c b/navit/navit.c
index 0ac6783cd..f9a96df20 100644
--- a/navit/navit.c
+++ b/navit/navit.c
@@ -2164,9 +2164,6 @@ navit_init(struct navit *this_)
 		navit_draw_async(this_, 1);
 	if (callback)
 		callback_list_call_attr_1(this_->attr_cbl, attr_graphics_ready, this_);
-#if 0
-	routech_test(this_);
-#endif
 }
 
 void
diff --git a/navit/routech.c b/navit/routech.c
deleted file mode 100644
index 853b89b0e..000000000
--- a/navit/routech.c
+++ /dev/null
@@ -1,578 +0,0 @@
-#include <glib.h>
-#include <stdio.h>
-#include "item.h"
-#include "coord.h"
-#include "navit.h"
-#include "transform.h"
-#include "profile.h"
-#include "mapset.h"
-#include "map.h"
-
-FILE *routefile;
-
-void routech_test(struct navit *navit);
-
-struct ch_edge {
-	int flags;
-	int weight;
-	struct item_id target,middle;
-};
-
-struct routech_search {
-	struct pq *pq;
-	GHashTable *hash;
-	int finished;
-	int dir;
-	unsigned int upper;
-	struct item_id *via;
-};
-
-
-struct pq_element {
-	struct item_id *node_id;
-	struct item_id *parent_node_id;
-	int stalled;
-	int key;
-	int heap_element;
-};
-
-struct pq_heap_element {
-	int key;
-	int element;
-};
-
-struct pq {
-	int capacity;
-	int size;
-	int step;
-	int elements_capacity;
-	int elements_size;
-	int elements_step;
-	struct pq_element *elements;
-	struct pq_heap_element *heap_elements;
-};
-
-static struct pq *
-pq_new(void)
-{
-	struct pq *ret=g_new(struct pq, 1);
-	ret->step=10;
-	ret->capacity=0;
-	ret->size=1;
-	ret->elements_step=10;
-	ret->elements_capacity=0;
-	ret->elements_size=1;
-	ret->elements=NULL;
-	ret->heap_elements=NULL;
-	return ret;
-}
-
-static int
-pq_insert(struct pq *pq, int key, struct item_id *node_id)
-{
-	int element,i;
-	if (pq->size >= pq->capacity) {
-		pq->capacity += pq->step;
-		pq->heap_elements=g_renew(struct pq_heap_element, pq->heap_elements, pq->capacity);
-	}
-	if (pq->elements_size >= pq->elements_capacity) {
-		pq->elements_capacity += pq->elements_step;
-		pq->elements=g_renew(struct pq_element, pq->elements, pq->elements_capacity);
-	}
-	element=pq->elements_size++;
-	pq->elements[element].node_id=node_id;
-	i=pq->size++;
-	while (i > 1 && pq->heap_elements[i/2].key > key) {
-		pq->heap_elements[i]=pq->heap_elements[i/2];
-		pq->elements[pq->heap_elements[i].element].heap_element=i;
-		i/=2;
-	}
-	pq->heap_elements[i].key=key;
-	pq->heap_elements[i].element=element;
-	pq->elements[element].heap_element=i;
-	pq->elements[element].key=key;
-	return element;
-}
-
-static int
-pq_get_key(struct pq *pq, int element, int *key)
-{
-	*key=pq->elements[element].key;
-	return 1;
-}
-
-static void
-pq_set_parent(struct pq *pq, int element, struct item_id *node_id, int stalled)
-{
-	pq->elements[element].parent_node_id=node_id;
-	pq->elements[element].stalled=stalled;
-}
-
-static struct item_id *
-pq_get_parent_node_id(struct pq *pq, int element)
-{
-	return pq->elements[element].parent_node_id;
-}
-
-static void
-pq_set_stalled(struct pq *pq, int element, int stalled)
-{
-	pq->elements[element].stalled=stalled;
-}
-
-static int
-pq_get_stalled(struct pq *pq, int element)
-{
-	return pq->elements[element].stalled;
-}
-
-static int
-pq_is_deleted(struct pq *pq, int element)
-{
-	return (pq->elements[element].heap_element == 0);
-}
-
-static int
-pq_min(struct pq *pq)
-{
-	return (pq->heap_elements[1].key);
-}
-
-static void
-pq_decrease_key(struct pq *pq, int element, int key)
-{
-	int i=pq->elements[element].heap_element;
-	while (i > 1 && pq->heap_elements[i/2].key > key) {
-		pq->heap_elements[i]=pq->heap_elements[i/2];
-		pq->elements[pq->heap_elements[i].element].heap_element=i;
-		i/=2;
-	}
-	pq->heap_elements[i].element=element;
-	pq->heap_elements[i].key=key;
-	pq->elements[element].heap_element=i;
-	pq->elements[element].key=key;
-}
-
-static int
-pq_delete_min(struct pq *pq, struct item_id **node_id, int *key, int *element)
-{
-	struct pq_heap_element min, last;
-	int i=1,j;
-	if (pq->size <= 1)
-		return 0;
-	min=pq->heap_elements[1];
-	if (node_id)
-		*node_id=pq->elements[min.element].node_id;
-	if (key)
-		*key=min.key;
-	if (element)
-		*element=min.element;
-	pq->elements[min.element].heap_element=0;
-	min.element=0;
-	last=pq->heap_elements[--pq->size];
-	while (i <= pq->size / 2) {
-		j=2*i;
-		if (j < pq->size && pq->heap_elements[j].key > pq->heap_elements[j+1].key)
-			j++;
-		if (pq->heap_elements[j].key >= last.key)
-			break;
-		pq->heap_elements[i]=pq->heap_elements[j];
-		pq->elements[pq->heap_elements[i].element].heap_element=i;
-		i=j;
-	}
-	pq->heap_elements[i]=last;
-	pq->elements[last.element].heap_element=i;
-	return 1;
-}
-
-static int
-pq_is_empty(struct pq *pq)
-{
-	return pq->size <= 1;
-}
-
-static void
-pq_check(struct pq *pq)
-{
-	int i;
-	for (i = 2 ; i < pq->size ; i++) {
-		if (pq->heap_elements[i/2].key > pq->heap_elements[i].key) {
-			printf("%d vs %d\n", pq->heap_elements[i/2].key, pq->heap_elements[i].key);
-			return;
-		}
-	}
-	for (i = 1 ; i < pq->size ; i++) {
-		if (i != pq->elements[pq->heap_elements[i].element].heap_element) {
-			printf("Error: heap_element %d points to element %d, but that points to %d\n",i,pq->heap_elements[i].element,pq->elements[pq->heap_elements[i].element].heap_element);
-		}
-	}
-}
-
-static struct routech_search *
-routech_search_new(int dir)
-{
-	struct routech_search *ret=g_new0(struct routech_search, 1);
-	ret->pq=pq_new();
-	ret->hash=g_hash_table_new_full(item_id_hash, item_id_equal, g_free, NULL);
-	ret->upper=UINT_MAX;
-	ret->dir=dir;
-
-	return ret;
-}
-
-static int
-routech_insert_node(struct routech_search *search, struct item_id **id, int val)
-{
-	struct item_id *ret;
-	int e;
-	if (g_hash_table_lookup_extended(search->hash, *id, (gpointer)&ret, (gpointer)&e)) {
-		int oldval;
-		pq_get_key(search->pq, e, &oldval);
-		// printf("Node = %d\n",node);
-		if (oldval > val) {
-			pq_decrease_key(search->pq, e, val);
-			*id=ret;
-			return e;
-		}
-		return 0;
-	}
-	ret=g_new(struct item_id, 1);
-	*ret=**id;
-	e=pq_insert(search->pq, val, ret);
-	g_hash_table_insert(search->hash, ret, GINT_TO_POINTER(e));
-	*id=ret;
-	return e;
-}
-
-
-static int
-routech_find_nearest(struct mapset *ms, struct coord *c, struct item_id *id, struct map **map_ret)
-{
-	int dst=50;
-	int dstsq=dst*dst;
-	int ret=0;
-	struct map_selection sel;
-	struct map_rect *mr;
-	struct mapset_handle *msh;
-	struct map *map;
-	struct item *item;
-	sel.next=NULL;
-	sel.order=18;
-	sel.range.min=type_ch_node;
-	sel.range.max=type_ch_node;
-	sel.u.c_rect.lu.x=c->x-dst;
-	sel.u.c_rect.lu.y=c->y+dst;
-	sel.u.c_rect.rl.x=c->x+dst;
-	sel.u.c_rect.rl.y=c->y-dst;
-	printf("0x%x,0x%x-0x%x,0x%x\n",sel.u.c_rect.lu.x,sel.u.c_rect.lu.y,sel.u.c_rect.rl.x,sel.u.c_rect.rl.y);
-	msh=mapset_open(ms);
-	while ((map=mapset_next(msh, 1))) {
-		mr=map_rect_new(map, &sel);
-		if (!mr)
-			continue;
-		while ((item=map_rect_get_item(mr))) {
-			struct coord cn;
-			if (item->type == type_ch_node && item_coord_get(item, &cn, 1)) {
-				int dist=transform_distance_sq(&cn, c);
-				if (dist < dstsq) {	
-					dstsq=dist;
-					id->id_hi=item->id_hi;
-					id->id_lo=item->id_lo;
-					*map_ret=map;
-					ret=1;
-				}
-			}
-		}
-		map_rect_destroy(mr);
-	}
-	mapset_close(msh);
-	dbg_assert(ret==1);
-	return ret;
-}
-
-static int
-routech_edge_valid(struct ch_edge *edge, int dir)
-{
-	if (edge->flags & (1 << dir))
-		return 1;
-	return 0;
-}
-
-static void
-routech_stall(struct map_rect *mr, struct routech_search *curr, struct item_id *id, int key)
-{
-	struct stall_element {
-		struct item_id id;
-		int key;
-	} *se;
-	GList *list=NULL;
-	struct item *item;
-	struct attr edge_attr;
-
-	int index=GPOINTER_TO_INT(g_hash_table_lookup(curr->hash, id));
-	pq_set_stalled(curr->pq, index, key);
-	se=g_new(struct stall_element, 1);
-	se->id=*id;
-	se->key=key;
-	list=g_list_append(list, se);
-	while (list) {
-		se=list->data;
-		key=se->key;
-		item=map_rect_get_item_byid(mr, se->id.id_hi, se->id.id_lo);
-		while (item_attr_get(item, attr_ch_edge, &edge_attr)) {
-			struct ch_edge *edge=edge_attr.u.data;
-			if (routech_edge_valid(edge, curr->dir)) {
-				int index=GPOINTER_TO_INT(g_hash_table_lookup(curr->hash, &edge->target));
-				if (index) {
-					int newkey=key+edge->weight;
-					int target_key;
-					pq_get_key(curr->pq, index, &target_key);
-					if (newkey < target_key) {
-						if (!pq_get_stalled(curr->pq, index)) {
-							pq_set_stalled(curr->pq, index, newkey);
-							se=g_new(struct stall_element, 1);
-							se->id=edge->target;
-							se->key=newkey;
-							list=g_list_append(list, se);
-						}	
-					}
-				}
-			}
-		}
-		list=g_list_remove(list, se);
-		g_free(se);
-	}
-}
-
-static void
-routech_relax(struct map_rect **mr, struct routech_search *curr, struct routech_search *opposite)
-{
-	int val,element;
-	struct item_id *id;
-	struct item *item;
-	struct attr edge_attr;
-	int opposite_element;
-	
-	if (!pq_delete_min(curr->pq, &id, &val, &element)) {
-		return;
-	}
-	pq_check(curr->pq);
-	opposite_element=GPOINTER_TO_INT(g_hash_table_lookup(opposite->hash, id));
-	if (opposite_element && pq_is_deleted(opposite->pq, opposite_element)) {
-		int opposite_val;
-		pq_get_key(opposite->pq, opposite_element, &opposite_val);
-		if (val+opposite_val < curr->upper) {
-			curr->upper=opposite->upper=val+opposite_val;
-			printf("%d path found: 0x%x,0x%x ub = %d\n",curr->dir,id->id_hi,id->id_lo,curr->upper);
-			curr->via=opposite->via=id;
-		}
-	}
-	if (pq_get_stalled(curr->pq, element)) 
-		return;
-	item=map_rect_get_item_byid(mr[0], id->id_hi, id->id_lo);
-	while (item_attr_get(item, attr_ch_edge, &edge_attr)) {
-		struct ch_edge *edge=edge_attr.u.data;
-		struct item_id *target_id=&edge->target;
-		int element;
-		if (routech_edge_valid(edge, curr->dir)) {
-			int index=GPOINTER_TO_INT(g_hash_table_lookup(curr->hash, target_id));
-			if (index && routech_edge_valid(edge, 1-curr->dir)) {
-				int newkey,stallkey;
-				stallkey=pq_get_stalled(curr->pq, index);
-				if (stallkey)
-					newkey=stallkey;
-				else
-					pq_get_key(curr->pq, index, &newkey);
-				newkey+=edge->weight;
-				if (newkey < val) {
-					routech_stall(mr[1], curr, id, newkey);
-					return;
-				}
-			}
-			element=routech_insert_node(curr, &target_id, edge->weight+val);
-			if (element) {
-				pq_set_parent(curr->pq, element, id, 0);
-			}
-		}
-	}
-}
-
-static void
-routech_print_coord(struct coord *c, FILE *out)
-{
-	int x=c->x;
-	int y=c->y;
-	char *sx="";
-	char *sy="";
-	if (x < 0) {
-		sx="-";
-		x=-x;
-	}
-	if (y < 0) {
-		sy="-";
-		y=-y;
-	}
-	fprintf(out,"%s0x%x %s0x%x\n",sx,x,sy,y);
-}
-
-static void
-routech_resolve_route(struct map_rect *mr, struct item_id *id, int flags, int dir)
-{
-	int i,count,max=16384;
-	struct coord *ca=g_alloca(sizeof(struct coord)*(max));
-	struct item *item;
-	int rev=0;
-	if (!(flags & 8) == dir)
-		rev=1;
-	item=map_rect_get_item_byid(mr, id->id_hi, id->id_lo);
-	dbg_assert(item->type >= type_line && item->type < type_area);
-	item->type=type_street_route;
-	
-        count=item_coord_get(item, ca, max);
-        item_dump_attr(item, item->map, routefile);
-	fprintf(routefile,"debug=\"flags=%d dir=%d rev=%d\"",flags,dir,rev);
-        fprintf(routefile,"\n");
-	if (rev) {
-		for (i = count-1 ; i >= 0 ; i--)
-			routech_print_coord(&ca[i], routefile);
-	} else {
-		for (i = 0 ; i < count ; i++)
-			routech_print_coord(&ca[i], routefile);
-	}
-}
-
-static int
-routech_find_edge(struct map_rect *mr, struct item_id *from, struct item_id *to, struct item_id *middle)
-{
-	struct item *item=map_rect_get_item_byid(mr, from->id_hi, from->id_lo);
-	struct attr edge_attr;
-	dbg_assert(item->type == type_ch_node);
-	dbg(lvl_debug,"type %s\n",item_to_name(item->type));
-	dbg(lvl_debug,"segment item=%p\n",item);
-	while (item_attr_get(item, attr_ch_edge, &edge_attr)) {
-		struct ch_edge *edge=edge_attr.u.data;
-		dbg(lvl_debug,"flags=%d\n",edge->flags);
-		if (edge->target.id_hi == to->id_hi && edge->target.id_lo == to->id_lo) {
-			*middle=edge->middle;
-			return edge->flags;
-		}
-	}
-	dbg(lvl_debug,"** not found\n");
-	return 0;
-}
-
-static void
-routech_resolve(struct map_rect *mr, struct item_id *from, struct item_id *to, int dir)
-{
-	struct item_id middle_node;
-	int res;
-	if (dir) 
-		res=routech_find_edge(mr, to, from, &middle_node);
-	else
-		res=routech_find_edge(mr, from, to, &middle_node);
-	dbg(lvl_debug,"res=%d\n",res);
-	if (res & 4) {
-		routech_resolve(mr, from, &middle_node, 1);
-		routech_resolve(mr, &middle_node, to, 0);
-	} else 
-		routech_resolve_route(mr, &middle_node, res, dir);
-}
-
-static void
-routech_find_path(struct map_rect *mr, struct routech_search *search)
-{
-	struct item_id *curr_node=search->via;
-	GList *i,*n,*list=NULL;
-	dbg(lvl_debug,"node %p\n",curr_node);
-	for (;;) {
-		int element=GPOINTER_TO_INT(g_hash_table_lookup(search->hash, curr_node));
-		struct item_id *next_node=pq_get_parent_node_id(search->pq,element);
-		if (search->dir) 
-			list=g_list_append(list, curr_node);
-		else
-			list=g_list_prepend(list, curr_node);
-		dbg(lvl_debug,"element %d\n",element);
-		dbg(lvl_debug,"next node %p\n",next_node);
-		if (!next_node)
-			break;
-		curr_node=next_node;
-	}
-	i=list;
-	while (i && (n=g_list_next(i))) {
-		routech_resolve(mr, i->data, n->data, search->dir);
-		i=n;
-	}
-}
-
-void
-routech_test(struct navit *navit)
-{
-	struct attr mapset;
-	struct coord src={0x3fd661,0x727146};
-	struct coord dst={0xfff07fc2,0x4754c9};
-	struct item_id id[2],*id_ptr;
-	struct routech_search *search[2],*curr,*opposite;
-	struct map *map[2];
-	struct map_rect *mr[2];
-	int element;
-	int k;
-	int search_id=0;
-	int i;
-
-	navit_get_attr(navit, attr_mapset, &mapset, NULL);
-	routech_find_nearest(mapset.u.mapset, &src, &id[0], &map[0]);
-	routech_find_nearest(mapset.u.mapset, &dst, &id[1], &map[1]);
-	for (k = 0 ; k < 2 ; k++) {
-	profile(0,"start\n");
-	search[0]=routech_search_new(0);
-	search[1]=routech_search_new(1);
-	printf("Start 0x%x,0x%x\n",id[0].id_hi,id[0].id_lo);
-	printf("End 0x%x,0x%x\n",id[1].id_hi,id[1].id_lo);
-	id_ptr=&id[0];
-	element=routech_insert_node(search[0], &id_ptr, 0);
-	pq_set_parent(search[0]->pq, element, NULL, 0);
-
-	id_ptr=&id[1];
-	element=routech_insert_node(search[1], &id_ptr, 0);
-	pq_set_parent(search[1]->pq, element, NULL, 0);
-
-	mr[0]=map_rect_new(map[0], NULL);
-	mr[1]=map_rect_new(map[0], NULL);
-	for (i=0 ; i < 5000 ; i++) {
-		if (pq_is_empty(search[0]->pq) && pq_is_empty(search[1]->pq)) 
-			break;
-		if (!pq_is_empty(search[1-search_id]->pq)) {
-			search_id=1-search_id;
-		}
-		if (search[0]->finished)
-			search_id=1;
-		if (search[1]->finished)
-			search_id=0;
-		curr=search[search_id];
-		opposite=search[1-search_id];
-		if (pq_is_empty(curr->pq)) {
-			dbg(lvl_debug,"empty\n");
-			break;
-		}
-		routech_relax(mr, curr, opposite);
-		if (pq_min(curr->pq) > curr->upper) {
-			dbg(lvl_debug,"min %d upper %d\n",pq_min(curr->pq), curr->upper);
-			curr->finished=1;
-		}
-		if (curr->finished && opposite->finished) {
-			dbg(lvl_debug,"finished\n");
-			break;
-		}
-	}
-	
-	printf("finished %d\n",search[0]->upper);
-	profile(0,"finished\n");
-	}
-	routefile=fopen("route.txt","w");
-	routech_find_path(mr[0], search[0]);
-	routech_find_path(mr[0], search[1]);
-	fclose(routefile);
-        printf("Heap size %d vs %d\n",search[0]->pq->size,search[1]->pq->size);
-        printf("Element size %d vs %d\n",search[0]->pq->elements_size,search[1]->pq->elements_size);
-
-}
-- 
cgit v1.2.1