summaryrefslogtreecommitdiff
path: root/app/bin/shrtpath.c
diff options
context:
space:
mode:
Diffstat (limited to 'app/bin/shrtpath.c')
-rw-r--r--app/bin/shrtpath.c195
1 files changed, 106 insertions, 89 deletions
diff --git a/app/bin/shrtpath.c b/app/bin/shrtpath.c
index b8fbe1e..f969a12 100644
--- a/app/bin/shrtpath.c
+++ b/app/bin/shrtpath.c
@@ -17,11 +17,9 @@
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
- * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
*/
-#include <string.h>
-
#include "shrtpath.h"
#include "track.h"
@@ -36,22 +34,22 @@ static int log_shortPathInitted;
typedef enum { Unknown, Working, Final } pathState_e;
typedef struct {
- pathState_e state;
- DIST_T dist; /* Distance from root to entry */
- track_p contTrk; /* continuation */
- EPINX_T contEP;
- int inxBack; /* Previous node on shortest path */
- int inxTracks; /* List of tracks along this path */
- int numTracks;
- } pathNode_t, *pathNode_p;
+ pathState_e state;
+ DIST_T dist; /* Distance from root to entry */
+ track_p contTrk; /* continuation */
+ EPINX_T contEP;
+ int inxBack; /* Previous node on shortest path */
+ int inxTracks; /* List of tracks along this path */
+ int numTracks;
+} pathNode_t, *pathNode_p;
static dynArr_t pathNode_da;
#define pathNode(N) DYNARR_N( pathNode_t, pathNode_da, N )
typedef struct {
- track_p trk;
- EPINX_T ep1, ep2;
- DIST_T dist;
- } trackep_t, *trackep_p;
+ track_p trk;
+ EPINX_T ep1, ep2;
+ DIST_T dist;
+} trackep_t, *trackep_p;
static dynArr_t trackep_da;
#define trackep(N) DYNARR_N( trackep_t, trackep_da, N )
@@ -59,12 +57,14 @@ static track_p shortPathTrk0, shortPathTrk1;
static EPINX_T shortPathEP0, shortPathEP1;
-static int DoShortPathFunc( shortestPathFunc_p func, char * title, SPTF_CMD cmd, track_p trk, EPINX_T ep1, EPINX_T ep2, DIST_T dist, void * data )
+static int DoShortPathFunc( shortestPathFunc_p func, char * title, SPTF_CMD cmd,
+ track_p trk, EPINX_T ep1, EPINX_T ep2, DIST_T dist, void * data )
{
int rc;
-LOG( log_shortPath, 4, ( " %s: T%d:%d.%d D:%0.3f ", title, trk?GetTrkIndex(trk):-1, ep1, ep2, dist ) )
+ LOG( log_shortPath, 4, ( " %s: T%d:%d.%d D:%0.3f ", title,
+ trk?GetTrkIndex(trk):-1, ep1, ep2, dist ) )
rc = func( cmd, trk, ep1, ep2, dist, data );
-LOG( log_shortPath, 4, ( "-> %d\n", rc ) )
+ LOG( log_shortPath, 4, ( "-> %d\n", rc ) )
return rc;
}
@@ -78,20 +78,21 @@ static void DumpPaths( int pinx )
for (pinx=0; pinx<pathNode_da.cnt; pinx++) {
pPath = &pathNode(pinx);
lprintf( " %3d: S%c T%d:%d D%0.3f T%d:%d",
- pinx,
- pPath->state==Unknown?'U':pPath->state==Working?'W':pPath->state==Final?'F':'?',
- (pPath->contTrk?GetTrkIndex(pPath->contTrk):-1),
- pPath->contEP,
- pPath->dist,
- pPath->inxTracks,
- pPath->numTracks );
+ pinx,
+ pPath->state==Unknown?'U':pPath->state==Working?'W':pPath->state==Final?'F':'?',
+ (pPath->contTrk?GetTrkIndex(pPath->contTrk):-1),
+ pPath->contEP,
+ pPath->dist,
+ pPath->inxTracks,
+ pPath->numTracks );
if (pPath->inxBack>=0) {
- lprintf(" B%d", pPath->inxBack );
+ lprintf(" B%d", pPath->inxBack );
}
lprintf("\n ");
for (tinx=0; tinx<pPath->numTracks; tinx++) {
pTrackep = &trackep(pPath->inxTracks+tinx);
- lprintf( " T%d:%d-%d=%0.1f", GetTrkIndex(pTrackep->trk), pTrackep->ep1, pTrackep->ep2, pTrackep->dist );
+ lprintf( " T%d:%d-%d=%0.1f", GetTrkIndex(pTrackep->trk), pTrackep->ep1,
+ pTrackep->ep2, pTrackep->dist );
}
lprintf("\n");
}
@@ -99,9 +100,9 @@ static void DumpPaths( int pinx )
static void AddTracksToPath(
- int inxCurr,
- shortestPathFunc_p func,
- void * data )
+ int inxCurr,
+ shortestPathFunc_p func,
+ void * data )
{
pathNode_p pPath;
int tinx;
@@ -109,9 +110,10 @@ static void AddTracksToPath(
while (inxCurr>=0) {
pPath = &pathNode(inxCurr);
- for (tinx=pPath->numTracks-1;tinx>=0;tinx--) {
+ for (tinx=pPath->numTracks-1; tinx>=0; tinx--) {
pTrackep = &trackep(pPath->inxTracks+tinx);
- DoShortPathFunc( func, "ADDTRK", SPTC_ADD_TRK, pTrackep->trk, pTrackep->ep1, pTrackep->ep2, pTrackep->dist, data );
+ DoShortPathFunc( func, "ADDTRK", SPTC_ADD_TRK, pTrackep->trk, pTrackep->ep1,
+ pTrackep->ep2, pTrackep->dist, data );
}
inxCurr = pPath->inxBack;
}
@@ -119,10 +121,10 @@ static void AddTracksToPath(
static void AddTrackToNode(
- track_p trk,
- EPINX_T ep1,
- EPINX_T ep2,
- DIST_T dist)
+ track_p trk,
+ EPINX_T ep1,
+ EPINX_T ep2,
+ DIST_T dist)
{
DYNARR_APPEND( trackep_t, trackep_da, 10 );
trackep(trackep_da.cnt-1).trk = trk;
@@ -133,13 +135,13 @@ static void AddTrackToNode(
static BOOL_T AddPath(
- int inxCurr,
- track_p trk0,
- EPINX_T ep1,
- EPINX_T ep2,
- DIST_T dist,
- shortestPathFunc_p func,
- void * data )
+ int inxCurr,
+ track_p trk0,
+ EPINX_T ep1,
+ EPINX_T ep2,
+ DIST_T dist,
+ shortestPathFunc_p func,
+ void * data )
{
EPINX_T epN;
track_p trk=trk0, trkN;
@@ -148,12 +150,13 @@ static BOOL_T AddPath(
int startTrack;
char * msg=NULL;
-LOG( log_shortPath, 2, ( " AddPath( T%d:%d.%d D=%0.3f B%d ) -> \n", GetTrkIndex(trk), ep1, ep2, dist, inxCurr ) )
+ LOG( log_shortPath, 2, ( " AddPath( T%d:%d.%d D=%0.3f B%d ) -> \n",
+ GetTrkIndex(trk), ep1, ep2, dist, inxCurr ) )
startTrack = trackep_da.cnt;
while (1) {
if ( ep2>=0 ) {
AddTrackToNode( trk, ep1, ep2, dist );
- dist += GetTrkLength( trk, ep1, -1 ) + GetTrkLength( trk, ep2, -1 );
+ dist += GetTrkLength( trk, ep1, ep2 );
if ( DoShortPathFunc( func, "MATCH", SPTC_MATCH, trk, ep2, ep1, dist, data ) ) {
trk = NULL;
ep1 = -1;
@@ -166,13 +169,15 @@ LOG( log_shortPath, 2, ( " AddPath( T%d:%d.%d D=%0.3f B%d ) -> \n", GetTrkIndex
msg = "dead end";
goto skipNode;
}
- if ( DoShortPathFunc( func, "IGNORE", SPTC_IGNNXTTRK, trk, ep2, ep1, dist, data ) ) {
+ if ( DoShortPathFunc( func, "IGNORE", SPTC_IGNNXTTRK, trk, ep2, ep1, dist,
+ data ) ) {
msg = "ignore end";
goto skipNode;
}
ep1 = GetEndPtConnectedToMe( trkN, trk );
trk = trkN;
- if ( (trk==shortPathTrk0 && ep1==shortPathEP0) || (trk==shortPathTrk1 && ep1==shortPathEP1) ) {
+ if ( (trk==shortPathTrk0 && ep1==shortPathEP0) || (trk==shortPathTrk1
+ && ep1==shortPathEP1) ) {
msg = "wrap around";
goto skipNode;
}
@@ -183,7 +188,8 @@ LOG( log_shortPath, 2, ( " AddPath( T%d:%d.%d D=%0.3f B%d ) -> \n", GetTrkIndex
goto skipNode;
}
if ( epCnt > 2 ) {
- if ( (epN=DoShortPathFunc( func, "MATCHANY", SPTC_MATCHANY, trk, ep1, -1, dist, data )) >= 0 ) {
+ if ( (epN=DoShortPathFunc( func, "MATCHANY", SPTC_MATCHANY, trk, ep1, -1, dist,
+ data )) >= 0 ) {
/* special match */
/*dist += GetTrkLength( trk, ep1, epN );*/
AddTrackToNode( trk, ep1, epN, dist );
@@ -197,12 +203,13 @@ LOG( log_shortPath, 2, ( " AddPath( T%d:%d.%d D=%0.3f B%d ) -> \n", GetTrkIndex
}
makeNode:
-if ( trk ) {
-LOG( log_shortPath, 2, ( " -> FORK: [%d] T%d:%d", pathNode_da.cnt, GetTrkIndex(trk), ep1 ) )
-} else {
-LOG( log_shortPath, 2, ( " -> MATCH%s: [%d]", msg, pathNode_da.cnt ) )
-}
-LOG( log_shortPath, 2, ( " t%d D=%0.3f\n", startTrack, dist ) )
+ if ( trk ) {
+ LOG( log_shortPath, 2, ( " -> FORK: [%d] T%d:%d", pathNode_da.cnt,
+ GetTrkIndex(trk), ep1 ) )
+ } else {
+ LOG( log_shortPath, 2, ( " -> MATCH%s: [%d]", msg, pathNode_da.cnt ) )
+ }
+ LOG( log_shortPath, 2, ( " t%d D=%0.3f\n", startTrack, dist ) )
DYNARR_APPEND( pathNode_t, pathNode_da, 10 );
pNode = &pathNode(pathNode_da.cnt-1);
@@ -210,90 +217,98 @@ LOG( log_shortPath, 2, ( " t%d D=%0.3f\n", startTrack, dist ) )
pNode->dist = dist;
pNode->contTrk = trk;
pNode->contEP = ep1;
- pNode->inxBack = inxCurr;
+ pNode->inxBack = inxCurr;
pNode->inxTracks = startTrack;
pNode->numTracks = trackep_da.cnt-startTrack;
- if ( trk )
+ if ( trk ) {
SetTrkBits( trk, TB_SHRTPATH );
+ }
return TRUE;
skipNode:
-LOG( log_shortPath, 2, ( " -> FAIL: %s @ T%d:%d.%d\n", msg, GetTrkIndex(trk), ep1, ep2 ) )
- trackep_da.cnt = startTrack;
+ LOG( log_shortPath, 2, ( " -> FAIL: %s @ T%d:%d.%d\n", msg, GetTrkIndex(trk),
+ ep1, ep2 ) )
+ DYNARR_SET( trackep_t, trackep_da, startTrack );
return FALSE;
}
int FindShortestPath(
- track_p trkN,
- EPINX_T epN,
- BOOL_T bidirectional,
- shortestPathFunc_p func,
- void * data )
+ track_p trkN,
+ EPINX_T epN,
+ BOOL_T bidirectional,
+ shortestPathFunc_p func,
+ void * data )
{
int inxCurr = 0;
pathNode_p pCurr;
pathNode_p pNext;
int pinx=0;
DIST_T minDist;
- int count;
int rc = 0;
EPINX_T ep2, epCnt, ep3;
static dynArr_t ep_da;
- #define ep(N) DYNARR_N( pathNode_p, ep_da, N )
+#define ep(N) DYNARR_N( pathNode_p, ep_da, N )
DYNARR_RESET( pathNode_t, pathNode_da );
DYNARR_RESET( trackep_t, trackep_da );
- count = 0;
if ( !log_shortPathInitted ) {
log_shortPath = LogFindIndex( "shortPath" );
- log_shortPathInitted = TRUE;
+ log_shortPathInitted = TRUE;
}
-LOG( log_shortPath, 1, ( "FindShortestPath( T%d:%d, %s, ... )\n", GetTrkIndex(trkN), epN, bidirectional?"bidir":"unidir" ) )
+ LOG( log_shortPath, 1, ( "FindShortestPath( T%d:%d, %s, ... )\n",
+ GetTrkIndex(trkN), epN, bidirectional?"bidir":"unidir" ) )
ClrAllTrkBits( TB_SHRTPATH );
/* Note: trkN:epN is not tested for MATCH */
shortPathTrk0 = trkN;
shortPathEP0 = epN;
shortPathTrk1 = GetTrkEndTrk( trkN, epN );
- if ( shortPathTrk1 != NULL )
+ if ( shortPathTrk1 != NULL ) {
shortPathEP1 = GetEndPtConnectedToMe( shortPathTrk1, shortPathTrk0 );
+ }
AddPath( -1, shortPathTrk0, shortPathEP0, -1, 0.0, func, data );
- if ( bidirectional && shortPathTrk1 != NULL )
+ if ( bidirectional && shortPathTrk1 != NULL ) {
AddPath( -1, shortPathTrk1, shortPathEP1, -1, 0.0, func, data );
+ }
while (1) {
- InfoMessage( "%d", ++count );
-
/* select next final node */
minDist = 0.0;
inxCurr = -1;
for (pinx=0; pinx<pathNode_da.cnt; pinx++) {
- pNext = &pathNode(pinx);
- if (pNext->state == Working &&
- (inxCurr < 0 || pNext->dist < minDist) ) {
+ pNext = &pathNode(pinx);
+ if (pNext->state == Working &&
+ (inxCurr < 0 || pNext->dist < minDist) ) {
minDist = pathNode(pinx).dist;
inxCurr = pinx;
}
}
- if ( inxCurr < 0 )
+ if ( inxCurr < 0 ) {
break;
-if (log_shortPath>=4) DumpPaths(inxCurr);
+ }
+ if (log_shortPath>=4) { DumpPaths(inxCurr); }
pCurr = &pathNode(inxCurr);
pCurr->state = Final;
if ( pCurr->contTrk == NULL ) {
- if ( !DoShortPathFunc( func, "VALID", SPTC_VALID, trackep(pCurr->inxTracks+pCurr->numTracks-1).trk, trackep(pCurr->inxTracks+pCurr->numTracks-1).ep2, -1, 0.0, data ) )
+ if ( !DoShortPathFunc( func, "VALID", SPTC_VALID,
+ trackep(pCurr->inxTracks+pCurr->numTracks-1).trk,
+ trackep(pCurr->inxTracks+pCurr->numTracks-1).ep2, -1, 0.0, data ) ) {
continue;
+ }
AddTracksToPath( inxCurr, func, data );
rc++;
- if ( DoShortPathFunc( func, "TERMINATE", SPTC_TERMINATE, trackep(pCurr->inxTracks+pCurr->numTracks-1).trk, trackep(pCurr->inxTracks+pCurr->numTracks-1).ep2, -1, 0.0, data ) )
+ if ( DoShortPathFunc( func, "TERMINATE", SPTC_TERMINATE,
+ trackep(pCurr->inxTracks+pCurr->numTracks-1).trk,
+ trackep(pCurr->inxTracks+pCurr->numTracks-1).ep2, -1, 0.0, data ) ) {
break;
+ }
} else {
epCnt = GetTrkEndPtCnt(pCurr->contTrk);
DYNARR_SET( pathNode_p, ep_da, epCnt );
- memset( ep_da.ptr, 0, epCnt * sizeof pNext );
+ memset( &ep(0), 0, epCnt * sizeof pNext );
if ( (GetTrkBits(pCurr->contTrk) & TB_SHRTPATH) ) {
for ( pinx=0; pinx<pathNode_da.cnt; pinx++ ) {
pNext = &pathNode(pinx);
@@ -306,25 +321,27 @@ if (log_shortPath>=4) DumpPaths(inxCurr);
pCurr = &pathNode(inxCurr);
/* don't point back at myself */
- if ( pCurr->contEP == ep2 ) continue;
+ if ( pCurr->contEP == ep2 ) { continue; }
/* no route to ep */
- if ( DoShortPathFunc( func, "IGNORE", SPTC_IGNNXTTRK, pCurr->contTrk, pCurr->contEP, ep2, pCurr->dist, data ) ) continue;
+ if ( DoShortPathFunc( func, "IGNORE", SPTC_IGNNXTTRK, pCurr->contTrk,
+ pCurr->contEP, ep2, pCurr->dist, data ) ) { continue; }
/* somebody got here first */
- if ( ep(ep2) ) continue;
+ if ( ep(ep2) ) { continue; }
/* there is already a path out via ep2 */
for ( ep3=0; ep3<epCnt; ep3++ ) {
- if ( ep3==pCurr->contEP || ep3==ep2 ) continue;
- if ( ep(ep3) == NULL ) continue;
- if ( DoShortPathFunc( func, "IGNORE", SPTC_IGNNXTTRK, pCurr->contTrk, ep2, ep3, pCurr->dist, data ) ) continue;
- if ( ep(ep3)->state == Final ) break;
+ if ( ep3==pCurr->contEP || ep3==ep2 ) { continue; }
+ if ( ep(ep3) == NULL ) { continue; }
+ if ( DoShortPathFunc( func, "IGNORE", SPTC_IGNNXTTRK, pCurr->contTrk, ep2, ep3,
+ pCurr->dist, data ) ) { continue; }
+ if ( ep(ep3)->state == Final ) { break; }
}
- if ( ep3 < epCnt ) continue;
+ if ( ep3 < epCnt ) { continue; }
AddPath( inxCurr, pCurr->contTrk, pCurr->contEP, ep2, pCurr->dist, func, data );
}
}
}
-if (log_shortPath>=1) DumpPaths(inxCurr);
+ if (log_shortPath>=1) { DumpPaths(inxCurr); }
ClrAllTrkBits( TB_SHRTPATH );
return rc;
}
generated by cgit v1.2.3 (git 2.25.1) at 2024-12-26 19:21:30 +0000