#ifndef NETWORK
#define NETWORK


#include <map>
#include <list>
#include <queue>
#include <stack>
#include <algorithm>
#include <sstream>

using namespace std;


template<class vertex, class Compare = less<vertex> >
class network
{
        struct vertex_weight_pair
        {
            vertex to;
            double weight;


            // Postcondition: this vertex_weight_pair has been initialized
            //                from x and y.
            vertex_weight_pair (const vertex& x, const double& y)
            {
                to = x;
                weight = y;
            } // two-parameter constructor



            // Postcondition: true has been returned if this
            //                vertex_weight_pair is less than x.
            //                Otherwise, false has been returned.
            bool operator> (const vertex_weight_pair& p) const
            {
                return weight > p.weight;
            } // operator>


        }; // class vertex_weight_pair


        typedef typename std::list< vertex_weight_pair > vertex_list_class;
        typedef typename vertex_list_class::iterator vertex_list_iterator;
        typedef typename std::map<vertex, vertex_list_class, Compare> map_class;
        typedef typename map_class::iterator map_iterator;


    protected:


        map_class adjacency_map;


    public:

    string string_me(double num)
    {
        ostringstream stream;
        stream << num << flush;
        return(stream.str()); //returns the string form of the stringstream object
    }
        
    void do_gay_stuff(network<string> cities, string start, string finish)
    {
     
      stack<vertex>* vertex_stack;
      stack<vertex> success_stack;
      list<string> neighbor_list;
      vertex_list_iterator list_itr;
      vertex v_temp1, v_temp2, finish_v;
      double temp_weight;
      
      //find the vertex to start with and push it to success_stack
      map_iterator itr = adjacency_map.find(start);
      
      
      v_temp1 = (*itr).first;  
      success_stack.push(v_temp1);
      //this vertex should not be popped as it is our starting point

      //find vertex of our ending point 
      map_iterator vfin = adjacency_map.find(finish);
      finish_v = (*vfin).first;
     
      //check to see if any of the neighbors are the finish vectors
      for (list_itr = ((*itr).second).begin(); list_itr != ((*itr).second).end(); list_itr++)
        if ((*list_itr).to == finish_v)
          cout << "Solution is single edge path from start to finish" << endl;

      // read list of neighbors into neighbor_list
//      neighbor_list =  cities.get_neighbor_list(v_temp1);
      
      string nodes[100][4];
      int node_counter = 0;
      network<string>::iterator n_itr;
      list< string >::iterator list_itr2; 
     
     // for the sake of undertanding - - read every vretex pair into a 2D matrix
     // [0] = from, [1] = to, [2] = weight, [3] = checked this node? 
      for (n_itr = cities.begin(); n_itr != cities.end(); n_itr++)
      {
        v_temp1 = (*n_itr).first;
        list<string> my_list = cities.get_neighbor_list (v_temp1);
        for (list_itr2 = my_list.begin(); list_itr2 != my_list.end(); list_itr2++)
        {
          nodes[node_counter][0] = v_temp1;
          nodes[node_counter][1] = *list_itr2;
          temp_weight = cities.get_edge_weight(v_temp1, *list_itr2);
          nodes[node_counter][2] = string_me(temp_weight);
          nodes[node_counter][3] = "false";
          node_counter++;
        }
       } 
      //done reading into array
      
      //test output array
      for(int i= 0; i<node_counter; i++)
      {
        cout << "nodes[node_counter][0] = " << nodes[i][0] <<endl<< "nodes[node_counter][1] = " << nodes[i][1]  <<endl<< "nodes[node_counter][2] = " << nodes[i][2] << endl << "nodes[node_counter][3] = " << nodes[i][3] << endl;
      }
     //test array output complete
     

      //iterate through array, doing gay stuff
      for(int i = 0; i < node_counter; i++)
      {
        nodes
      }
      
    }
      
        class iterator;
        friend class iterator;


        class iterator
        {
            friend class network;


            protected:


                 map_iterator adj_iterator;


            public:


                bool operator== (const iterator& other)
                {
                    return adj_iterator == other.adj_iterator;
                }


                bool operator!= (const iterator& other)
                {
                    return !(*this == other);
                }


                pair<vertex, list< vertex_weight_pair> > operator*()
                {
                    return *adj_iterator;
                }


                iterator operator++ (int)
                {
                    iterator temp_itr;
                    temp_itr.adj_iterator = adj_iterator++;
                    return temp_itr;
                }
        }; // class iterator



      struct edge_triple
      {
          vertex from,
                 to;


          double weight;


          // Postcondition: this edge_triple has been constructed from
          //                from, to and weight.
          edge_triple (const vertex& from, const vertex& to, double weight)
          {
              this -> from = from;
              this -> to = to;
              this -> weight = weight;
          } // three-parameter constructor



         // Postcondition: true has been returned if this edge_triple's
         //                weight is greater than other_edge_triple's
         //                weight.  Otherwise, false has been returned.
         bool operator> (const edge_triple& other_edge_triple) const
         {
             return weight > other_edge_triple.weight;
         } // operator>
      }; // struct edge_triple


        class breadth_first_iterator;
        friend class breadth_first_iterator;


        class breadth_first_iterator
        {
            friend class network;


            protected:


                queue<vertex>* vertex_queue;
                map<vertex, bool, Compare>* reached;
                map_class* map_ptr;


                // Postcondition: this breadth_first_iterator has been
                //                initialized at start.
                breadth_first_iterator (const vertex& start,
                                        map_class* ptr)
                {
                    map_ptr = ptr;
                    reached = new map<vertex, bool, Compare>();
                    vertex_queue = new queue<vertex>();


                    // Mark each vertex as not reached:
                    //                    map_class::iterator itr;
                    map_iterator itr;
                    for (itr = (*map_ptr).begin(); itr  !=(*map_ptr).end(); itr++)
                        (*reached)[(*itr).first] = false;


                    (*reached)[start] = true;
                    (*vertex_queue).push (start);
                } // two-parameter constructor 


            public:


                // Postcondition: this breadth_first_iterator is empty.
                breadth_first_iterator() { }



                // Postcondition: true has been returned if this and other are
                //                the same breadth_first_iterator.  Otherwise,
                //                false has been returned.
                bool operator== (const breadth_first_iterator& other)
                {
                    return (vertex_queue == other.vertex_queue) &&
                           (reached == other.reached) &&
                           (map_ptr == other.map_ptr);
                } // operator==



                // Postcondition: true has been returned if this and other are
                //                the different breadth_first_iterators.
                //                Otherwise, false has been returned.
                bool operator!= (const breadth_first_iterator& other)
                {
                    return !(*this == other);
                } // operator==



                // Postcondition: the vertex that this breadth_first_iterator
                //                is positioned at has been returned.
                vertex operator*()
                {
                    return (*vertex_queue).front();
                } // operator*



                // Precondition: this breadth_first_iterator has not yet
                //               reached all of the reachable vertices in this
                //               network.
                // Postcondition: this breadth_first_iterator has been advanced
                //                to the next reachable vertex in this network;
                //                the pre-advanced iterator has been returned.
                breadth_first_iterator operator++ (int)
                {
                    breadth_first_iterator temp = *this;
                    vertex current = (*vertex_queue).front();
                    (*vertex_queue).pop();


                    //                    map_class::iterator itr = (*map_ptr).find (current);
                    map_iterator itr = (*map_ptr).find (current);
                    vertex_list_iterator list_itr;


                    // Iterate through the list of neighbors of current
                    for (list_itr = (*itr).second.begin();
                         list_itr != (*itr).second.end();
                         list_itr++)
                    {
                        vertex to = (*list_itr).to;
                        if ((*reached) [to] == false)
                        {
                            (*reached) [to] = true;
                            (*vertex_queue).push (to);
                        } // if
                    } // for
                    if ((*vertex_queue).empty())
                    {
                        vertex_queue = NULL;
                        reached = NULL;
                        map_ptr = NULL;
                    } // if queue empty
                    return temp;
                } // operator++
        }; // class breadth_first_iterator




        class depth_first_iterator;
        friend class depth_first_iterator;


        class depth_first_iterator
        {
            friend class network;


            protected:


                stack<vertex>* vertex_stack;
                map<vertex, bool, Compare>* reached;
                map_class* map_ptr;


                // Postcondition: this depth_first_iterator has been
                //                initialized at start.
                depth_first_iterator (const vertex& start, map_class* ptr)
                {
                    map_ptr = ptr;
                    reached = new map<vertex, bool, Compare>();
                    vertex_stack = new stack<vertex>();


                    // Mark each vertex as not reached:
                    map_iterator itr;
                    for (itr = (*map_ptr).begin(); itr != (*map_ptr).end(); itr++)
                        (*reached)[(*itr).first] = false;


                    (*reached)[start] = true;
                    (*vertex_stack).push (start);
                } // two-parameter constructor    
 
            public:


                // Postcondition: this depth_first_iterator is empty.
                depth_first_iterator() { }



                // Postcondition: true has been returned if this and other are
                //                the same depth_first_iterator.  Otherwise,
                //                false has been returned.
                bool operator== (const depth_first_iterator& other)
                {
                    return (vertex_stack == other.vertex_stack) &&
                           (reached == other.reached) &&
                           (map_ptr == other.map_ptr);
                } // operator==



                bool operator!= (const depth_first_iterator& other)
                {
                    return !(*this == other);
                } // operator!=



                // Postcondition: the vertex that this depth_first_iterator
                //                is positioned at has been returned.
                vertex operator*()
                {
                    return (*vertex_stack).top();
                } // operator*



                // Precondition: this depth_first_iterator has not yet
                //               reached all of the reachable vertices in this
                //               network.
                // Postcondition: this depth_first_iterator has been advanced
                //                to the next reachable vertex in this network;
                //                the pre-advanced iterator has been returned.
                depth_first_iterator operator++ (int)
                {
                    depth_first_iterator temp = *this;
                    vertex current = (*vertex_stack).top();
                    (*vertex_stack).pop();


                    map_iterator itr = (*map_ptr).find (current);
                    vertex_list_iterator list_itr;
                    for (list_itr = (*itr).second.begin();
                         list_itr != (*itr).second.end();
                         list_itr++)
                    {
                        vertex to = (*list_itr).to;
                        if ((*reached) [to] == false)
                        {
                            (*reached) [to] = true;
                            (*vertex_stack).push (to);
                        } // if
                    } // for
                    if ((*vertex_stack).empty())
                    {
                        vertex_stack = NULL;
                        reached = NULL;
                        map_ptr = NULL;
                    } // if stack empty
                    return temp;
                } // operator++
        }; // class depth_first_iterator


        
        // Postcondition: this network is empty.
        network() { }



        // Postcondition: this network contains a clone of network.
        network (const network& other)
        {
            adjacency_map = other.adjacency_map;
        } // copy constructor



        // Postcondition: the number of vertices in this network has been
        //                returned.
        unsigned int size()
        {
            return adjacency_map.size();
        } // method size



        // Postcondition: true has been returned if this network contains no
        //                vertices.  Otherwise, false has been returned.
        bool empty()
        {
            return size() == 0;
        } // method empty


        // Postcondition: an iterator positioned at the beginning of this
        //                network has been returned.
        iterator begin()
        {
            iterator temp;
            temp.adj_iterator = adjacency_map.begin();


            return temp;
        } // begin



        // Postcondition: the iterator returned can be used in comparisons
        //                to terminate an iteration of this network.
        iterator end()
        {
            iterator temp;
            temp.adj_iterator = adjacency_map.end();


            return temp;
        } // end



        // Postcondition: the number of edges in this network has been returned.
        unsigned int get_edge_count()
        {
            int count = 0;


            map_iterator itr;


            for (itr = adjacency_map.begin(); itr != adjacency_map.end(); itr++)
                count += (*itr).second.size();
            return count;
        } // method get_edge_count



        // Postcondition: if <v1, v2> forms an edge in this network, the weight
        //                of that edge has been returned. Otherwise, -1.0 has
        //                been returned.
        double get_edge_weight (const vertex& v1, const vertex& v2)
        {
            map_iterator itr = adjacency_map.find (v1);
            if (itr == adjacency_map.end() ||
                    adjacency_map.find (v2) == adjacency_map.end())
                return -1.0;


            vertex_list_iterator list_itr;
            for (list_itr = ((*itr).second).begin();
                 list_itr != ((*itr).second).end();
                 list_itr++)
                if ((*list_itr).to == v2)
                    return (*list_itr).weight;
            return -1.0; // there is no edge <v1, v2>
        } // method get_edge_weight



        // Postcondition: true has been returned if this network contains v;
        //                otherwise, false has been returned.
        bool contains_vertex (vertex v)
        {
            return adjacency_map.find (v) != adjacency_map.end();
        } // method contains_vertex



        // Postcondition: true has been returned if this network contains the
        //                edge <v1, v2>.  Otherwise, false has been returned.
        bool contains_edge (const vertex& v1, const vertex& v2)
        {
            vertex_list_iterator list_itr;


            map_iterator itr = adjacency_map.find (v1);
            if (itr == adjacency_map.end() ||
                    adjacency_map.find (v2) == adjacency_map.end())
                return false;
            for (list_itr = ((*itr).second).begin();
                        list_itr != ((*itr).second).end();
                        list_itr++)
                if ((*list_itr).to == v2)
                    return true;
            return false;
        } // method contains_edge



        // Postcondition: if v is already in this network, false has been
        //                returned. Otherwise, the map with v and an empty list
        //                has been added to this network and true has been
        //                returned.
        bool insert_vertex (const vertex& v)
        {
                return adjacency_map.insert (
                        pair<vertex, list<vertex_weight_pair> >
                        (v, list<vertex_weight_pair>())).second;        
        } // method insert_vertex



        // Postcondition: if the edge <v1, v2> is already in this network false
        //                has been returned. Otherwise, that edge with the
        //                given weight has been inserted in this network and
        //                true has been returned.
        bool insert_edge (const vertex& v1, const vertex& v2, const double& weight)
        {
            if (contains_edge (v1, v2))
                return false;
            insert_vertex (v1);
            insert_vertex (v2);
            (*(adjacency_map.find (v1))).second.push_back
                            (vertex_weight_pair (v2, weight));
            return true;
        } // method insert_edge



        // Postcondition: if v is a vertex in this network, v and all of its
        //                edges have been deleted from this network and true has
        //                been returned.  Otherwise, false has been returned.
        bool erase_vertex (const vertex& v)
        {
            map_iterator itr = adjacency_map.find (v);
            if (itr == adjacency_map.end())
                return false;
            adjacency_map.erase (itr);
            vertex_list_iterator list_itr;
            for (itr = adjacency_map.begin(); itr != adjacency_map.end(); itr++)


                // Delete any pair with v from the list (*itr).second
                for (list_itr = (*itr).second.begin();
                     list_itr != (*itr).second.end();
                     list_itr++)
                    if ((*list_itr).to == v)
                    {
                        (*itr).second.erase (list_itr);
                        break;
                    } // v found in the list (*itr).second
            return true;
        } // erase_vertex



        // Postcondition: if <v1, v2> is an edge in this network, that edge has
        //                been removed and true has been returned.  Otherwise,
        //                false has been returned.
        bool erase_edge (const vertex& v1, const vertex& v2)
        {
            map_iterator itr = adjacency_map.find (v1);
            if (itr == adjacency_map.end() ||
                        adjacency_map.find (v2) == adjacency_map.end())
                return false;
            vertex_list_iterator list_itr;
            for (list_itr = (*itr).second.begin();
                 list_itr != (*itr).second.end();
                 list_itr++)
                if ((*list_itr).to == v2)
                {
                    (*itr).second.erase (list_itr);
                    return true;
                } // if
            return false;
        } // method erase_edge



        // Precondition: vertex v is in this network.
        // Postcondition: a breadth_first_iterator over all vertices reachable
        //                from v has been returned.
        breadth_first_iterator breadth_first_begin (const vertex& v)
        {
            breadth_first_iterator b_itr (v, &adjacency_map);
            return b_itr;
        } // method breadth_first_begin



        // Postcondition: the breadth_first_iterator returned can be used in
        //                comparisons to terminate this iteration of this
        //                network.
        breadth_first_iterator breadth_first_end()
        {
           breadth_first_iterator b_itr;
           b_itr.vertex_queue = NULL;
           b_itr.reached = NULL;
           b_itr.map_ptr = NULL;
           return b_itr;
        } // breadth_first_end



        // Precondition: vertex v is in this network.
        // Postcondition: a depth_first_iterator over all vertices reachable
        //                from v has been returned.
        depth_first_iterator depth_first_begin (const vertex& v)
        {
            depth_first_iterator d_itr (v, &adjacency_map);
            return d_itr;
        } // method depth_first_begin



        // Postcondition: the depth_first_iterator returned can be used in
        //                comparisons to terminate this iteration of this
        //                network.
        depth_first_iterator depth_first_end()
        {
           depth_first_iterator d_itr;
           d_itr.vertex_stack = NULL;
           d_itr.reached = NULL;
           d_itr.map_ptr = NULL;
           return d_itr;
        } // depth_first_end



        // Postcondition: true has been returned if this network is connected.
        //                Otherwise, false has been returned.
        bool is_connected()
        {
            map_iterator itr;


            // For each vertex v, see if the number of vertices reachable from v
            // is equal to the total number of vertices in this network.
            for (itr = adjacency_map.begin(); itr != adjacency_map.end();itr++)
            {
                vertex v = (*itr).first;


                // Count the vertices reachable from v.
                unsigned int count = 0;
                breadth_first_iterator b_itr;
                for (b_itr = breadth_first_begin (v);
                     b_itr != breadth_first_end();
                     b_itr++)
                    count++;
                if (count < adjacency_map.size())
                    return false;
            } // while itr1 not finished iterating
            return true;
        } // method is_connected



        // Precondition: v is in this network.
        // Postcondition: the list of neighbors of v has been returned.
        list<vertex > get_neighbor_list (const vertex& v)
        {
            vertex_list_iterator list_itr;
            list<vertex> vertex_list;
            for (list_itr = adjacency_map [v].begin(); 
                 list_itr != adjacency_map [v].end();
                 list_itr++)
                vertex_list.push_back (list_itr -> to);
            return vertex_list;
        } // method get_neighbor_list



        // Precondition: this network is connected.
        // Postcondition: a minimum spanning tree for this network has
        //                been returned.
        network<vertex> get_minimum_spanning_tree() {


               network min_spanning_tree; // the minimum spanning tree is a
                                          // network so weights can be included


               priority_queue<edge_triple,
                              vector<edge_triple>,
                              greater<edge_triple> > pq;


               vertex root,
                      x,
                      y,
                      z;


               iterator itr;


               list< vertex_weight_pair > adjacency_list;
               vertex_list_iterator list_itr1;


               double weight;


               if (empty())
                   return min_spanning_tree;
               itr = begin();
               root = (*itr).first;
               min_spanning_tree.insert_vertex (root);


               adjacency_list = adjacency_map [root];
               for (list_itr1 = adjacency_list.begin();
                         list_itr1 != adjacency_list.end();
                         list_itr1++)
                   pq.push (edge_triple (root, list_itr1 -> to,
                                       list_itr1 -> weight));
               while (min_spanning_tree.size() < size())
               {
                   x = pq.top().from;
                   y = pq.top().to;
                   weight = pq.top().weight;
                   pq.pop();
                   if (!min_spanning_tree.contains_vertex (y)) {


                       min_spanning_tree.insert_vertex (y);
                       min_spanning_tree.insert_edge (x, y, weight);


                       adjacency_list = adjacency_map [y];
                       for (list_itr1 = adjacency_list.begin();
                            list_itr1 != adjacency_list.end();
                            list_itr1++)
                       {
                           z = list_itr1 -> to;
                           if (!min_spanning_tree.contains_vertex (z))
                           {
                               weight = list_itr1 -> weight;
                               pq.push (edge_triple (y, z, weight));
                        } // z not already in tree
                    } // iterating over y's neighbors
                } // y not already in tree
            } // tree has fewer vertices than this Network
            return min_spanning_tree;
         } // method get_minimum_spanningTree




        // Postcondition: the shortest path from v1 to v2 and its total weight
        //                have been returned.
        pair<list<vertex>, double> get_shortest_path (const vertex& v1,
                                                      const vertex& v2)
        {
            const double MAX_PATH_WEIGHT = 1000000.0;


            map<vertex, vertex, Compare> predecessor;
            map<vertex, double, Compare> weight_sum;
            priority_queue<vertex_weight_pair,
                           vector<vertex_weight_pair>,
                           greater<vertex_weight_pair> > pq;


            list< vertex_weight_pair> adjacency_list;
            vertex_list_iterator list_itr;


            breadth_first_iterator b_itr;


            vertex to,
                   from;


            double weight;


            if (adjacency_map.find (v1) == adjacency_map.end() ||
                    adjacency_map.find (v2) == adjacency_map.end())
                return pair<list<vertex>, double> (list<vertex>(), -1.0);


            bool found_v2 = false;
            for (b_itr = breadth_first_begin (v1); b_itr != breadth_first_end();
                           b_itr++)
                if (*b_itr == v2)
                {
                    found_v2 = true;
                    break;
                } // if
            if (!found_v2)
                return pair<list<vertex>, double> (list<vertex>(), -1.0);


            weight_sum [v1] = 0.0;
            predecessor [v1] = v1;
            for (b_itr = breadth_first_begin (v1);
                 b_itr != breadth_first_end();
                 b_itr++)
            {
                weight_sum [*b_itr] = MAX_PATH_WEIGHT;
                predecessor [*b_itr] = vertex();
            } // initializing weight_sum and predecessor


            adjacency_list = adjacency_map [v1];
            for (list_itr = adjacency_list.begin();
                 list_itr != adjacency_list.end();
                 list_itr++)
            {
                weight_sum [list_itr -> to] = list_itr -> weight;
                predecessor [list_itr -> to] = v1;
                pq.push (vertex_weight_pair (*list_itr));
            }// adjusting weight_sum, predecessor, pq for vertices adjacent to v1


            bool path_found = false;
            while (!path_found)
            {
                from = pq.top().to;  // get vertex in vertex_weight_pair
                                     // with smallest weight sum
                pq.pop();
                if (from == v2)
                    path_found = true;
                else
                {
                    adjacency_list = adjacency_map [from];
                    for (list_itr = adjacency_list.begin();
                         list_itr != adjacency_list.end();
                         list_itr++)
                    {
                        to = list_itr -> to;
                        weight = list_itr -> weight;
                        if (weight_sum [from] + weight < weight_sum [to])
                        {
                            weight_sum [to] = weight_sum [from] + weight;
                            predecessor [to] = from;
                            pq.push (vertex_weight_pair (to, weight_sum [to]));
                        } // if from_weight_sum + weight > to_weight_sum
                    } // for iterating over from's list
                } // else path not yet found
            } // while path not found


            list<vertex> path;
            vertex current = v2;
            while (current != v1)
            {
                path.push_front (current);
                current = predecessor [current];
            } // while not yet back to v1
            path.push_front (v1);


            return pair<list<vertex>, double> (path, weight_sum [v2]);
        } // method get_shortest_path



        // Precondition: every vertex in this network is a neighbor of every
        //               other vertex.
        // Postcondition: the pair returned consisted of a cycle -- as a list
        //                of vertices -- and the sum of the weights of the
        //                edges in the cycle.
        pair< list<vertex>, double> get_cycle()
        {
            pair< list<vertex>, double> cycle;


            list<vertex> cycle_list;


            double weight,
                   cycle_weight = 0.0;


            list< vertex_weight_pair > adjacency_list;
            vertex_list_iterator adjacency_list_itr;


            network::iterator itr = begin();


            vertex v,
                   start = (*itr).first;


            cycle_list.push_back (start);
            v = start;
            while (cycle_list.size() < size())
            {
                adjacency_list = adjacency_map [v];
                adjacency_list_itr = adjacency_list.begin();
                do
                {
                    v = adjacency_list_itr -> to;
                    weight = adjacency_list_itr -> weight;
                    adjacency_list_itr++;
                } // do
                while (find (cycle_list.begin(), cycle_list.end(), v)
                       != cycle_list.end() && adjacency_list_itr != adjacency_list.end());
                if (find (cycle_list.begin(), cycle_list.end(), v)
                    == cycle_list.end())
                {
                    cycle_list.push_back (v);
                    cycle_weight += weight;
                } // if
            } // while
            cycle_list.push_back (start);
            cycle_weight += get_edge_weight (v, start);
            cycle.first = cycle_list;
            cycle.second = cycle_weight;
            return cycle;
        } // method get_cycle
}; // class network



#endif