trunk/src/relations.c

/***************************************
 $Header: /home/amb/CVS/routino/src/relations.c,v 1.3 2010-12-21 17:17:57 amb Exp $

 Relation data type functions.

 Part of the Routino routing software.
 ******************/ /******************
 This file Copyright 2008-2010 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 <sys/types.h>
#include <stdlib.h>

#include "relations.h"

#include "files.h"


/*++++++++++++++++++++++++++++++++++++++
  Load in a relation list from a file.

  Relations* LoadRelationList Returns the relation list.

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

Relations *LoadRelationList(const char *filename)
{
 Relations *relations;

 relations=(Relations*)malloc(sizeof(Relations));

#if !SLIM

 relations->data=MapFile(filename);

 /* Copy the RelationsFile header structure from the loaded data */

 relations->file=*((RelationsFile*)relations->data);

 /* Set the pointers in the Relations structure. */

 relations->turnrelations=(TurnRelation*)(relations->data+sizeof(RelationsFile));

#else

 relations->fd=ReOpenFile(filename);

 /* Copy the RelationsFile header structure from the loaded data */

 ReadFile(relations->fd,&relations->file,sizeof(RelationsFile));

 relations->troffset=sizeof(RelationsFile);

 relations->incache[0]=NO_RELATION;
 relations->incache[1]=NO_RELATION;

#endif

 if(relations->file.trnumber>0)
   {
    TurnRelation *relation;

    relation=LookupTurnRelation(relations,0,1);

    relations->via_start =relation->via;
    relations->from_start=relation->from;

    relation=LookupTurnRelation(relations,relations->file.trnumber-1,1);

    relations->via_end =relation->via;
    relations->from_end=relation->from;
   }

 return(relations);
}


/*++++++++++++++++++++++++++++++++++++++
  Find a particular turn relation in the file.

  index_t FindFirstTurnRelation1 Returns the index of the first turn relation matching via.

  Relations *relations The set of relations to process.

  index_t via The node that the route is going via.
  ++++++++++++++++++++++++++++++++++++++*/

index_t FindFirstTurnRelation1(Relations *relations,index_t via)
{
 TurnRelation *relation;
 int start=0;
 int end=relations->file.trnumber-1;
 int mid;
 int match=-1;

 /* Binary search - search key first match 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 relations */
    return(NO_RELATION);

 if(via<relations->via_start)       /* Check key is not before start */
    return(NO_RELATION);

 if(via>relations->via_end)         /* Check key is not after end */
    return(NO_RELATION);

 do
   {
    mid=(start+end)/2;              /* Choose mid point */

    relation=LookupTurnRelation(relations,mid,1);

    if(relation->via<via)           /* Mid point is too low for 'via' */
       start=mid+1;
    else if(relation->via>via)      /* Mid point is too high for 'via' */
       end=mid-1;
    else                            /* Mid point is correct for 'from' */
      {
       match=mid;
       break;
      }
   }
 while((end-start)>1);

 if(match==-1)                      /* Check if start matches */
   {
    relation=LookupTurnRelation(relations,start,1);

    if(relation->via==via)
       match=start;
   }

 if(match==-1)                      /* Check if end matches */
   {
    relation=LookupTurnRelation(relations,end,1);

    if(relation->via==via)
       match=end;
   }

 if(match==-1)
    return(NO_RELATION);

 while(match>0)                     /* Search backwards for the first match */
   {
    relation=LookupTurnRelation(relations,match-1,1);

    if(relation->via==via)
       match--;
    else
       break;
   }

 return(match);
}


/*++++++++++++++++++++++++++++++++++++++
  Find the next matching turn relation in the file.

  index_t FindNextTurnRelation1 Returns the index of the next turn relation matching via.

  Relations *relations The set of relations to process.

  index_t current The current index of a relation that matches.
  ++++++++++++++++++++++++++++++++++++++*/

index_t FindNextTurnRelation1(Relations *relations,index_t current)
{
 TurnRelation *relation;
 index_t via;

 relation=LookupTurnRelation(relations,current,1);

 via=relation->via;

 current++;

 relation=LookupTurnRelation(relations,current,1);

 if(relation->via==via)
    return(current);
 else
    return(NO_RELATION);
}


/*++++++++++++++++++++++++++++++++++++++
  Find a particular turn relation in the file.

  index_t FindFirstTurnRelation2 Returns the index of the first turn relation matching via and from.

  Relations *relations The set of relations to process.

  index_t via The node that the route is going via.

  index_t from The node that the route is coming from.
  ++++++++++++++++++++++++++++++++++++++*/

index_t FindFirstTurnRelation2(Relations *relations,index_t via,index_t from)
{
 TurnRelation *relation;
 int start=0;
 int end=relations->file.trnumber-1;
 int mid;
 int match=-1;

 /* Binary search - search key first match 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 relations */
    return(NO_RELATION);

 if(via<relations->via_start ||
    from<relations->from_start)     /* Check key is not before start */
    return(NO_RELATION);

 if(via>relations->via_end ||
    from>relations->from_end)       /* Check key is not after end */
    return(NO_RELATION);

 do
   {
    mid=(start+end)/2;              /* Choose mid point */

    relation=LookupTurnRelation(relations,mid,1);

    if(relation->via<via)           /* Mid point is too low for 'via' */
       start=mid+1;
    else if(relation->via>via)      /* Mid point is too high for 'via' */
       end=mid-1;
    else                            /* Mid point is correct for 'via' */
      {
       if(relation->from<from)      /* Mid point is too low for 'from' */
          start=mid+1;
       else if(relation->from>from) /* Mid point is too high for 'from' */
          end=mid-1;
       else                         /* Mid point is correct for 'from' */
         {
          match=mid;
          break;
         }
      }
   }
 while((end-start)>1);

 if(match==-1)                      /* Check if start matches */
   {
    relation=LookupTurnRelation(relations,start,1);

    if(relation->via==via && relation->from==from)
       match=start;
   }

 if(match==-1)                      /* Check if end matches */
   {
    relation=LookupTurnRelation(relations,end,1);

    if(relation->via==via && relation->from==from)
       match=end;
   }

 if(match==-1)
    return(NO_RELATION);

 while(match>0)                     /* Search backwards for the first match */
   {
    relation=LookupTurnRelation(relations,match-1,1);

    if(relation->via==via && relation->from==from)
       match--;
    else
       break;
   }

 return(match);
}


/*++++++++++++++++++++++++++++++++++++++
  Find the next matching turn relation in the file.

  index_t FindNextTurnRelation2 Returns the index of the next turn relation matching via and from.

  Relations *relations The set of relations to process.

  index_t current The current index of a relation that matches.
  ++++++++++++++++++++++++++++++++++++++*/

index_t FindNextTurnRelation2(Relations *relations,index_t current)
{
 TurnRelation *relation;
 index_t via,from;

 relation=LookupTurnRelation(relations,current,1);

 via=relation->via;
 from=relation->from;

 current++;

 relation=LookupTurnRelation(relations,current,1);

 if(relation->via==via && relation->from==from)
    return(current);
 else
    return(NO_RELATION);
}
1	amb	561	/***************************************
2	amb	563	$Header: /home/amb/CVS/routino/src/relations.c,v 1.3 2010-12-21 17:17:57 amb Exp $
3	amb	561
4			Relation data type functions.
5
6			Part of the Routino routing software.
7			****************/ /****************
8			This file Copyright 2008-2010 Andrew M. Bishop
9
10			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			***************************************/
23
24
25			#include <sys/types.h>
26			#include <stdlib.h>
27
28			#include "relations.h"
29
30			#include "files.h"
31
32
33			/*++++++++++++++++++++++++++++++++++++++
34			Load in a relation list from a file.
35
36			Relations* LoadRelationList Returns the relation list.
37
38			const char *filename The name of the file to load.
39			++++++++++++++++++++++++++++++++++++++*/
40
41			Relations LoadRelationList(const char filename)
42			{
43			Relations *relations;
44
45			relations=(Relations*)malloc(sizeof(Relations));
46
47			#if !SLIM
48
49			relations->data=MapFile(filename);
50
51			/* Copy the RelationsFile header structure from the loaded data */
52
53			relations->file=((RelationsFile)relations->data);
54
55			/* Set the pointers in the Relations structure. */
56
57			relations->turnrelations=(TurnRelation*)(relations->data+sizeof(RelationsFile));
58
59			#else
60
61			relations->fd=ReOpenFile(filename);
62
63			/* Copy the RelationsFile header structure from the loaded data */
64
65			ReadFile(relations->fd,&relations->file,sizeof(RelationsFile));
66
67			relations->troffset=sizeof(RelationsFile);
68
69	amb	562	relations->incache[0]=NO_RELATION;
70			relations->incache[1]=NO_RELATION;
71
72	amb	561	#endif
73
74	amb	563	if(relations->file.trnumber>0)
75			{
76			TurnRelation *relation;
77
78			relation=LookupTurnRelation(relations,0,1);
79
80			relations->via_start =relation->via;
81			relations->from_start=relation->from;
82
83			relation=LookupTurnRelation(relations,relations->file.trnumber-1,1);
84
85			relations->via_end =relation->via;
86			relations->from_end=relation->from;
87			}
88
89	amb	561	return(relations);
90			}
91	amb	562
92
93			/*++++++++++++++++++++++++++++++++++++++
94			Find a particular turn relation in the file.
95
96			index_t FindFirstTurnRelation1 Returns the index of the first turn relation matching via.
97
98			Relations *relations The set of relations to process.
99
100			index_t via The node that the route is going via.
101			++++++++++++++++++++++++++++++++++++++*/
102
103			index_t FindFirstTurnRelation1(Relations *relations,index_t via)
104			{
105			TurnRelation *relation;
106			int start=0;
107			int end=relations->file.trnumber-1;
108			int mid;
109			int match=-1;
110
111			/* Binary search - search key first match is required.
112			*
113			* # <- start \| Check mid and move start or end if it doesn't match
114			* # \|
115			* # \| Since an exact match is wanted we can set end=mid-1
116			* # <- mid \| or start=mid+1 because we know that mid doesn't match.
117			* # \|
118			* # \| Eventually either end=start or end=start+1 and one of
119			* # <- end \| start or end is the wanted one.
120			*/
121
122			if(end<start) /* There are no relations */
123			return(NO_RELATION);
124
125	amb	563	if(via<relations->via_start) /* Check key is not before start */
126	amb	562	return(NO_RELATION);
127
128	amb	563	if(via>relations->via_end) /* Check key is not after end */
129	amb	562	return(NO_RELATION);
130
131			do
132			{
133			mid=(start+end)/2; /* Choose mid point */
134
135	amb	563	relation=LookupTurnRelation(relations,mid,1);
136	amb	562
137			if(relation->via<via) /* Mid point is too low for 'via' */
138			start=mid+1;
139			else if(relation->via>via) /* Mid point is too high for 'via' */
140			end=mid-1;
141			else /* Mid point is correct for 'from' */
142			{
143			match=mid;
144			break;
145			}
146			}
147			while((end-start)>1);
148
149			if(match==-1) /* Check if start matches */
150			{
151	amb	563	relation=LookupTurnRelation(relations,start,1);
152	amb	562
153			if(relation->via==via)
154			match=start;
155			}
156
157			if(match==-1) /* Check if end matches */
158			{
159	amb	563	relation=LookupTurnRelation(relations,end,1);
160	amb	562
161			if(relation->via==via)
162			match=end;
163			}
164
165			if(match==-1)
166			return(NO_RELATION);
167
168			while(match>0) /* Search backwards for the first match */
169			{
170	amb	563	relation=LookupTurnRelation(relations,match-1,1);
171	amb	562
172			if(relation->via==via)
173			match--;
174			else
175			break;
176			}
177
178			return(match);
179			}
180
181
182			/*++++++++++++++++++++++++++++++++++++++
183			Find the next matching turn relation in the file.
184
185			index_t FindNextTurnRelation1 Returns the index of the next turn relation matching via.
186
187			Relations *relations The set of relations to process.
188
189			index_t current The current index of a relation that matches.
190			++++++++++++++++++++++++++++++++++++++*/
191
192			index_t FindNextTurnRelation1(Relations *relations,index_t current)
193			{
194			TurnRelation *relation;
195			index_t via;
196
197	amb	563	relation=LookupTurnRelation(relations,current,1);
198	amb	562
199			via=relation->via;
200
201			current++;
202
203	amb	563	relation=LookupTurnRelation(relations,current,1);
204	amb	562
205			if(relation->via==via)
206			return(current);
207			else
208			return(NO_RELATION);
209			}
210
211
212			/*++++++++++++++++++++++++++++++++++++++
213			Find a particular turn relation in the file.
214
215			index_t FindFirstTurnRelation2 Returns the index of the first turn relation matching via and from.
216
217			Relations *relations The set of relations to process.
218
219			index_t via The node that the route is going via.
220
221			index_t from The node that the route is coming from.
222			++++++++++++++++++++++++++++++++++++++*/
223
224			index_t FindFirstTurnRelation2(Relations *relations,index_t via,index_t from)
225			{
226			TurnRelation *relation;
227			int start=0;
228			int end=relations->file.trnumber-1;
229			int mid;
230			int match=-1;
231
232			/* Binary search - search key first match is required.
233			*
234			* # <- start \| Check mid and move start or end if it doesn't match
235			* # \|
236			* # \| Since an exact match is wanted we can set end=mid-1
237			* # <- mid \| or start=mid+1 because we know that mid doesn't match.
238			* # \|
239			* # \| Eventually either end=start or end=start+1 and one of
240			* # <- end \| start or end is the wanted one.
241			*/
242
243	amb	563	if(end<start) /* There are no relations */
244	amb	562	return(NO_RELATION);
245
246	amb	563	if(via<relations->via_start \|\|
247			from<relations->from_start) /* Check key is not before start */
248	amb	562	return(NO_RELATION);
249
250	amb	563	if(via>relations->via_end \|\|
251			from>relations->from_end) /* Check key is not after end */
252	amb	562	return(NO_RELATION);
253
254			do
255			{
256	amb	563	mid=(start+end)/2; /* Choose mid point */
257	amb	562
258	amb	563	relation=LookupTurnRelation(relations,mid,1);
259	amb	562
260	amb	563	if(relation->via<via) /* Mid point is too low for 'via' */
261	amb	562	start=mid+1;
262	amb	563	else if(relation->via>via) /* Mid point is too high for 'via' */
263	amb	562	end=mid-1;
264	amb	563	else /* Mid point is correct for 'via' */
265	amb	562	{
266	amb	563	if(relation->from<from) /* Mid point is too low for 'from' */
267	amb	562	start=mid+1;
268	amb	563	else if(relation->from>from) /* Mid point is too high for 'from' */
269	amb	562	end=mid-1;
270	amb	563	else /* Mid point is correct for 'from' */
271	amb	562	{
272			match=mid;
273			break;
274			}
275			}
276			}
277			while((end-start)>1);
278
279	amb	563	if(match==-1) /* Check if start matches */
280	amb	562	{
281	amb	563	relation=LookupTurnRelation(relations,start,1);
282	amb	562
283			if(relation->via==via && relation->from==from)
284			match=start;
285			}
286
287	amb	563	if(match==-1) /* Check if end matches */
288	amb	562	{
289	amb	563	relation=LookupTurnRelation(relations,end,1);
290	amb	562
291			if(relation->via==via && relation->from==from)
292			match=end;
293			}
294
295			if(match==-1)
296			return(NO_RELATION);
297
298	amb	563	while(match>0) /* Search backwards for the first match */
299	amb	562	{
300	amb	563	relation=LookupTurnRelation(relations,match-1,1);
301	amb	562
302			if(relation->via==via && relation->from==from)
303			match--;
304			else
305			break;
306			}
307
308			return(match);
309			}
310
311
312			/*++++++++++++++++++++++++++++++++++++++
313			Find the next matching turn relation in the file.
314
315			index_t FindNextTurnRelation2 Returns the index of the next turn relation matching via and from.
316
317			Relations *relations The set of relations to process.
318
319			index_t current The current index of a relation that matches.
320			++++++++++++++++++++++++++++++++++++++*/
321
322			index_t FindNextTurnRelation2(Relations *relations,index_t current)
323			{
324			TurnRelation *relation;
325			index_t via,from;
326
327	amb	563	relation=LookupTurnRelation(relations,current,1);
328	amb	562
329			via=relation->via;
330			from=relation->from;
331
332			current++;
333
334	amb	563	relation=LookupTurnRelation(relations,current,1);
335	amb	562
336			if(relation->via==via && relation->from==from)
337			return(current);
338			else
339			return(NO_RELATION);
340			}