trunk/src/results.h

/***************************************
 $Header: /home/amb/CVS/routino/src/results.h,v 1.17 2009-11-13 19:24:11 amb Exp $

 A header file for the results.

 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/>.
 ***************************************/


#ifndef RESULTS_H
#define RESULTS_H    /*+ To stop multiple inclusions. +*/

#include <stdint.h>

#include "types.h"


/* Constants */

/*+ A result is not currently queued. +*/
#define NOT_QUEUED (uint32_t)(~0)


/* Data structures */

/*+ The result for a node. +*/
typedef struct _Result
{
 index_t   node;                /*+ The node for which this result applies. +*/

 index_t   prev;                /*+ The previous node following the best path. +*/
 index_t   next;                /*+ The next node following the best path. +*/

 score_t   score;               /*+ The best actual weighted distance or duration score from the start to the node. +*/

 score_t   sortby;              /*+ The best possible weighted distance or duration score from the start to the finish. +*/
 uint32_t  queued;              /*+ The position of this result in the queue. +*/

 Segment  *segment;             /*+ The segment for the path to here (from prev). +*/
}
 Result;

/*+ A list of results. +*/
typedef struct _Results
{
 uint32_t  nbins;               /*+ The number of bins. +*/
 uint32_t  mask;                /*+ A bit mask to select the bottom 'nbins' bits. +*/

 uint32_t  alloced;             /*+ The amount of space allocated for results
                                    (the length of the number and pointers arrays and
                                     1/nbins times the amount in the real results). +*/
 uint32_t  number;              /*+ The total number of occupied results. +*/

 uint32_t *count;               /*+ An array of nbins counters of results in each array. +*/
 Result ***point;               /*+ An array of nbins arrays of pointers to actual results. +*/

 Result  **data;                /*+ An array of arrays containing the actual results
                                    (don't need to realloc the array of data when adding more,
                                    only realloc the array that points to the array of data).
                                    Most importantly pointers into the real data don't change
                                    as more space is allocated (since realloc is not being used). +*/

 index_t start;                 /*+ The start node. +*/
 index_t finish;                /*+ The finish node. +*/
}
 Results;


/* Forward definitions for opaque type */

typedef struct _Queue Queue;


/* Results Functions */

Results *NewResultsList(int nbins);
void FreeResultsList(Results *results);

Result *InsertResult(Results *results,index_t node);
void ZeroResult(Result *result);

Result *FindResult(Results *results,index_t node);

Result *FirstResult(Results *results);
Result *NextResult(Results *results,Result *result);


/* Queue Functions */

Queue *NewQueueList(void);
void FreeQueueList(Queue *queue);

void InsertInQueue(Queue *queue,Result *result);
Result *PopFromQueue(Queue *queue);


#endif /* RESULTS_H */
1	amb	29	/***************************************
2	amb	302	$Header: /home/amb/CVS/routino/src/results.h,v 1.17 2009-11-13 19:24:11 amb Exp $
3	amb	29
4			A header file for the results.
5	amb	151
6			Part of the Routino routing software.
7	amb	29	****************/ /****************
8	amb	151	This file Copyright 2008,2009 Andrew M. Bishop
9	amb	29
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	29	***************************************/
23
24
25			#ifndef RESULTS_H
26			#define RESULTS_H /+ To stop multiple inclusions. +/
27
28			#include <stdint.h>
29
30	amb	116	#include "types.h"
31	amb	29
32
33	amb	302	/* Constants */
34
35			/+ A result is not currently queued. +/
36			#define NOT_QUEUED (uint32_t)(~0)
37
38
39	amb	29	/* Data structures */
40
41	amb	113	/+ The result for a node. +/
42	amb	29	typedef struct _Result
43			{
44	amb	170	index_t node; /+ The node for which this result applies. +/
45	amb	113
46	amb	170	index_t prev; /+ The previous node following the best path. +/
47			index_t next; /+ The next node following the best path. +/
48	amb	116
49	amb	236	score_t score; /+ The best actual weighted distance or duration score from the start to the node. +/
50	amb	116
51	amb	236	score_t sortby; /+ The best possible weighted distance or duration score from the start to the finish. +/
52			uint32_t queued; /+ The position of this result in the queue. +/
53
54	amb	170	Segment segment; /+ The segment for the path to here (from prev). +*/
55	amb	29	}
56			Result;
57
58			/+ A list of results. +/
59			typedef struct _Results
60			{
61	amb	165	uint32_t nbins; /+ The number of bins. +/
62			uint32_t mask; /+ A bit mask to select the bottom 'nbins' bits. +/
63	amb	71
64	amb	165	uint32_t alloced; /*+ The amount of space allocated for results
65	amb	79	(the length of the number and pointers arrays and
66			1/nbins times the amount in the real results). +*/
67	amb	165	uint32_t number; /+ The total number of occupied results. +/
68	amb	71
69	amb	79	uint32_t count; /+ An array of nbins counters of results in each array. +*/
70			Result **point; /+ An array of nbins arrays of pointers to actual results. +*/
71	amb	71
72	amb	79	Result *data; /+ An array of arrays containing the actual results
73			(don't need to realloc the array of data when adding more,
74			only realloc the array that points to the array of data).
75			Most importantly pointers into the real data don't change
76	amb	113	as more space is allocated (since realloc is not being used). +*/
77	amb	165
78			index_t start; /+ The start node. +/
79			index_t finish; /+ The finish node. +/
80	amb	29	}
81			Results;
82
83
84	amb	236	/* Forward definitions for opaque type */
85
86			typedef struct _Queue Queue;
87
88
89	amb	234	/* Results Functions */
90	amb	29
91	amb	71	Results *NewResultsList(int nbins);
92	amb	29	void FreeResultsList(Results *results);
93
94	amb	116	Result InsertResult(Results results,index_t node);
95	amb	166	void ZeroResult(Result *result);
96	amb	29
97	amb	116	Result FindResult(Results results,index_t node);
98	amb	29
99	amb	79	Result FirstResult(Results results);
100			Result NextResult(Results results,Result *result);
101	amb	29
102	amb	234
103	amb	67	/* Queue Functions */
104
105	amb	236	Queue *NewQueueList(void);
106			void FreeQueueList(Queue *queue);
107	amb	67
108	amb	236	void InsertInQueue(Queue queue,Result result);
109			Result PopFromQueue(Queue queue);
110	amb	67
111	amb	236
112	amb	29	#endif /* RESULTS_H */