trunk/src/nodesx.c

/***************************************
 $Header: /home/amb/CVS/routino/src/nodesx.c,v 1.27 2009-07-19 12:54:07 amb Exp $

 Extented Node data type functions.

 Part of the Routino routing software.
 ******************/ /******************
 This file Copyright 2008,2009 Andrew M. Bishop

 This program is free software: you can redistribute it and/or modify
 it under the terms of the GNU Affero General Public License as published by
 the Free Software Foundation, either version 3 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 Affero General Public License for more details.

 You should have received a copy of the GNU Affero General Public License
 along with this program.  If not, see <http://www.gnu.org/licenses/>.
 ***************************************/


#include <assert.h>
#include <stdlib.h>
#include <stdio.h>

#include "types.h"
#include "functions.h"
#include "nodesx.h"
#include "segmentsx.h"
#include "waysx.h"
#include "segments.h"
#include "nodes.h"


/* Constants */

/*+ The array size increment for NodesX (UK is ~10.3M raw nodes, this is ~78 increments). +*/
#define INCREMENT_NODESX (128*1024)


/* Functions */

static int sort_by_id(NodeX **a,NodeX **b);
static int sort_by_lat_long(NodeX **a,NodeX **b);


/*++++++++++++++++++++++++++++++++++++++
  Allocate a new node list.

  NodesX *NewNodeList Returns the node list.
  ++++++++++++++++++++++++++++++++++++++*/

NodesX *NewNodeList(void)
{
 NodesX *nodesx;

 nodesx=(NodesX*)calloc(1,sizeof(NodesX));

 nodesx->row=-1;

 return(nodesx);
}


/*++++++++++++++++++++++++++++++++++++++
  Free a node list.

  NodesX *nodesx The list to be freed.
  ++++++++++++++++++++++++++++++++++++++*/

void FreeNodeList(NodesX *nodesx)
{
 if(nodesx->xdata)
   {
    int i;
    for(i=0;i<=nodesx->row;i++)
       free(nodesx->xdata[i]);
    free(nodesx->xdata);
   }

 if(nodesx->gdata)
    free(nodesx->gdata);
 if(nodesx->idata)
    free(nodesx->idata);

 if(nodesx->ndata)
    free(nodesx->ndata);

 free(nodesx);
}


/*++++++++++++++++++++++++++++++++++++++
  Save the node list to a file.

  NodesX* nodesx The set of nodes to save.

  const char *filename The name of the file to save.
  ++++++++++++++++++++++++++++++++++++++*/

void SaveNodeList(NodesX* nodesx,const char *filename)
{
 index_t i;
 int fd;
 Nodes *nodes=calloc(1,sizeof(Nodes));
 index_t *offsets;
 ll_bin_t lat_min_bin,lat_max_bin,lon_min_bin,lon_max_bin;
 latlong_t lat_min,lat_max,lon_min,lon_max;
 int latbins,lonbins,latlonbin;

 assert(nodesx->sorted);        /* Must be sorted */
 assert(nodesx->gdata);         /* Must have gdata filled in */
 assert(nodesx->ndata);         /* Must have ndata filled in */

 printf("Writing Nodes: Nodes=0");
 fflush(stdout);

 /* Work out the range of data */

 lat_min=radians_to_latlong( 2);
 lat_max=radians_to_latlong(-2);
 lon_min=radians_to_latlong( 4);
 lon_max=radians_to_latlong(-4);

 for(i=0;i<nodesx->number;i++)
   {
    if(nodesx->idata[i]->latitude<lat_min)
       lat_min=nodesx->idata[i]->latitude;
    if(nodesx->idata[i]->latitude>lat_max)
       lat_max=nodesx->idata[i]->latitude;
    if(nodesx->idata[i]->longitude<lon_min)
       lon_min=nodesx->idata[i]->longitude;
    if(nodesx->idata[i]->longitude>lon_max)
       lon_max=nodesx->idata[i]->longitude;
   }

 /* Work out the offsets */

 lat_min_bin=latlong_to_bin(lat_min);
 lon_min_bin=latlong_to_bin(lon_min);
 lat_max_bin=latlong_to_bin(lat_max);
 lon_max_bin=latlong_to_bin(lon_max);

 latbins=(lat_max_bin-lat_min_bin)+1;
 lonbins=(lon_max_bin-lon_min_bin)+1;

 offsets=(index_t*)malloc((latbins*lonbins+1)*sizeof(index_t));

 latlonbin=0;

 for(i=0;i<nodesx->number;i++)
   {
    ll_bin_t latbin=latlong_to_bin(nodesx->gdata[i]->latitude )-lat_min_bin;
    ll_bin_t lonbin=latlong_to_bin(nodesx->gdata[i]->longitude)-lon_min_bin;
    int llbin=lonbin*latbins+latbin;

    for(;latlonbin<=llbin;latlonbin++)
       offsets[latlonbin]=i;
   }

 for(;latlonbin<=(latbins*lonbins);latlonbin++)
    offsets[latlonbin]=nodesx->number;

 /* Fill in a Nodes structure with the offset of the real data in the file after
    the Node structure itself. */

 nodes->number=nodesx->number;

 nodes->latbins=latbins;
 nodes->lonbins=lonbins;

 nodes->latzero=lat_min_bin;
 nodes->lonzero=lon_min_bin;

 nodes->data=NULL;
 nodes->offsets=(void*)sizeof(Nodes);
 nodes->nodes=(void*)(sizeof(Nodes)+(latbins*lonbins+1)*sizeof(index_t));

 /* Write out the Nodes structure and then the real data. */

 fd=OpenFile(filename);

 WriteFile(fd,nodes,sizeof(Nodes));

 WriteFile(fd,offsets,(latbins*lonbins+1)*sizeof(index_t));

 for(i=0;i<nodes->number;i++)
   {
    NodeX **nodex=FindNodeX(nodesx,nodesx->gdata[i]->id);
    Node   *node =&nodesx->ndata[nodex-nodesx->idata];

    WriteFile(fd,node,sizeof(Node));

    if(!((i+1)%10000))
      {
       printf("\rWriting Nodes: Nodes=%d",i+1);
       fflush(stdout);
      }
   }

 printf("\rWrote Nodes: Nodes=%d  \n",nodes->number);
 fflush(stdout);

 CloseFile(fd);

 /* Free the fake Nodes */

 free(nodes);
 free(offsets);
}


/*++++++++++++++++++++++++++++++++++++++
  Find a particular node.

  NodeX **FindNodeX Returns a pointer to the extended node with the specified id.

  NodesX* nodesx The set of nodes to process.

  node_t id The node id to look for.
  ++++++++++++++++++++++++++++++++++++++*/

NodeX **FindNodeX(NodesX* nodesx,node_t id)
{
 int start=0;
 int end=nodesx->number-1;
 int mid;

 assert(nodesx->sorted);        /* Must be sorted */
 assert(nodesx->idata);         /* Must have idata filled in */

 /* Binary search - search key exact match only is required.
  *
  *  # <- start  |  Check mid and move start or end if it doesn't match
  *  #           |
  *  #           |  Since an exact match is wanted we can set end=mid-1
  *  # <- mid    |  or start=mid+1 because we know that mid doesn't match.
  *  #           |
  *  #           |  Eventually either end=start or end=start+1 and one of
  *  # <- end    |  start or end is the wanted one.
  */

 if(end<start)                        /* There are no nodes */
    return(NULL);
 else if(id<nodesx->idata[start]->id) /* Check key is not before start */
    return(NULL);
 else if(id>nodesx->idata[end]->id)   /* Check key is not after end */
    return(NULL);
 else
   {
    do
      {
       mid=(start+end)/2;                 /* Choose mid point */

       if(nodesx->idata[mid]->id<id)      /* Mid point is too low */
          start=mid+1;
       else if(nodesx->idata[mid]->id>id) /* Mid point is too high */
          end=mid-1;
       else                               /* Mid point is correct */
          return(&nodesx->idata[mid]);
      }
    while((end-start)>1);

    if(nodesx->idata[start]->id==id)      /* Start is correct */
       return(&nodesx->idata[start]);

    if(nodesx->idata[end]->id==id)        /* End is correct */
       return(&nodesx->idata[end]);
   }

 return(NULL);
}


/*++++++++++++++++++++++++++++++++++++++
  Append a node to a newly created node list (unsorted).

  NodesX* nodesx The set of nodes to process.

  node_t id The node identification.

  double latitude The latitude of the node.

  double longitude The longitude of the node.
  ++++++++++++++++++++++++++++++++++++++*/

void AppendNode(NodesX* nodesx,node_t id,double latitude,double longitude)
{
 /* Check that the array has enough space. */

 if(nodesx->row==-1 || nodesx->col==INCREMENT_NODESX)
   {
    nodesx->row++;
    nodesx->col=0;

    if((nodesx->row%16)==0)
       nodesx->xdata=(NodeX**)realloc((void*)nodesx->xdata,(nodesx->row+16)*sizeof(NodeX*));

    nodesx->xdata[nodesx->row]=(NodeX*)malloc(INCREMENT_NODESX*sizeof(NodeX));
   }

 /* Insert the node */

 nodesx->xdata[nodesx->row][nodesx->col].id=id;
 nodesx->xdata[nodesx->row][nodesx->col].super=0;
 nodesx->xdata[nodesx->row][nodesx->col].latitude =radians_to_latlong(latitude);
 nodesx->xdata[nodesx->row][nodesx->col].longitude=radians_to_latlong(longitude);

 nodesx->col++;

 nodesx->sorted=0;
}


/*++++++++++++++++++++++++++++++++++++++
  Sort the node list.

  NodesX* nodesx The set of nodes to process.
  ++++++++++++++++++++++++++++++++++++++*/

void SortNodeList(NodesX* nodesx)
{
 index_t i;
 int duplicate;

 assert(nodesx->xdata);         /* Must have xdata filled in */

 printf("Sorting Nodes");
 fflush(stdout);

 /* Allocate the array of pointers and sort them */

 nodesx->idata=(NodeX**)realloc(nodesx->idata,(nodesx->row*INCREMENT_NODESX+nodesx->col)*sizeof(NodeX*));

 do
   {
    nodesx->number=0;

    for(i=0;i<(nodesx->row*INCREMENT_NODESX+nodesx->col);i++)
       if(nodesx->xdata[i/INCREMENT_NODESX][i%INCREMENT_NODESX].id!=NO_NODE)
         {
          nodesx->idata[nodesx->number]=&nodesx->xdata[i/INCREMENT_NODESX][i%INCREMENT_NODESX];
          nodesx->number++;
         }

    qsort(nodesx->idata,nodesx->number,sizeof(NodeX*),(int (*)(const void*,const void*))sort_by_id);

    duplicate=0;

    for(i=1;i<nodesx->number;i++)
      {
       if(nodesx->idata[i]->id==nodesx->idata[i-1]->id &&
          nodesx->idata[i]->id!=NO_NODE)
         {
          nodesx->idata[i-1]->id=NO_NODE;
          duplicate++;
         }
      }

    if(duplicate)
      {
       printf(" - %d duplicates found; trying again.\nSorting Nodes",duplicate);
       fflush(stdout);
      }
   }
 while(duplicate);

 printf("\rSorted Nodes \n");
 fflush(stdout);

 nodesx->sorted=1;
}


/*++++++++++++++++++++++++++++++++++++++
  Sort the nodes into id order.

  int sort_by_id Returns the comparison of the id fields.

  NodeX **a The first Node.

  NodeX **b The second Node.
  ++++++++++++++++++++++++++++++++++++++*/

static int sort_by_id(NodeX **a,NodeX **b)
{
 node_t a_id=(*a)->id;
 node_t b_id=(*b)->id;

 if(a_id<b_id)
    return(-1);
 else if(a_id>b_id)
    return(1);
 else
    return(0);
}


/*++++++++++++++++++++++++++++++++++++++
  Sort the node list geographically.

  NodesX* nodesx The set of nodes to process.
  ++++++++++++++++++++++++++++++++++++++*/

void SortNodeListGeographically(NodesX* nodesx)
{
 index_t i;

 assert(nodesx->idata);         /* Must have idata filled in */

 printf("Sorting Nodes Geographically");
 fflush(stdout);

 /* Allocate the array of pointers and sort them */

 nodesx->gdata=(NodeX**)malloc(nodesx->number*sizeof(NodeX*));

 for(i=0;i<nodesx->number;i++)
    nodesx->gdata[i]=nodesx->idata[i];

 qsort(nodesx->gdata,nodesx->number,sizeof(NodeX*),(int (*)(const void*,const void*))sort_by_lat_long);

 printf("\rSorted Nodes Geographically \n");
 fflush(stdout);
}


/*++++++++++++++++++++++++++++++++++++++
  Sort the nodes into latitude and longitude order.

  int sort_by_lat_long Returns the comparison of the latitude and longitude fields.

  NodeX **a The first Node.

  NodeX **b The second Node.
  ++++++++++++++++++++++++++++++++++++++*/

static int sort_by_lat_long(NodeX **a,NodeX **b)
{
 ll_bin_t a_lon=latlong_to_bin((*a)->longitude);
 ll_bin_t b_lon=latlong_to_bin((*b)->longitude);

 if(a_lon<b_lon)
    return(-1);
 else if(a_lon>b_lon)
    return(1);
 else
   {
    ll_bin_t a_lat=latlong_to_bin((*a)->latitude);
    ll_bin_t b_lat=latlong_to_bin((*b)->latitude);

    if(a_lat<b_lat)
       return(-1);
    else if(a_lat>b_lat)
       return(1);
    else
       return(0);
   }
}


/*++++++++++++++++++++++++++++++++++++++
  Remove any nodes that are not part of a highway.

  NodesX *nodesx The complete node list.

  SegmentsX *segmentsx The list of segments.
  ++++++++++++++++++++++++++++++++++++++*/

void RemoveNonHighwayNodes(NodesX *nodesx,SegmentsX *segmentsx)
{
 index_t i;
 int highway=0,nothighway=0;

 assert(nodesx->xdata);         /* Must have xdata filled in */

 printf("Checking: Nodes=0");
 fflush(stdout);

 for(i=0;i<(nodesx->row*INCREMENT_NODESX+nodesx->col);i++)
   {
    if(FindFirstSegmentX(segmentsx,nodesx->xdata[i/INCREMENT_NODESX][i%INCREMENT_NODESX].id))
       highway++;
    else
      {
       nodesx->xdata[i/INCREMENT_NODESX][i%INCREMENT_NODESX].id=NO_NODE;
       nothighway++;
      }

    if(!((i+1)%10000))
      {
       printf("\rChecking: Nodes=%d Highway=%d not-Highway=%d",i+1,highway,nothighway);
       fflush(stdout);
      }
   }

 printf("\rChecked: Nodes=%d Highway=%d not-Highway=%d  \n",i,highway,nothighway);
 fflush(stdout);

 nodesx->sorted=0;
}


/*++++++++++++++++++++++++++++++++++++++
  Create the real node data.

  NodesX *nodesx The set of nodes to use.

  int iteration The final super-node iteration.
  ++++++++++++++++++++++++++++++++++++++*/

void CreateRealNodes(NodesX *nodesx,int iteration)
{
 index_t i;

 assert(nodesx->gdata);         /* Must have gdata filled in */

 printf("Creating Real Nodes: Nodes=0");
 fflush(stdout);

 /* Allocate the memory */

 nodesx->ndata=(Node*)malloc(nodesx->number*sizeof(Node));

 /* Loop through and allocate. */

 for(i=0;i<nodesx->number;i++)
   {
    nodesx->ndata[i].latoffset=latlong_to_off(nodesx->idata[i]->latitude);
    nodesx->ndata[i].lonoffset=latlong_to_off(nodesx->idata[i]->longitude);

    nodesx->ndata[i].firstseg=SEGMENT(NO_SEGMENT);

    if(nodesx->idata[i]->super==iteration)
       nodesx->ndata[i].firstseg|=NODE_SUPER;

    if(!((i+1)%10000))
      {
       printf("\rCreating Real Nodes: Nodes=%d",i+1);
       fflush(stdout);
      }
   }

 printf("\rCreating Real Nodes: Nodes=%d \n",nodesx->number);
 fflush(stdout);
}


/*++++++++++++++++++++++++++++++++++++++
  Assign the segment indexes to the nodes.

  NodesX *nodesx The list of nodes to process.

  SegmentsX* segmentsx The set of segments to use.
  ++++++++++++++++++++++++++++++++++++++*/

void IndexNodes(NodesX *nodesx,SegmentsX *segmentsx)
{
 index_t i;

 assert(nodesx->sorted);        /* Must be sorted */
 assert(nodesx->idata);         /* Must have idata filled in */
 assert(nodesx->ndata);         /* Must have ndata filled in */
 assert(segmentsx->sorted);     /* Must be sorted */
 assert(segmentsx->n1data);     /* Must have n1data filled in */
 assert(segmentsx->sdata);      /* Must have sdata filled in */

 printf("Indexing Segments: Segments=0");
 fflush(stdout);

 /* Index the nodes */

 for(i=0;i<segmentsx->number;i++)
   {
    NodeX **nodex1=FindNodeX(nodesx,segmentsx->n1data[i]->node1);
    NodeX **nodex2=FindNodeX(nodesx,segmentsx->n1data[i]->node2);
    Node  *node1=&nodesx->ndata[nodex1-nodesx->idata];
    Node  *node2=&nodesx->ndata[nodex2-nodesx->idata];

    /* Check node1 */

    if(SEGMENT(node1->firstseg)==SEGMENT(NO_SEGMENT))
      {
       node1->firstseg^=SEGMENT(NO_SEGMENT);
       node1->firstseg|=i;
      }
    else
      {
       index_t index=SEGMENT(node1->firstseg);

       do
         {
          if(segmentsx->n1data[index]->node1==segmentsx->n1data[i]->node1)
            {
             index++;

             if(index>=segmentsx->number || segmentsx->n1data[index]->node1!=segmentsx->n1data[i]->node1)
                break;
            }
          else
            {
             if(segmentsx->sdata[index].next2==NO_NODE)
               {
                segmentsx->sdata[index].next2=i;
                break;
               }
             else
                index=segmentsx->sdata[index].next2;
            }
         }
       while(1);
      }

    /* Check node2 */

    if(SEGMENT(node2->firstseg)==SEGMENT(NO_SEGMENT))
      {
       node2->firstseg^=SEGMENT(NO_SEGMENT);
       node2->firstseg|=i;
      }
    else
      {
       index_t index=SEGMENT(node2->firstseg);

       do
         {
          if(segmentsx->n1data[index]->node1==segmentsx->n1data[i]->node2)
            {
             index++;

             if(index>=segmentsx->number || segmentsx->n1data[index]->node1!=segmentsx->n1data[i]->node2)
                break;
            }
          else
            {
             if(segmentsx->sdata[index].next2==NO_NODE)
               {
                segmentsx->sdata[index].next2=i;
                break;
               }
             else
                index=segmentsx->sdata[index].next2;
            }
         }
       while(1);
      }

    if(!((i+1)%10000))
      {
       printf("\rIndexing Segments: Segments=%d",i+1);
       fflush(stdout);
      }
   }

 printf("\rIndexed Segments: Segments=%d \n",segmentsx->number);
 fflush(stdout);
}
1	amb	110	/***************************************
2	amb	229	$Header: /home/amb/CVS/routino/src/nodesx.c,v 1.27 2009-07-19 12:54:07 amb Exp $
3	amb	110
4			Extented Node data type functions.
5	amb	151
6			Part of the Routino routing software.
7	amb	110	****************/ /****************
8	amb	151	This file Copyright 2008,2009 Andrew M. Bishop
9	amb	110
10	amb	151	This program is free software: you can redistribute it and/or modify
11			it under the terms of the GNU Affero General Public License as published by
12			the Free Software Foundation, either version 3 of the License, or
13			(at your option) any later version.
14
15			This program is distributed in the hope that it will be useful,
16			but WITHOUT ANY WARRANTY; without even the implied warranty of
17			MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18			GNU Affero General Public License for more details.
19
20			You should have received a copy of the GNU Affero General Public License
21			along with this program. If not, see <http://www.gnu.org/licenses/>.
22	amb	110	***************************************/
23
24
25			#include <assert.h>
26			#include <stdlib.h>
27			#include <stdio.h>
28
29			#include "types.h"
30			#include "functions.h"
31			#include "nodesx.h"
32			#include "segmentsx.h"
33	amb	204	#include "waysx.h"
34	amb	228	#include "segments.h"
35			#include "nodes.h"
36	amb	110
37
38			/* Constants */
39
40	amb	216	/+ The array size increment for NodesX (UK is ~10.3M raw nodes, this is ~78 increments). +/
41			#define INCREMENT_NODESX (128*1024)
42	amb	110
43
44			/* Functions */
45
46			static int sort_by_id(NodeX a,NodeX b);
47			static int sort_by_lat_long(NodeX a,NodeX b);
48
49
50			/*++++++++++++++++++++++++++++++++++++++
51			Allocate a new node list.
52
53			NodesX *NewNodeList Returns the node list.
54			++++++++++++++++++++++++++++++++++++++*/
55
56			NodesX *NewNodeList(void)
57			{
58			NodesX *nodesx;
59
60	amb	213	nodesx=(NodesX*)calloc(1,sizeof(NodesX));
61	amb	110
62	amb	216	nodesx->row=-1;
63
64	amb	110	return(nodesx);
65			}
66
67
68			/*++++++++++++++++++++++++++++++++++++++
69	amb	226	Free a node list.
70
71			NodesX *nodesx The list to be freed.
72			++++++++++++++++++++++++++++++++++++++*/
73
74			void FreeNodeList(NodesX *nodesx)
75			{
76			if(nodesx->xdata)
77			{
78			int i;
79			for(i=0;i<=nodesx->row;i++)
80			free(nodesx->xdata[i]);
81			free(nodesx->xdata);
82			}
83
84			if(nodesx->gdata)
85			free(nodesx->gdata);
86			if(nodesx->idata)
87			free(nodesx->idata);
88
89			if(nodesx->ndata)
90			free(nodesx->ndata);
91
92			free(nodesx);
93			}
94
95
96			/*++++++++++++++++++++++++++++++++++++++
97	amb	110	Save the node list to a file.
98
99			NodesX* nodesx The set of nodes to save.
100
101			const char *filename The name of the file to save.
102			++++++++++++++++++++++++++++++++++++++*/
103
104			void SaveNodeList(NodesX* nodesx,const char *filename)
105			{
106	amb	214	index_t i;
107	amb	110	int fd;
108			Nodes *nodes=calloc(1,sizeof(Nodes));
109			index_t *offsets;
110	amb	219	ll_bin_t lat_min_bin,lat_max_bin,lon_min_bin,lon_max_bin;
111			latlong_t lat_min,lat_max,lon_min,lon_max;
112	amb	110	int latbins,lonbins,latlonbin;
113
114			assert(nodesx->sorted); /* Must be sorted */
115	amb	213	assert(nodesx->gdata); /* Must have gdata filled in */
116			assert(nodesx->ndata); /* Must have ndata filled in */
117	amb	110
118	amb	227	printf("Writing Nodes: Nodes=0");
119			fflush(stdout);
120
121	amb	219	/* Work out the range of data */
122
123			lat_min=radians_to_latlong( 2);
124			lat_max=radians_to_latlong(-2);
125			lon_min=radians_to_latlong( 4);
126			lon_max=radians_to_latlong(-4);
127
128			for(i=0;i<nodesx->number;i++)
129			{
130	amb	223	if(nodesx->idata[i]->latitude<lat_min)
131			lat_min=nodesx->idata[i]->latitude;
132			if(nodesx->idata[i]->latitude>lat_max)
133			lat_max=nodesx->idata[i]->latitude;
134			if(nodesx->idata[i]->longitude<lon_min)
135			lon_min=nodesx->idata[i]->longitude;
136			if(nodesx->idata[i]->longitude>lon_max)
137			lon_max=nodesx->idata[i]->longitude;
138	amb	219	}
139
140	amb	118	/* Work out the offsets */
141	amb	110
142	amb	219	lat_min_bin=latlong_to_bin(lat_min);
143			lon_min_bin=latlong_to_bin(lon_min);
144			lat_max_bin=latlong_to_bin(lat_max);
145			lon_max_bin=latlong_to_bin(lon_max);
146	amb	110
147	amb	219	latbins=(lat_max_bin-lat_min_bin)+1;
148			lonbins=(lon_max_bin-lon_min_bin)+1;
149	amb	110
150	amb	216	offsets=(index_t)malloc((latbinslonbins+1)*sizeof(index_t));
151	amb	110
152			latlonbin=0;
153
154			for(i=0;i<nodesx->number;i++)
155			{
156	amb	223	ll_bin_t latbin=latlong_to_bin(nodesx->gdata[i]->latitude )-lat_min_bin;
157			ll_bin_t lonbin=latlong_to_bin(nodesx->gdata[i]->longitude)-lon_min_bin;
158	amb	110	int llbin=lonbin*latbins+latbin;
159
160			for(;latlonbin<=llbin;latlonbin++)
161			offsets[latlonbin]=i;
162			}
163
164			for(;latlonbin<=(latbins*lonbins);latlonbin++)
165			offsets[latlonbin]=nodesx->number;
166
167			/* Fill in a Nodes structure with the offset of the real data in the file after
168			the Node structure itself. */
169
170			nodes->number=nodesx->number;
171
172			nodes->latbins=latbins;
173			nodes->lonbins=lonbins;
174
175	amb	223	nodes->latzero=lat_min_bin;
176			nodes->lonzero=lon_min_bin;
177	amb	110
178			nodes->data=NULL;
179			nodes->offsets=(void*)sizeof(Nodes);
180	amb	214	nodes->nodes=(void)(sizeof(Nodes)+(latbinslonbins+1)*sizeof(index_t));
181	amb	110
182			/* Write out the Nodes structure and then the real data. */
183
184			fd=OpenFile(filename);
185
186			WriteFile(fd,nodes,sizeof(Nodes));
187
188			WriteFile(fd,offsets,(latbinslonbins+1)sizeof(index_t));
189
190	amb	203	for(i=0;i<nodes->number;i++)
191	amb	132	{
192	amb	212	NodeX **nodex=FindNodeX(nodesx,nodesx->gdata[i]->id);
193			Node *node =&nodesx->ndata[nodex-nodesx->idata];
194	amb	110
195	amb	212	WriteFile(fd,node,sizeof(Node));
196
197	amb	132	if(!((i+1)%10000))
198			{
199			printf("\rWriting Nodes: Nodes=%d",i+1);
200			fflush(stdout);
201			}
202			}
203
204	amb	203	printf("\rWrote Nodes: Nodes=%d \n",nodes->number);
205	amb	132	fflush(stdout);
206
207	amb	110	CloseFile(fd);
208
209			/* Free the fake Nodes */
210
211			free(nodes);
212			free(offsets);
213			}
214
215
216			/*++++++++++++++++++++++++++++++++++++++
217			Find a particular node.
218
219	amb	212	NodeX **FindNodeX Returns a pointer to the extended node with the specified id.
220	amb	110
221			NodesX* nodesx The set of nodes to process.
222
223			node_t id The node id to look for.
224			++++++++++++++++++++++++++++++++++++++*/
225
226	amb	212	NodeX *FindNodeX(NodesX nodesx,node_t id)
227	amb	110	{
228			int start=0;
229			int end=nodesx->number-1;
230			int mid;
231
232			assert(nodesx->sorted); /* Must be sorted */
233	amb	213	assert(nodesx->idata); /* Must have idata filled in */
234	amb	110
235			/* Binary search - search key exact match only is required.
236			*
237			* # <- start \| Check mid and move start or end if it doesn't match
238			* # \|
239			* # \| Since an exact match is wanted we can set end=mid-1
240			* # <- mid \| or start=mid+1 because we know that mid doesn't match.
241			* # \|
242			* # \| Eventually either end=start or end=start+1 and one of
243			* # <- end \| start or end is the wanted one.
244			*/
245
246			if(end<start) /* There are no nodes */
247	amb	194	return(NULL);
248	amb	110	else if(id<nodesx->idata[start]->id) /* Check key is not before start */
249	amb	194	return(NULL);
250	amb	110	else if(id>nodesx->idata[end]->id) /* Check key is not after end */
251	amb	194	return(NULL);
252	amb	110	else
253			{
254			do
255			{
256			mid=(start+end)/2; /* Choose mid point */
257
258			if(nodesx->idata[mid]->id<id) /* Mid point is too low */
259			start=mid+1;
260			else if(nodesx->idata[mid]->id>id) /* Mid point is too high */
261			end=mid-1;
262			else /* Mid point is correct */
263	amb	212	return(&nodesx->idata[mid]);
264	amb	110	}
265			while((end-start)>1);
266
267			if(nodesx->idata[start]->id==id) /* Start is correct */
268	amb	212	return(&nodesx->idata[start]);
269	amb	110
270			if(nodesx->idata[end]->id==id) /* End is correct */
271	amb	212	return(&nodesx->idata[end]);
272	amb	110	}
273
274			return(NULL);
275			}
276
277
278			/*++++++++++++++++++++++++++++++++++++++
279			Append a node to a newly created node list (unsorted).
280
281			NodesX* nodesx The set of nodes to process.
282
283			node_t id The node identification.
284
285	amb	219	double latitude The latitude of the node.
286	amb	110
287	amb	219	double longitude The longitude of the node.
288	amb	110	++++++++++++++++++++++++++++++++++++++*/
289
290	amb	219	void AppendNode(NodesX* nodesx,node_t id,double latitude,double longitude)
291	amb	110	{
292			/* Check that the array has enough space. */
293
294	amb	216	if(nodesx->row==-1 \|\| nodesx->col==INCREMENT_NODESX)
295	amb	110	{
296	amb	216	nodesx->row++;
297			nodesx->col=0;
298	amb	110
299	amb	216	if((nodesx->row%16)==0)
300			nodesx->xdata=(NodeX*)realloc((void)nodesx->xdata,(nodesx->row+16)sizeof(NodeX));
301
302			nodesx->xdata[nodesx->row]=(NodeX)malloc(INCREMENT_NODESXsizeof(NodeX));
303	amb	110	}
304
305			/* Insert the node */
306
307	amb	216	nodesx->xdata[nodesx->row][nodesx->col].id=id;
308			nodesx->xdata[nodesx->row][nodesx->col].super=0;
309	amb	223	nodesx->xdata[nodesx->row][nodesx->col].latitude =radians_to_latlong(latitude);
310			nodesx->xdata[nodesx->row][nodesx->col].longitude=radians_to_latlong(longitude);
311	amb	110
312	amb	216	nodesx->col++;
313	amb	110
314			nodesx->sorted=0;
315			}
316
317
318			/*++++++++++++++++++++++++++++++++++++++
319			Sort the node list.
320
321			NodesX* nodesx The set of nodes to process.
322			++++++++++++++++++++++++++++++++++++++*/
323
324			void SortNodeList(NodesX* nodesx)
325			{
326	amb	214	index_t i;
327	amb	144	int duplicate;
328	amb	110
329	amb	213	assert(nodesx->xdata); /* Must have xdata filled in */
330
331	amb	227	printf("Sorting Nodes");
332			fflush(stdout);
333	amb	132
334	amb	213	/* Allocate the array of pointers and sort them */
335	amb	110
336	amb	216	nodesx->idata=(NodeX*)realloc(nodesx->idata,(nodesx->rowINCREMENT_NODESX+nodesx->col)sizeof(NodeX));
337	amb	110
338	amb	213	do
339			{
340			nodesx->number=0;
341	amb	144
342	amb	216	for(i=0;i<(nodesx->row*INCREMENT_NODESX+nodesx->col);i++)
343			if(nodesx->xdata[i/INCREMENT_NODESX][i%INCREMENT_NODESX].id!=NO_NODE)
344	amb	213	{
345	amb	216	nodesx->idata[nodesx->number]=&nodesx->xdata[i/INCREMENT_NODESX][i%INCREMENT_NODESX];
346	amb	213	nodesx->number++;
347			}
348	amb	110
349	amb	213	qsort(nodesx->idata,nodesx->number,sizeof(NodeX),(int ()(const void,const void))sort_by_id);
350	amb	110
351	amb	213	duplicate=0;
352	amb	144
353	amb	213	for(i=1;i<nodesx->number;i++)
354	amb	144	{
355	amb	213	if(nodesx->idata[i]->id==nodesx->idata[i-1]->id &&
356			nodesx->idata[i]->id!=NO_NODE)
357			{
358			nodesx->idata[i-1]->id=NO_NODE;
359			duplicate++;
360			}
361	amb	144	}
362
363	amb	213	if(duplicate)
364	amb	227	{
365			printf(" - %d duplicates found; trying again.\nSorting Nodes",duplicate);
366			fflush(stdout);
367			}
368	amb	144	}
369	amb	213	while(duplicate);
370	amb	144
371	amb	227	printf("\rSorted Nodes \n");
372			fflush(stdout);
373	amb	213
374			nodesx->sorted=1;
375	amb	110	}
376
377
378			/*++++++++++++++++++++++++++++++++++++++
379			Sort the nodes into id order.
380
381			int sort_by_id Returns the comparison of the id fields.
382
383			NodeX **a The first Node.
384
385			NodeX **b The second Node.
386			++++++++++++++++++++++++++++++++++++++*/
387
388			static int sort_by_id(NodeX a,NodeX b)
389			{
390			node_t a_id=(*a)->id;
391			node_t b_id=(*b)->id;
392
393			if(a_id<b_id)
394			return(-1);
395	amb	144	else if(a_id>b_id)
396			return(1);
397	amb	110	else
398	amb	144	return(0);
399	amb	110	}
400
401
402			/*++++++++++++++++++++++++++++++++++++++
403	amb	212	Sort the node list geographically.
404
405			NodesX* nodesx The set of nodes to process.
406			++++++++++++++++++++++++++++++++++++++*/
407
408			void SortNodeListGeographically(NodesX* nodesx)
409			{
410	amb	214	index_t i;
411	amb	212
412	amb	213	assert(nodesx->idata); /* Must have idata filled in */
413	amb	212
414	amb	227	printf("Sorting Nodes Geographically");
415			fflush(stdout);
416	amb	212
417	amb	213	/* Allocate the array of pointers and sort them */
418	amb	212
419			nodesx->gdata=(NodeX*)malloc(nodesx->numbersizeof(NodeX*));
420
421			for(i=0;i<nodesx->number;i++)
422			nodesx->gdata[i]=nodesx->idata[i];
423
424			qsort(nodesx->gdata,nodesx->number,sizeof(NodeX),(int ()(const void,const void))sort_by_lat_long);
425
426	amb	227	printf("\rSorted Nodes Geographically \n");
427			fflush(stdout);
428	amb	212	}
429
430
431			/*++++++++++++++++++++++++++++++++++++++
432	amb	110	Sort the nodes into latitude and longitude order.
433
434			int sort_by_lat_long Returns the comparison of the latitude and longitude fields.
435
436			NodeX **a The first Node.
437
438			NodeX **b The second Node.
439			++++++++++++++++++++++++++++++++++++++*/
440
441			static int sort_by_lat_long(NodeX a,NodeX b)
442			{
443	amb	223	ll_bin_t a_lon=latlong_to_bin((*a)->longitude);
444			ll_bin_t b_lon=latlong_to_bin((*b)->longitude);
445	amb	110
446			if(a_lon<b_lon)
447			return(-1);
448			else if(a_lon>b_lon)
449			return(1);
450			else
451			{
452	amb	223	ll_bin_t a_lat=latlong_to_bin((*a)->latitude);
453			ll_bin_t b_lat=latlong_to_bin((*b)->latitude);
454	amb	110
455			if(a_lat<b_lat)
456			return(-1);
457			else if(a_lat>b_lat)
458			return(1);
459			else
460			return(0);
461			}
462			}
463
464
465			/*++++++++++++++++++++++++++++++++++++++
466			Remove any nodes that are not part of a highway.
467
468			NodesX *nodesx The complete node list.
469
470			SegmentsX *segmentsx The list of segments.
471			++++++++++++++++++++++++++++++++++++++*/
472
473			void RemoveNonHighwayNodes(NodesX nodesx,SegmentsX segmentsx)
474			{
475	amb	214	index_t i;
476	amb	110	int highway=0,nothighway=0;
477
478	amb	213	assert(nodesx->xdata); /* Must have xdata filled in */
479
480	amb	227	printf("Checking: Nodes=0");
481			fflush(stdout);
482
483	amb	216	for(i=0;i<(nodesx->row*INCREMENT_NODESX+nodesx->col);i++)
484	amb	110	{
485	amb	216	if(FindFirstSegmentX(segmentsx,nodesx->xdata[i/INCREMENT_NODESX][i%INCREMENT_NODESX].id))
486	amb	110	highway++;
487			else
488			{
489	amb	216	nodesx->xdata[i/INCREMENT_NODESX][i%INCREMENT_NODESX].id=NO_NODE;
490	amb	110	nothighway++;
491			}
492
493			if(!((i+1)%10000))
494			{
495			printf("\rChecking: Nodes=%d Highway=%d not-Highway=%d",i+1,highway,nothighway);
496			fflush(stdout);
497			}
498			}
499
500	amb	216	printf("\rChecked: Nodes=%d Highway=%d not-Highway=%d \n",i,highway,nothighway);
501	amb	110	fflush(stdout);
502	amb	213
503			nodesx->sorted=0;
504	amb	110	}
505
506
507			/*++++++++++++++++++++++++++++++++++++++
508	amb	212	Create the real node data.
509	amb	110
510	amb	212	NodesX *nodesx The set of nodes to use.
511	amb	110
512	amb	212	int iteration The final super-node iteration.
513	amb	110	++++++++++++++++++++++++++++++++++++++*/
514
515	amb	212	void CreateRealNodes(NodesX *nodesx,int iteration)
516	amb	110	{
517	amb	214	index_t i;
518	amb	110
519	amb	213	assert(nodesx->gdata); /* Must have gdata filled in */
520	amb	110
521	amb	227	printf("Creating Real Nodes: Nodes=0");
522			fflush(stdout);
523
524	amb	212	/* Allocate the memory */
525
526			nodesx->ndata=(Node)malloc(nodesx->numbersizeof(Node));
527
528			/* Loop through and allocate. */
529
530	amb	110	for(i=0;i<nodesx->number;i++)
531			{
532	amb	223	nodesx->ndata[i].latoffset=latlong_to_off(nodesx->idata[i]->latitude);
533			nodesx->ndata[i].lonoffset=latlong_to_off(nodesx->idata[i]->longitude);
534	amb	208
535	amb	212	nodesx->ndata[i].firstseg=SEGMENT(NO_SEGMENT);
536
537			if(nodesx->idata[i]->super==iteration)
538			nodesx->ndata[i].firstseg\|=NODE_SUPER;
539
540	amb	110	if(!((i+1)%10000))
541			{
542	amb	212	printf("\rCreating Real Nodes: Nodes=%d",i+1);
543	amb	110	fflush(stdout);
544			}
545			}
546
547	amb	212	printf("\rCreating Real Nodes: Nodes=%d \n",nodesx->number);
548	amb	110	fflush(stdout);
549			}
550
551
552			/*++++++++++++++++++++++++++++++++++++++
553			Assign the segment indexes to the nodes.
554
555			NodesX *nodesx The list of nodes to process.
556
557			SegmentsX* segmentsx The set of segments to use.
558			++++++++++++++++++++++++++++++++++++++*/
559
560	amb	209	void IndexNodes(NodesX nodesx,SegmentsX segmentsx)
561	amb	110	{
562	amb	214	index_t i;
563	amb	110
564			assert(nodesx->sorted); /* Must be sorted */
565	amb	213	assert(nodesx->idata); /* Must have idata filled in */
566			assert(nodesx->ndata); /* Must have ndata filled in */
567	amb	110	assert(segmentsx->sorted); /* Must be sorted */
568	amb	229	assert(segmentsx->n1data); /* Must have n1data filled in */
569	amb	213	assert(segmentsx->sdata); /* Must have sdata filled in */
570	amb	110
571	amb	227	printf("Indexing Segments: Segments=0");
572			fflush(stdout);
573
574	amb	110	/* Index the nodes */
575
576			for(i=0;i<segmentsx->number;i++)
577			{
578	amb	229	NodeX **nodex1=FindNodeX(nodesx,segmentsx->n1data[i]->node1);
579			NodeX **nodex2=FindNodeX(nodesx,segmentsx->n1data[i]->node2);
580	amb	212	Node *node1=&nodesx->ndata[nodex1-nodesx->idata];
581			Node *node2=&nodesx->ndata[nodex2-nodesx->idata];
582	amb	110
583			/* Check node1 */
584
585	amb	212	if(SEGMENT(node1->firstseg)==SEGMENT(NO_SEGMENT))
586	amb	110	{
587	amb	212	node1->firstseg^=SEGMENT(NO_SEGMENT);
588			node1->firstseg\|=i;
589	amb	110	}
590			else
591			{
592	amb	212	index_t index=SEGMENT(node1->firstseg);
593	amb	110
594			do
595			{
596	amb	229	if(segmentsx->n1data[index]->node1==segmentsx->n1data[i]->node1)
597	amb	110	{
598	amb	209	index++;
599	amb	128
600	amb	229	if(index>=segmentsx->number \|\| segmentsx->n1data[index]->node1!=segmentsx->n1data[i]->node1)
601	amb	209	break;
602	amb	110	}
603			else
604			{
605	amb	209	if(segmentsx->sdata[index].next2==NO_NODE)
606	amb	110	{
607	amb	209	segmentsx->sdata[index].next2=i;
608			break;
609	amb	110	}
610			else
611	amb	209	index=segmentsx->sdata[index].next2;
612	amb	110	}
613			}
614	amb	209	while(1);
615	amb	110	}
616
617			/* Check node2 */
618
619	amb	212	if(SEGMENT(node2->firstseg)==SEGMENT(NO_SEGMENT))
620	amb	110	{
621	amb	212	node2->firstseg^=SEGMENT(NO_SEGMENT);
622			node2->firstseg\|=i;
623	amb	110	}
624			else
625			{
626	amb	212	index_t index=SEGMENT(node2->firstseg);
627	amb	110
628			do
629			{
630	amb	229	if(segmentsx->n1data[index]->node1==segmentsx->n1data[i]->node2)
631	amb	110	{
632	amb	209	index++;
633	amb	128
634	amb	229	if(index>=segmentsx->number \|\| segmentsx->n1data[index]->node1!=segmentsx->n1data[i]->node2)
635	amb	209	break;
636	amb	110	}
637			else
638			{
639	amb	209	if(segmentsx->sdata[index].next2==NO_NODE)
640	amb	110	{
641	amb	209	segmentsx->sdata[index].next2=i;
642			break;
643	amb	110	}
644			else
645	amb	209	index=segmentsx->sdata[index].next2;
646	amb	110	}
647			}
648	amb	209	while(1);
649	amb	110	}
650
651			if(!((i+1)%10000))
652			{
653			printf("\rIndexing Segments: Segments=%d",i+1);
654			fflush(stdout);
655			}
656			}
657
658			printf("\rIndexed Segments: Segments=%d \n",segmentsx->number);
659			fflush(stdout);
660			}