package queue;

import java.util.Scanner;
import java.lang.Math;
public class FindMiddle {
	private int maxSize;
	private String[] queArray;
	private int front;
	private int rear;
	private int nItems;

	public FindMiddle(int s) { // constructor

		maxSize = s;
		queArray = new String[maxSize];
		front = 0;
		rear = -1;
		nItems = 0;
	}

//	public boolean insert(String st)
//    {
//        if(isFull()) return false;
//        if(rear==maxSize-1) rear=-1;
//        rear++;
//        queArray[rear]=st;
//        nItems++;
//        return true;
//    }

	public void insert(String item) {
		if (nItems == 0) {
			queArray[0] = item;
		} else {
			int j = nItems;

			while (j > 0 && queArray[j - 1].length() > item.length()) {
				queArray[j] = queArray[j - 1];
				j--;
			}
			queArray[j] = item;
		}
		nItems++;
	}

	public String remove() { // take item from front of queue
		if (isEmpty()) {
			return null; // don’t remove if empty
		}
		String temp = queArray[front];// get value and incr front
		front++;
		if (front == maxSize) { // deal with wraparound
			front = 0;
		}
		nItems--; // one less item
		return temp;
	}

	public String peekFront() { // peek at front of queue

		return queArray[front];
	}

	public boolean isEmpty() { // true if queue is empty

		return (nItems == 0);
	}

	public boolean isFull() { // true if queue is full

		return (nItems == maxSize);
	}

	public int size() { // number of items in queue
		return nItems;
	}

	public void printMiddle() {
		if (nItems % 2 != 0) {
			//System.out.println(queArray[rear / 2]);
			System.out.println(queArray[(int)Math.floor(rear/2)]);
		} else {
			//System.out.println(queArray[rear / 2 + 1]);
			System.out.println(queArray[(int)Math.floor(rear/2) + 1]);
		}
	}
	public String middle()
    {
        int mid = (int)Math.floor(rear/2);
        return queArray[mid];
    }

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		FindMiddle que = new FindMiddle(4);

		String cleanInput = "(REMOVE )|(INSERT )";
		String checkRegex = "(REMOVE .*)|(INSERT .*)";
		boolean stop = false;
		while (!que.isFull() &&!stop) {
			String input = scan.nextLine();
			if(input.equalsIgnoreCase("stop")) {
				//System.out.println("stopping");
				stop = true;
			}
			else if(input.matches("REMOVE")) {
				//System.out.println("removing");
				que.remove();
			}
			else if(input.matches(checkRegex)) {
				input = input.replaceAll(cleanInput, "");
				//System.out.println("adding");
				que.insert(input);
			}
		}


		System.out.println("===print as ordered===");
		while (!que.isEmpty()) {
			System.out.println(que.remove());
		}
		System.out.println("=====================");
		//System.out.println("middle:");
		System.out.println("my middle");
		que.printMiddle();
		System.out.println("your middle");
		System.out.println(que.middle());

	}
}