public final class queue { //Class to describe a queue of moves
        public final int face, quads, mode;
        private queue next, prev;
        private boolean waiting;
        public queue() {
                face = -1;
                quads = -1;
                mode = -1;
                next = this;
                prev = this;
                waiting = true;
        }
        public queue(int face, int quads, int mode, int planes) {
                if (mode + mode + face / 3 >= planes) {
                        face = 5 - face;
                        quads = 4 - quads;
                        mode = planes - mode - 1;
                }
                this.face = face;
                this.quads = quads;
                this.mode = mode;
                next = null;
                prev = null;
                waiting = false;
        }
        private queue(queue src) {
                //this(src.face, src.quads, src.mode);
                this.face = src.face;
                this.quads = src.quads;
                this.mode = src.mode;
                next = null;
                prev = null;
                waiting = false;
        }
        public synchronized void add(queue next) {
                next.prev = this;
                next.next = this.next;
                this.next.prev = next;
                this.next = next;
                waiting = false;
                notifyAll();
        }
        public synchronized void add(int face, int quads, int mode, int planes) {
                if (mode + mode + face / 3 >= planes) {
                        face = 5 - face;
                        quads = 4 - quads;
                        mode = planes - mode - 1;
                }
                queue temp = next;
                while (temp != this && (temp.face + face == 5 || temp.face == face && temp.mode != mode)) temp = temp.next;
                if (temp.face == face && temp.mode == mode) {
                        quads = (quads + temp.quads) & 3;
                        temp.prev.next = temp.next;
                        temp.next.prev = temp.prev;
                        temp.next = null;
                        temp.prev = null;
                }
                if (quads != 0) add(new queue(face, quads, mode, planes));
        }
        public synchronized void sub(queue prev) {
                prev.next = this;
                prev.prev = this.prev;
                this.prev.next = prev;
                this.prev = prev;
                waiting = false;
                notifyAll();
        }
        public synchronized void sub(int face, int quads, int mode, int planes) {
                System.err.println("Normalizing parameters");
                if (mode + mode + face / 3 >= planes) {
                        face = 5 - face;
                        quads = 4 - quads;
                        mode = planes - mode - 1;
                }
                System.err.println("Looking for move to remove");
                queue temp = prev;
                while (temp != this && (temp.face + face == 5 || temp.face == face && temp.mode != mode)) temp = temp.prev;
                if (temp.face == face && temp.mode == mode) {
                        quads = (quads + temp.quads) & 3;
                        temp.next.prev = temp.prev;
                        temp.prev.next = temp.next;
                        temp.prev = null;
                        temp.next = null;
                }
                if (quads != 0) sub(new queue(face, quads, mode, planes));
        }
        public synchronized int length() {
                int count = 0;
                for (queue temp = this.prev; temp != this; temp = temp.prev) count++;
                return count;
        }
        private synchronized boolean copy2(queue dest, boolean all) {
                queue temp = this.prev;
                if (temp == this) return false;
                do dest.add(new queue(temp));
                while (all && (temp = temp.prev) != this);
                return true;
        }
        public synchronized boolean append(queue src, boolean all) {
                if (waiting && src != null && src.copy2(this, all)) {
                        notifyAll();
                        return true;
                }
                return false;
        }
        private synchronized boolean send2(queue dest) {
                if (prev == this) return false;
                next.prev = dest.prev;
                dest.prev.next = next;
                next = null;
                prev.next = dest;
                dest.prev = prev;
                prev = null;
                return true;
        }
        public synchronized boolean insert(queue src) {
                return src.send2(this);
        }
        public synchronized queue remove() throws InterruptedException {
                while (prev == this) {
                        waiting = true;
                        wait();
                }
                queue result = prev;
                this.prev = prev.prev;
                this.prev.next = this;
                result.next = null;
                result.prev = null;
                notifyAll();
                return result;
        }
        private synchronized boolean matches(queue src) {
                return prev.face == src.face && prev.quads == src.quads && prev.mode == src.mode;
        }
        public synchronized boolean startsWith(queue src) {
                return src.matches(prev);
        }
        public synchronized boolean iswaiting() {
                return waiting;
        }
        public synchronized boolean isempty() {
                return prev == this;
        }
        public synchronized boolean isnearempty() {
                return prev == next;
        }
        private static char faces[] = {'F', 'U', 'L', 'R', 'D', 'B'};
        private static char quad[] = {'\0', '-', '|', '+'};
        private static char quadr[] = {'\0', '+', '|', '-'};
        public synchronized String moves(boolean reversed) {
                StringBuffer sb = new StringBuffer();
                if (reversed) for (queue temp = next; temp != this; temp = temp.next) {
                        sb.append(faces[temp.face]);
                        sb.append(quadr[temp.quads]);
                        if (temp.mode != 0) sb.append('%');
                } else for (queue temp = prev; temp != this; temp = temp.prev) {
                        sb.append(faces[temp.face]);
                        sb.append(quad[temp.quads]);
                        if (temp.mode != 0) sb.append('%');
                }
                return sb.toString();
        }
        public synchronized void reset() {
                next = this;
                prev = this;
                waiting = true;
        }
}