trunk/src/results.h

/***************************************
 A header file for the results.

 Part of the Routino routing software.
 ******************/ /******************
 This file Copyright 2008-2011 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 */

typedef struct _Result Result;

/*+ The result for a node. +*/
struct _Result
{
 index_t   node;                /*+ The node for which this result applies. +*/
 index_t   segment;             /*+ The segmemt used to get to the node for which this result applies. +*/

 Result   *prev;                /*+ The previous result following the best path to get to this node via the segment. +*/
 Result   *next;                /*+ The next result following the best path from this node that was reached via the segment. +*/

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

/*+ 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_node;            /*+ The start node. +*/
 index_t prev_segment;          /*+ The previous segment to get to the start node (if any). +*/

 index_t finish_node;           /*+ The finish node. +*/
 index_t last_segment;          /*+ The last segment (to arrive at 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,index_t segment);

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

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	/***************************************
2	A header file for the results.
3
4	Part of the Routino routing software.
5	****************/ /****************
6	This file Copyright 2008-2011 Andrew M. Bishop
7
8	This program is free software: you can redistribute it and/or modify
9	it under the terms of the GNU Affero General Public License as published by
10	the Free Software Foundation, either version 3 of the License, or
11	(at your option) any later version.
12
13	This program is distributed in the hope that it will be useful,
14	but WITHOUT ANY WARRANTY; without even the implied warranty of
15	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16	GNU Affero General Public License for more details.
17
18	You should have received a copy of the GNU Affero General Public License
19	along with this program. If not, see <http://www.gnu.org/licenses/>.
20	***************************************/
21
22
23	#ifndef RESULTS_H
24	#define RESULTS_H /+ To stop multiple inclusions. +/
25
26	#include <stdint.h>
27
28	#include "types.h"
29
30
31	/* Constants */
32
33	/+ A result is not currently queued. +/
34	#define NOT_QUEUED (uint32_t)(~0)
35
36
37	/* Data structures */
38
39	typedef struct _Result Result;
40
41	/+ The result for a node. +/
42	struct _Result
43	{
44	index_t node; /+ The node for which this result applies. +/
45	index_t segment; /+ The segmemt used to get to the node for which this result applies. +/
46
47	Result prev; /+ The previous result following the best path to get to this node via the segment. +*/
48	Result next; /+ The next result following the best path from this node that was reached via the segment. +*/
49
50	score_t score; /+ The best actual weighted distance or duration score from the start to the node. +/
51	score_t sortby; /+ The best possible weighted distance or duration score from the start to the finish. +/
52
53	uint32_t queued; /+ The position of this result in the queue. +/
54	};
55
56	/+ A list of results. +/
57	typedef struct _Results
58	{
59	uint32_t nbins; /+ The number of bins. +/
60	uint32_t mask; /+ A bit mask to select the bottom 'nbins' bits. +/
61
62	uint32_t alloced; /*+ The amount of space allocated for results
63	(the length of the number and pointers arrays and
64	1/nbins times the amount in the real results). +*/
65	uint32_t number; /+ The total number of occupied results. +/
66
67	uint32_t count; /+ An array of nbins counters of results in each array. +*/
68	Result **point; /+ An array of nbins arrays of pointers to actual results. +*/
69
70	Result *data; /+ An array of arrays containing the actual results
71	(don't need to realloc the array of data when adding more,
72	only realloc the array that points to the array of data).
73	Most importantly pointers into the real data don't change
74	as more space is allocated (since realloc is not being used). +*/
75
76	index_t start_node; /+ The start node. +/
77	index_t prev_segment; /+ The previous segment to get to the start node (if any). +/
78
79	index_t finish_node; /+ The finish node. +/
80	index_t last_segment; /+ The last segment (to arrive at the finish node). +/
81	}
82	Results;
83
84
85	/* Forward definitions for opaque type */
86
87	typedef struct _Queue Queue;
88
89
90	/* Results Functions */
91
92	Results *NewResultsList(int nbins);
93	void FreeResultsList(Results *results);
94
95	Result InsertResult(Results results,index_t node,index_t segment);
96
97	Result FindResult1(Results results,index_t node);
98	Result FindResult(Results results,index_t node,index_t segment);
99
100	Result FirstResult(Results results);
101	Result NextResult(Results results,Result *result);
102
103
104	/* Queue Functions */
105
106	Queue *NewQueueList(void);
107	void FreeQueueList(Queue *queue);
108
109	void InsertInQueue(Queue queue,Result result);
110	Result PopFromQueue(Queue queue);
111
112
113	#endif /* RESULTS_H */