<?php
// ----------------------------------------------------------------------
// Copyright (C) 2006 by Khaled Al-Shamaa.
// http://www.al-shamaa.com/
// ----------------------------------------------------------------------
// LICENSE

// This program is open source product; you can redistribute it and/or
// modify it under the terms of the GNU General Public License (GPL)
// as published by the Free Software Foundation; either version 2
// of the License, or (at your option) any later version.

// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

// To read the license please visit http://www.gnu.org/copyleft/gpl.html
// ----------------------------------------------------------------------
// Filename: oods.class.php
// Original  Author(s): Khaled Al-Sham'aa <hide@address.com>
// Purpose:  Utility class to implement oods algorithem developed by  F. Thomas Bruss
//	      used to a stopping rule problem has a finite horizon
// ----------------------------------------------------------------------
// Keywords: Unimodality, odds-algorithm, pattern correlation, secretary problems,
//           optimality principle, differential equations, generating functions, Pascal
//           processes, upper bounds, lower bounds, search, investment, venture capital.
//           AMS suject classification
// Source:  "Le bon choix ... raisonne", Pour la Science 2005/9
// ----------------------------------------------------------------------

class Oods {
    var $n;           // Total events number
    var $k;           // Current event counter
    var $probK;       // Probability good event chance
    var $lastEvent;   // Type of last event (Good or Bad)
    var $Gk;          // Good event counter up to now
    var $Rs;          // Total sum of win ratio chance
    var $Qs;          // Total sum of bad event chance

    /**
    * @return NULL
    * @param Integer $n Total number of events stream
    * @param String $probK Set a new good event probability value. 
    *               You can use formulas like the following
    *        Constant: 0.2     Related to k (event order): 1/($k+1)        Unknown: NULL
    * @desc Class constructor
    * @author Khaled Al-Shamaa
    */
    function Oods($n, $probK = NULL){
        $this->n     = $n;
        $this->probK = $probK;
    }

    /**
    * @return NULL
    * @param Boolean $type TRUE if current event is good, and FALSE if it is bad event
    * @desc Update object status to reflect current situation of events stream
    * @author Khaled Al-Shamaa
    */
    function event($type = false){
        $this->lastEvent = $type;
        $this->k++;

        if(is_null($this->probK) && $type == true){
            $this->Gk++;
        }
    }

    /**
    * @return NULL
    * @param String $probK Set a new good event probability value. 
    *               You can use formulas like the following
    *        Constant: 0.2     Related to k (event order): 1/($k+1)        Unknown: NULL
    * @desc Change good events probablity equation
    * @author Khaled Al-Shamaa
    */
    function setProb($probK = NULL){
        $this->probK = $probK;
    }

    /**
    * @return List($accept, $w) where $accept is TRUE when you have to select current event, 
    *         and FALSE when you have to leave it. On the other hand $w will return number
    *         refer to chance to be an optimum answer (between 0 and 1), $w value is NULL when
    *         you should not select current event, or if good event probability is unknown
    * @desc  Find out if you have to select current event to win, and what is the probability
    *        that you make an optimum selection
    * @author Khaled Al-Shamaa
    */
    function doYouAccept(){
        $accept = false;
        $w = NULL;
        if($this->lastEvent == true){
            if(is_null($this->probK)){
                $side1 = $this->n - $this->k;
                $side2 = ($this->k + 1 + $this->Gk)/$this->Gk;
                if($side1 > $side2){
                    $accept = true;

                    // Unfortitily I don't know how I can calculate the chance that algorithem 
                    // selection is an optimum answer
                    $w = NULL;
                }else{
                    $accept = false;
                    $w = NULL;
                }
            }else{
                $k = $this->n;
                $this->Rs = 0;
                $this->Qs = 1;

                while($this->Rs < 1 && $k > 1){
                    // Calculate the chance for this event k to be a good one
                    eval('$pk='.$this->probK.';');

                    // Calculate the chance for this event k to be a bad one
                    $qk = 1 - $pk;

                    // Calculate the win chance
                    $rk = $pk / $qk;

                    $this->Rs += $rk;
                    $this->Qs *= $qk;

                    $k--;
                }

                $s = $k;

                if($this->k > $s){
                    $accept = true;

                    // Calculate the chance that algorithem selection is an optimum answer
                    $w = $this->Qs * $this->Rs;
                }else{
                    $accept = false;
                    $w = NULL;
                }
            }
        }
        
        return array($accept, $w);
    }
}
?>