Adding upstream version 15.5.upstream/15.5

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 123 insertions, 0 deletions

diff --git a/src/backend/optimizer/geqo/geqo_cx.c b/src/backend/optimizer/geqo/geqo_cx.c
new file mode 100644
index 0000000..34cc53a
--- /dev/null
+++ b/src/backend/optimizer/geqo/geqo_cx.c
@@ -0,0 +1,123 @@
+/*------------------------------------------------------------------------
+*
+* geqo_cx.c
+*
+*	 cycle crossover [CX] routines;
+*	 CX operator according to Oliver et al
+*	 (Proc 2nd Int'l Conf on GA's)
+*
+* src/backend/optimizer/geqo/geqo_cx.c
+*
+*-------------------------------------------------------------------------
+*/
+
+/* contributed by:
+   =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
+   *  Martin Utesch				 * Institute of Automatic Control	   *
+   =							 = University of Mining and Technology =
+   *  utesch@aut.tu-freiberg.de  * Freiberg, Germany				   *
+   =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
+ */
+
+/* the cx algorithm is adopted from Genitor : */
+/*************************************************************/
+/*															 */
+/*	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 "optimizer/geqo_random.h"
+#include "optimizer/geqo_recombination.h"
+
+#if defined(CX)
+
+/* cx
+ *
+ *	 cycle crossover
+ */
+int
+cx(PlannerInfo *root, Gene *tour1, Gene *tour2, Gene *offspring,
+   int num_gene, City * city_table)
+{
+	int			i,
+				start_pos,
+				curr_pos;
+	int			count = 0;
+	int			num_diffs = 0;
+
+	/* initialize city table */
+	for (i = 1; i <= num_gene; i++)
+	{
+		city_table[i].used = 0;
+		city_table[tour2[i - 1]].tour2_position = i - 1;
+		city_table[tour1[i - 1]].tour1_position = i - 1;
+	}
+
+	/* choose random cycle starting position */
+	start_pos = geqo_randint(root, num_gene - 1, 0);
+
+	/* child inherits first city  */
+	offspring[start_pos] = tour1[start_pos];
+
+	/* begin cycle with tour1 */
+	curr_pos = start_pos;
+	city_table[(int) tour1[start_pos]].used = 1;
+
+	count++;
+
+	/* cx main part */
+
+
+/* STEP 1 */
+
+	while (tour2[curr_pos] != tour1[start_pos])
+	{
+		city_table[(int) tour2[curr_pos]].used = 1;
+		curr_pos = city_table[(int) tour2[curr_pos]].tour1_position;
+		offspring[curr_pos] = tour1[curr_pos];
+		count++;
+	}
+
+
+/* STEP 2 */
+
+	/* failed to create a complete tour */
+	if (count < num_gene)
+	{
+		for (i = 1; i <= num_gene; i++)
+		{
+			if (!city_table[i].used)
+			{
+				offspring[city_table[i].tour2_position] =
+					tour2[(int) city_table[i].tour2_position];
+				count++;
+			}
+		}
+	}
+
+
+/* STEP 3 */
+
+	/* still failed to create a complete tour */
+	if (count < num_gene)
+	{
+
+		/* count the number of differences between mom and offspring */
+		for (i = 0; i < num_gene; i++)
+			if (tour1[i] != offspring[i])
+				num_diffs++;
+	}
+
+	return num_diffs;
+}
+
+#endif							/* defined(CX) */