/*
 * GrUtility.java:  Utility classes, with package visibility
 *
 * NOTE:  Mixed adjacency matrix / adjacency list implementation
 */

/*
 * CVertex --- a city/crossroads on the map
 */
class CVertex
{//Instance-scope fields:
   String m_Name;
   int    m_Flag;    // Pending, Unvisited, or Visited in traversal
   int    m_Distance;// Distance from start in Dijkstra's algorithm
   CEdge  m_List;    // Adjacency list entry point

   CVertex(String n)
   {  m_Name = n;  m_Flag = 0; m_Distance = -1;  m_List = null;  }

   void setName(String n)  {  m_Name = n;  }

   String getName()        { return m_Name; }

   void setFlag(int n)     { m_Flag = n;  }
   int  getFlag()          { return m_Flag;  }
   void incFlag()          { ++m_Flag;  }
   void decFlag()          { --m_Flag;  }

   void setDistance(int d) { m_Distance = d; }
   int  getDistance()      { return m_Distance; }

// Return the first edge in the adjacency list
   CEdge list()            { return m_List;  }

// Create a CEdge object for the adjacency list AND return it
// to be added to the adjacency matrix.
   CEdge addAdjacent ( int node, int dist )
   {  m_List = new CEdge( node, dist, m_List );
      return m_List;
   }

// Since the adjacency list was built in a stack fashion, invert
// the stack for forward alphabetizing.
   void invertList()
   {  m_List = CEdge.invert(m_List);  }
}

/*
 * Edge --- a road in the map
 */
class CEdge
{//Instance-scope field:
   int   m_Dest;
   int   m_Distance;
   CEdge m_Next;

   CEdge(int dest, int miles, CEdge next)
   {  m_Dest = dest;
      m_Distance = miles;
      m_Next = next;
   }

   int city()  { return m_Dest;  }

   CEdge next(){ return m_Next;  }

   int length(){ return m_Distance;  }

// Invert the list entered at "list"
   static CEdge invert( CEdge list )
   {  CEdge newList = null;

      while ( list != null )
      {  CEdge hold = list.m_Next;

         list.m_Next = newList;
         newList = list;
         list = hold;
      }
      return newList;
   }
}

/*
 * Two-ple (ordered pair of number)
 */
class CPair
{//Instance-scope fields:
   int m_First, m_Second;

   CPair(int v0, int v1)
   {  set(v0, v1);  }

   CPair(CPair v)
   {  set(v.get1(), v.get2()); }

   void set(int v0, int v1)
   {  m_First=v0;  m_Second=v1;  }

   int  get1() {  return m_First;  }
   int  get2() {  return m_Second; }

}

/*
 * Double-Ended Queue of 2-ples (ordered pairs)
 */
class Deque // Double-ended queue (stack AND queue behaviors)
{  Deque() { m_Front = m_Back = null; }

   void  push(CPair v)       // Stack discipline
   {  m_Front = new DQnode(new CPair(v), m_Front);
      if ( m_Back == null )
         m_Back = m_Front;   // Update for queue use
   }

   void  enqueue(CPair v)    // Queue discipline
   {  if ( m_Front == null )
         m_Front = m_Back = new DQnode(new CPair(v), null);
      else
         m_Back = m_Back.m_Next = new DQnode(new CPair(v), null);
   }

   CPair remove ()           // Single removal point
   {  CPair v = null;

      if ( m_Front != null )
      {  v = m_Front.m_Edge;
         m_Front = m_Front.m_Next ;
         if (m_Front == null)// Clean up for queue use
            m_Back = null;
      }
      return v;
   }

   boolean empty() { return m_Front == null; }

   class DQnode
   {  DQnode(CPair v, DQnode nxt)
      {  m_Edge = new CPair(v);   // Be sure to keep a COPY
         m_Next = nxt;
      }

      CPair   m_Edge;
      DQnode  m_Next;
   }

   DQnode m_Front, m_Back;
};

/*
 * MinHeap of 2-ples (ordered pairs)
 */
class MinHeap // Priority queue with smallest entry at root
{//Instance-scope fields
   MinHnode[] m_Heap;          // Dynamic array, MinHnode declared at end
   int m_Size;                 // Physical size (number of allocated cells)
   int m_N;                    // Logical size (number of entries)

   MinHeap(int size)
   {  m_Heap = new MinHnode[size+1];
      m_Heap[0] = new MinHnode(new CPair(0,0), -1);   // Sentinel value
      m_Size = size;
      m_N = 0;
   }

   void enter (CPair edge, int dist)
   {  if ( m_N == m_Size ) // About to overflow:  expand the array
      {  MinHnode[] newHeap;
         m_Size += 5;      // or whatever increment feels ok.
         newHeap = new MinHnode[m_Size+1];
         System.arraycopy(m_Heap, 0, newHeap, 0, m_Size+1);
         m_Heap = newHeap;
      }
   // Since [1] is the root, increment m_N, then use as subscript
      m_N++;
      m_Heap[m_N] = new MinHnode(edge, dist);
      upHeap(m_N);
   }

   CPair remove(MyInt dist)
   {  CPair rtnVal = null;

      dist.value = -1;  // failure flag value

      if ( m_N > 0 )
      {  rtnVal     = m_Heap[1].m_Edge;
         dist.value = m_Heap[1].m_Dist;
         m_Heap[1]  = m_Heap[m_N--];
         downHeap(1);
      }
      return rtnVal;
   }

   boolean empty() { return m_N == 0; }

   void  upHeap (int child)       // Correct the heap from child upwards
   {  MinHnode hold = m_Heap[child];
      int parent = child/2;

   // m_Heap[0] has a sentinel value forcing loop exit when parent == 0.
      while ( hold.m_Dist < m_Heap[parent].m_Dist )
      {  m_Heap[child] = m_Heap[parent];
         child = parent;
         parent = child/2;
      }
      m_Heap[child] = hold;
   }

   void downHeap(int parent)        // Correct the heap from parent downwards
   {  MinHnode hold = m_Heap[parent];
      int child = 2*parent;

      while (child <= m_N)
      {  if ( child < m_N && m_Heap[child].m_Dist > m_Heap[child+1].m_Dist )
            child++;
         if ( ! (m_Heap[child].m_Dist < hold.m_Dist) )
            break;
         m_Heap[parent] = m_Heap[child];
         parent = child;
         child = 2*parent;
      }
      m_Heap[parent] = hold;
   }

   class MinHnode
   {  CPair m_Edge;
      int   m_Dist;

   // Make sure that it is a COPY of the edge that goes into the heap
      MinHnode(CPair mE, int mD)
      {  m_Edge = new CPair(mE); m_Dist = mD;  }
   };
}