// Copyright (C) 1996 DIMACS Center, Rutgers, The State University of New Jersey
// Author(s): Patricia K. Fasel (Los Alamos Nat. Lab.), Jonathan Berry

// This software is copyrighted by the DIMACS Center at Rutgers, The State
// University of New Jersey.  IT IS PROVIDED AS IS, AND THE AUTHORS, DIMACS, AND
// RUTGERS, THE STATE UNIVERSITY OF NEW JERSEY  DISCLAIM
// ALL LIABILITY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL
// DAMAGES ARISING OUT OF THE USE OF THIS SOFTWARE, ITS DOCUMENTATION, OR ANY
// DERIVATIVES THEREOF, EVEN IF THE AUTHORS HAVE BEEN ADVISED OF THE
// POSSIBILITY OF SUCH DAMAGE.

// THE AUTHORS AND DISTRIBUTORS SPECIFICALLY DISCLAIM ANY WARRANTIES,
// INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE, AND NON-INFRINGEMENT.  THIS SOFTWARE
// IS PROVIDED ON AN "AS IS" BASIS, AND THE AUTHORS AND DISTRIBUTORS HAVE
// NO OBLIGATION TO PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR
// MODIFICATIONS.

// The authors hereby grant permission to use, copy, modify, distribute,
// and license this software and its documentation for any purpose, provided
// that existing copyright notices are retained in all copies and that this
// notice is included verbatim in any distributions. No written agreement,
// license, or royalty fee is required for any of the authorized uses.
// Modifications to this software may be copyrighted by their authors
// and need not follow the licensing terms described here, provided that
// the new terms are clearly indicated on the first page of each file where
// they apply.

// Last File Update: 31-Jul-1996
// 

#include <iostream.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <assert.h>
#include <LINK/graph/Vertex.h>
#include <LINK/graph/Edge.h>
#include <LINK/graph/Attribute.h>
#include <LINK/basic/Set.h>
#include <LINK/graph/Graph.h>


//
// constructor and destructor for vertex
//
Vertex::Vertex(Graph* owner) : GraphObject(owner)
{}

Vertex::Vertex(const Vertex &V, Flag clone) : GraphObject(V, clone)
{
  // Since this is a new isolated vertex for the current graph we don't
  // have to add any edges.
  // [ the Vertex isn't added to graph yet -- it's the callers responsibility ]
  if ( ! GraphObject::_graphBeingConstructed ) GraphObject::_owner = V._owner; 
}


Vertex::~Vertex()
{
    _edges.clear();
}

#if 0
Vertex*
Vertex::copy()
{
    return this;
}
#endif

//
// add an incident edge to the vertex
//
void
Vertex::addEdge(Edge* passed_edge)
{
    if (passed_edge->owner() != owner()) {
        error("Vertex::addEdge(Edge*): illegal vertex");
        return;
    }
    _edges.insert(passed_edge);
}


//
// remove the incident edge
//
void
Vertex::removeEdge(Edge *passed_edge)
{
    Iterator<Edge*> get_edge(&_edges);
    Edge* edge;
    while (get_edge(edge))
	if (edge == passed_edge) {
	    _edges.remove(edge);
	    break;
	}
}


//
// return the set of all vertices connected to this vertex
// either by in edges or outedges
//
Set<Vertex*>
Vertex::neighbors() const
{
    return outNeighbors();	// correct for undirected and directed

//    Set<Vertex*> return_vertices;
//
//  Iterator<Edge*> get_edge(&_edges);
//  Edge* edge;
//  while (get_edge(edge)) {
//      Iterator<Vertex*> get_vertex(edge->vertices());
//	Vertex* vertex;
//	while (get_vertex(vertex))
//            if ((vertex != this) && (!return_vertices.memberQ(vertex)))
//	        return_vertices.insert(vertex);
//    }
//    return return_vertices;
}


//
// return the set of vertices for which this vertex is the sink
//
Set<Vertex*>
Vertex::inNeighbors() const
{
    Set<Vertex*> return_vertices;

    Iterator<Edge*> get_edge(&_edges);
    Edge* edge;
    while (get_edge(edge)) {
	Set<Vertex*> neighbors = inNeighbors(edge);
        Iterator<Vertex*> get_in_neighbor(&neighbors);
        Vertex* vertex;
        while (get_in_neighbor(vertex))
            if((vertex != this) && (!return_vertices.memberQ(vertex)))
	        return_vertices.insert(vertex);
    }
    return return_vertices;
}


Set<Vertex*>
Vertex::inNeighbors(Edge* passed_edge) const
{
    Set<Vertex*> in_vertices;

    Collection<Vertex*>* vertices = passed_edge->vertices();
    Iterator<Vertex*> get_in_neighbor(vertices);
    //DataType edge_dir = passed_edge->type();
    int undirected = vertices->sortedQ();
    Vertex* vertex;
    if (undirected) {
        while (get_in_neighbor(vertex))
            if ((vertex != this) && (!in_vertices.memberQ(vertex)))
		in_vertices.insert(vertex);
    } else {
        while (get_in_neighbor(vertex) && vertex != this)
            if (!in_vertices.memberQ(vertex))
	        in_vertices.insert(vertex);
    }
    return in_vertices;
}


//
// return the set of vertices for which this vertex is the source
//
Set<Vertex*>
Vertex::outNeighbors() const
{
    Set<Vertex*> return_vertices;

    Iterator<Edge*> get_edge(&_edges);
    Edge* edge;
    while (get_edge(edge)) {
	Set<Vertex*> neighbors = outNeighbors(edge);
        Iterator<Vertex*> get_out_neighbor(&neighbors);
        Vertex* vertex;
        while (get_out_neighbor(vertex))
            if ((vertex != this) && (!return_vertices.memberQ(vertex)))
	        return_vertices.insert(vertex);
    }
    return return_vertices;
}


Set<Vertex*>
Vertex::outNeighbors(Edge* passed_edge) const
{
    Set<Vertex*> out_vertices;

    Collection<Vertex*>* vertices = passed_edge->vertices();
    Iterator<Vertex*> get_out_neighbor(vertices);
    //DataType edge_dir = passed_edge->type();
    int undirected = vertices->sortedQ();
    Vertex* vertex;
    if (undirected) {
        while (get_out_neighbor(vertex))
            if ((vertex != this) && (!out_vertices.memberQ(vertex)))
	        out_vertices.insert(vertex);
    } else {
        while (get_out_neighbor(vertex) && vertex != this);
        while (get_out_neighbor(vertex))
            if (!out_vertices.memberQ(vertex))
                out_vertices.insert(vertex);
    }
    return out_vertices;
}

String Vertex::name() const
{
  String nm = GraphObject::name();
  return nm;

//////**********************************************************************
////// the following was a bad hack
////// see compareItems in graphTemplate.cc and see the operators of Vertex
////// to see how things work now  (if no name specified, don't try to 
////// assign one - leave it null).
//////**********************************************************************
//  if ( nm[0] != 0 ) return nm;
// // else look up index and used it as its name 
// // this hack (for ostream) assumes that the graph has few vertices (say < 55)
//  nm = "[ ]";
//#ifndef __GNUC__
//  nm[1] = 'A' + _owner->vertices().search(this);
//#else
//  // gcc choking on 'this'.
//  Vertex *thisv = this;
//  nm[1] = 'A' + _owner->vertices().search(thisv);
//#endif
//
//return nm;

}

// ??? - JWB
//ostream&
//Vertex::display(ostream& stream) const
//{
//    if (CAST(*this,Vertex).name() == 0)
//    	stream << "<unnamed_vertex>";
//    else
//    	stream << CAST(*this,Vertex).name();
//    return stream;
//}

ostream&
Vertex::display(ostream& stream) const
{
    if (name() == 0)
    	stream << "<unnamed_vertex>";
    else
    	stream << name();
    return stream;
}

//
// save a vertex to an ascii file
//
void
Vertex::saveToFile(ofstream *fout, int indent)
{
    //cout << "*****Saving vertex " << *this << endl;
    char buf[BUFSIZE];
    sprintf(buf, "%*c", indent, ' ');
    *fout << buf << "  " << name();
    GraphObject::saveToFile(fout, indent);
}

//
// Vertex names are strings.  However, the strings usually contain
// only decimal digits.  It is not nice if  "2" > "10," so we test
// to see if the names are indeed integers before doing a strcmp.
//
int compareVertexNames(char *str1, char *str2)
{
	char *res1, *res2;
	int i1 = strtol(str1, &res1, 10);
	int i2 = strtol(str2, &res2, 10);
	if ((strlen(res1)>0) || (strlen(res2)>0))
		return strcmp(str1, str2); // give up; not ints
	return i1 - i2;
}

Bool
Vertex::operator<(const Vertex& obj) const
{       
	if (compareVertexNames(name(), obj.name()) < 0)
              return TRUE;
        else
              return FALSE;
}

Bool
Vertex::operator<=(const Vertex& obj) const
{       
	if (compareVertexNames(name(), obj.name()) <= 0)
                return TRUE;
        else
                return FALSE;
}

Bool
Vertex::operator>(const Vertex& obj) const
{       
	if (compareVertexNames(name(), obj.name()) > 0)
                return TRUE;
        else
                return FALSE;
}

Bool
Vertex::operator>=(const Vertex& obj) const
{       
	if (compareVertexNames(name(), obj.name()) >= 0)
                return TRUE;
        else
                return FALSE;
}

Bool
Vertex::operator==(const Vertex& obj) const
{       
	if (compareVertexNames(name(), obj.name()) == 0)
                return TRUE;
        else
                return FALSE;
}

Bool
Vertex::operator!=(const Vertex& obj) const
{       
	if (compareVertexNames(name(), obj.name()) != 0)
                return TRUE;
        else
                return FALSE;
}