/*
 *  Copyright (c) 2024 - 2025 by Paul Hertz <ignotus@gmail.com>
 *
 *   This program is free software; you can redistribute it and/or modify
 *   it under the terms of the GNU Library General Public License as published
 *   by the Free Software Foundation; either version 3 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 Library General Public License for more details.
 *
 *   You should have received a copy of the GNU Library General Public
 *   License along with this program; if not, write to the Free Software
 *   Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 */

package net.paulhertz.pixelaudio;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.Deque;
import java.util.List;
import java.util.Random;

/**
 * A non-functional experiment, left in as a placeholder. RandomContinousGen attempted to solve
 * a computationally complex problem, a random continuous path that visits every point in a grid. 
 * It went off in some interesting directions, but never really worked.
 */
@Deprecated 
public class RandomContinousGen extends PixelMapGen {
	// an experiment, not ready for prime time
	public final static String description = "RandomContinousGen starts at (0,0) makes random choices of the next pixels until it creates a continous path.";


	public RandomContinousGen(int width, int height, AffineTransformType type) {
		super(width, height, type);
		this.generate();
	}

	public RandomContinousGen(int width, int height) {
		super(width, height);
		this.generate();
	}

	@Override
	public String describe() {
		return RandomContinousGen.description;
	}

	@Override
	public boolean validate(int width, int height) {
		if (width < 2 || height < 2) {
			System.out.println("Width and height for BoustropheGen must be greater than 1.");
			return false;
		}
		return true;
	}

	/**
	 * Initializes this.coords, this.pixelMap, this.sampleMap: this is handled by 
	 * a call to PixelMapGen's setMapsFromCoords() method. 
	 * @return  this.pixelMap, the value for PixelAudioMapper.signalToImageLUT.
	 */
	@Override
	public int[] generate() {
		this.coords = this.generateCoordinates();
		return this.setMapsFromCoords(this.coords);
	}
	
	/**
	 * Generically-named method that calls the custom coordinate generation method for a particular 
	 * PixelMapGen child class. Here the method is generateBouCoordinates().
	 * Additional initializations belong here, if required by your coordinate generation method,
	 * rather than in the generate() method.
	 *
	 * @return 	An ArrayList<int[]> of bitmap coordinates in the order the signal mapping would visit them.
	 *
	 */
	private ArrayList<int[]> generateCoordinates() {
		return this.generateHamiltonianPath(this.w, this.h, 1024);
	}
	
	/**
	 * Generated by ChatGPT, not quite a solution to a non-trivial problem. 
	 * 
	 * 
	 * ChatGPT: 
	 * "
	 * Thanks for the clarification — and you're absolutely right: generating a truly continuous, 
	 * non-repeating, 4-connected path that visits every pixel exactly once is a classic problem. 
	 * What you're asking for is essentially a Hamiltonian path over a grid graph, restricted to 4-connected neighbors.
	 * 
	 * Requirements Recap:
	 *   Starts at (0, 0)
	 *   Visits every pixel exactly once
	 *   Moves only up/down/left/right (4-connected)
	 *   Never repeats, never jumps
	 *   Has some randomness in the generated path
	 * " 
	 * 
	 * This is an NP-Complete computational problem: 
	 * https://www.researchgate.net/publication/220616693_Hamilton_Paths_in_Grid_Graphs
	 * 
	 * @param width
	 * @param height
	 * @return
	 */
	public ArrayList<int[]> generateHamiltonianPath(int width, int height, int maxAttempts) {
		int endX = width - 1;
		int endY = 0;

		for (int attempt = 0; attempt < maxAttempts; attempt++) {
			boolean[][] visited = new boolean[height][width];
			ArrayList<int[]> path = new ArrayList<>(width * height);

			if (dfs(0, 0, width, height, visited, path, endX, endY)) {
				return path;
			}
		}
	    // Fallback: discontinuous but complete traversal
	    System.out.println("--->> Hamiltonian path calculation failed over "+ maxAttempts +" tries.");
	    return generateRandomContinuousCoordinates(width, height);
	}

	private boolean dfs(int x, int y, int width, int height, boolean[][] visited, ArrayList<int[]> path, int endX,
			int endY) {
		if (visited[y][x])
			return false;

		visited[y][x] = true;
		path.add(new int[] { x, y });

		if (path.size() == width * height) {
			return (x == endX && y == endY);
		}

		for (int[] dir : shuffledDirections()) {
			int nx = x + dir[0];
			int ny = y + dir[1];
			if (inBounds(nx, ny, width, height) && !visited[ny][nx]) {
				if (dfs(nx, ny, width, height, visited, path, endX, endY)) {
					return true;
				}
			}
		}

		visited[y][x] = false;
		path.remove(path.size() - 1);
		return false;
	}

	private boolean inBounds(int x, int y, int width, int height) {
		return x >= 0 && y >= 0 && x < width && y < height;
	}

	private int[][] shuffledDirections() {
		int[][] dirs = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
		List<int[]> dirList = Arrays.asList(dirs);
		Collections.shuffle(dirList);
		return dirList.toArray(new int[0][]);
	}

	private ArrayList<int[]> generateBoustrophedonPath(int width, int height) {
		ArrayList<int[]> path = new ArrayList<>(width * height);
		for (int y = 0; y < height; y++) {
			if (y % 2 == 0) {
				for (int x = 0; x < width; x++) {
					path.add(new int[] { x, y });
				}
			} else {
				for (int x = width - 1; x >= 0; x--) {
					path.add(new int[] { x, y });
				}
			}
		}
		return path;
	}

	private ArrayList<int[]> generateRandomContinuousCoordinates(int width, int height) {
	    ArrayList<int[]> path = new ArrayList<>(width * height);
	    boolean[][] visited = new boolean[height][width];
	    Random rand = new Random(System.nanoTime());

	    // 4-connected directions
	    int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

	    // Stack holds the path we're building
	    Deque<int[]> stack = new ArrayDeque<>();
	    stack.push(new int[]{0, 0});
	    visited[0][0] = true;
	    path.add(new int[]{0, 0});

	    while (!stack.isEmpty()) {
	        int[] current = stack.peek();
	        int cx = current[0];
	        int cy = current[1];

	        // Collect unvisited 4-connected neighbors
	        List<int[]> neighbors = new ArrayList<>();
	        for (int[] dir : directions) {
	            int nx = cx + dir[0];
	            int ny = cy + dir[1];
	            if (nx >= 0 && ny >= 0 && nx < width && ny < height && !visited[ny][nx]) {
	                neighbors.add(new int[]{nx, ny});
	            }
	        }

	        if (neighbors.isEmpty()) {
	            // No unvisited neighbors, backtrack
	            stack.pop();
	            continue;
	        }

	        // Pick a random unvisited neighbor
	        int[] next = neighbors.get(rand.nextInt(neighbors.size()));
	        visited[next[1]][next[0]] = true;
	        stack.push(next);
	        path.add(next);
	    }

	    return path;
	}

}
