//  mapdata.cpp
//
//  Application entry point for reading in LU map data and outputting it
//  in appropriate forms.

#include "stdafx.h"

#include <fstream.h>

// Definitions for MC structures
#include "context.h"
#include "line.h"
#include "station.h"
#include "stationnode.h"
#include "linesegment.h"

#include "exceptions.h"

class MapBuilder
{
    mcContext map;

    // Cached information
    CMapStringToPtr linesByCode;        // Line.code => Line *

    // History information
    Station *lastStation;
    StationNode *lastNode;

public:
    MapBuilder()
        : lastStation(0),
          lastNode(0)
    { }
    ~MapBuilder()
    { }

    // Utility function for splitting up strings
    // Note: ownership of the data returned is passed to the caller. It is eir
    // responsibility to delete it.
    static CStringArray *tokeniseString(const CString &data, const char *delim);

    // Other utilities for converting between string and flag representations
    // for zones and quadrants

// BUGBUG Properly ought to give these declarations throw specifiers...
    Line *buildLine(const CString &lineData);
    Station *buildStation(const CString &stationData);
    StationNode *buildStationNode(const CString &nodeData);
    LineSegment *buildLineSegment(const CString &segmentData);

    BOOL fixupLineSegments();

    void writeSQL(ofstream &outFile);
    void traverseNodes(ofstream &outFile);
    void followToNode(ofstream &outfile,
                      StationNode *root,
                      CMapStringToPtr *segsByFromNode);
};

IDManager mcThing::idman;

int main(int argc, char **argv)
{
    CString inputName;

    BOOL dumpRoutes = FALSE;

    // Command line is:
    //  mapdata <mapdata file>
    switch (argc)
    {
        case 3: // anything will do
            dumpRoutes = TRUE;
            // FALL THROUGH

        case 2:
            inputName = argv[1];
            break;

        default:
            cout << "Usage:\n"
                    "\tmapdata <mapdata file>\n"
                    "where output will be written to a file with the same name as the argument,\n"
                    "but with a .sql extension.";
            return 1;
//            break;
    }

    // Got an input name, now construct the two files we need
    ifstream inputFile;
    inputFile.open(inputName, ios::in | ios::nocreate);
    if (!inputFile.is_open())
    {
        cout << "*** Could not open input file " << inputName << "\n";
        return 1;
    }

    CString outExtn(dumpRoutes ? ".rts" : ".sql");
    int dotIx = inputName.ReverseFind('.');
    CString outputName((dotIx > 0
                            ? inputName.Left(dotIx)
                            : inputName)
                        + outExtn);
    ofstream outputFile;
    outputFile.open(outputName, ios::out | ios::trunc);
    if (!outputFile.is_open())
    {
        cout << "*** Could not open output file " << outputName << "\n";
        return 1;
    }

    // Time for a monster quick hack
    // Basically, I should do this properly, by splitting off parsing of the
    // types by type and by separating the input and output modules into
    // entirely separate classes which can be chosen at run time for different
    // input and output formats.
    // But I can't be arsed, and I need my spin data *now*. So I'm going to
    // hack it.

    // Input processing consists of:
    //  - reading in a line at a time of the input
    //  - looking at the opening word (delimited by tab)
    //  - dispatching the rest of the line to a per type parser which returns
    //      an object of the appropriate dooberry
    //  - tying up any references (may be done by the parsing module, but
    //      probably best not to)
    //  - dumping gracefully if any errors have been found
    // Once the input file is exhausted and processed cleanly, we move onto
    // output processing:
    //  - iterate through each type set
    //  - for each instance, write out a SQL INSERT statement which will write
    //      a data record into the tables created by the data design I've been
    //      working on
    // After that, it's up to the user (me) to execute the script in SQL*Plus.

    // Input processing
    // BUGBUG Assumption: no line is longer than 256 bytes
    MapBuilder builder;
    char buffer[256];
    int lineCount = 0;
    
    while (inputFile && !inputFile.eof())
    {
        lineCount++;

        //  - reading in a line at a time of the input
        inputFile.getline(buffer, 256);
        CString text(buffer);

        //  - looking at the opening word (delimited by tab)
        int tabIndex = -1;
        if (text.GetLength() > 0)
        {
            tabIndex = text.Find('\t');
        }
        else
        {
            cout << "** No line content found on line " << lineCount << "\n";
            break;
        }

        if (tabIndex == -1 && text.GetLength() > 0)
        {
            cout << "*** No tab character found on line " << lineCount << " - discarded.\n"
                 << "\t" << text << endl;
            break;
        }
        CString keyword(text.Left(tabIndex));

        //  - dispatching the rest of the line to a per type parser which returns
        //      an object of the appropriate dooberry
        if (keyword == "line")
        {
            try
            {
                Line *line = builder.buildLine(text.Mid(tabIndex + 1));
            }
            catch (BadRecordException *e)
            {
                cout << "*** Invalid Line record on line " << lineCount << " - discarded.\n"
                     << e->toString() << "\n"
                     << "\t" << text << endl;
            }
        }
        else if (keyword == "station")
        {
            try
            {
                Station *station = builder.buildStation(text.Mid(tabIndex + 1));
            }
            catch (BadRecordException *e)
            {
                cout << "*** Invalid Station record on line " << lineCount << " - discarded.\n"
                     << e->toString() << "\n"
                     << "\t" << text << endl;
            }
        }
        else if (keyword == "node")
        {
            try
            {
                StationNode *node = builder.buildStationNode(text.Mid(tabIndex + 1));
            }
            catch (BadRecordException *e)
            {
                cout << "*** Invalid StationNode record on line " << lineCount << " - discarded.\n"
                     << e->toString() << "\n"
                     << "\t" << text << endl;
            }
        }
        else if (keyword == "segment")
        {
            try
            {
                LineSegment *segment = builder.buildLineSegment(text.Mid(tabIndex + 1));
            }
            catch (BadRecordException *e)
            {
                cout << "*** Invalid LineSegment record on line " << lineCount << " - discarded.\n"
                     << e->toString() << "\n"
                     << "\t" << text << endl;
            }
        }
        else
        {
            cout << "*** Unrecognised record type found on line " << lineCount << " - discarded.\n"
                 << "\t" << text << endl;
            break;
        }

        //  - tying up any references (may be done by the parsing module, but
        //      probably best not to)
        //  - dumping gracefully if any errors have been found
    }

    inputFile.close();

    // Tie up all the line segments
    // Note: this function should return false if the map data is inconsistent
    if (builder.fixupLineSegments())
    {
        if (dumpRoutes)
            builder.traverseNodes(outputFile);
        else
            builder.writeSQL(outputFile);
    }

    outputFile.close();

    return 0;   // If it's got here, then it's worked. Nuff said.
}

// Implementation for map building class

CStringArray *MapBuilder::tokeniseString(const CString &data, const char *delim)
{
    CStringArray *tokens = new CStringArray;
    CString restOfData(data);
    for (int delimIdx = restOfData.FindOneOf(delim); delimIdx != -1;
             delimIdx = restOfData.FindOneOf(delim))
    {
        tokens->Add(restOfData.Left(delimIdx)); // Add found token to set
        restOfData = restOfData.Mid(delimIdx);  // Remove found token from data
        // Eliminate delimiters
        CString delimString = restOfData.SpanIncluding(delim);
        restOfData = restOfData.Mid(delimString.GetLength());
        if (restOfData.IsEmpty()) tokens->Add(restOfData);
    }

    // Add any closing token onto the set
    if (!restOfData.IsEmpty())
    {
        tokens->Add(restOfData);
    }

    return tokens;
}

Line *MapBuilder::buildLine(const CString &lineData)
{
    // Format for Line record is:
    //  <line code>,<colour>,<line name>
    CStringArray *tokens = tokeniseString(lineData, ",");

    // Check for invalid number of tokens
    int tokCount = tokens->GetSize();
    if (tokCount != 3)
    {
        delete tokens;
        throw new BadRecordException("MapBuilder::buildLine()",
                                     "incorrect token count - found " + CNumString(tokCount)
                                        +", expected 3");
//        return 0;   // keep Microsoft's compiler happy
    }

    // Construct Line object:
    Line *line = new Line(&map
                         ,tokens->GetAt(2)  // line name
                         ,tokens->GetAt(1)  // colour
                         ,tokens->GetAt(0)  // line code
                          );

    delete tokens;  // Finished with these now

    // Check for duplicate line codes
    Line *dummy;
    if (linesByCode.Lookup(line->getCode(), (void *&)dummy))
    {
        delete line;
        throw new BadRecordException("MapBuilder::buildLine()",
                                     "duplicate line code - " + dummy->getCode());
//        return 0;   // keep Microsoft's compiler happy
    }
    else
    {
        linesByCode.SetAt(line->getCode(), line);
    }

    map.addThing(line);

    return line;
}

// Mapping data from strings to zones and quadrants (and back again at a push)
struct strInt
{
    const char *string;
    int integer;
};

// There is actually a simple mathematical mapping here, but this is going to
// be quicker.
static strInt zones[] =
{
    // Simple zones
    { "1", Station::ZONE1 },
    { "2", Station::ZONE2 },
    { "3", Station::ZONE3 },
    { "4", Station::ZONE4 },
    { "5", Station::ZONE5 },
    { "6", Station::ZONE6 },
    { "7", Station::ZONE7 },

    // Zone boundaries
    { "1b2", Station::ZONE1 | Station::ZONE2 },
    { "2b3", Station::ZONE2 | Station::ZONE3 },
    { "3b4", Station::ZONE3 | Station::ZONE4 },
    { "4b5", Station::ZONE4 | Station::ZONE5 },
    { "5b6", Station::ZONE5 | Station::ZONE6 },
    { "6b7", Station::ZONE6 | Station::ZONE7 },

    { 0, 0 }
};
CMapStringToPtr zonesByName;
CMapStringToString zonesByNumber;   // Note: must use string rep

static strInt quadrants[] =
{
    // No quadrant
    { "-", StationNode::NONE },

    // Quadrants
    { "NE", StationNode::QUAD1 },
    { "SE", StationNode::QUAD2 },
    { "SW", StationNode::QUAD3 },
    { "NW", StationNode::QUAD4 },

    // Halves
    { "N", StationNode::QUAD1 | StationNode::QUAD4 },
    { "S", StationNode::QUAD2 | StationNode::QUAD3 },
    { "E", StationNode::QUAD1 | StationNode::QUAD2 },
    { "W", StationNode::QUAD3 | StationNode::QUAD4 },

    { 0, 0 }
};
CMapStringToPtr quadsByName;
CMapStringToString quadsByNumber;   // Note: must use string rep

static int directionToAlignment(int direction)
{
    static int dirAlignments[][2] =
    {
        // Diagonals
        { StationNode::QUAD1, Station::ONE_THREE },
        { StationNode::QUAD2, Station::TWO_FOUR },
        { StationNode::QUAD3, Station::ONE_THREE },
        { StationNode::QUAD4, Station::TWO_FOUR },

        // Rectilineals
        { StationNode::QUAD1 | StationNode::QUAD4, Station::VERTICAL },
        { StationNode::QUAD2 | StationNode::QUAD3, Station::VERTICAL },
        { StationNode::QUAD1 | StationNode::QUAD2, Station::HORIZONTAL },
        { StationNode::QUAD3 | StationNode::QUAD4, Station::HORIZONTAL },

        { 0, 0 }
    };
    for (int i = 0; dirAlignments[i][0]; i++)
    {
        if (direction == dirAlignments[i][0])
            return dirAlignments[i][1];
    }
    return Station::UNKNOWN;
};

Station *MapBuilder::buildStation(const CString &stationData)
{
    // Format for Station record is:
    //  <station name>,<zone>{'b'+<outer zone>},{[<quadrant>|<half>|'-']}
    // if quadrant is omitted here, its must be specified on the node
    CStringArray *tokens = tokeniseString(stationData, ",");

    // Check for invalid number of tokens
    int tokCount = tokens->GetSize();
    if (tokCount != 3)
    {
        delete tokens;
        throw new BadRecordException("MapBuilder::buildStation()",
                                     "incorrect token count - found " + CNumString(tokCount)
                                        +", expected 3");
//        return 0;   // keep Microsoft's compiler happy
    }

    // Populate maps
    if (zonesByName.IsEmpty())
    {
        for (strInt *zoneRow = zones; zoneRow->string; zoneRow++)
        {
            zonesByName.SetAt(zoneRow->string, (void *)(zoneRow->integer));
            zonesByNumber.SetAt(CNumString(zoneRow->integer), zoneRow->string);
        }
    }
    if (quadsByName.IsEmpty())
    {
        for (strInt *quadRow = quadrants; quadRow->string; quadRow++)
        {
            quadsByName.SetAt(quadRow->string, (void *)(quadRow->integer));
            quadsByNumber.SetAt(CNumString(quadRow->integer), quadRow->string);
        }
    }

    // Evaluate zone and (possibly) quadrant
    int zone;
    int defaultQuadrant = StationNode::UNKNOWN;
    if (!zonesByName.Lookup(tokens->GetAt(1), (void *&)zone))
    {
        BadRecordException *e = new BadRecordException("MapBuilder::buildStation()",
                                     "invalid zone " + tokens->GetAt(1));
        delete tokens;
        throw e;
//        return 0;   // keep Microsoft's compiler happy
    }
    if (!tokens->GetAt(2).IsEmpty()
     && !quadsByName.Lookup(tokens->GetAt(2), (void *&)defaultQuadrant))
    {
        BadRecordException *e = new BadRecordException("MapBuilder::buildStation()",
                                     "invalid quadrant " + tokens->GetAt(2));
        delete tokens;
        throw e;
//        return 0;   // keep Microsoft's compiler happy
    }

    // Construct Line object:
    Station *station = new Station(&map
                         ,tokens->GetAt(0)  // station name
                         ,zone              // zone
                         ,defaultQuadrant   // default quadrant
                          );

    delete tokens;  // Finished with these now

    map.addThing(station);

    // Save Station reference and reset node reference
    lastStation = station;
    lastNode = 0;

    return station;
}

StationNode *MapBuilder::buildStationNode(const CString &nodeData)
{
    // Format for StationNode record is:
    //  <line code>,<node ordinal>,'('+['i']+['t']+')','('+<x coord>,<y coord>+')'{,[<quadrant>|<half>]}
    // Station of which StationNode is a part is the last Station encountered
    // quadrant may be used to override default value given for Station
    CStringArray *tokens = tokeniseString(nodeData, ",");

    // Check for invalid number of tokens
    int tokCount = tokens->GetSize();
    if (tokCount != 5 && tokCount != 6)
    {
        delete tokens;
        throw new BadRecordException("MapBuilder::buildStationNode()",
                                     "incorrect token count - found " + CNumString(tokCount)
                                        +", expected 5 or 6");
//        return 0;   // keep Microsoft's compiler happy
    }

    // Check for parent Station
    if (lastStation == 0)
    {
        delete tokens;
        throw new BadRecordException("MapBuilder::buildStationNode()",
                                     "no station for node");
//        return 0;   // keep Microsoft's compiler happy
    }

    // Populate maps
    if (quadsByName.IsEmpty())
    {
        for (strInt *quadRow = quadrants; quadRow->string; quadRow++)
        {
            quadsByName.SetAt(quadRow->string, (void *)(quadRow->integer));
            quadsByNumber.SetAt(CNumString(quadRow->integer), quadRow->string);
        }
    }

    // Look for line
    Line *line;
    if (!linesByCode.Lookup(tokens->GetAt(0), (void *&)line))
    {
        BadRecordException *e = new BadRecordException("MapBuilder::buildStationNode()",
                                     "invalid line code - " + tokens->GetAt(0));
        delete tokens;
        throw e;
//        return 0;   // keep Microsoft's compiler happy
    }

    // Evaluate node ordinal
    int nodeOrdinal = atoi(tokens->GetAt(1));

    // Evaluate interchange and terminus flags if required
    BOOL interchange = FALSE;
    BOOL terminus = FALSE;
    CString flags = tokens->GetAt(2);
    if (flags != "()")
    {
        BOOL valid = TRUE;

        // Verify format of flag string
        if (valid = (flags.GetLength() > 2
         && flags[0] == '(' && flags[flags.GetLength() - 1] == ')'))
        {
            // Strip off surrounding brackets
            flags = flags.Mid(1);
            flags = flags.Left(flags.GetLength() - 1);

            for (const char *fptr = flags; *fptr && valid; fptr++)
            {
                switch (*fptr)
                {
                    case 'i':
                        interchange = TRUE;
                        break;

                    case 't':
                        terminus = TRUE;
                        break;

                    default:
                        valid = FALSE;
                        break;
                }
            }
        }

        if (!valid)
        {
            BadRecordException *e = new BadRecordException("MapBuilder::buildStationNode()",
                                         "invalid node flags - " + flags);
            delete tokens;
            throw e;
//            return 0;   // keep Microsoft's compiler happy
        }
    }

    // Evaluate coordinates
    CString xStr = tokens->GetAt(3);
    CString yStr = tokens->GetAt(4);
    // Verify format
    if (xStr[0] != '(' || yStr[yStr.GetLength() - 1] != ')')
    {
        BadRecordException *e = new BadRecordException("MapBuilder::buildStationNode()",
                                     "invalid coordinates - " + xStr + "," + yStr);
        delete tokens;
        throw e;
//        return 0;   // keep Microsoft's compiler happy
    }
    xStr = xStr.Mid(1);
    yStr = yStr.Left(yStr.GetLength() - 1);
    int x = atoi(xStr);
    int y = atoi(yStr);

    // Look for and evaluate a quadrant override
    int quadrant = lastStation->getDefaultQuad();
    if (tokCount == 6
     && !quadsByName.Lookup(tokens->GetAt(5), (void *&)quadrant))
    {
        BadRecordException *e = new BadRecordException("MapBuilder::buildStationNode()",
                                     "invalid quadrant " + tokens->GetAt(6));
        delete tokens;
        throw e;
//        return 0;   // keep Microsoft's compiler happy
    }
    // Quadrant could still be invalid though...
    if (quadrant == StationNode::UNKNOWN)
    {
        BadRecordException *e = new BadRecordException("MapBuilder::buildStationNode()",
                                     "no quadrant specified");
        delete tokens;
        throw e;
//        return 0;   // keep Microsoft's compiler happy
    }

    // Construct StationNode object:
    StationNode *node = new StationNode(&map
                         ,lastStation       // station
                         ,line              // line
                         ,quadrant          // quadrant
                         ,nodeOrdinal       // ordinal
                         ,interchange       // interchange
                         ,terminus          // terminus
                         ,CPoint(x, y)      // coordinates
                          );

    delete tokens;  // Finished with these now

    // Adds node to name map which we use again later as the mapping for line
    // segment fixup
    map.addThing(node);

    // Save node reference
    lastNode = node;

    return node;
}

LineSegment *MapBuilder::buildLineSegment(const CString &nodeData)
{
    // Format for LineSegment record is:
    //  <direction>,'('+['p']+')',<destination station name>+':'+<destination node ordinal>
    // Source StationNode is last one encountered
    // <direction> is used to populate the alignment member of the source station
    CStringArray *tokens = tokeniseString(nodeData, ",:");  // ':' is additional delim

    // Check for invalid number of tokens
    int tokCount = tokens->GetSize();
    if (tokCount != 4)
    {
        delete tokens;
        throw new BadRecordException("MapBuilder::buildLineSegment()",
                                     "incorrect token count - found " + CNumString(tokCount)
                                        +", expected 4 (3 + ordinal after ':')");
//        return 0;   // keep Microsoft's compiler happy
    }

    // Check for parent StationNode
    if (lastNode == 0)
    {
        delete tokens;
        throw new BadRecordException("MapBuilder::buildStationNode()",
                                     "no source node for line segment");
//        return 0;   // keep Microsoft's compiler happy
    }

    // Evaluate direction - use quadrant patterns
    int direction = StationNode::UNKNOWN;
    if (!quadsByName.Lookup(tokens->GetAt(0), (void *&)direction))
    {
        BadRecordException *e = new BadRecordException("MapBuilder::buildLineSegment()",
                                     "invalid line direction " + tokens->GetAt(0));
        delete tokens;
        throw e;
//        return 0;   // keep Microsoft's compiler happy
    }

    // Evaluate peak only flag
    BOOL peakOnly = FALSE;
    CString flags = tokens->GetAt(1);
    if (flags == "(p)")
    {
        peakOnly = TRUE;
    }
    else if (flags != "()") // Verify valid form
    {
        BadRecordException *e = new BadRecordException("MapBuilder::buildLineSegment()",
                                     "invalid line segment flags " + tokens->GetAt(1));
        delete tokens;
        throw e;
//        return 0;   // keep Microsoft's compiler happy
    }

    // Recover destination station node information (cannot resolve yet)
    CString destStation = tokens->GetAt(2);
    int destOrdinal = atoi(tokens->GetAt(3));

    // Construct LineSegment object using partial knowledge ctor:
    LineSegment *segment = new LineSegment(&map
                         ,lastNode      // from
                         ,destStation   // to name
                         ,destOrdinal   // to ordinal
                         ,peakOnly      // peak only
                         ,direction     // direction
                          );

    delete tokens;  // Finished with these now

    map.addThing(segment);

    // Populate alignment in parent Station
    Station *hostStation = lastNode->getStation();
    hostStation->setAlignBit(directionToAlignment(direction));

    return segment;
}

BOOL MapBuilder::fixupLineSegments()
{
    // Iterate through set of LineSegment instances and resolve destination
    // node information
    // Remove any line segments which cannot be fixed up
    const CMapStringToPtr *segments = &(map.getThings(mcThing::LINE_SEGMENT));

    CPtrList deadSegments;

    LineSegment *segment;
    CString key;
    StationNode *destNode = 0;
    for (POSITION lsp = segments->GetStartPosition(); lsp != NULL; )
    {
        segments->GetNextAssoc(lsp, key, (void *&)segment);

        CString destNodeName = StationNode::deriveName(segment->getToName(),
                                                       segment->getFromNode()->getLine()->getName(),
                                                       segment->getToOrdinal());
        if (destNode = (StationNode *)map.findThing(mcThing::STATION_NODE, destNodeName))
        {
            // Resolve it!
            segment->setToNode(destNode);
        }
        else
        {
            deadSegments.AddTail(segment);
        }
    }

    BOOL result = deadSegments.IsEmpty();

    // Iterate through dead segments, recording their deadness and removing them
    for (lsp = deadSegments.GetHeadPosition(); lsp != NULL; )
    {
        segment = (LineSegment *)deadSegments.GetNext(lsp);
        cout << "*** Could not resolve destination node for " << segment->getName() << '\n';
        map.removeThing(segment);
    }
    if (!result) cout << endl;

    return result;
}

void MapBuilder::writeSQL(ofstream &outFile)
{
    static strInt typeOrder[mcThing::TYPE_COUNT] =
    { { "Lines",            mcThing::LINE },
      { "Stations",         mcThing::STATION },
      { "Station Nodes",    mcThing::STATION_NODE },
      { "Line Segments",    mcThing::LINE_SEGMENT }
    };

    outFile << "-- SQL insert statements for LU map data\n\n";

    for (int i = 0; i < mcThing::TYPE_COUNT; i++)
    {
        outFile << "-- Data for " << typeOrder[i].string << "\n";

        const CMapStringToPtr *things = &(map.getThings((mcThing::type)typeOrder[i].integer));
        CString key; mcThing *thing;
        for (POSITION tp = things->GetStartPosition(); tp != NULL; )
        {
            things->GetNextAssoc(tp, key, (void *&)thing);

            CString table = thing->getSqlTable();
            CString insertData = thing->getSqlInsertData();

            outFile << "INSERT INTO " << table << " VALUES (" << insertData << ");\n";
        }
        outFile << "-- End of data for " << typeOrder[i].string << "\n\n";
    }
}

struct lineData
{
    Line *line;
    StationNode *nwMost;
    CMapStringToPtr segsByFromNode;

    lineData(Line *a_line) : line(a_line), nwMost(0) { }
};

void MapBuilder::traverseNodes(ofstream &outFile)
{
    // Method to follow the set of line segments for each line, starting at
    // the most northwesterly node.

    // Algorithm is:
    //  - get all the line segments
    //  - sort them by line and by from node name, terminating in a list
    //  - during the sorting, look for the most northwesterly from node
    //  - starting at the most northwesterly node for each line, iterate and
    //      recurse across the line segments.
    // Note: need to keep a record of nodes output (probably through a visited
    // flag), since the line segments are bi-directional.

    const CMapStringToPtr &lineSegments = map.getThings(mcThing::LINE_SEGMENT);
    CMapStringToPtr lineDataByLineName;

    CString key; LineSegment *seg;
    StationNode *from; Line *line; lineData *ld;
    CPtrList *segsFrom;
    for (POSITION lsp = lineSegments.GetStartPosition(); lsp != NULL; )
    {
        lineSegments.GetNextAssoc(lsp, key, (void *&)seg);

        from = seg->getFromNode();
        line = from->getLine();
        if (!lineDataByLineName.Lookup(line->getName(), (void *&)ld))
        {
            ld = new lineData(line);
            lineDataByLineName.SetAt(line->getName(), ld);
        }
        if (!ld->segsByFromNode.Lookup(from->getName(), (void *&)segsFrom))
        {
            segsFrom = new CPtrList;
            ld->segsByFromNode.SetAt(from->getName(), segsFrom);
        }
        segsFrom->AddTail(seg);

        // Sort out nwMost
        if (ld->nwMost == 0
         || from->getCoords().x < ld->nwMost->getCoords().x
         || (from->getCoords().x == ld->nwMost->getCoords().x
          && from->getCoords().y > ld->nwMost->getCoords().y))
        {
            ld->nwMost = from;
        }
    }

    // Right, that's that sorted. Now, iterate across the Lines and recurse
    // across the segment sets
    for (POSITION lp = lineDataByLineName.GetStartPosition(); lp != NULL; )
    {
        lineDataByLineName.GetNextAssoc(lp, key, (void *&)ld);
        outFile << "Route for " << key << " Line\n"
                << CString('-', 50) << "\n"; 
        followToNode(outFile, ld->nwMost, &(ld->segsByFromNode));
        outFile << CString('=', 80) << "\n\n";
    }
}

void MapBuilder::followToNode(ofstream &outfile,
                              StationNode *root,
                              CMapStringToPtr *segsByFromNode)
{
    // Algorithm for traversal is:
    //  - get set of segments for passed root node
    //  - iterate through set of segments, copying the ones which don't go to
    //      an already visited node into another list
    //  - print out contents of copied list
    //  - set current node as visited
    //  - if the list has only one entry, move onto next node in chain and go
    //      back to start
    //  - if the list has no entries, return
    //  - otherwise, call this function with each target node.
    CPtrList *allSegs;
    CPtrList freshSegs;
    LineSegment *seg;
    StationNode *targetNode;
    for (;;)
    {
        freshSegs.RemoveAll();
        if (!segsByFromNode->Lookup(root->getName(), (void *&)allSegs))
        {
            outfile << "*** Node " << root->getName() << " has no segments\n";
        }
        for (POSITION p = allSegs->GetHeadPosition(); p != NULL; )
        {
            seg = (LineSegment *)(allSegs->GetNext(p));
            targetNode = seg->getToNode();
            if (!targetNode->visited)
            {
                freshSegs.AddTail(seg);
            }
        }

        root->visited = TRUE;

        // Test for termination condition
        if (freshSegs.GetCount() == 0)
            return;

        // Output routes to take
        for (p = freshSegs.GetHeadPosition(); p != NULL; )
        {
            seg = (LineSegment *)freshSegs.GetNext(p);
            targetNode = seg->getToNode();
            outfile << "    "
                    << root->getName() << "[" << root->getCoords().x << "," << root->getCoords().y << "] => "
                    << targetNode->getName() << "[" << targetNode->getCoords().x << "," << targetNode->getCoords().y << "]\n"
                    << "\tdx = " << targetNode->getCoords().x - root->getCoords().x
                    << "; dy = " << targetNode->getCoords().y - root->getCoords().y << "\n";
        }

        if (freshSegs.GetCount() == 1)
        {
            root = targetNode;
        }
        else
        {
            for (p = freshSegs.GetHeadPosition(); p != NULL; )
            {
                seg = (LineSegment *)freshSegs.GetNext(p);
                targetNode = seg->getToNode();
                followToNode(outfile, targetNode, segsByFromNode);
            }
        }
    }
}