#include "misc.h"
#include "data.h"
#include <map>
#include <unordered_map>
#include <string>
#include <queue>
#include <vector>
#include <iostream>
#include <algorithm>
#include <climits>

using namespace std;

class Order {
private:
    int _pid;
    int _quantity;
    int _expected_days;
    Region _region;
    double _date;
    
public:
    Order (int pid_, int quantity_, int expected_days_, Region region_, double date_) :
    _pid (pid_),
    _quantity (quantity_),
    _expected_days (expected_days_),
    _region (region_),
    _date (date_) {};
    
    Order (const Order &other_) {
        _pid = other_._pid;
        _quantity = other_._quantity;
        _expected_days = other_._expected_days;
        _region = other_._region;
        _date = other_._date;
    }
    
    const int getPid () const { return _pid; }
    const int getQuantity () const { return _quantity; }
    const Region getDestination () const { return _region; }
};

class ProductInventory {
private:
    int _pid;
    int _quantity;
    Region _region;
    
public:
    ProductInventory (int pid_, int quantity_, Region region_) :
    _pid (pid_),
    _quantity (quantity_),
    _region (region_) {};
    
    ProductInventory (const ProductInventory &other_) {
        _pid = other_._pid;
        _quantity = other_._quantity;
        _region = other_._region;
    }
    
    const int getPid () const { return _pid; }
    const int getQuantity () const { return _quantity; }
    void reduceQuantity (int val) { _quantity -= val; }
    const Region getRegion () const { return _region; }
};

class ShippingCost {
private:
    Region _ship_from;
    Region _ship_to;
    Method _method;
    int _cost_per_item;
    int _days;
    
public:
    ShippingCost (Region ship_from_, Region ship_to_, Method method_, int cost_per_item_, int days_) :
    _ship_from (ship_from_),
    _ship_to (ship_to_),
    _method (method_),
    _cost_per_item (cost_per_item_),
    _days (days_) {};
    
    ShippingCost (const ShippingCost &_other) {
        _ship_from = _other._ship_from;
        _ship_to = _other._ship_to;
        _method = _other._method;
        _cost_per_item = _other._cost_per_item;
        _days = _other._days;
    }
    
    const Region getShipFrom () const { return _ship_from; }
    const Region getShipTo () const { return _ship_to; }
    const int getDays () const { return _days; }
    const int getCost () const { return _cost_per_item; }
};


//data----------------------------------------------------------------
const static vector<Order> orders {
    Order (1, 6, 4, center, 0.3),
    Order (1, 3, 2, west, 0.0),
    Order (1, 4, 0, east, 0.2),
    Order (3, 100, 0, center, 0.1),
    Order (2, 6, 4, center, 0.3)
};

static vector<ProductInventory> productInventoryList {
    ProductInventory (1, 7, north),
    ProductInventory (3, 70, north),
    ProductInventory (3, 20, north),
    ProductInventory (3, 40, east),
    ProductInventory (3, 30, north),
};

const static vector<ShippingCost> shippingCostList {
    ShippingCost (north, west, express, 3, 10),
    ShippingCost (north, west, ground, 1, 15),
    ShippingCost (north, east, ground, 2, 20),
    ShippingCost (north, center, express, 2, 5)
};

//---------------------------------------------------------------

class ProductShippingCost{
public:
    ProductInventory productInventory;
    vector<ShippingCost> shippingCostList;
    
    ProductShippingCost(ProductInventory productInventory, vector<ShippingCost> shippingCostList): productInventory(productInventory), shippingCostList(shippingCostList){}
};


//milestone 1
vector<ProductShippingCost> Solution1(int pid, Region toRegin) {
    
    vector<ProductShippingCost> result;
    
    for(ProductInventory& currentInventory : productInventoryList) {
        
        //if currentInventory contains the product we want
        if (pid == currentInventory.getPid()) {
            
            ProductShippingCost temp(currentInventory,{});
            
            for (ShippingCost currentShippingCost : shippingCostList) {
                if (currentShippingCost.getShipFrom() == currentInventory.getRegion() &&
                    currentShippingCost.getShipTo() == toRegin) {
                    
                    temp.shippingCostList.push_back(currentShippingCost);
                }
            }//for shippingCostList
            
            //if there exist a way that the product can be shipped to the destination
            if(!temp.shippingCostList.empty()) result.push_back(temp);
        }
    }//for productInventoryList
    
    return result;
    
}



struct OrderQuantityComparator {
    bool operator () (const Order &order1, const Order &order2) {
        return order1.getQuantity() < order2.getQuantity();
    }
} orderQuantityComparator;

struct ShippingCostTimeComparator {
    bool operator () (ShippingCost shippingCost1, ShippingCost shippingCost2) {
        return shippingCost1.getDays() < shippingCost2.getDays();
    }
}shippingCostTimeComparator;


//void Solution2() {
//    vector<Order> orderList = orders;
//    sort(orderList.begin(),orderList.end(),orderQuantityComparator);
//    
//    for(Order& order : orderList) {
//        
//        vector<ProductShippingCost> orderShippingCostList = Solution1(order.getPid(), order.getDestination());
//        //orderShippingCostList -> { productInventory, vector<shippingCost> }
//        
//        unordered_map<ShippingCost,ProductInventory> productInventoryToMinTime;
//        
//        
//        
//        int inventoryQuantitySum = 0;
//        
//        //for one specific inventory
//        for(ProductShippingCost& orderShippingCost : orderShippingCostList) {
//            inventoryQuantitySum += orderShippingCost.productInventory.getQuantity();
//            
//            int minShppingTime = 99999;
//            ShippingCost minTimeShipping = orderShippingCost.shippingCostList[0];
//
//            //get current inventory's shippingCost with least shipping time
//            for (ShippingCost& shippingCost : orderShippingCost.shippingCostList) {
//                if (shippingCost.getDays() < minShppingTime) {
//                    minShppingTime = shippingCost.getDays();
//                    minTimeShipping = shippingCost;
//                }
//            }
//            //productInventoryToMinTime[minTimeShipping] = orderShippingCost.productInventory;
//            
//            //Now we have productInventoryToMinTime<ProductInventory,ShippingCost> ordered by shippingTime
//        }
//        
////        if(inventoryQuantitySum < order.getQuantity()) continue;
////        
////        int unfinishedQuantity = order.getQuantity();
////        while(unfinishedQuantity > 0)
////        {
////            ProductInventory currentInventory = productInventoryToMinTime.begin()->first;
////            currentInventory.reduceQuantity(min(currentInventory.getQuantity(), unfinishedQuantity));
////            unfinishedQuantity -= min(currentInventory.getQuantity(), unfinishedQuantity);
////            cout << "from Inventory " << currentInventory.getRegion() << " ship " << min(currentInventory.getQuantity(), unfinishedQuantity) << endl;
////            if(currentInventory.getQuantity() == 0) productInventoryToMinTime.erase(currentInventory);
////        }
//    
//    }
//    
//
//}
//

typedef pair<ProductInventory *, int> InventoryMinTimePair;

struct InventoryMinTimePairComparator {
    bool operator()(const InventoryMinTimePair & InventoryMinTimePair1,const InventoryMinTimePair & InventoryMinTimePair2) {
        return InventoryMinTimePair1.second < InventoryMinTimePair2.second;
    
    }

};

void Solution22(vector<Order> orderList) {
    sort(orderList.begin(),orderList.end(),orderQuantityComparator);
    for(Order& order : orderList) {
        cout << "Order " << order.getPid() << endl;
        

//Order shipping plan selection part:
        vector<ProductShippingCost> productShippingCostList = Solution1(order.getPid(), order.getDestination());
        priority_queue<InventoryMinTimePair,vector<InventoryMinTimePair>, InventoryMinTimePairComparator> productInventoryPQ;
        
        //iterator in this loop has form { productInventory, vector<shippingCost> }
        for(ProductShippingCost & productShippingCost : productShippingCostList) {
        
            //there is no way the product can be shipped
            if(productShippingCost.shippingCostList.empty()) continue;
            
            int inventoryQuantitySum = 0;
            
            //GOAL: select the least time shippingCost from vector<shippingCost>
            //      and save it to a pq of pair <procuetInventory, shippingCostMinTime>
            int minTime = productShippingCost.shippingCostList[0].getDays();
            InventoryMinTimePair productInventoryWithMinTimeShipping;
            
            //O(N), N = size of shippingCostList, Linear search
            for(ShippingCost &shippingCost : productShippingCost.shippingCostList) {
                minTime = min(minTime,shippingCost.getDays());
            } //for shippingCost
            
            productInventoryWithMinTimeShipping.first = &productShippingCost.productInventory;
            productInventoryWithMinTimeShipping.second = minTime;
            
            //O(logN), N = #inventories contains current product, PQ push in C++
            //Now we get a pq contains all the inventorys sorted by the shipping time
            productInventoryPQ.push(productInventoryWithMinTimeShipping);
            
            inventoryQuantitySum += productShippingCost.productInventory.getQuantity();
            
            //Order can NOT be fulfilled
            if(inventoryQuantitySum < order.getQuantity()) continue;
            
            //Inventory shipping part:
            int unShippedCount = order.getQuantity();
            while(unShippedCount > 0 ) {
                //inventory can at most ship all its products
                int shipQuaitity = min(productInventoryPQ.top().first->getQuantity(),unShippedCount);
                
                productInventoryPQ.top().first->reduceQuantity(shipQuaitity);//O(1)
                
                cout << "Ship " << shipQuaitity << " from inventory " << productInventoryPQ.top().first->getRegion() << endl;
                
                productInventoryPQ.pop();//O(logN), N = size of PQ
                
                unShippedCount -= shipQuaitity;
            
            }
            
            
        } //for productShippingCost
        
        
    }

}

struct InventoryMinCostPairComparator {
    bool operator()(const InventoryMinTimePair & InventoryMinCostPair1,const InventoryMinTimePair & InventoryMinCostPair2) {
        return InventoryMinCostPair1.second < InventoryMinCostPair2.second;
        
    }
    
};

void Solution3(vector<Order> orderList) {
    sort(orderList.begin(),orderList.end(),orderQuantityComparator);
    for(Order& order : orderList) {
        cout << "Order " << order.getPid() << endl;
        
        
        //Order shipping plan selection part:
        vector<ProductShippingCost> productShippingCostList = Solution1(order.getPid(), order.getDestination());
        priority_queue<InventoryMinTimePair,vector<InventoryMinTimePair>, InventoryMinTimePairComparator> productInventoryPQ;
        
        //iterator in this loop has form { productInventory, vector<shippingCost> }
        for(ProductShippingCost & productShippingCost : productShippingCostList) {
            
            //there is no way the product can be shipped
            if(productShippingCost.shippingCostList.empty()) continue;
            
            int inventoryQuantitySum = 0;
            
            //GOAL: select the least time shippingCost from vector<shippingCost>
            //      and save it to a pq of pair <procuetInventory, shippingCostMinTime>
            int minCost = productShippingCost.shippingCostList[0].getCost();
            InventoryMinTimePair productInventoryWithMinTimeShipping;
            
            //O(N), N = size of shippingCostList, Linear search
            for(ShippingCost &shippingCost : productShippingCost.shippingCostList) {
                minCost = min(minCost,shippingCost.getDays());
            } //for shippingCost
            
            productInventoryWithMinTimeShipping.first = &productShippingCost.productInventory;
            productInventoryWithMinTimeShipping.second = minCost;
            
            //O(logN), N = #inventories contains current product, PQ push in C++
            //Now we get a pq contains all the inventorys sorted by the shipping time
            productInventoryPQ.push(productInventoryWithMinTimeShipping);
            
            inventoryQuantitySum += productShippingCost.productInventory.getQuantity();
            
            //Order can NOT be fulfilled
            if(inventoryQuantitySum < order.getQuantity()) continue;
            
            //Inventory shipping part:
            int unShippedCount = order.getQuantity();
            while(unShippedCount > 0 ) {
                //inventory can at most ship all its products
                int shipQuaitity = min(productInventoryPQ.top().first->getQuantity(),unShippedCount);
                
                productInventoryPQ.top().first->reduceQuantity(shipQuaitity);//O(1)
                
                cout << "Ship " << shipQuaitity << " from inventory " << productInventoryPQ.top().first->getRegion() << endl;
                
                productInventoryPQ.pop();//O(logN), N = size of PQ
                
                unShippedCount -= shipQuaitity;
                
            }
            
            
        } //for productShippingCost
        
        
    }
    
}


struct testComp {
    bool operator()(const string &a ,const string &b) const {
        return a < b;
    }
    
}comp;

int main(int argc, const char * argv[]) {
    vector<ProductShippingCost> result = Solution1(3, west);
    
    //cout << result.size() << endl;
    
    //Solution2(orderList);
    
//    map<string,int,testComp> test;
//    test["hjq"] = 3;
//    test["12"] = 4;
//    test["kkk"] = 2;
//    test["asdf"] = 1;
//    test["34234"] = 5;
//    test["asdfg"] = 9;
    
//    for(auto it : test) {
//        cout << it.second << endl;
//    }
    
    Solution22(orders);
    
    return 0;
}