/* -*- Mode: C; tab-width: 4 -*- */
/* rubik --- Shows a auto-solving Rubik's cube */

#if !defined( lint ) && !defined( SABER )
static const char sccsid[] = "@(#)rubik.c	4.14 99/04/27 xlockmore";

#endif

#undef DEBUG_LISTS

/*-
 * Permission to use, copy, modify, and distribute this software and its
 * documentation for any purpose and without fee is hereby granted,
 * provided that the above copyright notice appear in all copies and that
 * both that copyright notice and this permission notice appear in
 * supporting documentation.
 *
 * This file is provided AS IS with no warranties of any kind.  The author
 * shall have no liability with respect to the infringement of copyrights,
 * trade secrets or any patents by this file or any part thereof.  In no
 * event will the author be liable for any lost revenue or profits or
 * other special, indirect and consequential damages.
 *
 * This mode shows an auto-solving rubik's cube "puzzle". If somebody
 * intends to make a game or something based on this code, please let me
 * know first, my e-mail address is provided in this comment. Marcelo.
 *
 * Thanks goes also to Brian Paul for making it possible and inexpensive
 * to use OpenGL at home.
 *
 * Since I'm not a native English speaker, my apologies for any grammatical
 * mistake.
 *
 * My e-mail address is
 * m-vianna@usa.net
 *
 * Marcelo F. Vianna (Jul-31-1997)
 *
 * Revision History:
 * 27-Apr-99: LxMxN stuff added.
 * 26-Sep-98: Added some more movement (the cube does not stay in the screen
 *            center anymore. Also fixed the scale problem imediatelly after
 *            shuffling when the puzzle is solved.
 * 08-Aug-97: Now has some internals from xrubik by David Bagley
 *            This should make it easier to add features.
 * 02-Aug-97: Now behaves more like puzzle.c: first show the cube being
 *            shuffled and then being solved. A mode specific option was added:
 *            "+/-hideshuffling" to provide the original behavior (in which
 *            only the solution is shown).
 *            The color labels corners are now rounded.
 *            Optimized the cubit() routine using glLists.
 * 01-Aug-97: Shuffling now avoids movements that undoes the previous movement
 *            and three consecutive identical moves (which is pretty stupid).
 *            improved the "cycles" option in replacement of David's hack,
 *            now rp->anglestep is a GLfloat, so this option selects the
 *            "exact" number of frames that a rotation (movement) takes to
 *            complete.
 * 30-Jul-97: Initial release, there is no algorithm to solve the puzzle,
 *            instead, it randomly shuffle the cube and then make the
 *            movements in the reverse order.
 *            The mode was written in 1 day (I got sick and had the day off).
 *            There was not much to do since I could not leave home... :)
 *
 */

/*-
 * Color labels mapping:
 * =====================
 *
 *                       +------------+
 *                       |0-->        |
 *                       ||           |
 *                       |v           |
 *                       |   TOP(0)   |
 *                       |            |
 *                       |            |
 *                       |           8|
 *           +-----------+------------+-----------+
 *           |0-->       |0-->        |0-->       |
 *           ||          ||           ||          |
 *           |v          |v           |v          |
 *           |  LEFT(1)  |  FRONT(2)  |  RIGHT(3) |
 *           |           |            |           |
 *           |           |            |           |
 *           |          8|           8|          8|
 *           +-----------+------------+-----------+
 *                       |0-->        |
 *                       ||           |
 *                       |v           |
 *                       |  BOTTOM(4) |
 *                       |            |
 *                       |            |
 *                       |           8|         +---+---+---+
 *                       +------------+         |   |   |   |
 *                       |0-->        |         | 0 | 1 | 2 |
 *                       ||           |         |---+---+---+
 *                       |v           |         |  xxxxx(N) |
 *                       |   BACK(5)  |         | 3 | 4 | 5 |
 *                       |            |         +---+---+---+
 *                       |            |         |   |   |   |
 *                       |           8|         | 6 | 7 | 8 |
 *                       +------------+         +---+---+---+
 *
 *  Map to 3d
 *  FRONT  => X, Y
 *  BACK   => X, Y
 *  LEFT   => Z, Y
 *  RIGHT  => Z, Y
 *  TOP    => X, Z
 *  BOTTOM => X, Z
 */

/*-
 * PURIFY 3.0a on SunOS4 reports an unitialized memory read on each of
 * the glCallList() functions below when using MesaGL 2.1.  This has
 * been fixed in MesaGL 2.2 and later releases.
 */

/*-
 * due to a Bug/feature in VMS X11/Intrinsic.h has to be placed before xlock.
 * otherwise caddr_t is not defined correctly
 */
#include <X11/Intrinsic.h>

#ifdef STANDALONE
#define PROGCLASS "Rubik"
#define HACK_INIT init_rubik
#define HACK_DRAW draw_rubik
#define rubik_opts xlockmore_opts
#define DEFAULTS "*delay: 40000 \n" \
 "*count: -30 \n" \
 "*cycles: 5 \n" \
 "*size: -6 \n"
#include "xlockmore.h"		/* from the xscreensaver distribution */
#else /* !STANDALONE */
#include "xlock.h"		/* from the xlockmore distribution */
#include "vis.h"
#endif /* !STANDALONE */

#ifdef MODE_rubik

#define DEF_SIZEX     "0"
#define DEF_SIZEY     "0"
#define DEF_SIZEZ     "0"
#define DEF_HIDESHUFFLING     "False"

static int sizex;
static int sizey;
static int sizez;
static Bool hideshuffling;

static XrmOptionDescRec opts[] =
{
        {"-sizex", ".rubik.sizex", XrmoptionSepArg, (caddr_t) NULL},
        {"-sizey", ".rubik.sizey", XrmoptionSepArg, (caddr_t) NULL},
        {"-sizez", ".rubik.sizez", XrmoptionSepArg, (caddr_t) NULL},
	{"-hideshuffling", ".rubik.hideshuffling", XrmoptionNoArg, (caddr_t) "on"},
	{"+hideshuffling", ".rubik.hideshuffling", XrmoptionNoArg, (caddr_t) "off"}
};

static argtype vars[] =
{
	{(caddr_t *) & sizex, "sizex", "SizeX", DEF_SIZEX, t_Int},
	{(caddr_t *) & sizey, "sizey", "SizeY", DEF_SIZEY, t_Int},
	{(caddr_t *) & sizez, "sizez", "SizeZ", DEF_SIZEZ, t_Int},
	{(caddr_t *) & hideshuffling, "hideshuffling", "Hideshuffling", DEF_HIDESHUFFLING, t_Bool}
};

static OptionStruct desc[] =
{
	{"-sizex num", "number of cubies along x axis (overrides size)"},
	{"-sizey num", "number of cubies along y axis (overrides size)"},
	{"-sizez num", "number of cubies along z axis (overrides size)"},
	{"-/+hideshuffling", "turn on/off hidden shuffle phase"}
};

ModeSpecOpt rubik_opts =
{sizeof opts / sizeof opts[0], opts, sizeof vars / sizeof vars[0], vars, desc};

#ifdef USE_MODULES
ModStruct   rubik_description =
{"rubik", "init_rubik", "draw_rubik", "release_rubik",
 "draw_rubik", "change_rubik", NULL, &rubik_opts,
 10000, -30, 5, -6, 64, 1.0, "",
 "Shows an auto-solving Rubik's Cube", 0, NULL};

#endif

#define VectMul(X1,Y1,Z1,X2,Y2,Z2) (Y1)*(Z2)-(Z1)*(Y2),(Z1)*(X2)-(X1)*(Z2),(X1)*(Y2)-(Y1)*(X2)
#define sqr(A)                     ((A)*(A))

#ifndef Pi
#define Pi                         M_PI
#endif


#define ACTION_SOLVE    1
#define ACTION_SHUFFLE  0

#define DELAY_AFTER_SHUFFLING  5
#define DELAY_AFTER_SOLVING   20

/*************************************************************************/

#define MINSIZE 2
#define MAXSIZEX (rp->sizex)
#define MAXSIZEY (rp->sizey)
#define MAXSIZEZ (rp->sizez)
#define AVSIZE ((rp->sizex+rp->sizey+rp->sizez)/3.0)     /* Use of this should be minimized */
#define MAXMAXSIZE (MAX(MAXSIZEX,MAX(MAXSIZEY,MAXSIZEZ)))
#define MAXSIZEXY (MAXSIZEX*MAXSIZEY)
#define MAXSIZEYZ (MAXSIZEY*MAXSIZEZ)
#define MAXSIZEZX (MAXSIZEZ*MAXSIZEX)
#define LASTX (MAXSIZEX-1)
#define LASTY (MAXSIZEY-1)
#define LASTZ (MAXSIZEZ-1)
/* These are not likely to change but... */
#define FIRSTX 0
#define FIRSTY 0
#define FIRSTZ 0

#define Scale4Window               (0.9/AVSIZE)
#define Scale4Iconic               (2.1/AVSIZE)

#define MAXORIENT 4		/* Number of orientations of a square */
#define MAXFACES 6		/* Number of faces */

/* Directions relative to the face of a cubie */
#define TOP 0
#define RIGHT 1
#define BOTTOM 2
#define LEFT 3
#define CW (MAXORIENT+1)
#define HALF (MAXORIENT+2)
#define CCW (2*MAXORIENT-1)

#define TOP_FACE 0
#define LEFT_FACE 1
#define FRONT_FACE 2
#define RIGHT_FACE 3
#define BOTTOM_FACE 4
#define BACK_FACE 5
#define NO_FACE (MAXFACES)
#define NO_ROTATION (2*MAXORIENT)
#define NO_DEPTH MAXMAXSIZE

#define REVX(a) (MAXSIZEX - a - 1)
#define REVY(a) (MAXSIZEY - a - 1)
#define REVZ(a) (MAXSIZEZ - a - 1)

typedef struct _RubikLoc {
	int         face;
	int         rotation;	/* Not used yet */
} RubikLoc;

typedef struct _RubikRowNext {
	int         face, direction, sideFace;
} RubikRowNext;

typedef struct _RubikMove {
	int         face, direction;
	int         position;
} RubikMove;

typedef struct _RubikSlice {
	int         face, rotation;
	int         depth;
} RubikSlice;

/*-
 * Pick a face and a direction on face the next face and orientation
 * is then known.
 */
static RubikLoc slideNextRow[MAXFACES][MAXORIENT] =
{
	{
		{5, TOP},
		{3, RIGHT},
		{2, TOP},
		{1, LEFT}},
	{
		{0, RIGHT},
		{2, TOP},
		{4, LEFT},
		{5, BOTTOM}},
	{
		{0, TOP},
		{3, TOP},
		{4, TOP},
		{1, TOP}},
	{
		{0, LEFT},
		{5, BOTTOM},
		{4, RIGHT},
		{2, TOP}},
	{
		{2, TOP},
		{3, LEFT},
		{5, TOP},
		{1, RIGHT}},
	{
		{4, TOP},
		{3, BOTTOM},
		{0, TOP},
		{1, BOTTOM}}
};

/*-
 * Examine cubie 0 on each face, its 4 movements (well only 2 since the
 * other 2 will be opposites) and translate it into slice movements).
 * CW = DEEP Depth CCW == SHALLOW Depth with reference to faces 0, 1, and 2
 */
static RubikLoc rotateSlice[MAXFACES][MAXORIENT / 2] =
{
	{
		{1, CCW},
		{2, CW},
	},
	{
		{2, CW},
		{0, CCW},
	},
	{
		{1, CCW},
		{0, CCW},
	},
	{
		{2, CCW},
		{0, CCW},
	},
	{
		{1, CCW},
		{2, CCW},
	},
	{
		{1, CCW},
		{0, CW},
	}
};

/*-
 * Rotate face clockwise by a number of orients, then the top of the
 * face then points to this face
 */
static int  rowToRotate[MAXFACES][MAXORIENT] =
{
	{3, 2, 1, 5},
	{2, 4, 5, 0},
	{3, 4, 1, 0},
	{5, 4, 2, 0},
	{3, 5, 1, 2},
	{3, 0, 1, 4}
};

/*
 * This translates a clockwise move to something more manageable
 */
static RubikRowNext rotateToRow[MAXFACES] =	/*CW to min face */
{
	{1, LEFT, TOP},
	{0, BOTTOM, RIGHT},
	{0, RIGHT, BOTTOM},
	{0, TOP, LEFT},
	{1, RIGHT, BOTTOM},
	{0, LEFT, TOP}
};

typedef struct {
	GLint       WindH, WindW;
	GLfloat     step;
	RubikMove  *moves;
	int         storedmoves;
	int         degreeTurn;
	int         shufflingmoves;
	int         sizex, sizey, sizez;
	float       avsize, avsizeSq;
	int         action;
	int         done;
	GLfloat     anglestep;
	RubikLoc   *cubeLoc[MAXFACES];
	RubikLoc   *rowLoc[MAXORIENT];
	RubikMove   movement;
	GLfloat     rotatestep;
	GLfloat     PX, PY, VX, VY;
	GLXContext *glx_context;
	int         AreObjectsDefined[1];
} rubikstruct;

static float front_shininess[] =
{60.0};
sta