text: /*-------------------------------------------------------------------------
   *
   * geqo_selection.c
   *	  linear selection scheme for the genetic query optimizer
   *
   * Portions Copyright (c) 1996-2021, PostgreSQL Global Development Group
   * Portions Copyright (c) 1994, Regents of the University of California
   *
   * src/backend/optimizer/geqo/geqo_selection.c
   *
   *-------------------------------------------------------------------------
   */
  
  /* contributed by:
     =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
     *  Martin Utesch				 * Institute of Automatic Control	   *
     =							 = University of Mining and Technology =
     *  utesch@aut.tu-freiberg.de  * Freiberg, Germany				   *
     =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
   */
  
  /* this is adopted from D. Whitley's Genitor algorithm */
  
  /*************************************************************/
  /*															 */
  /*	Copyright (c) 1990										 */
  /*	Darrell L. Whitley										 */
  /*	Computer Science Department								 */
  /*	Colorado State University								 */
  /*															 */
  /*	Permission is hereby granted to copy all or any part of  */
  /*	this program for free distribution.   The author's name  */
  /*	and this copyright notice must be included in any copy.  */
  /*															 */
  /*************************************************************/
  
  #include "postgres.h"
  
  #include <math.h>
  
  #include "optimizer/geqo_copy.h"
  #include "optimizer/geqo_random.h"
  #include "optimizer/geqo_selection.h"
  
  static int	linear_rand(PlannerInfo *root, int max, double bias);
  
  
  /*
   * geqo_selection
   *	 according to bias described by input parameters,
   *	 first and second genes are selected from the pool
   */
  void
  geqo_selection(PlannerInfo *root, Chromosome *momma, Chromosome *daddy,
  			   Pool *pool, double bias)
  {
  	int			first,
  				second;
  
  	first = linear_rand(root, pool->size, bias);
  	second = linear_rand(root, pool->size, bias);
  
  	/*
  	 * Ensure we have selected different genes, except if pool size is only
  	 * one, when we can't.
  	 *
  	 * This code was observed to hang up in an infinite loop when the
  	 * platform's implementation of erand48() was broken.  We now always use
  	 * our own version.
  	 */
  	if (pool->size > 1)
  	{
  		while (first == second)
  			second = linear_rand(root, pool->size, bias);
  	}
  
  	geqo_copy(root, momma, &pool->data[first], pool->string_length);
  	geqo_copy(root, daddy, &pool->data[second], pool->string_length);
  }
  
  /*
   * linear_rand
   *	  generates random integer between 0 and input max number
   *	  using input linear bias
   *
   *	  bias is y-intercept of linear distribution
   *
   *	  probability distribution function is: f(x) = bias - 2(bias - 1)x
   *			 bias = (prob of first rule) / (prob of middle rule)
   */
  static int
  linear_rand(PlannerInfo *root, int pool_size, double bias)
  {
  	double		index;			/* index between 0 and pool_size */
  	double		max = (double) pool_size;
  
  	/*
  	 * If geqo_rand() returns exactly 1.0 then we will get exactly max from
  	 * this equation, whereas we need 0 <= index < max.  Also it seems
  	 * possible that roundoff error might deliver values slightly outside the
  	 * range; in particular avoid passing a value slightly less than 0 to
  	 * sqrt(). If we get a bad value just try again.
  	 */
  	do
  	{
  		double		sqrtval;
  
  		sqrtval = (bias * bias) - 4.0 * (bias - 1.0) * geqo_rand(root);
  		if (sqrtval > 0.0)
  			sqrtval = sqrt(sqrtval);
  		index = max * (bias - sqrtval) / 2.0 / (bias - 1.0);
  	} while (index < 0.0 || index >= max);
  
  	return (int) index;
  }
  