<?php
/*
 * Name: Friend Analyzer Class
 * Author: Caleb Mingle
 * Date: 4/14/2011 @ 10:31 PM.
 */
class Analyzer {
    private $_data;
    private $_steps;
    private $_friends;
    private $_path;
    private $_startFriend;
    private $_endFriend;
    private $_delimeter;
    private $_parents;
    private $_checked;
    private $_tmpPath;
    private $_verbose;

    function __construct($file, $delimeter = '    ', $verbose = false) {
        $this->_friends   = array();
        $this->_data      = @file_get_contents($file);
        $this->_delimeter = $delimeter;
        $this->_verbose   = $verbose;
        $this->__processFriends();
        $this->_steps     = 2;
        $this->_parents   = array();
    }

    /*
     * This will find the path.  Will check to see if startFriend is a direct friend to endFriend,
     * then process from there.
     */
    public function findPath($startFriend, $endFriend) {
        $this->_startFriend = $startFriend;
        $this->_endFriend   = $endFriend;

        if(in_array($endFriend, $this->_friends[$startFriend])) {
            $this->_path[] = $startFriend;
            $this->_path[] = $endFriend;
            return;
        }

        $check = $this->__match($startFriend);

        if(!$check === false) {
            $key = array_keys($check);
            $key = $this->_friends[$this->_startFriend][$key[0]];
            $this->_steps++;

            $this->_path[] = $this->_startFriend;
            $this->_path[] = $key;
            $this->_path[] = $this->_endFriend;
            return;
        }
        $this->_path[] = $this->_startFriend;

        $this->__processInitialFriends();

        $this->_path[] = $this->_endFriend;
    }

    /*
     * Since we know that someone HAS to be friends with our startFriend, we need to start here.
     * We start by procesing all of the friends of startFriend, and their friends.
     */
    private function __processInitialFriends() {
        $start_friends = $this->_friends[$this->_startFriend];

        if($this->_verbose) {
            echo "<pre>";
            print_r($this->_friends);
        }

        $this->log("__processInitialFriends()", "Processing friends for {$this->_startFriend}.");

        $this->_checked[] = $this->_startFriend;

        foreach($start_friends as $subfriend) {

            if(!$this->__processFriend($subfriend)) {
                $this->log("__processInitialFriends()", "Failed for {$subfriend}.");
                $this->_path  = array($this->_startFriend);
                $this->_steps = 0;
            } else {
                break;
            }
        }

        $this->__optimizePath();
    }

    /*
     * Makes sure there are NO shorter paths to the target before reporting back.
     */
    private function __optimizePath() {
        $temp_path = array();

        $index      = 1;
        $stop       = count($this->_path) - 1;
        $is_counter = 0;
        $last_added = 0;

        foreach($this->_path as $friend) {

            for($i = $index; $i <= $stop; $i++) {
                $is_counter++;
                if(in_array($friend, $this->_friends[$this->_path[$i]])) {
                    if(!in_array($this->_path[$i], $temp_path)) {
                        $temp_path[$friend] = $this->_path[$i];
                    }
                }
            }

            $is_counter = 0;
            $index++;
        }

        $this->_path   = array();
        $this->_path[] = $this->_startFriend;
        $this->_path   = array_merge($this->_path, $temp_path);

    }

    /*
     * Process individual friend, report back.
     */
    private function __processFriend($friend) {
        $match = $this->__match($friend);

        $this->_checked[] = $friend;

        if(!($match === false)) {
            $this->log("__processFriend({$friend})", "Match found on {$friend}.");



            $key = array_keys($match);
            $key = $key[0];
            $key = $this->_friends[$friend][$key];
            $this->_parents[$key] = $friend;

            $this->__processParents($key);
            $this->_tmpPath = array_reverse($this->_tmpPath);
            $this->_path    = array_merge($this->_path, $this->_tmpPath);

            $this->_steps++;
            $this->_path[] = $key;

            return true;
        }

        $this->log("__processFriend($friend)", "No match found for {$friend}.");

        $friends = $this->_friends[$friend]; // friends of Susie.

        foreach($friends as $subfriend) {
            $this->log("__processFriend($friend)", "Processing subfriend: {$subfriend}.");

            if(in_array($subfriend, $this->_checked)) {
                $this->log("__processFriend($friend)", "Already checked: {$subfriend}");
                continue;
            }

            $this->_checked[] = $subfriend;
            $this->_parents[$subfriend] = $friend;

            if($this->__processFriend($subfriend)) {
                return true;
            } else {
                $this->log("__processFriend({$subfriend})", "Failed for {$subfriend}.");
            }
        }

    }

    /*
     * Will process the hierarchy of people above $friend.  Recursive.
     */
    private function __processParents($friend) {
        if(!key_exists($friend, $this->_parents)) {
            return;
        } else {
            $this->_steps++;
            $this->_tmpPath[] = $this->_parents[$friend];
            $this->__processParents($this->_parents[$friend]);
        }
    }

    /*
     * This will determine if there are matches (intersection) in the current friends AND the target friends.
     * Will return either false OR the compare array.
     */
    private function __match($current_index) {
        $compare = array_intersect($this->_friends[$current_index], $this->_friends[$this->_endFriend]);
        return (!count($compare)) ? false : $compare;
    }

    /*
     * Process friends function.
     * This will split the file into an array based on new lines, then create our relationships.
     */
    private function __processFriends() {
        $lines = explode("\n", $this->_data);

        foreach($lines as $line) {
            if(!empty($line)) {
                $friend_data = explode($this->_delimeter, $line);
                $left  = trim($friend_data[0]);
                $right = trim($friend_data[1]);

                $this->_friends[$left][] = $right; // adds the right side as a new friend of left.
                $this->_friends[$right][] = $left; // adds the left side as a new friend of right.
            }
        }
    }

    /*
     * Will return the path array for processing.
     */
    public function getPath() {
        return $this->_path;
    }

    /*
     * Will return the steps taken.
     */
    public function getSteps() {
        return $this->_steps;
    }

    /*
     * Used in verbose mode to output information.
     */
    private function log($function, $message) {
        if($this->_verbose) {
            echo ">>> {$function}: {$message}<br />";
        }
    }
}