#include <stdio.h>

#include "mud.h"
#include "search.h"

/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
 * Coordinate
 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
coordinate::coordinate()
{
    x = 0;
    y = 0;
    z = 0;
}

coordinate::coordinate(int p_x, int p_y, int p_z)
{
    x = p_x;
    y = p_y;
    z = p_z;
}

/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
 * Coordinate Operators: direction
 */
coordinate operator+(const struct coordinate &coord, dir_types dir)
{
    coordinate ret = coord;

    switch(dir)
    {
    case DIR_NORTH:
        ret.y++;
        break;
    case DIR_EAST:
        ret.x++;
        break;
    case DIR_SOUTH:
        ret.y--;
        break;
    case DIR_WEST:
        ret.x--;
        break;
    case DIR_NORTHEAST:
        ret.x++;
        ret.y++;
        break;
    case DIR_SOUTHEAST:
        ret.x++;
        ret.y--;
        break;
    case DIR_SOUTHWEST:
        ret.x--;
        ret.y--;
        break;
    case DIR_NORTHWEST:
        ret.x--;
        ret.y++;
        break;
    case DIR_UP:
        ret.z++;
        break;
    case DIR_DOWN:
        ret.z--;
        break;

    default:
        break;
    }

    return ret;
}

/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
 * Coordinate Operators: coordinate
 */
coordinate operator+(const struct coordinate &coorda, const struct coordinate &coordb)
{
    coordinate ret;
    
    ret.x = coorda.x+coordb.x;
    ret.y = coorda.y+coordb.y;
    ret.z = coorda.z+coordb.z;
    return ret;
}

coordinate operator-(const struct coordinate &coorda, const struct coordinate &coordb)
{
    coordinate ret;
    
    ret.x = coorda.x-coordb.x;
    ret.y = coorda.y-coordb.y;
    ret.z = coorda.z-coordb.z;
    return ret;
}

/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
 * Coordinate Operators: comparison
 */
bool operator<(const struct coordinate &a, const struct coordinate &b)
{
    long aval, bval;

    // Handle Z here
    if (b.z < a.z)
        return true;
    if (b.z > a.z)
        return false;

    // Convert each xy into a long
    aval = a.x + (a.y << 16);
    bval = b.x + (b.y << 16);
    return (bval < aval);
}

bool operator<=(const struct coordinate &a, const struct coordinate &b)
{
    long aval, bval;

    // Handle Z here
    if (b.z < a.z)
        return true;
    if (b.z > a.z)
        return false;

    // Convert each xy into a long
    aval = a.x + (a.y << 16);
    bval = b.x + (b.y << 16);
    return (bval <= aval);
}

bool operator>(const struct coordinate &a, const struct coordinate &b)
{
    long aval, bval;

    // Handle Z here
    if (b.z < a.z)
        return false;
    if (b.z > a.z)
        return true;

    // Convert each xy into a long
    aval = a.x + (a.y << 16);
    bval = b.x + (b.y << 16);
    return (bval > aval);
}

bool operator>=(const struct coordinate &a, const struct coordinate &b)
{
    long aval, bval;

    // Handle Z here
    if (b.z < a.z)
        return false;
    if (b.z > a.z)
        return true;

    // Convert each xy into a long
    aval = a.x + (a.y << 16);
    bval = b.x + (b.y << 16);
    return (bval >= aval);
}

bool operator==(const struct coordinate &a, const struct coordinate &b)
{
    return (a.z == b.z && a.x == b.x && a.y == b.y);
}

/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
 * Search Frame
 *
 * Used to represent a single node in the search tree.
 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
search_frame::search_frame(void)
{
    udf[0]   = 0;
    udf[1]   = 0;
    udf[2]   = 0;
    udf[3]   = 0;
    udf[4]   = 0;

    value    = 0;
    last_dir = DIR_SOMEWHERE;
    offset.x = 0;
    offset.y = 0;
    offset.z = 0;
}

search_frame *search_frame::make_exit(EXIT_DATA *exit)
{
    search_frame *ret = NULL;
    ROOM_INDEX_DATA *to = NULL;

    // Validate Exit
    if (exit->vdir == DIR_SOMEWHERE || !(to = exit->to_room))
        return NULL;

    // generate result
    ret           = new search_frame();
    ret->offset   = offset+(dir_types)exit->vdir;
    ret->last_dir = (dir_types)exit->vdir;
    ret->target   = to;
    ret->value    = value+1;

    return ret;
}

dir_types search_frame::get_dir(void)
{
    long x,y,z;

    x = offset.x;
    y = offset.y;
    z = offset.z;

    if (x == 0 && y == 0 && z == 0)
        return DIR_SOMEWHERE;

    if (z != 0)
    {
        if (z > 0)
            return DIR_UP;
        return DIR_DOWN;
    }

    if (x == 0)
    {
        if (y > 0)
            return DIR_NORTH;
        return DIR_SOUTH;
    }

    if (y == 0)
    {
        if (x > 0)
            return DIR_EAST;
        return DIR_WEST;
    }

    if (x > 0)
    {
        if (y > 0)
            return DIR_NORTHEAST;
        return DIR_SOUTHEAST;
    }

    if (y > 0)
        return DIR_NORTHWEST;
    return DIR_SOUTHWEST;
}

/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
 * Search Algorithms
 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
void search_BFS::search(ROOM_INDEX_DATA *start, search_callback *callback, long max_dist, bool e_closed)
{
    search(start, callback, max_dist, e_closed, false);
}

void search_BFS::search(ROOM_INDEX_DATA *start, search_callback *callback, long max_dist, bool e_closed, bool use_z)
{
    std::list<search_frame*> open;   // Frame Queue
    std::set<long>           closed; // Visited Rooms

    search_frame *frame, *tmp_frame; // Frames
    EXIT_DATA *exit;                 // Exit

    long cnt;
    bool found = false;

    // Initialize
    cnt             = 1;
    frame           = new search_frame();
    frame->value    = 0;
    frame->target   = start;
    frame->last_dir = DIR_SOMEWHERE;
    open.push_back(frame);
    closed.insert(frame->target->vnum);

    // Search Loop
    while(!found && cnt)
    {
        --cnt;
        frame = open.front();
        open.pop_front();

        // Search Exits
        for (exit = frame->target->first_exit; exit; exit = exit->next)
        {

            if (!exit)
                continue;
            // No "other" dir_types...
            if (exit->vdir == DIR_SOMEWHERE)
                continue;

            // No "Z" search
            if (!use_z && (exit->vdir == DIR_UP || exit->vdir == DIR_DOWN))
                continue;

            // Don't pass through e_closed.
            if (!e_closed && IS_SET(exit->exit_info, EX_CLOSED))
                continue;

            tmp_frame = frame->make_exit(exit);

            // The exit was unsuitable for searching.
            if (!tmp_frame)
                continue;

            // Too Far
            if (tmp_frame->value >= max_dist)
            {
                delete tmp_frame;
                continue;
            }

            // Already Visited
            if (closed.find(tmp_frame->target->vnum) != closed.end())
            {
                delete tmp_frame;
                continue;
            }

            // Handle Callback
            if (callback->search(tmp_frame))
            {
                delete tmp_frame;
                found = true;
                break;
            }

            cnt++;
            // Update Open and Closed
            open.push_back(tmp_frame);
            closed.insert(tmp_frame->target->vnum);
        }

        // finally, cleanup this frame
        delete frame;
    }

    // cleanup any remaining frames.
    while (open.size() > 0)
    {
        frame = open.front();
        open.pop_front();
        delete frame;
    }
}

void search_LOS::search(ROOM_INDEX_DATA *start, search_callback *callback, long max_dist, bool e_closed)
{
    search(start, callback, max_dist, e_closed, false);
}

void search_LOS::search(ROOM_INDEX_DATA *start, search_callback *callback, long max_dist, bool e_closed, bool use_z)
{
    ROOM_INDEX_DATA *from, *to;
    EXIT_DATA *exit, *tmp;
    dir_types  dir;
    search_frame *frame;
    bool found = false;

    // Flyweight Frame
    frame = new search_frame();

    // Exit Loop (search for appropriate dir_typess)
    for (exit = start->first_exit; exit; exit = exit->next)
    {
        dir = (dir_types)exit->vdir;

        // No "other" dir_types...
        if (exit->vdir == DIR_SOMEWHERE)
            continue;

        if (!use_z && (dir == DIR_UP || dir == DIR_DOWN))
            continue;

        // Don't pass through e_closed.
        if (!e_closed && IS_SET(exit->exit_info, EX_CLOSED))
            continue;

        // Reset Frame
        frame->offset.x = 0;
        frame->offset.y = 0;
        frame->offset.z = 0;
        frame->value    = 0.00;
        frame->last_dir = dir;

        // Init
        from = start;

        // Handle the distance
        while(++frame->value <= max_dist)
        {
            // No exit?
            if (!(tmp = get_exit(from, dir)))
                break;

            // Exit closed?
            if (!e_closed && IS_SET(tmp->exit_info, EX_CLOSED))
                break;

            // No target?
            if (!(to = tmp->to_room))
                break;

            // Update Frame
            frame->target = to;
            frame->offset = frame->offset + dir;

            // Found
            if (callback->search(frame))
            {
                found = true;
                break;
            }
            from = to;
        }
        if (found)
            break;
    }

    // Cleanup
    delete frame;
}

void search_DIR::search(ROOM_INDEX_DATA *start, search_callback *callback, dir_types dir, long max_dist, bool e_closed)
{
    ROOM_INDEX_DATA *from, *to;
    EXIT_DATA *exit;
    search_frame *frame;
    bool found = false;

    // Flyweight Frame
    frame = new search_frame();

    // No exit
    if (!(exit = get_exit(start, dir)))
        return;

    // Don't pass through e_closed.
    if (!e_closed && IS_SET(exit->exit_info, EX_CLOSED))
        return;

    // Reset Frame
    frame->offset.x = 0;
    frame->offset.y = 0;
    frame->offset.z = 0;
    frame->value    = 0.00;
    frame->last_dir = dir;

    // Init
    from = start;

    // Handle the distance
    while(++frame->value <= max_dist)
    {
        // No exit?
        if (!(exit = get_exit(from, dir)))
            break;

        // Exit closed?
        if (!e_closed && IS_SET(exit->exit_info, EX_CLOSED))
            break;

        // No target?
        if (!(to = exit->to_room))
            break;

        // Update Frame
        frame->target = to;
        frame->offset = frame->offset + dir;

        // Found
        if (callback->search(frame))
        {
            found = true;
            break;
        }
        from = to;
    }

    // Cleanup
    delete frame;
}

/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
 * Search Callbacks
 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */

/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
 * Scan
 */
void do_scan2( CHAR_DATA * ch, char *argument )
{
    srch_scan cb(ch);
    char arg[MAX_INPUT_LENGTH];
    dir_types dir;

    argument = one_argument(argument, arg);

    if (!str_cmp(arg, "BFS"))
    {
        send_to_char("Using BFS Search:\r\n", ch);
        search_BFS::search(ch->in_room, &cb, 4, false);
    }
    else if (!str_cmp(arg, "DIR"))
    {
        send_to_char("Using DIR Search:\r\n", ch);

        dir = (dir_types)get_dir(argument);
        search_DIR::search(ch->in_room, &cb, dir, 4, false);
    }
    else
    {
        send_to_char("Using LOS Search:\r\n", ch);
        search_LOS::search(ch->in_room, &cb, 4, false);
    }

    if (!cb.found)
        send_to_char("Nobody.", ch);
}

srch_scan::srch_scan(CHAR_DATA *p_actor)
{
    actor = p_actor;
    found = 0;
}

bool srch_scan::search(search_frame *frame)
{
    CHAR_DATA *target;

    if (!frame->target->first_person)
        return false;

    ch_printf(actor, "  %d %s\r\n", (int)frame->value, dir_name[frame->get_dir()]);
    send_to_char("--------------------\r\n", actor);

    for (target = frame->target->first_person; target; target = target->next_in_room)
    {
        if (target == actor)
            continue;
        ch_printf(actor, "%s\r\n", target->short_descr);
        found++;
    }
    return false;
}

/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
 * Map
 */
void do_map( CHAR_DATA * ch, char *argument )
{
    srch_map cb;
    char arg[MAX_INPUT_LENGTH];
    dir_types dir;

    argument = one_argument(argument, arg);

    if (!str_cmp(arg, "BFS"))
    {
        send_to_char("Using BFS Search:\r\n", ch);
        search_BFS::search(ch->in_room, &cb, 4, false);
    }
    else if (!str_cmp(arg, "DIR"))
    {
        send_to_char("Using DIR Search:\r\n", ch);

        dir = (dir_types)get_dir(argument);
        search_DIR::search(ch->in_room, &cb, dir, 4, false);
    }
    else
    {
        send_to_char("Using LOS Search:\r\n", ch);
        search_LOS::search(ch->in_room, &cb, 4, false);
    }

    // Output map
    ch_printf(ch,
        "-------\r\n|%-5.5s|\r\n|%-5.5s|\r\n|%-5.5s|\r\n|%-5.5s|\r\n|%-5.5s|\r\n-------\r\n",
        cb.buf, cb.buf+5, cb.buf+10, cb.buf+15, cb.buf+20);
}

srch_map::srch_map(void)
{
    int i;
    for (i=0; i<25; i++)
        buf[i] = ' ';
    buf[12] = '#';
}

bool srch_map::search(search_frame *frame)
{
    int x,y,i;

    // No "Z" movement allowed
    if (frame->offset.z)
        return false;

    // Localize
    x = frame->offset.x;
    y = frame->offset.y;

    // X/Y constraints
    if (x > 2 || x < -2)
        return false;
    if (y > 2 || y < -2)
        return false;

    // Normalize (0 to 4 instead of -2 to 2)
    x += 2;
    y += 2;

    // Generate array position.
    // Flip the y (so north is up, south is down)
    i  = ((4-y)*5)+(x%5);

    // Already found
    if (buf[i] != ' ')
        return false;

    // Update map
    buf[i] = '.';
    return false;
}