Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- package fr.istic.prg1.tree;
- import java.awt.Color;
- import java.util.Scanner;
- import fr.istic.prg1.tree_util.AbstractImage;
- import fr.istic.prg1.tree_util.Iterator;
- import fr.istic.prg1.tree_util.Node;
- import fr.istic.prg1.tree_util.NodeType;
- /**
- * @author Mickaël Foursov <foursov@univ-rennes1.fr>
- * @version 5.0
- * @since 2016-04-20
- * <p>
- * Classe décrivant les images en noir et blanc de 256 sur 256 pixels
- * sous forme d'arbres binaires.
- */
- public class Image extends AbstractImage
- {
- private static final Scanner standardInput = new Scanner(System.in);
- public Image()
- {
- super();
- }
- public static void closeAll()
- {
- standardInput.close();
- }
- /**
- * @param x abscisse du point
- * @param y ordonnée du point
- * @return true, si le point (x, y) est allumé dans this, false sinon
- * @pre !this.isEmpty()
- */
- @Override
- public boolean isPixelOn(int x, int y)
- {
- return isPixelAux(x, y, 0, 0, WINDOW_SIZE, WINDOW_SIZE, true, this.iterator());
- }
- private boolean isPixelAux(int x, int y, int xMin, int yMin, int xMax, int yMax, boolean horizontal, Iterator<Node> it)
- {
- if (it.getValue().equals(Node.valueOf(2)))
- {
- if (horizontal)
- {
- int yMid = (yMax + yMin) / 2;
- if (y < yMid)
- {
- it.goLeft();
- return isPixelAux(x, y, xMin, yMin, xMax, yMid, false, it);
- } else
- {
- it.goRight();
- return isPixelAux(x, y, xMin, yMid, xMax, yMax, false, it);
- }
- } else
- {
- int xMid = (xMax + xMin) / 2;
- if (x < xMid)
- {
- it.goLeft();
- return isPixelAux(x, y, xMin, yMin, xMid, yMax, true, it);
- } else
- {
- it.goRight();
- return isPixelAux(x, y, xMid, yMin, xMax, yMax, true, it);
- }
- }
- } else
- {
- return it.getValue().state == 1;
- }
- }
- /**
- * this devient identique à image2.
- *
- * @param image2 image à copier
- * @pre !image2.isEmpty()
- */
- @Override
- public void affect(AbstractImage image2)
- {
- Iterator<Node> it = this.iterator();
- Iterator<Node> sit = image2.iterator();
- it.clear();
- affectAux(it, sit);
- }
- private void affectAux(Iterator<Node> it, Iterator<Node> sit)
- {
- if (sit.isEmpty())
- {
- it.clear();
- } else
- {
- if (!it.isEmpty())
- {
- it.clear();
- }
- it.addValue(Node.valueOf(sit.getValue().state));
- it.goLeft();
- sit.goLeft();
- affectAux(it, sit);
- it.goUp();
- sit.goUp();
- it.goRight();
- sit.goRight();
- affectAux(it, sit);
- it.goUp();
- sit.goUp();
- }
- }
- /**
- * this devient rotation de image2 à 180 degrés.
- *
- * @param image2 image pour rotation
- * @pre !image2.isEmpty()
- */
- @Override
- public void rotate180(AbstractImage image2)
- {
- Iterator<Node> it = iterator();
- it.clear();
- affectAux(it, image2.iterator());
- rotate180Aux(it);
- }
- /**
- * this devient rotation de image2 à 90 degrés dans le sens des aiguilles
- * d'une montre.
- *
- * @param image2 image pour rotation
- * @pre !image2.isEmpty()
- */
- @Override
- public void rotate90(AbstractImage image2)
- {
- System.out.println();
- System.out.println("-------------------------------------------------");
- System.out.println("Fonction non demeand�e");
- System.out.println("-------------------------------------------------");
- System.out.println();
- }
- private void rotate180Aux(Iterator<Node> it)
- {
- if (!it.isEmpty())
- {
- if (it.getValue().equals(Node.valueOf(2)))
- {
- it.goLeft();
- rotate180Aux(it);
- it.goUp();
- it.goRight();
- rotate180Aux(it);
- it.goUp();
- swapChildren(it);
- }
- }
- }
- /**
- * swap the children of the Element where 'it' is placed
- *
- * @param it
- */
- private void swapChildren(Iterator<Node> it)
- {
- if (!it.isEmpty())
- {
- if (it.getValue().equals(Node.valueOf(2)))
- {
- it.goRight();
- Image right = new Image();
- right.affectAux(right.iterator(), it);
- it.goUp();
- it.goLeft();
- Image left = new Image();
- affectAux(left.iterator(), it);
- it.clear();
- affectAux(it, right.iterator());
- it.goUp();
- it.goRight();
- it.clear();
- affectAux(it, left.iterator());
- it.goUp();
- }
- }
- }
- /**
- * this devient inverse vidéo de this, pixel par pixel.
- *
- * @pre !image.isEmpty()
- */
- @Override
- public void videoInverse()
- {
- vidAux(iterator());
- }
- private void vidAux(Iterator<Node> it)
- {
- if (!it.isEmpty())
- {
- if (it.getValue().state == 1)
- {
- it.setValue(Node.valueOf(0));
- } else if (it.getValue().state == 0)
- {
- it.setValue(Node.valueOf(1));
- } else
- {
- it.goRight();
- vidAux(it);
- it.goUp();
- it.goLeft();
- vidAux(it);
- it.goUp();
- }
- }
- }
- /**
- * this devient image miroir verticale de image2.
- *
- * @param image2 image à agrandir
- * @pre !image2.isEmpty()
- *
- * @warning tests de mirrorV et mirrorH inversé, donc noms de fonctions érronés.
- */
- @Override
- public void mirrorV(AbstractImage image2)
- {
- Iterator<Node> it = iterator();
- it.clear();
- affectAux(it, image2.iterator());
- mirrorAux(it, true);
- }
- /**
- * this devient image miroir horizontale de image2.
- *
- * @param image2 image à agrandir
- * @pre !image2.isEmpty()
- */
- @Override
- public void mirrorH(AbstractImage image2)
- {
- Iterator<Node> it = this.iterator();
- it.clear();
- affectAux(it, image2.iterator());
- mirrorAux(it, false);
- }
- private void mirrorAux(Iterator<Node> it, boolean swap)
- {
- if (it.getValue().equals(Node.valueOf(2)))
- {
- it.goLeft();
- mirrorAux(it, !swap);
- it.goUp();
- it.goRight();
- mirrorAux(it, !swap);
- it.goUp();
- if (swap)
- {
- swapChildren(it);
- }
- }
- }
- /**
- * this devient quart supérieur gauche de image2.
- *
- * @param image2 image à agrandir
- * @pre !image2.isEmpty()
- */
- @Override
- public void zoomIn(AbstractImage image2)
- {
- Iterator<Node> it = this.iterator();
- it.clear();
- zoomInAux(it, image2.iterator());
- }
- private void zoomInAux(Iterator<Node> it, Iterator<Node> it1)
- {
- if (it1.getValue().equals(Node.valueOf(2)))
- {
- it1.goLeft(); //partie sup
- if (it1.getValue().equals(Node.valueOf(2)))
- {
- it1.goLeft(); //partie gauche de partie sup -> quart sup gauche
- }
- affectAux(it, it1);
- }
- }
- /**
- * Le quart supérieur gauche de this devient image2, le reste de this
- * devient éteint.
- *
- * @param image2 image à réduire
- * @pre !image2.isEmpty()
- */
- @Override
- public void zoomOut(AbstractImage image2)
- {
- Iterator<Node> it = this.iterator();
- it.clear();
- zoomOutAux(it, reduce(image2.iterator(), 0).iterator());
- }
- private void zoomOutAux(Iterator<Node> it, Iterator<Node> it1)
- {
- it.clear();
- it.addValue(Node.valueOf(2));
- it.goLeft();
- it.addValue(Node.valueOf(2));
- it.goLeft();
- affectAux(it, it1);
- it.goUp();
- it.goRight();
- it.addValue(Node.valueOf(0));
- it.goUp();
- fix(it);
- it.goUp();
- it.goRight();
- it.addValue(Node.valueOf(0));
- it.goUp();
- fix(it);
- }
- /**
- * Retourne l'image reduite de it pour correspondre au nombre de pixels présent dans 1/4 de la taille de la fenêtre
- *
- * @param it
- * @param height
- * @return
- */
- private Image reduce(Iterator<Node> it, int height)
- {
- Image ret = new Image();
- Iterator<Node> retIt = ret.iterator();
- int maxHeight = (int) (Math.log(256 / 2) / Math.log(2) + 1e-10) * 2;
- if (height == maxHeight)
- {
- if (freqOne(it, 1) >= 0.5)
- {
- retIt.addValue(Node.valueOf(1));
- } else
- {
- retIt.addValue(Node.valueOf(0));
- }
- } else if (it.getValue().equals(Node.valueOf(1)))
- {
- retIt.addValue(Node.valueOf(1));
- } else if (it.getValue().equals(Node.valueOf(0)))
- {
- retIt.addValue(Node.valueOf(0));
- } else
- {
- retIt.addValue(Node.valueOf(2));
- it.goLeft();
- retIt.goLeft();
- Image temp = new Image();
- temp = reduce(it, height + 1);
- affectAux(retIt, temp.iterator());
- it.goUp();
- it.goRight();
- retIt.goUp();
- retIt.goRight();
- temp = reduce(it, height + 1);
- affectAux(retIt, temp.iterator());
- it.goUp();
- retIt.goUp();
- fix(retIt);
- }
- return ret;
- }
- /**
- * Calcule la fréquence de 1 dans l'arbre afin de le simplifier lors de la réduction
- * @param it
- * @param divideBy
- * @return le pourcentage de 1 au noeud où it est situé
- */
- private double freqOne(Iterator<Node> it, int divideBy)
- {
- if (it.getValue().equals(Node.valueOf(2)))
- {
- it.goLeft();
- double left = freqOne(it, divideBy * 2);
- it.goUp();
- it.goRight();
- double right = freqOne(it, divideBy * 2);
- it.goUp();
- return left + right;
- } else if (it.getValue().equals(Node.valueOf(0)))
- {
- return 0;
- } else
- {
- return (double) 1 / (double) divideBy;
- }
- }
- /**
- * this devient l'intersection de image1 et image2 au sens des pixels
- * allumés.
- *
- * @param image1 premiere image
- * @param image2 seconde image
- * @pre !image1.isEmpty() && !image2.isEmpty()
- */
- @Override
- public void intersection(AbstractImage image1, AbstractImage image2)
- {
- Iterator<Node> it = this.iterator();
- it.clear();
- Iterator<Node> it1 = image1.iterator();
- Iterator<Node> it2 = image2.iterator();
- intersectionAux(it, it1, it2);
- }
- private void intersectionAux(Iterator<Node> it, Iterator<Node> it1, Iterator<Node> it2)
- {
- if (it1.getValue().state == 0)
- {
- //si == 0 l'intersection est finie ici
- it.addValue(Node.valueOf(it1.getValue().state));
- } else if (it1.getValue().state == 1)
- {
- //si it1 == 1 l'intersection est image 2
- affectAux(it, it2);
- } else if (it2.getValue().state == 0)
- {
- //idem above
- it.addValue(Node.valueOf(it2.getValue().state));
- } else if (it2.getValue().state == 1)
- {
- //idem above
- affectAux(it, it1);
- } else
- {
- it.addValue(Node.valueOf(2));
- it.goLeft();
- it1.goLeft();
- it2.goLeft();
- intersectionAux(it, it1, it2);
- int tmp0 = it.getValue().state;
- it.goUp();
- it1.goUp();
- it2.goUp();
- it.goRight();
- it1.goRight();
- it2.goRight();
- intersectionAux(it, it1, it2);
- int tmp1 = it.getValue().state;
- it.goUp();
- it1.goUp();
- it2.goUp();
- fix(it);
- }
- }
- /**
- * this devient l'union de image1 et image2 au sens des pixels allumés.
- *
- * @param image1 premiere image
- * @param image2 seconde image
- * @pre !image1.isEmpty() && !image2.isEmpty()
- */
- @Override
- public void union(AbstractImage image1, AbstractImage image2)
- {
- Iterator<Node> it = this.iterator();
- it.clear();
- unionAux(it, image1.iterator(), image2.iterator());
- }
- private void unionAux(Iterator<Node> it, Iterator<Node> it1, Iterator<Node> it2)
- {
- int state1 = it1.getValue().state;
- int state2 = it2.getValue().state;
- if (state1 == state2 && state1 == 0)
- {
- it.addValue(Node.valueOf(0));
- } else if (state1 == 1 || state2 == 1)
- {
- it.addValue(Node.valueOf(1));
- } else if (state1 == state2 && state1 == 2)
- {
- it.addValue(Node.valueOf(2));
- it1.goLeft();
- it2.goLeft();
- it.goLeft();
- unionAux(it, it1, it2);
- it.goUp();
- it.goRight();
- it1.goUp();
- it1.goRight();
- it2.goUp();
- it2.goRight();
- unionAux(it, it1, it2);
- it.goUp();
- it1.goUp();
- it2.goUp();
- fix(it);
- } else if (state1 == 0)
- {
- affectAux(it, it2);
- } else
- {
- affectAux(it, it1);
- }
- }
- /**
- * Attention : cette fonction ne doit pas utiliser la commande isPixelOn
- *
- * @return true si tous les points de la forme (x, x) (avec 0 <= x <= 255)
- * sont allumés dans this, false sinon
- */
- @Override
- public boolean testDiagonal()
- {
- Iterator<Node> it = this.iterator();
- return it.getValue().state == 1 || testDiagAux(it);
- }
- private boolean testDiagAux(Iterator<Node> it)
- {
- if (it.getValue().state == 1)
- {
- return true;
- } else if (it.getValue().state == 2)
- {
- it.goLeft();
- boolean left = aux(it, true);
- it.goUp();
- it.goRight();
- boolean right = aux(it, false);
- it.goUp();
- return left && right;
- } else
- {
- return false;
- }
- }
- /**
- * fonction auxiliaire à la fonction testDiagAux, qui permet de
- * @param it
- * @param isLeft
- * @return
- */
- private boolean aux(Iterator<Node> it, boolean isLeft)
- {
- if (it.getValue().state == 1)
- {
- return true;
- } else if (it.getValue().state == 0)
- {
- return false;
- } else
- {
- if (isLeft)
- {
- it.goLeft();
- } else
- {
- it.goRight();
- }
- boolean ret = testDiagAux(it);
- it.goUp();
- return ret;
- }
- }
- /**
- * @param x1 abscisse du premier point
- * @param y1 ordonnée du premier point
- * @param x2 abscisse du deuxième point
- * @param y2 ordonnée du deuxième point
- * @return true si les deux points (x1, y1) et (x2, y2) sont représentés par
- * la même feuille de this, false sinon
- * @pre !this.isEmpty()
- */
- @Override
- public boolean sameLeaf(int x1, int y1, int x2, int y2)
- {
- return sameLeafAux(x1, y1, x2, y2, 0, 0, AbstractImage.WINDOW_SIZE, AbstractImage.WINDOW_SIZE, true, iterator());
- }
- private boolean sameLeafAux(int x1, int y1, int x2, int y2, int xMin, int yMin, int xMax, int yMax, boolean horizontal, Iterator<Node> it)
- {
- if (it.getValue().state == 2)
- {
- if (horizontal)
- {
- int yMid = (yMax + yMin) / 2;
- if (y1 < yMid && y2 < yMid)
- {
- it.goLeft();
- return sameLeafAux(x1, y1, x2, y2, xMin, yMin, xMax, yMid, false, it);
- } else if (y1 >= yMid && y2 >= yMid)
- {
- it.goRight();
- return sameLeafAux(x1, y1, x2, y2, xMin, yMid, xMax, yMax, false, it);
- } else
- {
- return false;
- }
- } else
- {
- int xMid = (xMax + xMin) / 2;
- if (x1 < xMid && x2 < xMid)
- {
- it.goLeft();
- return sameLeafAux(x1, y1, x2, y2, xMin, yMin, xMid, yMax, true, it);
- } else if (x1 >= xMid && x2 >= xMid)
- {
- it.goRight();
- return sameLeafAux(x1, y1, x2, y2, xMid, yMin, xMax, yMax, true, it);
- } else
- {
- return false;
- }
- }
- } else
- {
- return true;
- }
- }
- /**
- * @param image2 autre image
- * @return true si this est incluse dans image2 au sens des pixels allumés
- * false sinon
- * @pre !this.isEmpty() && !image2.isEmpty()
- */
- @Override
- public boolean isIncludedIn(AbstractImage image2)
- {
- return isIncludedAux(this.iterator(), image2.iterator());
- }
- private boolean isIncludedAux(Iterator<Node> it, Iterator<Node> it1)
- {
- if (((it.getValue().state == 1 || it.getValue().state == 2) && it1.getValue().state == 0)
- || it.getValue().state == 1 && it1.getValue().state == 2)
- {
- return false;
- } else if (it.getValue().state == it1.getValue().state && it1.getValue().state == 2)
- {
- it.goLeft();
- it1.goLeft();
- boolean left = isIncludedAux(it, it1);
- it.goUp();
- it.goRight();
- it1.goUp();
- it1.goRight();
- boolean right = isIncludedAux(it, it1);
- it.goUp();
- it1.goUp();
- return left && right;
- } else
- {
- return true;
- }
- }
- /**
- * Si un noeud d'état deux possède deux fils de même état, change l'état du noeud à celui des fils
- * @param it
- */
- private void fix(Iterator<Node> it)
- {
- it.goLeft();
- Node n = it.getValue();
- it.goUp();
- it.goRight();
- Node n2 = it.getValue();
- Node n3 = Node.valueOf(2);
- if (n.equals(n2) && !n.equals(Node.valueOf(2)))
- {
- it.clear();
- it.goUp();
- it.goLeft();
- it.clear();
- n3 = n2;
- }
- it.goUp();
- it.setValue(n3);
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement