Advertisement
Mph0

Untitled

Nov 28th, 2018
220
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 19.60 KB | None | 0 0
  1. package fr.istic.prg1.tree;
  2.  
  3.  
  4. import java.awt.Color;
  5. import java.util.Scanner;
  6.  
  7. import fr.istic.prg1.tree_util.AbstractImage;
  8. import fr.istic.prg1.tree_util.Iterator;
  9. import fr.istic.prg1.tree_util.Node;
  10. import fr.istic.prg1.tree_util.NodeType;
  11.  
  12. /**
  13.  * @author Mickaël Foursov <foursov@univ-rennes1.fr>
  14.  * @version 5.0
  15.  * @since 2016-04-20
  16.  * <p>
  17.  * Classe décrivant les images en noir et blanc de 256 sur 256 pixels
  18.  * sous forme d'arbres binaires.
  19.  */
  20.  
  21. public class Image extends AbstractImage
  22. {
  23.     private static final Scanner standardInput = new Scanner(System.in);
  24.  
  25.     public Image()
  26.     {
  27.         super();
  28.     }
  29.  
  30.     public static void closeAll()
  31.     {
  32.         standardInput.close();
  33.     }
  34.  
  35.     /**
  36.      * @param x abscisse du point
  37.      * @param y ordonnée du point
  38.      * @return true, si le point (x, y) est allumé dans this, false sinon
  39.      * @pre !this.isEmpty()
  40.      */
  41.     @Override
  42.     public boolean isPixelOn(int x, int y)
  43.     {
  44.         return isPixelAux(x, y, 0, 0, WINDOW_SIZE, WINDOW_SIZE, true, this.iterator());
  45.     }
  46.  
  47.     private boolean isPixelAux(int x, int y, int xMin, int yMin, int xMax, int yMax, boolean horizontal, Iterator<Node> it)
  48.     {
  49.         if (it.getValue().equals(Node.valueOf(2)))
  50.         {
  51.             if (horizontal)
  52.             {
  53.                 int yMid = (yMax + yMin) / 2;
  54.                 if (y < yMid)
  55.                 {
  56.                     it.goLeft();
  57.                     return isPixelAux(x, y, xMin, yMin, xMax, yMid, false, it);
  58.                 } else
  59.                 {
  60.                     it.goRight();
  61.                     return isPixelAux(x, y, xMin, yMid, xMax, yMax, false, it);
  62.                 }
  63.  
  64.             } else
  65.             {
  66.                 int xMid = (xMax + xMin) / 2;
  67.                 if (x < xMid)
  68.                 {
  69.                     it.goLeft();
  70.                     return isPixelAux(x, y, xMin, yMin, xMid, yMax, true, it);
  71.                 } else
  72.                 {
  73.                     it.goRight();
  74.                     return isPixelAux(x, y, xMid, yMin, xMax, yMax, true, it);
  75.                 }
  76.  
  77.             }
  78.         } else
  79.         {
  80.             return it.getValue().state == 1;
  81.         }
  82.     }
  83.  
  84.     /**
  85.      * this devient identique à image2.
  86.      *
  87.      * @param image2 image à copier
  88.      * @pre !image2.isEmpty()
  89.      */
  90.  
  91.     @Override
  92.     public void affect(AbstractImage image2)
  93.     {
  94.         Iterator<Node> it = this.iterator();
  95.         Iterator<Node> sit = image2.iterator();
  96.         it.clear();
  97.         affectAux(it, sit);
  98.     }
  99.  
  100.     private void affectAux(Iterator<Node> it, Iterator<Node> sit)
  101.     {
  102.         if (sit.isEmpty())
  103.         {
  104.             it.clear();
  105.         } else
  106.         {
  107.             if (!it.isEmpty())
  108.             {
  109.                 it.clear();
  110.             }
  111.             it.addValue(Node.valueOf(sit.getValue().state));
  112.             it.goLeft();
  113.             sit.goLeft();
  114.             affectAux(it, sit);
  115.             it.goUp();
  116.             sit.goUp();
  117.             it.goRight();
  118.             sit.goRight();
  119.             affectAux(it, sit);
  120.             it.goUp();
  121.             sit.goUp();
  122.         }
  123.     }
  124.  
  125.     /**
  126.      * this devient rotation de image2 à 180 degrés.
  127.      *
  128.      * @param image2 image pour rotation
  129.      * @pre !image2.isEmpty()
  130.      */
  131.     @Override
  132.     public void rotate180(AbstractImage image2)
  133.     {
  134.         Iterator<Node> it = iterator();
  135.         it.clear();
  136.         affectAux(it, image2.iterator());
  137.         rotate180Aux(it);
  138.     }
  139.  
  140.     /**
  141.      * this devient rotation de image2 à 90 degrés dans le sens des aiguilles
  142.      * d'une montre.
  143.      *
  144.      * @param image2 image pour rotation
  145.      * @pre !image2.isEmpty()
  146.      */
  147.     @Override
  148.     public void rotate90(AbstractImage image2)
  149.     {
  150.         System.out.println();
  151.         System.out.println("-------------------------------------------------");
  152.         System.out.println("Fonction non demeand�e");
  153.         System.out.println("-------------------------------------------------");
  154.         System.out.println();
  155.     }
  156.  
  157.     private void rotate180Aux(Iterator<Node> it)
  158.     {
  159.         if (!it.isEmpty())
  160.         {
  161.             if (it.getValue().equals(Node.valueOf(2)))
  162.             {
  163.                 it.goLeft();
  164.                 rotate180Aux(it);
  165.                 it.goUp();
  166.                 it.goRight();
  167.                 rotate180Aux(it);
  168.                 it.goUp();
  169.                 swapChildren(it);
  170.             }
  171.         }
  172.     }
  173.  
  174.     /**
  175.      * swap the children of the Element where 'it' is placed
  176.      *
  177.      * @param it
  178.      */
  179.     private void swapChildren(Iterator<Node> it)
  180.     {
  181.         if (!it.isEmpty())
  182.         {
  183.             if (it.getValue().equals(Node.valueOf(2)))
  184.             {
  185.                 it.goRight();
  186.                 Image right = new Image();
  187.                 right.affectAux(right.iterator(), it);
  188.                 it.goUp();
  189.                 it.goLeft();
  190.                 Image left = new Image();
  191.                 affectAux(left.iterator(), it);
  192.                 it.clear();
  193.                 affectAux(it, right.iterator());
  194.                 it.goUp();
  195.                 it.goRight();
  196.                 it.clear();
  197.                 affectAux(it, left.iterator());
  198.                 it.goUp();
  199.             }
  200.         }
  201.     }
  202.  
  203.     /**
  204.      * this devient inverse vidéo de this, pixel par pixel.
  205.      *
  206.      * @pre !image.isEmpty()
  207.      */
  208.     @Override
  209.     public void videoInverse()
  210.     {
  211.         vidAux(iterator());
  212.  
  213.     }
  214.  
  215.     private void vidAux(Iterator<Node> it)
  216.     {
  217.         if (!it.isEmpty())
  218.         {
  219.             if (it.getValue().state == 1)
  220.             {
  221.                 it.setValue(Node.valueOf(0));
  222.             } else if (it.getValue().state == 0)
  223.             {
  224.                 it.setValue(Node.valueOf(1));
  225.             } else
  226.             {
  227.                 it.goRight();
  228.                 vidAux(it);
  229.                 it.goUp();
  230.                 it.goLeft();
  231.                 vidAux(it);
  232.                 it.goUp();
  233.             }
  234.         }
  235.     }
  236.  
  237.     /**
  238.      * this devient image miroir verticale de image2.
  239.      *
  240.      * @param image2 image à agrandir
  241.      * @pre !image2.isEmpty()
  242.      *
  243.      * @warning tests de mirrorV et mirrorH inversé, donc noms de fonctions érronés.
  244.      */
  245.     @Override
  246.     public void mirrorV(AbstractImage image2)
  247.     {
  248.         Iterator<Node> it = iterator();
  249.         it.clear();
  250.         affectAux(it, image2.iterator());
  251.         mirrorAux(it, true);
  252.     }
  253.  
  254.  
  255.     /**
  256.      * this devient image miroir horizontale de image2.
  257.      *
  258.      * @param image2 image à agrandir
  259.      * @pre !image2.isEmpty()
  260.      */
  261.     @Override
  262.     public void mirrorH(AbstractImage image2)
  263.     {
  264.         Iterator<Node> it = this.iterator();
  265.         it.clear();
  266.         affectAux(it, image2.iterator());
  267.         mirrorAux(it, false);
  268.     }
  269.  
  270.     private void mirrorAux(Iterator<Node> it, boolean swap)
  271.     {
  272.         if (it.getValue().equals(Node.valueOf(2)))
  273.         {
  274.             it.goLeft();
  275.             mirrorAux(it, !swap);
  276.             it.goUp();
  277.             it.goRight();
  278.             mirrorAux(it, !swap);
  279.             it.goUp();
  280.             if (swap)
  281.             {
  282.                 swapChildren(it);
  283.             }
  284.         }
  285.     }
  286.  
  287.     /**
  288.      * this devient quart supérieur gauche de image2.
  289.      *
  290.      * @param image2 image à agrandir
  291.      * @pre !image2.isEmpty()
  292.      */
  293.     @Override
  294.     public void zoomIn(AbstractImage image2)
  295.     {
  296.         Iterator<Node> it = this.iterator();
  297.         it.clear();
  298.         zoomInAux(it, image2.iterator());
  299.     }
  300.  
  301.     private void zoomInAux(Iterator<Node> it, Iterator<Node> it1)
  302.     {
  303.         if (it1.getValue().equals(Node.valueOf(2)))
  304.         {
  305.             it1.goLeft(); //partie sup
  306.             if (it1.getValue().equals(Node.valueOf(2)))
  307.             {
  308.                 it1.goLeft(); //partie gauche de partie sup -> quart sup gauche
  309.             }
  310.             affectAux(it, it1);
  311.         }
  312.     }
  313.  
  314.     /**
  315.      * Le quart supérieur gauche de this devient image2, le reste de this
  316.      * devient éteint.
  317.      *
  318.      * @param image2 image à réduire
  319.      * @pre !image2.isEmpty()
  320.      */
  321.     @Override
  322.     public void zoomOut(AbstractImage image2)
  323.     {
  324.  
  325.         Iterator<Node> it = this.iterator();
  326.         it.clear();
  327.         zoomOutAux(it, reduce(image2.iterator(), 0).iterator());
  328.  
  329.     }
  330.  
  331.     private void zoomOutAux(Iterator<Node> it, Iterator<Node> it1)
  332.     {
  333.         it.clear();
  334.         it.addValue(Node.valueOf(2));
  335.         it.goLeft();
  336.         it.addValue(Node.valueOf(2));
  337.         it.goLeft();
  338.         affectAux(it, it1);
  339.         it.goUp();
  340.         it.goRight();
  341.         it.addValue(Node.valueOf(0));
  342.         it.goUp();
  343.         fix(it);
  344.         it.goUp();
  345.         it.goRight();
  346.         it.addValue(Node.valueOf(0));
  347.         it.goUp();
  348.         fix(it);
  349.     }
  350.  
  351.     /**
  352.      * Retourne l'image reduite de it pour correspondre au nombre de pixels présent dans 1/4 de la taille de la fenêtre
  353.      *
  354.      * @param it
  355.      * @param height
  356.      * @return
  357.      */
  358.     private Image reduce(Iterator<Node> it, int height)
  359.     {
  360.         Image ret = new Image();
  361.         Iterator<Node> retIt = ret.iterator();
  362.         int maxHeight = (int) (Math.log(256 / 2) / Math.log(2) + 1e-10) * 2;
  363.         if (height == maxHeight)
  364.         {
  365.             if (freqOne(it, 1) >= 0.5)
  366.             {
  367.                 retIt.addValue(Node.valueOf(1));
  368.             } else
  369.             {
  370.                 retIt.addValue(Node.valueOf(0));
  371.             }
  372.         } else if (it.getValue().equals(Node.valueOf(1)))
  373.         {
  374.             retIt.addValue(Node.valueOf(1));
  375.         } else if (it.getValue().equals(Node.valueOf(0)))
  376.         {
  377.             retIt.addValue(Node.valueOf(0));
  378.         } else
  379.         {
  380.             retIt.addValue(Node.valueOf(2));
  381.             it.goLeft();
  382.             retIt.goLeft();
  383.             Image temp = new Image();
  384.             temp = reduce(it, height + 1);
  385.             affectAux(retIt, temp.iterator());
  386.             it.goUp();
  387.             it.goRight();
  388.             retIt.goUp();
  389.             retIt.goRight();
  390.             temp = reduce(it, height + 1);
  391.             affectAux(retIt, temp.iterator());
  392.             it.goUp();
  393.             retIt.goUp();
  394.             fix(retIt);
  395.         }
  396.         return ret;
  397.     }
  398.  
  399.     /**
  400.      * Calcule la fréquence de 1 dans l'arbre afin de le simplifier lors de la réduction
  401.      * @param it
  402.      * @param divideBy
  403.      * @return le pourcentage de 1 au noeud où it est situé
  404.      */
  405.     private double freqOne(Iterator<Node> it, int divideBy)
  406.     {
  407.         if (it.getValue().equals(Node.valueOf(2)))
  408.         {
  409.             it.goLeft();
  410.             double left = freqOne(it, divideBy * 2);
  411.             it.goUp();
  412.             it.goRight();
  413.             double right = freqOne(it, divideBy * 2);
  414.             it.goUp();
  415.             return left + right;
  416.         } else if (it.getValue().equals(Node.valueOf(0)))
  417.         {
  418.             return 0;
  419.         } else
  420.         {
  421.             return (double) 1 / (double) divideBy;
  422.         }
  423.     }
  424.  
  425.     /**
  426.      * this devient l'intersection de image1 et image2 au sens des pixels
  427.      * allumés.
  428.      *
  429.      * @param image1 premiere image
  430.      * @param image2 seconde image
  431.      * @pre !image1.isEmpty() && !image2.isEmpty()
  432.      */
  433.     @Override
  434.     public void intersection(AbstractImage image1, AbstractImage image2)
  435.     {
  436.         Iterator<Node> it = this.iterator();
  437.         it.clear();
  438.         Iterator<Node> it1 = image1.iterator();
  439.         Iterator<Node> it2 = image2.iterator();
  440.         intersectionAux(it, it1, it2);
  441.     }
  442.  
  443.     private void intersectionAux(Iterator<Node> it, Iterator<Node> it1, Iterator<Node> it2)
  444.     {
  445.         if (it1.getValue().state == 0)
  446.         {
  447.             //si == 0 l'intersection est finie ici
  448.             it.addValue(Node.valueOf(it1.getValue().state));
  449.         } else if (it1.getValue().state == 1)
  450.         {
  451.             //si it1 == 1 l'intersection est image 2
  452.             affectAux(it, it2);
  453.         } else if (it2.getValue().state == 0)
  454.         {
  455.             //idem above
  456.             it.addValue(Node.valueOf(it2.getValue().state));
  457.         } else if (it2.getValue().state == 1)
  458.         {
  459.             //idem above
  460.             affectAux(it, it1);
  461.         } else
  462.         {
  463.             it.addValue(Node.valueOf(2));
  464.             it.goLeft();
  465.             it1.goLeft();
  466.             it2.goLeft();
  467.             intersectionAux(it, it1, it2);
  468.             int tmp0 = it.getValue().state;
  469.             it.goUp();
  470.             it1.goUp();
  471.             it2.goUp();
  472.             it.goRight();
  473.             it1.goRight();
  474.             it2.goRight();
  475.             intersectionAux(it, it1, it2);
  476.             int tmp1 = it.getValue().state;
  477.             it.goUp();
  478.             it1.goUp();
  479.             it2.goUp();
  480.             fix(it);
  481.         }
  482.     }
  483.  
  484.     /**
  485.      * this devient l'union de image1 et image2 au sens des pixels allumés.
  486.      *
  487.      * @param image1 premiere image
  488.      * @param image2 seconde image
  489.      * @pre !image1.isEmpty() && !image2.isEmpty()
  490.      */
  491.     @Override
  492.     public void union(AbstractImage image1, AbstractImage image2)
  493.     {
  494.         Iterator<Node> it = this.iterator();
  495.         it.clear();
  496.         unionAux(it, image1.iterator(), image2.iterator());
  497.     }
  498.  
  499.     private void unionAux(Iterator<Node> it, Iterator<Node> it1, Iterator<Node> it2)
  500.     {
  501.         int state1 = it1.getValue().state;
  502.         int state2 = it2.getValue().state;
  503.  
  504.         if (state1 == state2 && state1 == 0)
  505.         {
  506.             it.addValue(Node.valueOf(0));
  507.         } else if (state1 == 1 || state2 == 1)
  508.         {
  509.             it.addValue(Node.valueOf(1));
  510.         } else if (state1 == state2 && state1 == 2)
  511.         {
  512.             it.addValue(Node.valueOf(2));
  513.             it1.goLeft();
  514.             it2.goLeft();
  515.             it.goLeft();
  516.             unionAux(it, it1, it2);
  517.             it.goUp();
  518.             it.goRight();
  519.             it1.goUp();
  520.             it1.goRight();
  521.             it2.goUp();
  522.             it2.goRight();
  523.             unionAux(it, it1, it2);
  524.             it.goUp();
  525.             it1.goUp();
  526.             it2.goUp();
  527.             fix(it);
  528.         } else if (state1 == 0)
  529.         {
  530.             affectAux(it, it2);
  531.         } else
  532.         {
  533.             affectAux(it, it1);
  534.         }
  535.     }
  536.  
  537.  
  538.  
  539.     /**
  540.      * Attention : cette fonction ne doit pas utiliser la commande isPixelOn
  541.      *
  542.      * @return true si tous les points de la forme (x, x) (avec 0 <= x <= 255)
  543.      * sont allumés dans this, false sinon
  544.      */
  545.     @Override
  546.     public boolean testDiagonal()
  547.     {
  548.         Iterator<Node> it = this.iterator();
  549.         return it.getValue().state == 1 || testDiagAux(it);
  550.     }
  551.  
  552.     private boolean testDiagAux(Iterator<Node> it)
  553.     {
  554.         if (it.getValue().state == 1)
  555.         {
  556.             return true;
  557.         } else if (it.getValue().state == 2)
  558.         {
  559.             it.goLeft();
  560.             boolean left = aux(it, true);
  561.             it.goUp();
  562.             it.goRight();
  563.             boolean right = aux(it, false);
  564.             it.goUp();
  565.             return left && right;
  566.         } else
  567.         {
  568.             return false;
  569.         }
  570.     }
  571.  
  572.     /**
  573.      * fonction auxiliaire à la fonction testDiagAux, qui permet de
  574.      * @param it
  575.      * @param isLeft
  576.      * @return
  577.      */
  578.     private boolean aux(Iterator<Node> it, boolean isLeft)
  579.     {
  580.         if (it.getValue().state == 1)
  581.         {
  582.             return true;
  583.         } else if (it.getValue().state == 0)
  584.         {
  585.             return false;
  586.         } else
  587.         {
  588.             if (isLeft)
  589.             {
  590.                 it.goLeft();
  591.             } else
  592.             {
  593.                 it.goRight();
  594.             }
  595.             boolean ret = testDiagAux(it);
  596.             it.goUp();
  597.             return ret;
  598.         }
  599.     }
  600.  
  601.     /**
  602.      * @param x1 abscisse du premier point
  603.      * @param y1 ordonnée du premier point
  604.      * @param x2 abscisse du deuxième point
  605.      * @param y2 ordonnée du deuxième point
  606.      * @return true si les deux points (x1, y1) et (x2, y2) sont représentés par
  607.      * la même feuille de this, false sinon
  608.      * @pre !this.isEmpty()
  609.      */
  610.     @Override
  611.     public boolean sameLeaf(int x1, int y1, int x2, int y2)
  612.     {
  613.         return sameLeafAux(x1, y1, x2, y2, 0, 0, AbstractImage.WINDOW_SIZE, AbstractImage.WINDOW_SIZE, true, iterator());
  614.     }
  615.  
  616.     private boolean sameLeafAux(int x1, int y1, int x2, int y2, int xMin, int yMin, int xMax, int yMax, boolean horizontal, Iterator<Node> it)
  617.     {
  618.         if (it.getValue().state == 2)
  619.         {
  620.             if (horizontal)
  621.             {
  622.                 int yMid = (yMax + yMin) / 2;
  623.                 if (y1 < yMid && y2 < yMid)
  624.                 {
  625.                     it.goLeft();
  626.                     return sameLeafAux(x1, y1, x2, y2, xMin, yMin, xMax, yMid, false, it);
  627.                 } else if (y1 >= yMid && y2 >= yMid)
  628.                 {
  629.  
  630.                     it.goRight();
  631.                     return sameLeafAux(x1, y1, x2, y2, xMin, yMid, xMax, yMax, false, it);
  632.                 } else
  633.                 {
  634.                     return false;
  635.                 }
  636.             } else
  637.             {
  638.                 int xMid = (xMax + xMin) / 2;
  639.                 if (x1 < xMid && x2 < xMid)
  640.                 {
  641.                     it.goLeft();
  642.                     return sameLeafAux(x1, y1, x2, y2, xMin, yMin, xMid, yMax, true, it);
  643.                 } else if (x1 >= xMid && x2 >= xMid)
  644.                 {
  645.  
  646.                     it.goRight();
  647.                     return sameLeafAux(x1, y1, x2, y2, xMid, yMin, xMax, yMax, true, it);
  648.                 } else
  649.                 {
  650.                     return false;
  651.                 }
  652.             }
  653.         } else
  654.         {
  655.             return true;
  656.         }
  657.  
  658.     }
  659.  
  660.  
  661.     /**
  662.      * @param image2 autre image
  663.      * @return true si this est incluse dans image2 au sens des pixels allumés
  664.      * false sinon
  665.      * @pre !this.isEmpty() && !image2.isEmpty()
  666.      */
  667.     @Override
  668.     public boolean isIncludedIn(AbstractImage image2)
  669.     {
  670.         return isIncludedAux(this.iterator(), image2.iterator());
  671.     }
  672.  
  673.     private boolean isIncludedAux(Iterator<Node> it, Iterator<Node> it1)
  674.     {
  675.         if (((it.getValue().state == 1 || it.getValue().state == 2) && it1.getValue().state == 0)
  676.                 || it.getValue().state == 1 && it1.getValue().state == 2)
  677.         {
  678.             return false;
  679.         } else if (it.getValue().state == it1.getValue().state && it1.getValue().state == 2)
  680.         {
  681.             it.goLeft();
  682.             it1.goLeft();
  683.             boolean left = isIncludedAux(it, it1);
  684.             it.goUp();
  685.             it.goRight();
  686.             it1.goUp();
  687.             it1.goRight();
  688.             boolean right = isIncludedAux(it, it1);
  689.             it.goUp();
  690.             it1.goUp();
  691.             return left && right;
  692.         } else
  693.         {
  694.             return true;
  695.         }
  696.     }
  697.  
  698.     /**
  699.      * Si un noeud d'état deux possède deux fils de même état, change l'état du noeud à celui des fils
  700.      * @param it
  701.      */
  702.     private void fix(Iterator<Node> it)
  703.     {
  704.         it.goLeft();
  705.         Node n = it.getValue();
  706.         it.goUp();
  707.         it.goRight();
  708.         Node n2 = it.getValue();
  709.         Node n3 = Node.valueOf(2);
  710.         if (n.equals(n2) && !n.equals(Node.valueOf(2)))
  711.         {
  712.             it.clear();
  713.             it.goUp();
  714.             it.goLeft();
  715.             it.clear();
  716.             n3 = n2;
  717.  
  718.         }
  719.         it.goUp();
  720.         it.setValue(n3);
  721.     }
  722.  
  723. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement