trunk/src/results.h

/***************************************
 $Header: /home/amb/CVS/routino/src/results.h,v 1.12 2009-04-27 18:56:39 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"


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

 distance_t  distance;          /*+ The distance travelled to the node following the best path. +*/
 duration_t  duration;          /*+ The time taken to the node following the best path. +*/

 distance_t  sortby;            /*+ The value to sort the results by in the queue. +*/
}
 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;


/* Functions */

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

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

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

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

/* Queue Functions */

void insert_in_queue(Result *result);
Result *pop_from_queue(void);


#endif /* RESULTS_H */
1	/***************************************
2	$Header: /home/amb/CVS/routino/src/results.h,v 1.12 2009-04-27 18:56:39 amb Exp $
3
4	A header file for the results.
5
6	Part of the Routino routing software.
7	****************/ /****************
8	This file Copyright 2008,2009 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	#ifndef RESULTS_H
26	#define RESULTS_H /+ To stop multiple inclusions. +/
27
28	#include <stdint.h>
29
30	#include "types.h"
31
32
33	/* Data structures */
34
35	/+ The result for a node. +/
36	typedef struct _Result
37	{
38	index_t node; /+ The node for which this result applies. +/
39
40	index_t prev; /+ The previous node following the best path. +/
41	index_t next; /+ The next node following the best path. +/
42
43	distance_t distance; /+ The distance travelled to the node following the best path. +/
44	duration_t duration; /+ The time taken to the node following the best path. +/
45
46	distance_t sortby; /+ The value to sort the results by in the queue. +/
47	}
48	Result;
49
50	/+ A list of results. +/
51	typedef struct _Results
52	{
53	uint32_t nbins; /+ The number of bins. +/
54	uint32_t mask; /+ A bit mask to select the bottom 'nbins' bits. +/
55
56	uint32_t alloced; /*+ The amount of space allocated for results
57	(the length of the number and pointers arrays and
58	1/nbins times the amount in the real results). +*/
59	uint32_t number; /+ The total number of occupied results. +/
60
61	uint32_t count; /+ An array of nbins counters of results in each array. +*/
62	Result **point; /+ An array of nbins arrays of pointers to actual results. +*/
63
64	Result *data; /+ An array of arrays containing the actual results
65	(don't need to realloc the array of data when adding more,
66	only realloc the array that points to the array of data).
67	Most importantly pointers into the real data don't change
68	as more space is allocated (since realloc is not being used). +*/
69
70	index_t start; /+ The start node. +/
71	index_t finish; /+ The finish node. +/
72	}
73	Results;
74
75
76	/* Functions */
77
78	Results *NewResultsList(int nbins);
79	void FreeResultsList(Results *results);
80
81	Result InsertResult(Results results,index_t node);
82
83	Result FindResult(Results results,index_t node);
84
85	Result FirstResult(Results results);
86	Result NextResult(Results results,Result *result);
87
88	/* Queue Functions */
89
90	void insert_in_queue(Result *result);
91	Result *pop_from_queue(void);
92
93
94	#endif /* RESULTS_H */