#include "mapTools.h"

// populateSegments populates the segmentsInIntersections global variable. The
// indices in this vector represent the interesection IDs (IntersectionIdx)
// for convenince. The nested vectors represent all of the
// street segments connected to the interesection by their
// street segment ID (streetSegmentIdx)
void populateSegments() {
    for(int intersection_id=0; intersection_id < getNumIntersections(); ++intersection_id){

        std::vector<StreetSegmentIdx> segmentsOfAnIntersection;
        
        //loop through all street segments of an intersection
        for(int segment_id=0; segment_id< getNumIntersectionStreetSegment(intersection_id); ++segment_id){
            
            //adds street segment to segmentsOfAnIntersection
             segmentsOfAnIntersection.push_back(getIntersectionStreetSegment(segment_id, intersection_id)); 
        }
        segmentsInIntersections.push_back(segmentsOfAnIntersection);
    }
}

// populateAllSegments populates a vector to store all street segments of a street
// this is for convience to compute the total length of streets
void populateAllSegments() {
    
    // loop through all intersections and insert street segment ids to allSegments
    for(int intersection_id=0; intersection_id < getNumIntersections(); ++intersection_id){
        for(int segment_id=0; segment_id < getNumIntersectionStreetSegment(intersection_id); ++segment_id){
            StreetSegmentIdx seg = getIntersectionStreetSegment(segment_id, intersection_id);
            allSegments.insert(seg); //adds street segment to allSegments
        }
    }

}
 
// populateStreetIntersections populates the streetIntersections global variable. 
// The streetIntersections vector is mapped so that the index represents the street ID (StreetIdx), and the 
// value is an unordered set of the intersections. Note: the unordered set was chosen
// so that insertion produced no duplicates 
void populateStreetIntersections() {
    streetIntersections.resize(getNumStreets());
    
    // loops through all streets and add from and to intersection id to street intersection vector
    for(int streetSegID = 0; streetSegID < getNumStreetSegments(); streetSegID++){
        StreetSegmentInfo streetSeg = getStreetSegmentInfo(streetSegID);
        streetIntersections[streetSeg.streetID].insert(streetSeg.from);
        streetIntersections[streetSeg.streetID].insert(streetSeg.to);
    }
}

// populateStreetNames populates the streetNames global variable. 
// The streetNames vector is mapped so that it is in pairs of (StreetIdx(Street ID), streetName).
void populateStreetNames() {
    streetNames.resize(getNumStreets());
    
    // loop through streets and add street names to vector
    for (int streetID = 0; streetID < getNumStreets(); streetID ++){
        std::string currStreet = getStreetName(streetID);
        currStreet = parseName(currStreet);
        streetNames[streetID] = std::make_pair(streetID, currStreet);
    }
}

// populateOSMContent populates the OSMContent global variable. The data is stored in key-value 
// pairs of (OSMID, LatLon) and fetched from the OSM API
void populateOSMContent() {
    const OSMNode* curr;
    
    // loop through OSM nodes and insert into ordered map
    for(int i=0; i<getNumberOfNodes(); i++){
        curr = getNodeByIndex(i); 
        OSMContent.insert({curr->id(), getNodeCoords(curr)});
    }
}

// find an index where streetName contains a given prefix. (Binary Search)
// more matches of the prefix can be contained in indicies left OR right to the found index.
int findPartialLocations(std::string street_prefix){
    // set left and right pointers
    int left = 0 ;
    int right = getNumStreets() - 1;
    
    //to compare that the prefix matches -> type cast strings into cstrings. 
    const char *str = street_prefix.c_str();
    while (left <= right){
        int mid = left + (right - left) / 2; 
        int res = -2;   //placeholder value 

        //check if the middle index of current search subtree contains the prefix. 
        const char *str2 = streetNames[mid].second.c_str();
        if (strncmp (str, str2, street_prefix.size()) == 0)
            res = 0;

        // Check if street_prefix is present at mid
        if (res == 0)
            return mid;

        // If street_prefix greater, ignore left half
        if (street_prefix > streetNames[mid].second)
            left = mid + 1;

        // If street_prefix is smaller, ignore right half
        else
            right = mid - 1;
    }
    //return -1 if there are no matches of the prefix in the entire tree. 
    return -1;
}

// asciiToLower is called with a char argument and returns the corresponding lowercase
// equivalent char of the argument
char asciiToLower(char c) {
    if (c <= 'Z' && c >= 'A')
        return c - ('A' - 'a');
   return c;
}

//make sure std::sort method sorts by Street Name (alphabetically), not by Street_ID
//when sorting through streetNames vector
bool sortbysec(const std::pair<StreetIdx, std::string> &a, const std::pair<StreetIdx, std::string> &b){
    return (a.second < b.second);
}

//make sure std::sort method sorts Features by its size, not by streetid
bool sortfeaturebysec(const std::pair<int,double> &a,const std::pair<int,double> &b){
    return (a.second > b.second);
}

// removeSpaces takes a constant string argument to be parsed and returns
// the argument in a form without whitespace
std::string removeSpaces(const std::string& s) {
    std::string temp = s;
    temp.erase(std::remove(temp.begin(), temp.end(), ' '), temp.end());
    return temp;
}

// parseName takes a string argument and calls both asciiToLower and removeSpaces ,
// then returns a string wihthout capital letters or whitespace
std::string parseName(std::string name){
    std::transform(name.begin(), name.end(), name.begin(), asciiToLower);
    std::string parsedName = removeSpaces(name); 
    return parsedName;
}

// getHour gets the current hour in local time
int getHour() {
    time_t now;
    struct tm *time_now;

    now = time(NULL);
    time_now = localtime(&now);
    return time_now->tm_hour;
}

// loadSOMRoads loops through all OSM ways to find the roads in the city
// there are 3 categories, highways, main roads, and residential roads
// they are differentiated by tags and are all stored into their respective
// global vectors
void loadOSMRoads(){
    for (unsigned i = 0; i < getNumberOfWays(); i++) {
        const OSMWay *currWay = getWayByIndex(i);

        // Check the tag of the currWay
        for (unsigned j = 0; j < getTagCount(currWay); j++) {
            std::pair<std::string, std::string> tagPair = getTagPair(currWay, j);

            // Push relations with the route=highway tag
            if (tagPair.first == "highway") {
                if (tagPair.second == "motorway" || tagPair.second == "motorway_junction" || tagPair.second == "trunk" || tagPair.second == "motorway_link" || tagPair.second == "trunk_link") {
                    osm_highways.push_back(currWay);
                    break;
                }
                if (tagPair.second == "primary" || tagPair.second == "secondary" || tagPair.second == "tertiary" /*|| tagPair.second == "primary_link" || tagPair.second = "secondary_link"*/) {
                    osm_main_roads.push_back(currWay);
                    break;
                }
                if (tagPair.second == "residential" || tagPair.second == "unclassified" || tagPair.second == "living_street" || tagPair.second == "service"){
                    osm_residential.push_back(currWay);
                    break;
                }
            }
            
        }
    }
}

// loadOSMSubwayRoutes loops through all OSM Relations to get subway routes
// stores subway station locations in a vector of OSMRelations
void loadOSMSubwayRoutes() {
    // Loop through all OSM relations
    for (unsigned i = 0; i < getNumberOfRelations(); i++) {
        const OSMRelation *currRel = getRelationByIndex(i);

        // Check the tag of the currRel
        for (unsigned l = 0; l < getTagCount(currRel); l++) {
            std::pair<std::string, std::string> tagPair = getTagPair(currRel, l);

            // Push relations with the route=subway tag
            if (tagPair.first == "route" && tagPair.second == "subway") {
                std::vector<TypedOSMID> route_members = getRelationMembers(currRel);
                   
                // iterate through subway route nodes and add coords to subwayStationsxy
                for (unsigned j = 0; j < route_members.size(); j ++) {
                    if (route_members[j].type() == TypedOSMID::Node) {
                        
                        // Node lookup by OSMID
                        for (unsigned k= 0; k < getNumberOfNodes(); k++) {

                            const OSMNode *currNode = nullptr;
                            currNode = getNodeByIndex(k);
                            ezgl::point2d stationLatLon;
                            LatLon stationCoords = getNodeCoords(currNode);

                            // if the current id is equal to the current route member
                            if (currNode->id() == route_members[j]){
                                stationLatLon = latlon_to_point2d(stationCoords);
                                subwayStationsxy.push_back(stationLatLon);
                                break;
                            }
                        }
                    }           
                }
                break;
            }
        }
    }
}


// setLineWidths
void setLineWidths(int & road, int & mainRoad, int & highwayRoad, std::vector<int> & roadColor, std::vector<int> & mainRoadColor, std::vector<int> & highwayRoadColor, int curr, bool light_mode) {
    
    // choose line widths based on zoom level
    if(curr < 650) {
        road = 11;
        mainRoad = 14;
        highwayRoad = 14;
    } else if(curr < 1000) {
        road = 7;
        mainRoad = 11;
        highwayRoad = 11;
    } else if(curr < 1800) {
        road = 4;
        mainRoad = 7;
        highwayRoad = 9;
    } else if(curr < 4000) {
        road = 2;
        mainRoad = 4;
        highwayRoad = 7;

    } else if(curr < 8000) {
        road = 1;
        mainRoad = 3;
        highwayRoad = 5;
    } else if(curr < 50000) {
        road = 0;
        mainRoad = 2;
        highwayRoad = 2; 
    } else {
        road = 0;
        mainRoad = 1;
        highwayRoad = 2;
    } 

    // choose colours based on light mode and zoom level
    if(!light_mode) {
        if(curr < 650) {
            roadColor[0] = 47;
            roadColor[1] = 52;
            roadColor[2] = 63;

            mainRoadColor[0] = 47;
            mainRoadColor[1] = 52;
            mainRoadColor[2] = 63;

            highwayRoadColor[0] = 47;
            highwayRoadColor[1] = 52;
            highwayRoadColor[2] = 63;
        } else if(curr < 1000) {
            roadColor[0] = 80;
            roadColor[1] = 88;
            roadColor[2] = 103;
            
            mainRoadColor[0] = 100;
            mainRoadColor[1] = 112;
            mainRoadColor[2] = 130;

            highwayRoadColor[0] = 127;
            highwayRoadColor[1] = 142;
            highwayRoadColor[2] = 164;
        } else if(curr < 5500) {
            roadColor[0] = 101;
            roadColor[1] = 115;
            roadColor[2] = 135;
            
            mainRoadColor[0] = 129;
            mainRoadColor[1] = 139;
            mainRoadColor[2] = 160;

            highwayRoadColor[0] = 90;
            highwayRoadColor[1] = 100;
            highwayRoadColor[2] = 121;
        } else if(curr < 15000) {
            roadColor[0] = 66;
            roadColor[1] = 74;
            roadColor[2] = 88;
            
            mainRoadColor[0] = 129;
            mainRoadColor[1] = 139;
            mainRoadColor[2] = 160;

            highwayRoadColor[0] = 90;
            highwayRoadColor[1] = 100;
            highwayRoadColor[2] = 121;

        } else if(curr < 25000) {
            roadColor[0] = 105;
            roadColor[1] = 119;
            roadColor[2] = 139;
            
            mainRoadColor[0] = 87;
            mainRoadColor[1] = 101;
            mainRoadColor[2] = 120;

            highwayRoadColor[0] = 135;
            highwayRoadColor[1] = 152;
            highwayRoadColor[2] = 181;
        } else {
            roadColor[0] = 66;
            roadColor[1] = 74;
            roadColor[2] = 88;
            
            mainRoadColor[0] = 66;
            mainRoadColor[1] = 74;
            mainRoadColor[2] = 88;

            highwayRoadColor[0] = 135;
            highwayRoadColor[1] = 152;
            highwayRoadColor[2] = 181;
        } 
    } else {
        if(curr < 650) {
            roadColor[0] = 255;
            roadColor[1] = 255;
            roadColor[2] = 255;

            mainRoadColor[0] = 221;
            mainRoadColor[1] = 221;
            mainRoadColor[2] = 223;

            highwayRoadColor[0] = 223;
            highwayRoadColor[1] = 198;
            highwayRoadColor[2] = 74;     
        } else if(curr < 2000) {
            roadColor[0] = 255;
            roadColor[1] = 255;
            roadColor[2] = 255;

            mainRoadColor[0] = 221;
            mainRoadColor[1] = 221;
            mainRoadColor[2] = 223;

            highwayRoadColor[0] = 223;
            highwayRoadColor[1] = 198;
            highwayRoadColor[2] = 74;     
        } else if(curr < 4000) {
            roadColor[0] = 240;
            roadColor[1] = 240;
            roadColor[2] = 240;

            mainRoadColor[0] = 221;
            mainRoadColor[1] = 221;
            mainRoadColor[2] = 223;

            highwayRoadColor[0] = 223;
            highwayRoadColor[1] = 198;
            highwayRoadColor[2] = 74;     
        } else if(curr < 15000) {
            roadColor[0] = 240;
            roadColor[1] = 240;
            roadColor[2] = 240;

            mainRoadColor[0] = 214;
            mainRoadColor[1] = 204;
            mainRoadColor[2] = 194;

            highwayRoadColor[0] = 223;
            highwayRoadColor[1] = 198;
            highwayRoadColor[2] = 74;     

        } else if(curr < 25000) {
            roadColor[0] = 255;
            roadColor[1] = 255;
            roadColor[2] = 255;

            mainRoadColor[0] = 214;
            mainRoadColor[1] = 204;
            mainRoadColor[2] = 194;

            highwayRoadColor[0] = 223;
            highwayRoadColor[1] = 198;
            highwayRoadColor[2] = 74;     
        } else {
            roadColor[0] = 255;
            roadColor[1] = 255;
            roadColor[2] = 255;

            mainRoadColor[0] = 214;
            mainRoadColor[1] = 204;
            mainRoadColor[2] = 194;

            highwayRoadColor[0] = 223;
            highwayRoadColor[1] = 198;
            highwayRoadColor[2] = 74;     
        }  
    } 
}

// x_from_lon changes lon to x coord
float x_from_lon(float lon) {
    float x = kDegreeToRadian * kEarthRadiusInMeters * lon * cos(kDegreeToRadian * avgLat);
    return x;
}

// y_from_lat changes lat to y coord
float y_from_lat(float lat) {
    float y = kDegreeToRadian * kEarthRadiusInMeters * lat;
    return y;
}

// latlon_to_point2d converts latlon to xy
ezgl::point2d latlon_to_point2d(LatLon point) {
    float x = x_from_lon(point.longitude());
    float y = y_from_lat(point.latitude());

    return ezgl::point2d(x, y);
}

// point2d_to_latlon converts xy to latlon
LatLon point2d_to_latlon(ezgl::point2d a_point2d){
    float lon = a_point2d.x / kDegreeToRadian / kEarthRadiusInMeters / cos(kDegreeToRadian * avgLat);
    float lat = a_point2d.y / kDegreeToRadian / kEarthRadiusInMeters; 
    
    return LatLon(lat,lon); 
}

// intersection_to_point2d converts an intersection into type point2d
void intersection_to_point2d() {
    intersectionPoint2d.resize(getNumIntersections());
    
    //loop through all intersections, converting LatLon types to point2d types
    for (int i = 0; i < getNumIntersections(); i ++) {
        ezgl::point2d currPoint = latlon_to_point2d(getIntersectionPosition(i));
        intersectionPoint2d[i]=(currPoint);
    }
}

// avgLatFinder finds the average lat, max/min lat and lons for bounds
void avgLatFinder(){
    max_lat = getIntersectionPosition(0).latitude();
    min_lat = max_lat;
    max_lon = getIntersectionPosition(0).longitude();
    min_lon = max_lon;
    intersections.resize(getNumIntersections());

    //determine the max and min values of the map by iterating through each intersection position
    //and comparing it to current maximum value
    for (int id = 1; id < getNumIntersections(); id ++) {
        intersections[id].position = getIntersectionPosition(id);
        intersections[id].name = getIntersectionName(id);

        max_lat = std::max(max_lat, intersections[id].position.latitude());
        min_lat = std::min(min_lat, intersections[id].position.latitude());
        max_lon = std::max(max_lon, intersections[id].position.longitude());
        min_lon = std::min(min_lon, intersections[id].position.longitude());
    }

    avgLat = (max_lat + min_lat) /2;
}

//change the features from latlon to xy 
void convertFeaturesLatLon(){

   // featuresInPoint2d.resize(getNumFeatures());

    for (int i  = 0; i < getNumFeatures(); i++){
        std::vector<ezgl::point2d> currFeature; 
        for(int j = 0; j < getNumFeaturePoints(i); j++){
            LatLon currPoint = getFeaturePoint(j,i);
            ezgl::point2d currInXy = latlon_to_point2d(currPoint);
            currFeature.push_back(currInXy);  
          //  std::cout << j << " " << getNumFeaturePoints(i)   << " " <<  i << " " <<  getNumFeatures()<<"\n";       
        }
       featuresInPoint2d.push_back(currFeature);
    }
}

//empty all global variables, before loading in another region
void clearMemory() {

    //for nested vectors and unordered maps, loop through each element as well
    for(auto it = segmentsInIntersections.begin(); it != segmentsInIntersections.end(); it++) {
        (*it).clear();
    }
    segmentsInIntersections.clear();
    

    for(auto it = streetIntersections.begin(); it != streetIntersections.end(); it++) {
        (*it).clear();
    }
    streetIntersections.clear();

    streetNames.clear();

    for(auto it = featuresInPoint2d.begin(); it != featuresInPoint2d.end(); it++) {
        (*it).clear();
    }
    featuresInPoint2d.clear();

    nodes.clear();
    
    segPath.clear();

    streetLengths.clear();

    timeTravel.clear();
    
    OSMContent.clear();

    featureMin.clear();

    featureMax.clear();

    osm_highways.clear();

    osm_main_roads.clear();

    osm_residential.clear();

    osm_subway_lines.clear();

    intersectionPoint2d.clear();

    subwayStationsxy.clear();

    all_stations.clear();

    intersections.clear();

    sortedFeaturesArea.clear(); 
}


// recursive function to populate path vector
void populatePath(std::vector<StreetSegmentIdx> & path, IntersectionIdx head, IntersectionIdx tail) {

    // base case for when starting node is reached
    if(head == tail) {
        return;
    }    

    // gets the next segment ID from the previous segment
    StreetSegmentIdx segID = nodes[head].reachingEdge;
    StreetSegmentInfo segInfo = getStreetSegmentInfo(segID);
    StreetSegmentIdx nextID = (segInfo.to == head) ? segInfo.from : segInfo.to;


    // recursive call with next node
    populatePath(path, nextID, tail);
    // std::cout << "Reaching Edge: " << nodes[head].reachingEdge << std::endl;
    // std::cout << "to: " << segInfo.to << std::endl;
    // std::cout << "from: " << segInfo.from << std::endl;

    // add segment ID to path global variable
    path.push_back(segID);
    return;
}


// sets node members as UNVISITED
void clearNodes() {
    // loops over every intersection
    for(int i = 0; i < getNumIntersections(); i++) {
        nodes[i].bestTime = UNVISITED;
        nodes[i].bestTime = UNVISITED;

    }
}

// finds whether to turn left right or go straight (-1, 1, 0) respectively
int findLeftorRight(StreetSegmentInfo curr, StreetSegmentInfo next) {
    // get the position of the intersections, want to determine if c is on the left
    // or right of vector ab
    LatLon a, b, c;
    if (curr.to == next.from) {
        a = getIntersectionPosition(curr.from);
        b = getIntersectionPosition(curr.to);
        c = getIntersectionPosition(next.to);
    }
    else if (curr.from == next.from) {
        a = getIntersectionPosition(curr.to);
        b = getIntersectionPosition(curr.from);
        c = getIntersectionPosition(next.to);
    }
    else if (curr.to == next.to) {
        a = getIntersectionPosition(curr.from);
        b = getIntersectionPosition(curr.to);
        c = getIntersectionPosition(next.from);
    }
    else if (curr.from == next.to) {
        a = getIntersectionPosition(curr.to);
        b = getIntersectionPosition(curr.from);
        c = getIntersectionPosition(next.from);
    }

    // convert coordinates from latlon to xy
    float ax = x_from_lon(a.longitude());
    float ay = y_from_lat(a.latitude());
    float bx = x_from_lon(b.longitude());
    float by = y_from_lat(b.latitude());
    float cx = x_from_lon(c.longitude());
    float cy = y_from_lat(c.latitude());

    // calculate cross product of vector ab and point c wrt a
    double k = ((bx-ax)*(cy-ay) - (cx-ax)*(by-ay));

    // initialize return value
    int val = 0;

    // k =0 meand straight, k >0 means right, k <0 means left
    if (k == 0) 
        val = 0;
    if (k > 0)
        val = -1;
    if (k < 0)
        val = 1;

    return val;
}