Rubix-cube modelization library

As for now the library supports basic representation of a Rubix-cube The library is built for speed, most operations cost no allocations to perform. This does however mean that the library is NOT thread-safe and should be handled with the appropriate mutual-exclusion mechanisms to avoid memory corruption or unintended side-effects on a single cube.

The library supports the singmaster notation as a way to perform operations on a Rubix cube.

No solver is (yet) provided along with the library.

Introduced classes

class RubixCube

rubix :: RubixCube

In-memory representation of a Rubix Cube

Redefined classes

redef enum Int

rubix :: rubix $ Int

Native integer numbers.
redef class Sys

rubix :: rubix $ Sys

The main class of the program.

All class definitions

redef enum Int

rubix :: rubix $ Int

Native integer numbers.
class RubixCube

rubix $ RubixCube

In-memory representation of a Rubix Cube
redef class Sys

rubix :: rubix $ Sys

The main class of the program.
package_diagram rubix::rubix rubix console console rubix::rubix->console core core console->core ...core ... ...core->core a_star-m a_star-m a_star-m->rubix::rubix

Ancestors

module abstract_collection

core :: abstract_collection

Abstract collection classes and services.
module abstract_text

core :: abstract_text

Abstract class for manipulation of sequences of characters
module array

core :: array

This module introduces the standard array structure.
module bitset

core :: bitset

Services to handle BitSet
module bytes

core :: bytes

Services for byte streams and arrays
module circular_array

core :: circular_array

Efficient data structure to access both end of the sequence.
module codec_base

core :: codec_base

Base for codecs to use with streams
module codecs

core :: codecs

Group module for all codec-related manipulations
module collection

core :: collection

This module define several collection classes.
module core

core :: core

Standard classes and methods used by default by Nit programs and libraries.
module environ

core :: environ

Access to the environment variables of the process
module error

core :: error

Standard error-management infrastructure.
module exec

core :: exec

Invocation and management of operating system sub-processes.
module file

core :: file

File manipulations (create, read, write, etc.)
module fixed_ints

core :: fixed_ints

Basic integers of fixed-precision
module fixed_ints_text

core :: fixed_ints_text

Text services to complement fixed_ints
module flat

core :: flat

All the array-based text representations
module gc

core :: gc

Access to the Nit internal garbage collection mechanism
module hash_collection

core :: hash_collection

Introduce HashMap and HashSet.
module iso8859_1

core :: iso8859_1

Codec for ISO8859-1 I/O
module kernel

core :: kernel

Most basic classes and methods.
module list

core :: list

This module handle double linked lists
module math

core :: math

Mathematical operations
module native

core :: native

Native structures for text and bytes
module numeric

core :: numeric

Advanced services for Numeric types
module protocol

core :: protocol

module queue

core :: queue

Queuing data structures and wrappers
module range

core :: range

Module for range of discrete objects.
module re

core :: re

Regular expression support for all services based on Pattern
module ropes

core :: ropes

Tree-based representation of a String.
module sorter

core :: sorter

This module contains classes used to compare things and sorts arrays.
module stream

core :: stream

Input and output streams of characters
module text

core :: text

All the classes and methods related to the manipulation of text entities
module time

core :: time

Management of time and dates
module union_find

core :: union_find

union–find algorithm using an efficient disjoint-set data structure
module utf8

core :: utf8

Codec for UTF-8 I/O

Parents

module console

console :: console

Defines some ANSI Terminal Control Escape Sequences.

Children

module a_star-m

a_star-m

# Rubix-cube modelization library
#
# As for now the library supports basic representation of a Rubix-cube
# The library is built for speed, most operations cost no allocations to perform.
# This does however mean that the library is NOT thread-safe and should be handled
# with the appropriate mutual-exclusion mechanisms to avoid memory corruption
# or unintended side-effects on a single cube.
#
# The library supports the singmaster notation as a way to perform operations
# on a Rubix cube.
#
# No solver is (yet) provided along with the library.
module rubix

import console

private fun array1d_copy_to(fromarr: Array[Int], oarr: Array[Int]) do
	while oarr.length > fromarr.length do oarr.pop
	while oarr.length < fromarr.length do oarr.push 0
	fromarr.copy_to(0, fromarr.length, oarr, 0)
end

private fun front_face: Int do return 0
private fun left_face: Int do return 1
private fun top_face: Int do return 2
private fun right_face: Int do return 3
private fun bottom_face: Int do return 4
private fun back_face: Int do return 5

private fun top_ln: Int do return 0
private fun mid_ln: Int do return 1
private fun bottom_ln: Int do return 2

private fun left_col: Int do return 0
private fun mid_col: Int do return 1
private fun right_col: Int do return 2

private fun clock: Int do return 0
private fun counterclock: Int do return 1

private fun square: String do return once "■"

redef class Int

	# Returns a coloured square for a defined colour id
	#
	# Assume colours are:
	#
	# * Green -> 0
	# * White (replaced with light gray) -> 1
	# * Red -> 2
	# * Yellow -> 3
	# * Orange (replaced with purple) -> 4
	# * Blue -> 5
	#
	private fun rubix_colour: String do
		if self == 0 then return square.green
		if self == 1 then return square.light_gray
		if self == 2 then return square.red
		if self == 3 then return square.yellow
		if self == 4 then return square.purple
		if self == 5 then return square.blue
		abort
	end
end

# In-memory representation of a Rubix Cube
#
# Faces are represented in memory as if they were a flattened cube like:
#
# ~~~raw
#       B B B
#       B B B
#       B B B
#       U U U
#       U U U
#       U U U
# L L L F F F R R R
# L L L F F F R R R
# L L L F F F R R R
#       D D D
#       D D D
#       D D D
# ~~~
#
# All the commands detailed in the class respect the Singmaster notation
class RubixCube
	# Faces of the Cube
	#
	# 0 - Front
	# 1 - Left
	# 2 - Up
	# 3 - Right
	# 4 - Down
	# 5 - Back
	#
	# Each line is:
	#
	# 0 - Top line
	# 1 - Middle line
	# 2 - Down line
	var faces: Array[Array[Array[Int]]]

	# Build a new Rubix Cube with a solved layout
	init solved do
		var faces = new Array[Array[Array[Int]]]
		var colour = 0
		for i in [0 .. 6[ do
			var face = new Array[Array[Int]]
			faces.add face
			for j in [0 .. 3[ do
				var line = new Array[Int]
				for k in [0 .. 3[ do
					line.add colour
				end
				face.add line
			end
			colour += 1
		end
		init faces
	end

	# Build a new Rubix Cube with a scrambled layout
	#
	# NOTE: The layout is not random, but scrambled nonetheless
	init scrambled do
		var colours = once [0, 1, 2, 3, 4, 5]
		var colour_pos = 0
		var faces = new Array[Array[Array[Int]]]
		var increment = 1
		for i in [0 .. 6[ do
			var face = new Array[Array[Int]]
			faces.add face
			for j in [0 .. 3[ do
				var line = new Array[Int]
				for k in [0 .. 3[ do
					line.add colours[colour_pos]
					colour_pos += increment
					if colour_pos > 5 then
						increment = -1
						colour_pos = 5
					end
					if colour_pos < 0 then
						increment = 1
						colour_pos = 0
					end
				end
				face.add line
			end
		end
		init faces
	end

	# Reset the Rubix Cube to a solved position
	fun reset do
		for i in [0 .. 6[ do
			var face = faces[i]
			for j in [0 .. 3[ do
				var line = face[j]
				for k in [0 .. 3[ do
					line[k] = i
				end
			end
		end
	end

	# Checks if both objects are Rubix cubes and their content is equivalent
	#
	# NOTE: Rotationed versions are not yet considered equal
	redef fun ==(o) do
		if not o isa RubixCube then return false
		for mf in faces, tf in o.faces do
			for ml in mf, tl in tf do
				for mc in ml, tc in tl do if mc != tc then return false
			end
		end
		return true
	end

	# Is `self` a solved Rubix Cube ?
	fun is_solved: Bool do
		for face_id in [0 .. 6[ do
			var i = faces[face_id]
			var colour = i.first.first
			for j in [0 .. 3[ do
				var ln = i[j]
				for k in [0 .. 3[ do
					if ln[k] != colour then return false
				end
			end
		end
		return true
	end

	redef fun to_s do
		var buf = new Buffer
		buf.append(single_face(back_face))
		buf.append(single_face(top_face))
		buf.append(three_faces(left_face, front_face, right_face))
		buf.append(single_face(bottom_face))
		return buf.to_s
	end

	private fun single_face(face_id: Int): Text do
		var b = new Buffer
		var face = faces[face_id]
		for i in [0 .. 3[ do
			var ln = face[i]
			b.append("{" " * 6}{ln[0].rubix_colour} {ln[1].rubix_colour} {ln[2].rubix_colour}{" " * 6}\n")
		end
		return b
	end

	private fun three_faces(face1, face2, face3: Int): Text do
		var b = new Buffer
		var face_ids = [face1, face2, face3]
		for i in [0 .. 3[ do
			for j in face_ids do
				var face = faces[j]
				var ln = face[i]
				b.append("{ln[0].rubix_colour} {ln[1].rubix_colour} {ln[2].rubix_colour} ")
			end
			b.add '\n'
		end
		return b
	end

	private var rot_ln_buffer = new Array[Array[Int]].with_capacity(4)
	private fun rotate_line(ln_id: Int, direction: Int) do
		var line_data = rot_ln_buffer
		if line_data.is_empty then for i in [0 .. 4[ do line_data.add(new Array[Int])
		array1d_copy_to(faces[front_face][ln_id], line_data[0])
		array1d_copy_to(faces[left_face][ln_id], line_data[1])
		array1d_copy_to(faces[back_face][2 - ln_id], line_data[2])
		array1d_copy_to(faces[right_face][ln_id], line_data[3])
		if direction == counterclock then
			line_data[3].swap_at(0, 2)
			line_data[2].swap_at(0, 2)
			rot_ln_buffer.rotate_left
		else if direction == clock then
			line_data[1].swap_at(0, 2)
			line_data[2].swap_at(0, 2)
			rot_ln_buffer.rotate_right
		else
			abort
		end
		array1d_copy_to(line_data[0], faces[front_face][ln_id])
		array1d_copy_to(line_data[1], faces[left_face][ln_id])
		array1d_copy_to(line_data[2], faces[back_face][2 - ln_id])
		array1d_copy_to(line_data[3], faces[right_face][ln_id])
	end

	private var colbuf = new Array[Int].with_capacity(3)
	private fun coldata(face_id: Int, col_id: Int): Array[Int] do
		if colbuf.is_empty then for i in [0 .. 3[ do colbuf.add 0
		var face = faces[face_id]
		for i in [0 .. 3[ do colbuf[i] = face[i][col_id]
		return colbuf
	end

	private fun set_coldata(face_id, col_id: Int, coldata: Array[Int]) do
		var face = faces[face_id]
		for i in [0 .. 3[ do face[i][col_id] = coldata[i]
	end

	private var rot_col_buffer = new Array[Array[Int]].with_capacity(4)
	private fun rotate_column(col_id: Int, direction: Int) do
		var col_data = rot_col_buffer
		if col_data.is_empty then for i in [0 .. 4[ do col_data.add(new Array[Int])
		array1d_copy_to(coldata(front_face, col_id), rot_col_buffer[0])
		array1d_copy_to(coldata(top_face, col_id), rot_col_buffer[1])
		array1d_copy_to(coldata(back_face, col_id), rot_col_buffer[2])
		array1d_copy_to(coldata(bottom_face, col_id), rot_col_buffer[3])
		if direction == clock then
			rot_col_buffer.rotate_left
		else if direction == counterclock then
			rot_col_buffer.rotate_right
		else
			abort
		end
		set_coldata(front_face, col_id, rot_col_buffer[0])
		set_coldata(top_face, col_id, rot_col_buffer[1])
		set_coldata(back_face, col_id, rot_col_buffer[2])
		set_coldata(bottom_face, col_id, rot_col_buffer[3])
	end

	private var r90_cache = new Array[Array[Int]]
	private fun rotate_l90_face(face_id: Int) do
		var lines = r90_cache
		if lines.is_empty then for i in [0 .. 3[ do lines.add(new Array[Int])
		array1d_copy_to(faces[face_id][top_ln], lines[0])
		array1d_copy_to(faces[face_id][mid_ln], lines[1])
		array1d_copy_to(faces[face_id][bottom_ln], lines[2])
		for i in [0 .. 3[ do lines[i].swap_at(0, 2)
		set_coldata(face_id, left_col, lines[0])
		set_coldata(face_id, mid_col, lines[1])
		set_coldata(face_id, right_col, lines[2])
	end

	private fun rotate_r90_face(face_id: Int) do
		var lines = r90_cache
		if lines.is_empty then for i in [0 .. 3[ do lines.add(new Array[Int])
		array1d_copy_to(faces[face_id][top_ln], lines[0])
		array1d_copy_to(faces[face_id][mid_ln], lines[1])
		array1d_copy_to(faces[face_id][bottom_ln], lines[2])
		set_coldata(face_id, right_col, lines[0])
		set_coldata(face_id, mid_col, lines[1])
		set_coldata(face_id, left_col, lines[2])
	end

	# U command
	fun clock_U do
		rotate_line(top_ln, clock)
		rotate_r90_face(top_face)
	end

	# U' command
	fun cclock_U do
		rotate_line(top_ln, counterclock)
		rotate_l90_face(top_face)
	end

	# D command
	fun clock_D do
		rotate_line(bottom_ln, counterclock)
		rotate_r90_face(bottom_face)
	end

	# D' command
	fun cclock_D do
		rotate_line(bottom_ln, clock)
		rotate_l90_face(bottom_face)
	end

	# L command
	fun clock_L do
		rotate_column(left_col, clock)
		rotate_r90_face(left_face)
	end

	# L' command
	fun cclock_L do
		rotate_column(left_col, counterclock)
		rotate_l90_face(left_face)
	end

	# R command
	fun clock_R do
		rotate_column(right_col, counterclock)
		rotate_r90_face(right_face)
	end

	# R' command
	fun cclock_R do
		rotate_column(right_col, clock)
		rotate_l90_face(right_face)
	end

	# M command
	fun clock_M do rotate_column(mid_col, clock)

	# M' command
	fun cclock_M do rotate_column(mid_col, counterclock)

	# E command
	fun clock_E do rotate_line(mid_ln, counterclock)

	# E' command
	fun cclock_E do rotate_line(mid_ln, clock)

	# F command
	fun clock_F do
		cube_Y_rotation
		clock_L
		ccube_Y_rotation
	end

	# F' command
	fun cclock_F do
		cube_Y_rotation
		cclock_L
		ccube_Y_rotation
	end

	# B command
	fun clock_B do
		ccube_Y_rotation
		clock_L
		cube_Y_rotation
	end

	# B' command
	fun cclock_B do
		ccube_Y_rotation
		cclock_L
		cube_Y_rotation
	end

	# S command
	fun clock_S do
		cube_Y_rotation
		clock_M
		ccube_Y_rotation
	end

	# S' command
	fun cclock_S do
		cube_Y_rotation
		cclock_M
		ccube_Y_rotation
	end

	# u command
	fun clock_u do
		clock_U
		cclock_E
	end

	# u' command
	fun cclock_u do
		cclock_U
		clock_E
	end

	# l command
	fun clock_l do
		clock_L
		clock_M
	end

	# l' command
	fun cclock_l do
		cclock_L
		cclock_M
	end

	# f command
	fun clock_f do
		clock_F
		clock_S
	end

	# f' command
	fun cclock_f do
		cclock_F
		cclock_S
	end

	# r command
	fun clock_r do
		clock_R
		cclock_M
	end

	# r' command
	fun cclock_r do
		cclock_R
		clock_M
	end

	# b command
	fun clock_b do
		clock_B
		cclock_S
	end

	# b' command
	fun cclock_b do
		cclock_B
		clock_S
	end

	# d command
	fun clock_d do
		clock_D
		clock_E
	end

	# d' command
	fun cclock_d do
		cclock_D
		cclock_E
	end

	# Y command
	fun cube_Y_rotation do
		clock_U
		cclock_E
		cclock_D
	end

	# Y' command
	fun ccube_Y_rotation do
		cclock_U
		clock_E
		clock_D
	end

	# X command
	fun cube_X_rotation do
		cclock_L
		cclock_M
		clock_R
	end

	# X' command
	fun ccube_X_rotation do
		clock_L
		clock_M
		cclock_R
	end

	# Z command
	fun cube_Z_rotation do
		ccube_Y_rotation
		cube_X_rotation
		cube_Y_rotation
	end

	# Z' command
	fun ccube_Z_rotation do
		cube_Y_rotation
		cube_X_rotation
		ccube_Y_rotation
	end

	# Applies a command `cmd` to `self`, returns the number of operations performed during the command
	fun do_cmd(cmd: String): Int do
		if cmd == "" then return 0
		var iters = 1
		var cmdln = cmd.length
		if cmd[cmdln - 1] == '2' then
			iters = 2
		end
		var cmd1 = cmd[0]
		var cmd2 = '\0'
		if cmdln > 1 then
			cmd2 = cmd[1]
			if cmd2 == '2' then cmd2 = '\0'
		end
		for i in [1 .. iters] do
			if cmd1 == 'U' then
				if cmd2 == '\'' then
					cclock_U
				else
					clock_U
				end
			else if cmd1 == 'L' then
				if cmd2 == '\'' then
					cclock_L
				else
					clock_L
				end
			else if cmd1 == 'F' then
				if cmd2 == '\'' then
					cclock_F
				else
					clock_F
				end
			else if cmd1 == 'R' then
				if cmd2 == '\'' then
					cclock_R
				else
					clock_R
				end
			else if cmd1 == 'B' then
				if cmd2 == '\'' then
					cclock_B
				else
					clock_B
				end
			else if cmd1 == 'D' then
				if cmd2 == '\'' then
					cclock_D
				else
					clock_D
				end
			else if cmd1 == 'M' then
				if cmd2 == '\'' then
					cclock_M
				else
					clock_M
				end
			else if cmd1 == 'E' then
				if cmd2 == '\'' then
					cclock_E
				else
					clock_E
				end
			else if cmd1 == 'S' then
				if cmd2 == '\'' then
					cclock_S
				else
					clock_S
				end
			else if cmd1 == 'u' then
				if cmd2 == '\'' then
					cclock_u
				else
					clock_u
				end
			else if cmd1 == 'l' then
				if cmd2 == '\'' then
					cclock_l
				else
					clock_l
				end
			else if cmd1 == 'f' then
				if cmd2 == '\'' then
					cclock_f
				else
					clock_f
				end
			else if cmd1 == 'r' then
				if cmd2 == '\'' then
					cclock_r
				else
					clock_r
				end
			else if cmd1 == 'b' then
				if cmd2 == '\'' then
					cclock_b
				else
					clock_b
				end
			else if cmd1 == 'd' then
				if cmd2 == '\'' then
					cclock_d
				else
					clock_d
				end
			else if cmd1 == 'X' then
				if cmd2 == '\'' then
					ccube_X_rotation
				else
					cube_X_rotation
				end
			else if cmd1 == 'Y' then
				if cmd2 == '\'' then
					ccube_Y_rotation
				else
					cube_Y_rotation
				end
			else if cmd1 == 'Z' then
				if cmd2 == '\'' then
					ccube_Z_rotation
				else
					cube_Z_rotation
				end
			else
				abort
			end
		end
		return iters
	end
end

redef fun force_console_colors do return true
lib/rubix/rubix.nit:11,1--668,45