1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
|
#include <stdlib.h>
#define __LIBSCOUT_INTERNAL__
#include "scout.h"
typedef struct scnode scnode;
typedef struct scway scway;
typedef struct scwaypoint scwaypoint;
scway *scaddway(scnode *from, const scnode *to, int len)
{
scway *way = malloc(sizeof(scway));
way->lto = to;
way->alt = NULL;
way->len = len;
scway *apar, *par = NULL;
for (apar = from->way; apar != NULL; par = apar, apar = apar->alt);
if (par)
par->alt = way;
else
from->way = way;
return way;
}
scwaypoint *scout(const scnode *from, const scnode *to, scwaypoint *stack)
{
scwaypoint *wayp = NULL;
if (from == to)
return __scallocwayp(from, NULL);
for (scway *way = from->way; way != NULL; way = way->alt) {
scwaypoint *stackend;
if ((stackend = __scstackfindgetend(stack, way)) == NULL)
continue;
scwaypoint *twayp = __scallocwayp(from, way);
stackend->nxt = twayp;
scwaypoint *nwayp = scout(way->lto, to, stack)
if (wayp && wayp->len <= (twayp->len = __scstackgetlen(twayp)))
__scstackfree(wayp);
wayp = twayp;
}
return wayp;
}
scwaypoint *__scallocwayp(const scnode *node, const scway *way)
{
scwaypoint *wayp = malloc(sizeof(scwaypoint));
wayp->nod = node;
wayp->way = way;
wayp->nxt = NULL;
wayp->len = way->len;
}
scwaypoint *__scstackfindgetend(scwaypoint *stack, const scway *way)
{
scwaypoint *asptr, *sptr;
for (asptr = stack; asptr != NULL; sptr = asptr, asptr = asptr->nxt)
if (asptr->nod == way->lto)
return NULL;
return sptr;
}
void __scstackfree(scwaypoint *stack)
{
for (scwaypoint *sptr = stack; sptr != NULL; sptr = sptr->nxt)
free(sptr);
}
|
