package Task;

import java.util.Arrays;

public class Main {

	/**
	 * sorts an array of bits in a single pass (<=)
	 * because boolean not equals to 0 or 1, type is int
	 * @param array - array of bits
	 * @return void
	 */
	public static void bitSort(int[] array){
		int i=0,j=array.length-1;
		while(i<j){
			while((i<array.length)&&(array[i]==0))++i;
			while((j>-1)&&(array[j]==1))--j;
			if(i<j){
				int temp=array[i];
				array[i]=array[j];
				array[j]=temp;
			}
		}
	}

	/*
	 * use it for testing..
	 */
	public static void testBitSort(){
		System.out.print("try testing bitSort: ");
		int[] test1={};
		bitSort(test1);
		int[] res1={};
		if(Arrays.equals(test1, res1))
			System.out.print('.');
		else
			System.out.print('E');

		int[] test2={0,0,0};
		bitSort(test1);
		int[] res2={0,0,0};
		if(Arrays.equals(test2, res2))
			System.out.print('.');
		else
			System.out.print('E');

		int[] test3={1,1,0};
		bitSort(test1);
		int[] res3={1,1,0};
		if(Arrays.equals(test3, res3))
			System.out.print('.');
		else
			System.out.print('E');

		System.out.println();
	}

	/**
	 * @param array1
	 * @param array2 (both without repetition in each)
	 * @return int number of repetitive elements in both arrays, O(n log n)
	 */
	public static int repeatsNum(int[] array1, int[]array2){
		Arrays.sort(array1);
		Arrays.sort(array2);
		int i=0, j=0, result=0;
		while((i<array1.length)&&(j<array2.length)){
			if(array1[i]==array2[j]){
				++result;
				++i;
				++j;
			}else if(array1[i]>array2[j]){
				++j;
			}else{
				++i;
			}
		}
		return result;
	}

	/*
	 * use it for testing..
	 */
	public static void testRepeatsNum(){
		System.out.print("try testing repeatsNum: ");
		int[] test10={1,1,1}, test11={0,0,0};
		int res= repeatsNum(test10,test11);
		if(res==0)
			System.out.print('.');
		else
			System.out.print('E');

		int[] test20={4,2,3}, test21={3,2,1,4};
		res= repeatsNum(test20,test21);
		if(res==3)
			System.out.print('.');
		else
			System.out.print('E');

		int[] test30={5,4,3}, test31={};
		res= repeatsNum(test30,test31);
		if(res==0)
			System.out.print('.');
		else
			System.out.print('E');

		System.out.println();
	}

	/*
	 * @param matrix[0..n-1][0..m-1], что matrix[i][j]<matrix[i][j+1] && matrix[i][j]<matrix[i+1][j]
	 * @param v - search item
	 * begin with matrix[n-1][0]. right, if larger. up - if less. if can't go - the element is not exist in matrix
	 */
	public static boolean isInMatrix(int v, int[][]matrix){
		int i=matrix.length-1, j=0;
		//пока можем идти
		while((i>-1)&&(j<matrix[0].length)){
			if(v>matrix[i][j]){
				++j;
			}else if(v<matrix[i][j]){
				--i;
			}else{
				return true;
			}
		}
		return false;
	}

	/*
	 * use it for testing..
	 */
	public static void testIsInMatrix(){
		System.out.print("try testing isInMatrix: ");
		int[][] test1={{3,5,8,9},{13,15,17,28},{14,16,18,50}};

		if(isInMatrix(0,test1)==false)
			System.out.print('.');
		else
			System.out.print('E');

		if(isInMatrix(16,test1)==true)
			System.out.print('.');
		else
			System.out.print('E');

		if(isInMatrix(57,test1)==false)
			System.out.print('.');
		else
			System.out.print('E');

		if(isInMatrix(10,test1)==false)
			System.out.print('.');
		else
			System.out.print('E');

		System.out.println();
	}

	/*
	 * use it for testing..
	 */
	public static void testIsCorrect(){
		System.out.print("try testing isCorrect: ");

		if(MyStack.isCorrect("")==true)
			System.out.print('.');
		else
			System.out.print('E');

		if(MyStack.isCorrect("23rfsd")==true)
			System.out.print('.');
		else
			System.out.print('E');

		if(MyStack.isCorrect("(((")==false)
			System.out.print('.');
		else
			System.out.print('E');

		if(MyStack.isCorrect("23)4))")==false)
			System.out.print('.');
		else
			System.out.print('E');

		if(MyStack.isCorrect("[][]{(2+3)*(2-3)}")==true)
			System.out.print('.');
		else
			System.out.print('E');

		System.out.println();
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		//start testing..
		testBitSort();
		testRepeatsNum();
		testIsInMatrix();
		testIsCorrect();


	}

}