#include "copyright.h"

//#include <stdio.h>
#include <stdlib.h>

#include "db.h"
#include "config.h"

/* Compute shortest path to each room */
/* Locks cost extra */
#define INFINITY 2148575        /* MAXINT or thereabouts */
#define LOCK_COST 10000         /* extra cost for a lock */

/* This code blasts a lot of fields in the database, so */
/* you don't ever want to write it back out afterwards. */

/* Where things get stored: */
/* cost to get here gets put in pennies */
/* location is the previous room that gets you here */
/* next is the next room in the search queue */
/* key non-zero means already queued */
/* contents is previous exit that gets you here */

/* this should be a priority queue, but we're cheap */
dbref search_queue_head = NOTHING;
dbref search_queue_tail = NOTHING;

void queue_room (dbref room)
{
  if (db[room].key)
    return;

  if (search_queue_tail == NOTHING) {
    search_queue_head = room;
  } else {
    db[search_queue_tail].next = room;
  }
  search_queue_tail = room;
  db[room].next = NOTHING;
  db[room].key = 1;
}

dbref dequeue_room (void)
{
  dbref room;

  if ((room = search_queue_head) == NOTHING)
    return NOTHING;
  if ((search_queue_head = db[room].next) == NOTHING) {
    search_queue_tail = NOTHING;
  }
  db[room].next = NOTHING;
  db[room].key = 0;

  return room;
}

void find_paths (void)
{
  dbref room;
  dbref exit;
  dbref mycost;                 /* dbref[room].pennies */
  dbref cost;                   /* mycost + cost to use exit */
  dbref dest;                   /* exit destination */

  while ((room = dequeue_room ()) != NOTHING) {
    /* get first one */

    /* check its exits */
    mycost = db[room].pennies;
    DOLIST (exit, db[room].exits) {
      if ((dest = db[exit].location) < 0)
        continue;
      cost = mycost + 1;
      if (db[exit].key != NOTHING) {
        if (!(db[exit].flags & ANTILOCK)
          && Typeof (db[exit].key) != TYPE_THING) {
          continue;             /* we can't get it */
        } else {
          cost += LOCK_COST;
        }
      }
      if (cost < db[dest].pennies) {
        /* it's cheaper, set and queue it */
        db[dest].pennies = cost;
        db[dest].location = room;
        db[dest].contents = exit;
        queue_room (dest);
      }
    }
  }
}

void compute_paths (dbref start)
{
  dbref room;

  /* clear out all fields we use */
  for (room = 0; room < db_top; room++) {
    if (Typeof (room) == TYPE_ROOM) {
      db[room].location = db[room].next = db[room].contents = NOTHING;
      db[room].pennies = INFINITY;
      db[room].key = 0;
    }
  }

  /* set up start */
  db[start].pennies = 0;
  queue_room (start);

  find_paths ();
}

void print_path (dbref room)
{
  dbref prev;
  dbref exit;
  dbref key;

  if ((prev = db[room].location) != NOTHING) {
    print_path (prev);
    exit = db[room].contents;
    if ((key = db[exit].key) != NOTHING) {
      printf ("LOCKED[%s(%d)] ", db[key].name, key);
    }
    printf ("%s => %s\n", db[exit].name, db[room].name);
  }
}

void print_paths (void)
{
  dbref room;

  for (room = 0; room < db_top; room++) {
    if (Typeof (room) == TYPE_ROOM) {
      printf ("%s(%d)[%s]: ", db[room].name, room, db[db[room].owner].name);
      if (db[room].pennies == INFINITY) {
        puts ("UNREACHABLE");
      } else {
        printf ("%d + %d locks\n",
          db[room].pennies % LOCK_COST, db[room].pennies / LOCK_COST);
      }
      print_path (room);
      putchar ('\n');
    }
  }
}

int main (int argc, char **argv)
{
  dbref start = 0;

  if (argc >= 2) {
    start = atol (argv[2]);
  } else {
    start = PLAYER_START;
  }

  if (db_read (stdin) < 0) {
    fprintf (stderr, "%s: bad input\n", argv[0]);
    exit (5);
  }

  compute_paths (start);
  print_paths ();

  return 0;
}