package core.astar;

import core.problem.Action;
import core.problem.Problem; //操作
import core.problem.State;

import java.util.ArrayList;

public class AStar {
	
	public AStar(Problem problem) {
		super();
		this.problem = problem;
	}
	
	public Node childNode(Node parent, Action action) {
		State state = problem.result(parent.getState(), action);
		//getPathCost 初始到当前的实际代价   stepCost 从父级到后续任务的路径成本
		int pathCost = parent.getPathCost() + problem.stepCost(parent.getState(), action);
		int heuristic = problem.heuristic(state);  //估计从状态到目标状态最便宜路径的成本
		return new Node(state, parent, action, pathCost, heuristic);
	}
	
	public Problem getProblem() {
		return problem;
	}

	public void setProblem(Problem problem) {
		this.problem = problem;
	}
	
	public Node Search()
	{
		//起始节点
		State initState = problem.getInitialState();
		Node node = new Node(initState, null, null, 0, problem.heuristic(initState));
		
		Fringe fringe = new Fringe();
		fringe.insert(node);
		
		Explored explored = new Explored();
		
		while (true) {
			
			if (fringe.isEmpty())	return null;	//失败
			
			node = fringe.pop(); //choose the lowest-cost node in frontier
			if (problem.goalTest(node.getState())) return node;
			explored.insert(node.getState());

			for (Action action : problem.Actions(node.getState())) {
				Node child = childNode(node, action);
				//child.getState()不再在扩展节点的集合(Close表中）且fringe(Open表）中不存在状态为state的节点  则将节点插入fringe中
				if (!explored.contains(child.getState()) && !fringe.contains(child.getState())) {
					fringe.insert(child);
				}
				else {
					/**
					如果邻接结点N’在CLOSED表中，比较CLOSED表中的g(N')值和当前的g(N')值，如果当前的g(N')更小，那么删除CLOSED表中的N'，把N设成N'的父节点，重新将N'插入OPEN表。
   	如果邻接结点N’在OPEN表中，比较OPEN表中的g(N')值和当前的g(N')值，如果当前的g(N')更小，那么删除OPEN表中的N'，把N设成N'的父节点，重新将N'插入OPEN表。
				***/
					Node revisited = fringe.revisited(child.getState());
					if (revisited != null && revisited.evaluation() > child.evaluation()) {
						fringe.replace(revisited, child);//用child节点代替Fringe中的 revisited节点
					}
				}
			}

		}	
	}
	
	//用动画展示问题的解路径
	public void solution(Node node)
	{
		// Fix me
		// 调用Problem的drawWorld方法，和simulateResult方法
		problem.drawWorld();
	}
	
	private Problem problem;
}

ArrayList<Problem> problems = ProblemFactory.getProblems(1);
		test2(problems);

	public static void test2(ArrayList<Problem> problems) {


		for (Problem problem : problems) {

			Rstep=0;
			flg=0;
			result = new int[200][20];
			PuzzleState state = (PuzzleState) problem.getInitialState();
			side = state.getSide();
			tmp = state.getStatus();
			System.out.println();
			xx = new int[20];
			yy = new int[20];
			for (int i = 0; i < side * side; i++) {
				if (tmp[i] == 0) pos = i;
				else {
					xx[tmp[i]] = (i / side);
					yy[tmp[i]] = (i % side);
				}
			}

			if (!check(tmp)) System.out.println("No");
			mat = new int[20];
			for (int i = 0; i < side * side; i++) mat[i] = i + 1;
			mat[side * side - 1] = 0;
			pos = side * side - 1;

			double time1 = 0;
			Stopwatch timer1 = new Stopwatch();
//			for(int i=0;i<100;i++){
//				layer[i]=-1;
//			}
			//System.out.println(H(mat));
			for (bound = H(mat); bound <= 100; bound = dfs(0, H(mat), 4))
				if (flg == 1) break;
			time1 = timer1.elapsedTime();
			Ans_show();
			System.out.printf("行走了 %s 步，执行了 %.3f 秒\n", Rstep, time1);
		}

	}

public static boolean check(int[] a) {
		int tot=0;
		int flag=0;
		for(int i=0;i<side*side;i++){
			if(a[i]==0) {
				flag = i/side;
				continue;
			}
			for(int j=0;j<i;j++){
				if(a[j]>a[i]){
					tot++;
				}
			}
		}
		if(side%2==1) return tot%2==0;
		else{
			tot+= abs(flag-(side-1));
			if(tot%2==0) return true;
			else return false;
		}
	}

public static int H(int[] mat) {
	int h = 0;
	for (int i = 0; i < side*side-1; i++) {
		h += abs(xx[mat[i]] - (i / side)) + abs(yy[mat[i]] - (i % side));
	}
	return h;
}

public static boolean ok(int x,int y){
	if(x>y){
		int ff=x;
		x=y;
		y=ff;
	}
	if(x==0&y==1) return false;  //与操作  1 1 为1
	if(x==2&&y==3) return false;
	return true;
}

public static int dfs(int step, int h, int las) {
		//g(n)+h(n)=f(n) 更新f(n) bound 最大限度  采用估值函数，剪掉f(n)大于depth的路径
		if (step + h > bound) return step + h; //
//		if(layer[h]==-1)layer[h]=step;
//		if(step>layer[h]+15){
//			System.out.printf("enter\n");
//			return step+h;
//		}
		if (h == 0) { // 到达最终状态 输出g(n)即可
			//		System.out.println(step);
			flg = 1;
			Rstep = step;
			return step;
		}
		int pos1 = pos;
		int ret = 127, x = pos1 / side, y = pos1 % side;
		int dx, dy, tar, ht, temp, i;
		for (i = 0; i < 4; i++) { //四个方向扩展
			dx = x + u[i];
			dy = y + p[i];
			if (dx < 0 || dy < 0 || dx > side - 1 || dy > side - 1 || !ok(i, las)) continue;
			tar = (dx * side) + dy; //计算出扩展出的新节点的一维坐标 2,2 2*4+2= 10
			mat[pos1] = mat[tar]; // 0的坐标等于扩展出来的点的坐标 a.mat[10]=11;
			mat[tar] = 0;//相当于swap()
			pos = tar;
			//计算新的h值
        //阶段三主要在这修改 用不相交模式数据库 h(n) 为当前节点的各点的曼哈顿距离和。
			ht = h - (Math.abs(xx[mat[pos1]] - dx) + Math.abs(yy[mat[pos1]] - dy))  + Math.abs(xx[mat[pos1]] - x) + Math.abs(yy[mat[pos1]] - y);
			if (step + ht <= bound)
				for (int k = 0; k < side*side; k++)
					result[step][k] = mat[k];
			temp = dfs(step + 1, ht, i);
			if (flg == 1)  return temp;
			if (ret > temp) ret = temp;
			mat[tar] = mat[pos1];
			mat[pos1] = 0;
			pos = pos1;
		}
		return ret;
	}

/**
 * File: PatternDatabaseGenerator.java
 * Author: Brian Borowski
 * Date created: June 10, 2010
 * Date last modified: May 13, 2011
 */
import java.io.BufferedOutputStream;
import java.io.DataOutputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.IOException;
import java.util.Collections;
import java.util.Comparator;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Set;
import java.util.StringTokenizer;

/**
 * Examples:
 * When generating a complete pattern database (i.e. no dummy tiles):
 *  java PatternDatabaseGenerator 8 1,2,3,4,5,6,7,8,0 8-puzzle.db
 *
 * When generating a disjoint additive pattern database (i.e. dummy tiles 'x'):
 *  java PatternDatabaseGenerator 15 0,2,3,4,x,x,x,x,x,x,x,x,x,x,x,0     15-puzzle-663-0.db
 *  java PatternDatabaseGenerator 15 1,x,x,x,5,6,x,x,9,10,x,x,13,x,x,0   15-puzzle-663-1.db
 *  java PatternDatabaseGenerator 15 x,x,x,x,x,x,7,8,x,x,11,12,x,14,15,0 15-puzzle-663-2.db
 */
public final class PatternDatabaseGenerator {
    public static final byte KEY_NOT_FOUND = -1;

    final int numOfTiles, numOfTilesMinusOne, dimension;

    PrimitiveHashMap tempMap;
    List<Entry> stateToCostEntries_8_puzzle;
    byte[] costTable_15_puzzle;
    long[] configTable_15_puzzle;

    public PatternDatabaseGenerator(final int numOfTiles, final long boardConfig,
                                    final byte dummyTile, final String filename) {

        this.numOfTiles = Node.numOfTiles = numOfTiles;
        this.numOfTilesMinusOne = numOfTiles - 1;
        this.dimension = Node.dimension = (int)Math.sqrt(numOfTiles);

        DataOutputStream dos = null;
        if (filename != null) {
            try {
                dos = new DataOutputStream(new BufferedOutputStream(
                                           new FileOutputStream(filename)));
            } catch (final FileNotFoundException fnfe) {
                System.err.println("Error: Cannot open file '" + filename + "' for output.");
                System.exit(1);
            }
        }

        if (numOfTilesMinusOne == 15) {
            generateFifteenPuzzleDB(dummyTile, boardConfig);
            outputFifteenPuzzleData(filename, dos);
        } else {
            generateEightPuzzleDB(boardConfig);
            outputEightPuzzleData(filename, dos);
        }
    }

    private void generateFifteenPuzzleDB(final byte dummyTile,
                                         final long boardConfig) {

        final boolean[] tilesInSubset = computeSubset(dummyTile, boardConfig);
        final int[] tilePositions = new int[tilesInSubset.length];
        int numTilesInSubset = 0;
        for (int i = 0; i < tilePositions.length; ++i) {
            if (tilesInSubset[i]) {
                tilePositions[i] = numTilesInSubset++;
            }
        }
        breadthFirstSearch(boardConfig, tilesInSubset);
        final int tableLength = (int)Math.pow(2, numTilesInSubset * 4);
        costTable_15_puzzle = new byte[tableLength];
        configTable_15_puzzle = new long[tableLength];
        for (int i = tableLength - 1; i >= 0; --i) {
            costTable_15_puzzle[i] = KEY_NOT_FOUND;
        }

        System.err.println("Total states visited: " + tempMap.size());
        System.err.print("Removing duplicates...");
        final Set<Entry> entries = tempMap.entrySet();
        final Iterator<Entry> it = entries.iterator();
        while (it.hasNext()) {
            final Entry entry = it.next();
            final long config = entry.getKey();
            final byte movesRequired = entry.getValue();

            final int index = indexFor(config, true, tilesInSubset, tilePositions);
            final byte moves = costTable_15_puzzle[index];
            if (moves == KEY_NOT_FOUND || movesRequired < moves) {
                configTable_15_puzzle[index] = config;
                costTable_15_puzzle[index] = movesRequired;
            }
        }

        int numElements = 0;
        for (int i = tableLength - 1; i >= 0; --i) {
            if (costTable_15_puzzle[i] != KEY_NOT_FOUND) {
                ++numElements;
            }
        }

        System.err.println("done");
        System.err.println("States in subset: " + numElements);
    }

    private void generateEightPuzzleDB(final long boardConfig) {
        breadthFirstSearch(boardConfig, null);
        final PrimitiveHashMap costMap_8_puzzle = new PrimitiveHashMap();

        System.err.println("Total states visited: " + tempMap.size());
        System.err.print("Removing duplicates...");
        final Set<Entry> entries = tempMap.entrySet();
        final Iterator<Entry> it = entries.iterator();
        while (it.hasNext()) {
            final Entry entry = it.next();
            final long config = entry.getKey();
            final byte movesRequired = entry.getValue();

            final byte moves = costMap_8_puzzle.get(config);
            if (moves == PrimitiveHashMap.KEY_NOT_FOUND || movesRequired < moves) {
                costMap_8_puzzle.put(config, movesRequired);
            }
            it.remove();
        }
        System.err.println("done");

        final int numElements = costMap_8_puzzle.size();
        stateToCostEntries_8_puzzle = new LinkedList<Entry>(costMap_8_puzzle.entrySet());
        System.err.print("Sorting entries...");
        Collections.sort(stateToCostEntries_8_puzzle, new Comparator<Entry>() {
            public int compare(final Entry e1, final Entry e2) {
                return e1.getValue() - e2.getValue();
            }
        });
        System.err.println("done");

        System.err.println("States in subset: " + numElements);
    }

    private void outputFifteenPuzzleData(final String filename,
                                         final DataOutputStream dos) {
        System.err.print("Writing file...");
        if (filename == null) {
            // Write values to stdout. User can redirect stdout to a file, if desired.
            for (int i = 0; i < configTable_15_puzzle.length; ++i) {
                final long config = configTable_15_puzzle[i];
                System.out.println((i + 1) + "," + config + "," +
                    costTable_15_puzzle[i] + "," +
                    Utility.longToString(config, numOfTiles));
            }
        } else {
            int i = 0;
            try {
                for ( ; i < costTable_15_puzzle.length; ++i) {
                    dos.writeByte(costTable_15_puzzle[i]);
                }
            } catch (final IOException ioe) {
                System.err.println("Error: Cannot write entry " + i + " to file.");
                System.exit(1);
            } finally {
                try {
                    if (dos != null) {
                        dos.close();
                    }
                } catch (final IOException ioe) { }
            }
        }
        System.err.println("done");
    }

    private void outputEightPuzzleData(final String filename,
                                       final DataOutputStream dos) {
        System.err.print("Writing file...");
        final Iterator<Entry> listIter = stateToCostEntries_8_puzzle.iterator();
        if (filename == null) {
            // Write values to stdout. User can redirect stdout to a file, if desired.
            int i = 1;
            while (listIter.hasNext()) {
                final Entry entry = listIter.next();
                final long config = entry.getKey();
                System.out.println(i + "," + config + "," + entry.getValue() +
                    "," + Utility.longToString(config, numOfTiles));
                ++i;
            }
        } else {
            int i = 0;
            try {
                while (listIter.hasNext()) {
                    final Entry entry = listIter.next();
                    dos.writeLong(((Long)entry.getKey()).longValue());
                    dos.writeByte(((Byte)entry.getValue()).byteValue());
                    ++i;
                }
            } catch (final IOException ioe) {
                System.err.println("Error: Cannot write entry " + i + " to file.");
                System.exit(1);
            } finally {
                try {
                    if (dos != null) {
                        dos.close();
                    }
                } catch (final IOException ioe) { }
            }
        }
        System.err.println("done");
    }

    private void breadthFirstSearch(final long boardConfig,
                                    final boolean[] tilesInSubset) {
        BFSNode currentState = new BFSNode(boardConfig);
        currentState.cost = 0;

        tempMap = new PrimitiveHashMap();
        tempMap.put(boardConfig, (byte)0);

        final Queue<BFSNode> queue = new LinkedList<BFSNode>();
        queue.add(currentState);

        byte previous = 1;
        while (true) {
            final char fromDirection = currentState.direction;

            if (fromDirection != 'R') {
                final BFSNode left = currentState.moveLeftNode(tilesInSubset);
                if (left != null) {
                    final byte moves = tempMap.get(left.boardConfig);
                    if (moves == PrimitiveHashMap.KEY_NOT_FOUND || left.cost < moves) {
                        tempMap.put(left.boardConfig, left.cost);
                        queue.add(left);
                    }
                }
            }

            if (fromDirection != 'L') {
                final BFSNode right = currentState.moveRightNode(tilesInSubset);
                if (right != null) {
                    final byte moves = tempMap.get(right.boardConfig);
                    if (moves == PrimitiveHashMap.KEY_NOT_FOUND || right.cost < moves) {
                        tempMap.put(right.boardConfig, right.cost);
                        queue.add(right);
                    }
                }
            }

            if (fromDirection != 'D') {
                final BFSNode up = currentState.moveUpNode(tilesInSubset);
                if (up != null) {
                    final byte moves = tempMap.get(up.boardConfig);
                    if (moves == PrimitiveHashMap.KEY_NOT_FOUND || up.cost < moves) {
                        tempMap.put(up.boardConfig, up.cost);
                        queue.add(up);
                    }
                }
            }

            if (fromDirection != 'U') {
                final BFSNode down = currentState.moveDownNode(tilesInSubset);
                if (down != null) {
                    final byte moves = tempMap.get(down.boardConfig);
                    if (moves == PrimitiveHashMap.KEY_NOT_FOUND || down.cost < moves) {
                        tempMap.put(down.boardConfig, down.cost);
                        queue.add(down);
                    }
                }
            }

            if (!queue.isEmpty()) {
                currentState = queue.remove();
                final byte movesRequired = currentState.cost;
                if (movesRequired > previous) {
                    System.err.println("Generating boards with up to " + previous +
                        " moves; map size: " + tempMap.size());
                    previous = movesRequired;
                }
            } else {
                break;
            }
        }
    }

    private int indexFor(final long boardConfig, final boolean isFifteenPuzzle,
                         final boolean[] tilesInSubset, final int[] tilePositions) {
        if (isFifteenPuzzle) {
            int hashCode = 0;
            for (int i = numOfTilesMinusOne; i >= 0; --i) {
                final int tile = (int)((boardConfig >> (i << 2)) & 0xF);
                if (tilesInSubset[tile]) {
                    hashCode |= i << (tilePositions[tile] << 2);
                }
            }
            return hashCode;
        }
        return (int)boardConfig;
    }

    private boolean[] computeSubset(final byte dummyValue, final long boardConfig) {
        final boolean[] tilesInSubset = new boolean[numOfTiles];
        for (int pos = numOfTiles - 1; pos >= 0; --pos) {
            final byte tile = (byte)((boardConfig >> (pos << 2)) & 0xF);
            if (tile != dummyValue && tile != 0) {
                tilesInSubset[tile] = true;
            }
        }
        return tilesInSubset;
    }

    private static byte getArray(final String arrayString, final byte[] tiles,
                                 final int numOfTiles) {

        final StringTokenizer st = new StringTokenizer(arrayString, ",");
        final int numOfTokens = st.countTokens();

        // Validate the number of tiles entered.
        if (numOfTokens < numOfTiles) {
            System.out.println("Error: Input contains only " + numOfTokens +
                " of the " + numOfTiles + " tiles.");
            System.exit(1);
        } else if (numOfTokens > numOfTiles) {
            System.out.println("Error: Input exceeds required " +
                numOfTiles + " tiles.");
            System.exit(1);
        }

        // Create an array of String representations of the tile numbers.
        final String[] numStrings = new String[numOfTokens];
        int i = 0;
        while (st.hasMoreTokens()) {
            numStrings[i++] = st.nextToken();
        }

        // Make sure each string is a number.
        final int[] tilePositions = new int[numOfTiles];
        for (i = 0; i < tiles.length; ++i) {
            tiles[i] = -1;
            tilePositions[i] = -1;
        }
        for (i = 0; i < numStrings.length; ++i) {
            final String s = numStrings[i];
            try {
                final byte tile = Byte.parseByte(s);
                tiles[i] = tile;
                tilePositions[tile] = i;
            } catch (final NumberFormatException nfe) {
                if (!s.trim().toLowerCase().equals("x")) {
                    System.err.println("Error: Expected integer or 'X' at index " + (i + 1) +
                        ", received '" + numStrings[i] + "'.");
                    System.exit(1);
                }
            }
        }

        byte dummyTile = -1;
        // Make sure no tile number is missing from the input.
        for (i = 0; i < numOfTiles; ++i) {
            if (tilePositions[i] == -1) {
                if (i == 0) {
                    System.err.println("Error: Tile 0 is missing for input.");
                    System.exit(1);
                }
                dummyTile = (byte)i;
                break;
            }
        }

        // Replace 'X' (-1) tiles with the dummy value.
        for (i = 0; i < tiles.length; ++i) {
            if (tiles[i] == -1) {
                tiles[i] = dummyTile;
            }
        }

        return dummyTile;
    }

    public static void main(final String[] args) {
        if (args.length < 2 || args.length > 3) {
            System.err.println(
                "Usage: java PatternDatabaseGenerator <num of tiles> <tile order> [filename]");
            System.exit(1);
        }
        int puzzleSize = 0;
        try {
            puzzleSize = Integer.parseInt(args[0].trim());
            if ((puzzleSize != 8) && (puzzleSize != 15)) {
                System.err.println("Error: Puzzle size must be either 8 or 15.");
                System.exit(1);
            }
            ++puzzleSize;
        } catch (final NumberFormatException nfe) {
            System.err.println("Error: Puzzle size must be either 8 or 15.");
            System.exit(1);
        }

        final String tileOrder = args[1].trim();
        final byte[] tiles = new byte[puzzleSize];
        final byte dummyTile = getArray(tileOrder, tiles, puzzleSize);
        System.err.println("Using dummy tile: " + dummyTile);
        String filename = null;
        if (args.length == 3) {
            filename = args[2];
        }
        new PatternDatabaseGenerator(
                puzzleSize, Utility.byteArrayToLong(tiles), dummyTile, filename);
    }
}

public static int dfs(int step, int h, int las) {
		if (step + h > bound) return step + h; // 从目标开始找 f(n)刚开始最小 如果有更大的则更新 f(n) 反方向找
//		if(layer[h]==-1)layer[h]=step;
//		if(step>layer[h]+15){
//			System.out.printf("enter\n");
//			return step+h;
//		}
		if (h == 0) { // 到达最终状态 输出g(n)即可
			//		System.out.println(step);
			flg = 1;
			Rstep = step;
			return step;
		}
		int pos1 = pos;
		int ret = 127, x = pos1 / side, y = pos1 % side;
		int dx, dy, tar, ht, temp, i;
		for (i = 0; i < 4; i++) { //四个方向扩展
			dx = x + u[i];
			dy = y + p[i];
			if (dx < 0 || dy < 0 || dx > side - 1 || dy > side - 1 || !ok(i, las)) continue;
			tar = (dx * side) + dy; //计算出扩展出的新节点的一维坐标 2,2 2*4+2= 10
			tmp[pos1] = tmp[tar]; // 0的坐标等于扩展出来的点的坐标 a.mat[10]=11;
			tmp[tar] = 0;//相当于swap()
			pos = tar;
			//如果换一个评估函数呢
			//阶段三  使用不相交模式数据库得到评估函数 ht值为分为的块的h的和加起来
			//

			ht = getH(tmp);
			//ht = h - (Math.abs(xx[mat[pos1]] - dx) + Math.abs(yy[mat[pos1]] - dy))  + Math.abs(xx[mat[pos1]] - x) + Math.abs(yy[mat[pos1]] - y);
			if (step + ht <= bound) {
				for (int k = 0; k < side * side; k++) {
					result[step][k] = tmp[k];
				}
				//System.out.println(i);
				if(i==0){
					redir[step]='r';
				}
				else if(i==1){
					redir[step]='l';
				}
				else if(i==2){
					redir[step]='d';
				}
				else{
					redir[step]='u';
				}
			}
			temp = dfs(step + 1, ht, i);
			if (flg == 1)  return temp;
			if (ret > temp) ret = temp;
			tmp[tar] = tmp[pos1];
			tmp[pos1] = 0;
			pos = pos1;
		}
		return ret;
	}

static final int[] tilePositions = {-1, 0, 0, 1, 2, 1, 2, 0, 1, 3, 4, 2, 3, 5, 4, 5};
static final int[] tileSubsets = {-1, 1, 0, 0, 0, 1, 1, 2, 2, 1, 1, 2, 2, 1, 2, 2};
public static int getH(int [] tmp) {

   int index0 = 0, index1 = 0, index2 = 0;
   for (int pos = 15; pos >= 0; --pos) {
      final int tile = tmp[pos];
      if (tile != 0) {
         final int subsetNumber = tileSubsets[tile];
         switch (subsetNumber) {
            case 2:
               index2 |= pos << (tilePositions[tile] << 2);
               break;
            case 1:
               index1 |= pos << (tilePositions[tile] << 2);
               break;
            default:
               index0 |= pos << (tilePositions[tile] << 2);
               break;
         }
      }
   }
   return PuzzleConfiguration.costTable_15_puzzle_0[index0] +
         PuzzleConfiguration.costTable_15_puzzle_1[index1] +
         PuzzleConfiguration.costTable_15_puzzle_2[index2];
}