import java.awt.Color;
import java.awt.Graphics;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.util.ArrayList;
import javax.swing.JApplet;
import javax.swing.JButton;
import javax.swing.JLabel;
import javax.swing.JOptionPane;
import javax.swing.JPanel;
import javax.swing.JSlider;
import javax.swing.JTextField;
import javax.swing.SwingUtilities;
import javax.swing.event.ChangeEvent;
import javax.swing.event.ChangeListener;
 
public class Dragon extends JApplet {
 
	JButton generate = new JButton("Generuj");
	DragonImage panel = new DragonImage();
	ArrayList<Pixel> pixelList = new ArrayList<Pixel>();
	JTextField textField = new JTextField();
	JTextField xCor = new JTextField();
	JTextField yCor = new JTextField();
	JLabel iterLab = new JLabel("Iteracje: ");
	JLabel xLab = new JLabel("x: ");
	JLabel yLab = new JLabel("y: ");
	JLabel zoomLab = new JLabel("zoom: ");
	double x,y;
	JSlider zoomSlider = new JSlider();
	int zoom=100;
 
	public void init(){
		try {
			SwingUtilities.invokeAndWait(new Runnable() {
				public void run() {
					setLayout(null);
					setSize(650, 410);
 
					iterLab.setBounds(418,40,50,20);
					add(iterLab);		
					xLab.setBounds(455,70,50,20);
					add(xLab);
					yLab.setBounds(455,100,50,20);
					add(yLab);
					zoomLab.setBounds(430,130,80,20);
					add(zoomLab);
 
					textField.setBounds(470,40,75,25);
					add(textField);
					xCor.setBounds(470,70,35,25);
					add(xCor);
					yCor.setBounds(470,100,35,25);
					add(yCor);
					generate.setBounds(470, 10, 100, 25);
					generate.addActionListener(new GenButtonListener());
					add(generate);
 
					zoomSlider = new JSlider(1, 1000,100);
					zoomSlider.setBounds(430, 150, 200, 20);
					add(zoomSlider);
					zoomSlider.addChangeListener(new ZoomSliderListener());
 
					add(panel);
					panel.setBounds(5, 5, 400, 400);
					panel.setBackground(Color.white);
					panel.repaint();
				}
			});
		} catch(Exception e){
			JOptionPane.showMessageDialog(null,e.toString(),"Błąd",JOptionPane.ERROR_MESSAGE);
		}
	}
 
	class ZoomSliderListener implements ChangeListener {
		public void stateChanged(ChangeEvent arg0) {
			zoom = zoomSlider.getValue();
			zoomLab.setText("zoom: "+zoom);
			panel.repaint();
		}
	}
 
	class GenButtonListener implements ActionListener{
		public void actionPerformed(ActionEvent arg0) {
			if(xCor.getText().equals("") || yCor.getText().equals("") || textField.getText().equals("") || Integer.parseInt(textField.getText())<100){
				JOptionPane.showMessageDialog(null,"iteracje > 100"+'\n'+"x,y dowolne","Błąd - błędne dane wejściowe",JOptionPane.ERROR_MESSAGE);
			}else{
				int option=0;
				double xp=0,yp=0;
				x = Double.parseDouble(xCor.getText());
				y = Double.parseDouble(yCor.getText());
 
				pixelList.clear();
 
				for(int i=0;i<Integer.parseInt(textField.getText());i++){
					option = (int)Math.round(Math.random());
					if(option==1){
						xp=-0.4*x-1;
						yp=-0.4*y+0.1;
						pixelList.add(new Pixel(xp, yp));
						x=xp;
						y=yp;
					}else{
						xp=0.76*x-0.4*y;
						yp=0.4*x+0.76*y;
						pixelList.add(new Pixel(xp, yp));
						x=xp;
						y=yp;
					}
				}
				for(int i=0;i<100;i++)
					pixelList.remove(0);
 
				panel.repaint();
			}
		}
 
	}
 
	class DragonImage extends JPanel {
 
		public void paint(Graphics g){
			super.paint(g);
			int dx = panel.getWidth()/2;
			int dy = panel.getHeight()/2;
 
			g.setColor(Color.white);
			g.fillRect(0, 0, 300, 300);
 
			g.setColor(Color.LIGHT_GRAY);
			for(int i=1;i<8;i++)
				g.drawLine(50*i, 0, 50*i, 450);
			for(int i=1;i<8;i++)
				g.drawLine(0, 50*i, 450, 50*i);
 
			g.setColor(Color.red);
			for(Pixel pixel:pixelList){
				g.fillRect((int)(pixel.x*zoom)+dx, (int)(pixel.y*zoom)+dy, 1, 1);
			}
		}
	}
 
	class Pixel {
		double x,y;
 
		Pixel(double X,double Y){
			x=X; y=Y;
		}
 
		public void set(double X,double Y){
			x=X; y=Y;
		}
	}
}

public class BinarySearch {
 
	public static int tab[] = {3,5,12,20,28,34,38,41,55,67,71,78,81,85,94,99,102};
 
	//funkcja zwraca indeks elementu, jeśli go nie ma zwróci -1
	public static int binSearch(int find,int left,int right){
		//System.out.println("Szukam "+find+" lewy: "+left+" a prawy: "+right);
		int index=(left+right)/2;
 
		if(tab[index]==find){
 
			return index;
 
		} else {
 
			if(left>right){
 
				//System.out.println("Nie ma takiej liczby!");
				return -1;
 
			} else {
 
				if(tab[index]<find){
 
					return binSearch(find,index+1,right);
 
				} else {
 
					return binSearch(find,left,index-1);
				}
			}
		}
	}
 
	public static void main(String[] args){
		System.out.println(binSearch(67,0,16));
	}
 
}

//********************************
//wierzchołek   1
//lewy potomek  2*i
//prawy potomek 2*i+1
//********************************
public class Heap {
 
	private int tab[];
	private int size = 0;
 
	public Heap(int size){
		tab = new int[size+1];
	}
 
	public void insert(int val){
		tab[++size]=val;
		up();
	}
 
	public void up(){
		int temp=tab[size];
		int n=size;
 
		while( (n!=1) && (tab[n/2]<=temp) ){
			tab[n] = tab[n/2];
			n=n/2;
		}
		tab[n]=temp;
	}
 
	public int getFirst(){
		int temp=tab[1];
		tab[1]=tab[size--];
		down();
		return temp;
	}
 
	public void down(){
		int i=1;
		while(true){
			int pos=2*i;
 
			if(pos>size)
				break;
 
			if(pos+1<=size)
				if(tab[pos]<tab[pos+1])
					pos++;
 
			if(tab[i]>=tab[pos])
				break;
 
			int temp = tab[pos];
			tab[pos]=tab[i];
			tab[i]=temp;
 
			i=pos;
		}
	}
}

public class Test {
 
	public static void main(String[] args){
		int tab[] = {32,43,2,46,23,1,0,-34,54,230};
 
		Heap heap = new Heap(10);
 
		for(int i=0;i<tab.length;i++)
			heap.insert(tab[i]);
 
		for(int i=tab.length;i>0;i--)
			tab[i-1]=heap.getFirst();
 
		System.out.println("Tablica posortowana");
 
		for(int i=0;i<tab.length;i++)
			System.out.println(tab[i]);
	}
 
}

public class BSTree {
	private Node root;
	private Comparator comp;
 
	//konstruktor
	public BSTree(Comparator comparator){
		comp = comparator;
	}
 
	//wyświetlanie inOrder
	public void inOrder(Node node){
		if(node!=null){
			inOrder(node.getLeft());
			System.out.print(node+", ");
			inOrder(node.getRight());
		}
	}
 
	//wyświetlanie preOrder
	public void preOrder(Node node){
		if(node!=null){
			System.out.print(node+", ");
			preOrder(node.getLeft());
			preOrder(node.getRight());
		}
	}
 
	//wyświetlanie postOrder
	public void postOrder(Node node){
		if(node!=null){
			postOrder(node.getLeft());
			postOrder(node.getRight());
			System.out.print(node+", ");
		}
	}
 
	//usuwanie wartości z drzewa
	public Node delete(Object value){
		Node node = search(value);
		if(node==null)
			return null;
 
		Node deleted;
 
		if(node.getLeft()!= null && node.getRight() != null)
			deleted = node.succ();
		else
			deleted = node;
 
		Node replacement;
 
		if(deleted.getLeft() != null)
			replacement = deleted.getLeft();
		else
			replacement = deleted.getRight();
 
		if(replacement != null)
			replacement.setParent(deleted.getParent());
 
		if(deleted == root)
			root = replacement;
		else
			if(deleted.isSmaller())
				deleted.getParent().setLeft(replacement);
			else
				deleted.getParent().setRight(replacement);
 
		if(deleted != node){
			Object deletedValue = node.getValue();
			node.setValue(deleted.getValue());
			deleted.setValue(deletedValue);
		}
 
		return deleted;
	}
 
	//wstawianie wartości do drzewa
	public Node insert(Object value){
		Node parent = null;
		Node node = root;
		int result = 0;
 
		while(node!=null){
			parent = node;
			result = comp.compare(value, node.getValue());
 
			if(result<=0)
				node = node.getLeft();
			else
				node = node.getRight();
		}
 
		Node inserted = new Node(value);
		inserted.setParent(parent);
 
		if(parent==null)
			root=inserted;
		else 
			if(result<0)
				parent.setLeft(inserted);
			else 
				parent.setRight(inserted);
 
		return inserted;
	}
 
	//wyszukiwanie elementu
	public Node search(Object value){
 
		Node node = root;
 
		while(node!=null){
			int result = comp.compare(value, node.getValue());
 
			if(result==0)
				return node;
 
			if(result<0)
				node = node.getLeft();
			else
				node = node.getRight();
		}
		return null;
	}
 
	public Node getRoot(){
		return root;
	}
 
	public String toString(){
		return root.toString();
	}
}

public class Node implements Cloneable {
 
	private Node parent;
	private Node left;
	private Node right;
 
	private Object value;
 
	public Node(Object value){
		this(value,null,null);
	}
 
	public Node(Object v,Node l,Node r){
		value=v;
		left=l;
		right=r;
 
		if(left!=null){
			left.setParent(this);
		}
 
		if(right!=null){
			right.setParent(this);
		}
	}
 
	//wysokosc
	public int height(Node node){
		return node==null?-1:1+Math.max(height(node.left),height(node.right));
	}
 
	//następnik
	public Node pred(){
		if(getLeft()!=null)
			return getLeft().max();
 
		Node node = this;
 
		while(node.isSmaller())
			node = node.getParent();
 
		return node.getParent();
	}
 
	//następnik
	public Node succ(){
		if(getRight()!=null)
			return getRight().min();
 
		Node node = this;
 
		while(node.isLarger())
			node = node.getParent();
 
		return node.getParent();
	}
 
	//najmniejszy węzeł
	public Node min(){
		Node node = this;
 
		while(node.getLeft()!=null)
			node=node.getLeft();
 
		return node;
	}
 
	//największy węzeł
	public Node max(){
		Node node = this;
 
		while(node.getRight()!=null)
			node=node.getRight();
 
		return node;
	}
 
	public Node clone() throws CloneNotSupportedException {
		Node node = (Node)super.clone();
		return node;
	}
 
	public Object getValue(){
		return value;
	}
 
	public Node getLeft(){
		return left;
	}
 
	public Node getRight(){
		return right;
	}
 
	public Node getParent(){
		return parent;
	}
 
	public void setLeft(Node node){
		left = node;
	}
 
	public void setRight(Node node){
		right = node;
	}
 
	public void setParent(Node node){
		parent = node;
	}
 
	public void setValue(Object val){
		value=val;
	}
 
	public String toString(){
		return value.toString();
	}
 
	//czy jest mniejszym z synow
	public boolean isSmaller(){
		return getParent() != null && this.equals(getParent().getLeft());
	}
 
	//czy jest wiekszym z synow
	public boolean isLarger(){
		return getParent() != null && this.equals(getParent().getRight());
	}
}

public interface Comparator {
 
    public int compare(Object left, Object right) throws ClassCastException;
 
}

public class CharCom implements Comparator {
 
	public int compare(Object left, Object right) throws ClassCastException {
		int result = (Character)left-(Character)right;
		return result;
	}
 
}

public class IntCom implements Comparator {
 
	public int compare(Object left, Object right) throws ClassCastException {
		int result = (Integer)left-(Integer)right;
		return result;
	}
 
}

public class Test {
 
	public static void main(String[] args){
		BSTree tree = new BSTree(new IntCom());
 
		tree.insert(13);
		tree.insert(14);
		tree.insert(10);
		tree.insert(5);
		tree.insert(12);
		tree.insert(11);
		tree.insert(7);
		tree.insert(4);
		tree.insert(6);
 
		//tree.delete(10);
 
		System.out.println("postOrder:");
		tree.postOrder(tree.getRoot());
		System.out.println("\ninOrder:");
		tree.inOrder(tree.getRoot());
		System.out.println("\npreOrder:");
		tree.preOrder(tree.getRoot());
 
		System.out.println();
		System.out.println("min: "+tree.getRoot().min());
		System.out.println("max: "+tree.getRoot().max());
 
	}
 
}

public class FifoQueue implements Queue {
 
	private final int INITIAL_CAPACITY = 5;
	private Object _tab[];
	private int _size = 0;
 
	//konstruktor
	public FifoQueue() {
		_tab = new Object[INITIAL_CAPACITY];
	}
 
	//Odkłada obiekt na koniec kolejki
	public void enqueue(Object ob){
		// gdy w tablicy zaczyna brakować miejsca zwiększamy jej rozmiar o połowę
		if(_tab.length==_size){
			Object temp[] = new Object[_size+_size/2];
			System.arraycopy(_tab, 0, temp, 0, _size);
			_tab = temp;
		}
 
		_tab[_size]=ob;
		_size++;
	}
 
	//Pobiera z kolejki obiekt, który został, zapisany jako pierwszy
	public Object dequeue() throws Exception{
		if(_size==0) 
			throw new Exception(); 
 
		Object temp = _tab[0];
		System.arraycopy(_tab, 1, _tab, 0, _tab.length-1);
 
		_size--;
		return temp;
	}
 
	//Usuwa wszystkie obiekty z kolejki
	public void clear(){
		_tab = new Object[INITIAL_CAPACITY];
		_size=0;
	}
 
	//Podaje rozmiar kolejki
	public int size(){
		return _size;
	}
 
	//Sprawdza czy kolejka jest pusta
	public boolean isEmpty(){
		return _size==0;
	}
}

public class Test {
 
	public static FifoQueue kolejka = new FifoQueue();
 
	public static void main(String[] args){
		//Sprawdzamy czy kolejka jest pusta
		System.out.println( kolejka.isEmpty() );
 
		//Dodajemy dwa obiekty string do kolejki
		kolejka.enqueue("Piotr");
		kolejka.enqueue("Alicja");
 
		//Ponownie sprawdzamy czy kolejka jest pusta
		System.out.println( kolejka.isEmpty() );
 
		//Odczytujemy rozmiar
		System.out.println( kolejka.size() );
 
		//Pobieramy element dodany jako pierwszy
		System.out.println( kolejka.dequeue() );
 
		//Znów dodajemy kikla obiektów
		kolejka.enqueue("Marcin");
		kolejka.enqueue("Halina");
		kolejka.enqueue("Tomek");
		kolejka.enqueue("Ania");
 
		kolejka.clear();
 
		//Odczytujemy rozmiar i sprawdzamy czy jest pusta
		System.out.println( kolejka.size() );
		System.out.println( kolejka.isEmpty() );
 
	}
 
}