content: /*
   * Licensed to the Apache Software Foundation (ASF) under one or more
   * contributor license agreements.  See the NOTICE file distributed with
   * this work for additional information regarding copyright ownership.
   * The ASF licenses this file to you under the Apache License, Version 2.0
   * (the "License"); you may not use this file except in compliance with
   * the License.  You may obtain a copy of the License at
   *
   * http://www.apache.org/licenses/LICENSE-2.0
   *
   * Unless required by applicable law or agreed to in writing, software
   * distributed under the License is distributed on an "AS IS" BASIS,
   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   * See the License for the specific language governing permissions and
   * limitations under the License.
   */
  package org.apache.calcite.example.maze;
  
  import org.apache.calcite.linq4j.Enumerator;
  
  import java.io.PrintWriter;
  import java.util.ArrayDeque;
  import java.util.ArrayList;
  import java.util.Deque;
  import java.util.LinkedHashSet;
  import java.util.List;
  import java.util.Random;
  import java.util.Set;
  
  /** Maze generator. */
  class Maze {
    private final int width;
    final int height;
    private final int[] regions;
    private final boolean[] ups;
    private final boolean[] lefts;
  
    static final boolean DEBUG = false;
    private final boolean horizontal = false;
    private final boolean spiral = false;
  
    Maze(int width, int height) {
      this.width = width;
      this.height = height;
      this.regions = new int[width * height];
      for (int i = 0; i < regions.length; i++) {
        regions[i] = i;
      }
      this.ups = new boolean[width * height + width];
      this.lefts = new boolean[width * height + 1];
    }
  
    private int region(int cell) {
      int region = regions[cell];
      if (region == cell) {
        return region;
      }
      return regions[cell] = region(region);
    }
  
    /** Prints the maze. Results are like this:
     *
     * <blockquote>
     * +--+--+--+--+--+
     * |        |     |
     * +--+  +--+--+  +
     * |     |  |     |
     * +  +--+  +--+  +
     * |              |
     * +--+--+--+--+--+
     * </blockquote>
     *
     * @param pw Print writer
     * @param space Whether to put a space in each cell; if false, prints the
     *              region number of the cell
     */
    public void print(PrintWriter pw, boolean space) {
      pw.println();
      final StringBuilder b = new StringBuilder();
      final StringBuilder b2 = new StringBuilder();
      final CellContent cellContent;
      if (space) {
        cellContent = c -> "  ";
      } else {
        cellContent = c -> {
          String s = region(c) + "";
          return s.length() == 1 ? " " + s : s;
        };
      }
      for (int y = 0; y < height; y++) {
        row(cellContent, b, b2, y);
        pw.println(b.toString());
        pw.println(b2.toString());
        b.setLength(0);
        b2.setLength(0);
      }
      for (int x = 0; x < width; x++) {
        pw.print("+--");
      }
      pw.println('+');
      pw.flush();
    }
  
    /** Generates a list of lines representing the maze in text form. */
    public Enumerator<String> enumerator(final Set<Integer> solutionSet) {
      final CellContent cellContent;
      if (solutionSet == null) {
        cellContent = CellContent.SPACE;
      } else {
        cellContent = c -> solutionSet.contains(c) ? "* " : "  ";
      }
      return new Enumerator<String>() {
        int i = -1;
        final StringBuilder b = new StringBuilder();
        final StringBuilder b2 = new StringBuilder();
  
        @Override public String current() {
          return i % 2 == 0 ? b.toString() : b2.toString();
        }
  
        @Override public boolean moveNext() {
          if (i >= height * 2) {
            return false;
          }
          ++i;
          if (i % 2 == 0) {
            b.setLength(0);
            b2.setLength(0);
            row(cellContent, b, b2, i / 2);
          }
          return true;
        }
  
        @Override public void reset() {
          i = -1;
        }
  
        @Override public void close() {}
      };
    }
  
    /** Returns a pair of strings representing a row of the maze. */
    private void row(CellContent cellContent, StringBuilder b, StringBuilder b2,
        int y) {
      final int c0 = y * width;
      for (int x = 0; x < width; x++) {
        b.append('+');
        b.append(ups[c0 + x] ? "  " : "--");
      }
      b.append('+');
      if (y == height) {
        return;
      }
      for (int x = 0; x < width; x++) {
        b2.append(lefts[c0 + x] ? ' ' : '|')
            .append(cellContent.get(c0 + x));
      }
      b2.append('|');
    }
  
    public Maze layout(Random random, PrintWriter pw) {
      int[] candidates =
          new int[width * height - width
              + width * height - height];
      int z = 0;
      for (int y = 0, c = 0; y < height; y++) {
        for (int x = 0; x < width; x++) {
          if (x > 0) {
            candidates[z++] = c;
          }
          ++c;
          if (y > 0) {
            candidates[z++] = c;
          }
          ++c;
        }
      }
      assert z == candidates.length;
      shuffle(random, candidates);
  
      for (int candidate : candidates) {
        final boolean up = (candidate & 1) != 0;
        final int c = candidate >> 1;
        if (up) {
          int region = region(c - width);
  
          // make sure we are not joining the same region, that is, making
          // a cycle
          if (region(c) != region) {
            ups[c] = true;
            regions[regions[c]] = region;
            regions[c] = region;
            if (DEBUG) {
              pw.println("up " + c);
            }
          } else {
            if (DEBUG) {
              pw.println("cannot remove top wall at " + c);
            }
          }
        } else {
          int region = region(c - 1);
  
          // make sure we are not joining the same region, that is, making
          // a cycle
          if (region(c) != region) {
            lefts[c] = true;
            regions[regions[c]] = region;
            regions[c] = region;
            if (DEBUG) {
              pw.println("left " + c);
            }
          } else {
            if (DEBUG) {
              pw.println("cannot remove left wall at " + c);
            }
          }
        }
        if (DEBUG) {
          print(pw, false);
          print(pw, true);
        }
      }
      return this;
    }
  
    Set<Integer> solve(int x, int y) {
      int c = y * width + x;
      final int target = regions.length - 1;
      Direction d = Direction.UP;
      final List<Integer> list = new ArrayList<>();
      final Deque<Direction> fromStack = new ArrayDeque<>();
      final Deque<Direction> directionStack = new ArrayDeque<>();
      Direction from = Direction.BACKTRACK;
      int cNext = 0;
      Direction dNext = Direction.UP;
      boolean move = false;
      for (;;) {
        switch (d) {
        case UP:
          // try to go up
          move = from != Direction.DOWN && ups[c];
          cNext = c - width;
          dNext = Direction.LEFT;
          break;
        case LEFT:
          // try to go left
          move = from != Direction.RIGHT && lefts[c];
          cNext = c - 1;
          dNext = Direction.DOWN;
          break;
        case DOWN:
          // try to go down
          move = from != Direction.UP && c + width < regions.length
              && ups[c + width];
          cNext = c + width;
          dNext = Direction.RIGHT;
          break;
        case RIGHT:
          move = from != Direction.LEFT && c % width < width - 1
              && lefts[c + 1];
          cNext = c + 1;
          dNext = Direction.BACKTRACK;
          break;
        case BACKTRACK:
          move = false;
          do {
            c = list.remove(list.size() - 1);
            dNext = directionStack.pop();
            from = fromStack.pop();
          } while (dNext == Direction.BACKTRACK);
          break;
        default:
          break;
        }
        if (move) {
          directionStack.push(dNext);
          fromStack.push(from);
          list.add(c);
          if (cNext == target) {
            list.add(cNext);
            return new LinkedHashSet<>(list);
          }
          from = d;
          d = Direction.UP;
          c = cNext;
        } else {
          d = dNext;
        }
      }
    }
  
    /** Direction. */
    private enum Direction {
      UP, LEFT, DOWN, RIGHT, BACKTRACK
    }
  
    /**
     * Randomly permutes the members of an array. Based on the Fisher-Yates
     * algorithm.
     *
     * @param random Random number generator
     * @param ints Array of integers to shuffle
     */
    private void shuffle(Random random, int[] ints) {
      for (int i = ints.length - 1; i > 0; i--) {
        int j = random.nextInt(i + 1);
        int t = ints[j];
        ints[j] = ints[i];
        ints[i] = t;
      }
  
      // move even walls (left) towards the start, so we end up with
      // long horizontal corridors
      if (horizontal) {
        for (int i = 2; i < ints.length; i++) {
          if (ints[i] % 2 == 0) {
            int j = random.nextInt(i);
            int t = ints[j];
            ints[j] = ints[i];
            ints[i] = t;
          }
        }
      }
  
      // move walls towards the edges towards the start
      if (spiral) {
        for (int z = 0; z < 5; z++) {
          for (int i = 2; i < ints.length; i++) {
            int x = ints[i] / 2 % width;
            int y = ints[i] / 2 / width;
            int xMin = Math.min(x, width - x);
            int yMin = Math.min(y, height - y);
            if (ints[i] % 2 == (xMin < yMin ? 1 : 0)) {
              int j = random.nextInt(i);
              int t = ints[j];
              ints[j] = ints[i];
              ints[i] = t;
            }
          }
        }
      }
    }
  
    /** Callback to get what to print in a particular cell. Must be two characters
     * long, usually two spaces. */
    interface CellContent {
      CellContent SPACE = c -> "  ";
  
      String get(int c);
    }
  }
  