static char *sccs_id= (sccs_id, "@(#)cpath.cc	1.9 7/28/92");

#include	"Dictionary.h"
#include	"SortedOList.h"
#include	"ObjFloat.h"
#include	"ObjInt.h"
#include	"ByteArray.h"
#include	"IO/stream.h"


bool	gMemStatistics= FALSE;


class OidList {
  long	*list;
  long	size;
public:
  ~OidList() {
    delete list;
  }
  OidList(int oid) {
    list= new long[size= 1];
    list[0]= oid;
  }
  OidList(OidList *l, long oid) {
    list= new long[size= l->Size() + 1];
    bcopy(l->list, list, sizeof(long) * l->Size());
    list[size-1]= oid;
  }
  long operator[](long i) {
    return list[i];
  }
  long Size() {
    return size;
  }
};


class Edge: public Object {
  ByteArray	*to_node;
  long		oid;
  float		distance;
  Edge		*next;
#ifdef LEVELS
  int		level;
#endif
public:
  Edge(ByteArray *to, long the_oid, float the_d, int l):
#ifdef LEVELS
    to_node(to), oid(the_oid), distance(the_d), next(0) , level(l)
#else
    to_node(to), oid(the_oid), distance(the_d), next(0)
#endif
    {}

  long		GetOid() { return oid; }
  float		GetDistance() { return distance; }
  ByteArray	*GetToNode() { return to_node; }
  void		Link(Edge *e) { e->next= next; next= e; }
  Edge		*GetNext() { return next; }
};


class Path: public Object {
  ByteArray	*node;
  float		cost;
  OidList	*path;

public:
  Path(ByteArray *n): node(n), path(0) {};

  int Compare (Object *o) {
    float diff= (cost - ((Path*) o)->cost);
    return diff < 0 ? -1: (diff > 0 ? 1: 0);
  }
  InitPath(long oid, float new_cost) {
    SafeDelete(path);
    path= new OidList(oid);
    cost= new_cost;
  }
  SetPath(Path *p, long oid, float new_cost) {
    SafeDelete(path);
    path= new OidList(p->path, oid);
    cost= new_cost;
  }
  ByteArray *GetNode()
    { return node; }
  float	GetCost()
    { return cost; }
  OidList* GetOidList()
    { return path; }
};


static Dictionary	*from_dict;
static Dictionary	*costs;

static SortedObjList	*U;

static int		districting;
static int		directed;
static int		levels;

void		Solve(ByteArray *, long, long);
ByteArray	*FindP(long oid);
void		PathReadData();
void		OutputPath(ByteArray *, long end_oid);
void		OutputDistrict(double max_dist);



extern int topol_main(int argc, char *argv[]);
extern int cpath_main(int argc, char *argv[]);


char *strip_name(char *s)
{
  char *rs= rindex(s, '/');

  if (!rs)
    return s;
  return rs+1;
}


main(int argc, char *argv[])
{
  if (strcmp(strip_name(argv[0]), "topol") == 0)
    return topol_main(argc, argv);
  else if (strncmp(strip_name(argv[0]), "district", 8) == 0) {
    districting= 1;
    return cpath_main(argc, argv);
  } else
    return cpath_main(argc, argv);
}


int cpath_main(int argc, char *argv[])
{
  long		start_oid;
  long		end_oid;
  double	max_distance;
  char		*progname= argv[0];

  while (argc > 1 && argv[1][0] == '-') {
    switch (argv[1][1]) {
    case 'd':
      directed= 1;
      break;
    case 'l':
      levels= 1;
      break;
    }
    argc--;
    argv++;
  }

  if (!districting) {
    if (argc != 3) {
      cerr << "Usage: " << progname << " [-d -l] from_oid to_oid" NL;
      exit(1);
    }
  } else {
    if (argc != 3) {
      cerr << "Usage: " << progname << " [-d -l] from_oid max_distance" NL;
      exit(1);
    }
  }

  from_dict= new Dictionary;
  costs= new Dictionary;
  U= new SortedObjList;

  cout << "Reading Data...\n";
  cout.flush();
  PathReadData();

  start_oid= atol(argv[1]);

  if (districting) {

    max_distance= atof(argv[2]);
    cout << "Searching start point...\n";
    cout.flush();
    ByteArray *start_p= FindP(start_oid);
    if (!start_p) {
      cerr << "Cannot find start point in network !!!\n";
      exit(2);
    }

    cout << "Searching district...\n";
    cout.flush();
    Solve(start_p, start_oid, 0);

    OutputDistrict(max_distance);

  } else {

    end_oid= atol(argv[2]);

    cout << "Searching start/end points...\n";
    cout.flush();
    ByteArray *start_p= FindP(start_oid);
    ByteArray *end_p= FindP(end_oid);
    if (!start_p || !end_p) {
      cerr << "Cannot find points in network !!!\n";
      exit(2);
    }

    cout << "Searching shortest path...\n";
    cout.flush();
    Solve(start_p, start_oid, end_oid);

    OutputPath(end_p, end_oid);
  }

  return(0);
}


void Add2Dict(Dictionary *dict, ByteArray *key, Edge *e)
{
  Edge *fe= (Edge*) dict->AtKey(key);

  if (fe) {
    fe->Link(e);
  } else
    dict->AtKeyPut(key, e);
}


void PathReadData()
{
  char		the_from[1000];
  char		the_to[1000];
  long		the_oid;
  float		the_distance;
  int		direction;
  int		level;

  while (cin >> the_oid >> the_from >> the_to >> the_distance) {

    if (directed)
      cin >> direction;
    else
      direction= 2;

    if (levels)
      cin >> level;
    else
      level= 0;

    // cerr << the_oid << the_from << the_to << the_distance NL;

    ByteArray	*from_key= new ByteArray(the_from);
    ByteArray	*to_key= new ByteArray(the_to);

    Edge *new_e= new Edge(to_key, the_oid, the_distance, level);

    Add2Dict(from_dict, from_key, new_e);

    if (direction == 2) {
      Edge *new_e_rev= new Edge(from_key, the_oid, the_distance, level);
      Add2Dict(from_dict, to_key, new_e_rev);
    }
  }
}


ByteArray *FindP(long oid)
{
  DictIterValues	*next= new DictIterValues(from_dict);
  Edge			*edge;

  while (edge= (Edge*) (*next)()) {
    do {
      if (edge->GetOid() == oid)
        break;
    } while (edge= edge->GetNext());
    if (edge)
      break;
  }

  delete next;

  return edge ? edge->GetToNode(): 0;
}


const float	Infinity= 1e20;

void Solve(ByteArray *start_p, long start_oid, long end_oid)
{
  Path	*start_path= new Path(start_p);

  // start_path->InitPath(start_oid, 0);
  start_path->InitPath(0, 0);
  costs->AtKeyPut(start_p, start_path);

  U->Add(start_path);

  while (U->Size()) {
    Path	*up= (Path*) U->Remove(U->First());
    float	ucost= up->GetCost();
    ByteArray	*u= up->GetNode();

    Edge *v= (Edge*) from_dict->AtKey(u);
    if (v) do {
      ByteArray	*vnode= v->GetToNode();
      Path	*vp= (Path*) costs->AtKey(vnode);
      float	vcost= vp ? vp->GetCost(): Infinity;
      float	sum;

      if ((sum= ucost + v->GetDistance()) < vcost) {
	if (!vp) {
	  vp= new Path(vnode);
	  costs->AtKeyPut(vnode, vp);
	}
	vp->SetPath(up, v->GetOid(), sum);
	U->Add(vp);

#if 1 // Remove the next lines if you want the SP to all points...
        if (!districting && v->GetOid() == end_oid)
	  return;
#endif

      }
    } while (v= v->GetNext());
  }
}


char *OIDS_OUT= "oids_out";
char *STAT_OUT= "pathstat_out";

void OutputPath(ByteArray *vnode, long end_oid)
{
  Path *sol= (Path*) costs->AtKey(vnode);

  if (!sol) {
    cout << "No path exists\n";
    cout.flush();
    // Empty files:
    ostream results(OIDS_OUT);
    ostream stats(STAT_OUT);
    return;
  }

  ostream	stat_out(STAT_OUT);
  stat_out << "Distance: " << sol->GetCost() NL;
  cout << "Distance: " << sol->GetCost() NL;

  ostream	results(OIDS_OUT);
  OidList	*list= sol->GetOidList();

  for (int i= 0; i < list->Size(); i++) {
    results << (*list)[i] NL;
  }
  // results << end_oid NL;
}


void OutputDistrict(double max_distance)
{
  Set	*oidset= new Set;
  Iter	next(new DictIterValues(costs));
  Path	*sol;
  ObjInt *oi= new ObjInt;

  ostream	results(OIDS_OUT);

  while (sol= (Path*) next()) {
    if (sol->GetCost() <= max_distance) {
	OidList	*list= sol->GetOidList();
	for (int i= 0; i < list->Size(); i++) {
		int oid= (*list)[i];
		oi->SetValue(oid);
		if (oidset->Contains(oi))
		  continue;
		oidset->Add(new ObjInt(oid));
		results << oid NL;
	}
    }
  }
}