#import "AStarSearch.h"
#import "Route.h"
#import "Destination.h"
#import "GameMap.h"


@implementation AStarSearch

@synthesize nodeGraph;
@synthesize sourceNode, targetNode, pathByNode;
@synthesize pathWeight;


/* Init. */


/* Override the default init and zero/null properties out. */
- (id) init
{
    if (self == [super init])
    {
        sourceNode = nil;
        targetNode = nil;
        nodeGraph  = nil;
        pathWeight = 0;
        pathByNode = nil;
    }
    
    return self;
}


/* The main init method - This should be the one used. */
-(id) initWithGraph:(m42Graph *)graph andStartNode:(AStarNode *)startNode andEndNode:(AStarNode *)endNode
{
    if (self == [self init])
    {
        sourceNode = startNode;
        targetNode = endNode;
        nodeGraph  = graph;
    }
    
    return self;
}


/* Implementation / Workhorse. */


/* Apply A* with weighted hops to find the lowest and quickest solution. 
   This search works on a particular JSON DS. It also has knowledge of
   the Graph & Connection class. 
 
   Hop's are weighted simply by parent+1, where source = 1.
*/
-(void) search
{
    /* Used in the loop. */    
    NSMutableArray *nodesToCheck = [NSMutableArray arrayWithCapacity:20];
    NSMutableArray *nodesChecked = [NSMutableArray arrayWithCapacity:20];
    AStarNode *currentNode = nil;
    
    /* An array of nodes we have to check. */
    [nodesToCheck addObject:sourceNode];
    
    while([nodesToCheck count] > 0)
    {
        currentNode = [self lowestCostNodeInArray: nodesToCheck];
        
        [nodesChecked addObject:currentNode];
        [nodesToCheck removeObject: currentNode];
        
        /* Load all the locations from the current node. */
		// TODO: move this connection based shit out into the game
        NSArray *neighborNodeSet =  [(GameMap *)nodeGraph connectionsFrom:currentNode.nodeId];
        
        for (int i=0; i < [neighborNodeSet count]; i++)
        {
            /* Find all our neighbors and load their id's. */
            //id connection = nil;
            Route *connection = [neighborNodeSet objectAtIndex:i];
            
            AStarNode *anotherNode = [[AStarNode alloc] initWithWeight:currentNode.weight+1 
															// NOT SAFE, SEE ABOVE TODO.
														     andNodeId:((Destination *)connection.mDestination).mId
													   andParentNodeId:currentNode.nodeId andParentNode:currentNode];
             
            /* If our neighbor is the target, great, we've found a path. */
            if ([anotherNode.nodeId isEqualToString:targetNode.nodeId])
            {          
                pathByNode = anotherNode; /* We'll traverse it when necessary. */
                return; 
            }
            
            /* This is to make sure we don't test a neighbor twice. A* typically
               checks a single node at a time, but since we support mutltiple connections
               the code below makes sure we don't add an already processed node back into
               the list of "to process nodes". We also do this for nodes in the queue
               to be checked.
             */
            if (![self doesNode:anotherNode existInTargetNodeSet:nodesChecked] &&
                ![self doesNode:anotherNode existInTargetNodeSet:nodesToCheck])
            {
                [nodesToCheck addObject: anotherNode];
            }

            [anotherNode release];
        }
    } /* End while. */
}


/* Check the supplied NSMuteableArray of Nodes, for the existence of the supplied AStarNode.
   If we find a match return TRUE, otherwise return FALSE. err, YES/NO.
*/
-(Boolean) doesNode:(AStarNode *)node existInTargetNodeSet:(NSMutableArray *)targetNodeSet
{
    for (int n=0; n < [targetNodeSet count]; n++)
    {
        AStarNode *tmpNode;
        tmpNode = [targetNodeSet objectAtIndex:n];
        if (tmpNode.nodeId == node.nodeId)
        {
            return YES;
        }
    }
    
    return NO;
}


/* Return an NSArray where each member is an NString of the node name. 
   All the callee has to do is walk to each node name, in order.
*/
-(NSArray *) getPathToTarget
{
    NSMutableArray *pathToTarget = [NSMutableArray arrayWithCapacity:20];
    
    /* Because our Search() method returns when we locate a member node
       touching the destination node, the actual destination node is never
       added to the linked list. So here we will append the node data from 
       the init method to the array. 
     */
    [pathToTarget addObject:targetNode.nodeId];
    
    /* Walk 'up' the linked list, from destination to source. */
    while(pathByNode.parentNode != nil)
    {
        [pathToTarget addObject:pathByNode.cameFromNode];
        pathByNode = pathByNode.parentNode;
    }
    
    /* Reverse the order for the callee. */
    return [[pathToTarget reverseObjectEnumerator] allObjects];
}


-(int) getCostToTarget
{
    assert(!"fuck you");
}


/* Search an entire array of nodes and return the node with
   the lowest weight.
*/
-(AStarNode *) lowestCostNodeInArray:(NSMutableArray *) nodeSet
{
    /* Set a default value in the lowest node, so we have something
       to compare against. 
     */
    AStarNode *tmpLowest = [nodeSet objectAtIndex:0];
    AStarNode *currentNode;
    
    /* Iterate through all the nodes we have, and compare its weight
       against the temporary holder weight. If we find a weight <
       than the temp, we assign the value of the current node to that
       of the tmp node.
     */
    int nodeSetCount = [nodeSet count];
    int i;
    for (i=0; i<nodeSetCount; i++)
    {
        currentNode = [nodeSet objectAtIndex:i];
        if (currentNode.weight < tmpLowest.weight)
        {
            tmpLowest = currentNode;
        }
    }
    
    return tmpLowest;
}


/* Clean up. */
-(void) dealloc
{
    [nodeGraph release];
    [sourceNode release];
    [targetNode release];
    [pathByNode release];
    [super dealloc];

}
@end