API tools faq
paste
Advertisement
Mph0

Untitled

Mph0
Nov 28th, 2018
222
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 19.60 KB | None | 0 0
raw download clone embed print report
  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
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!