API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Aug 27th, 2016
77
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 14.54 KB | None | 0 0
raw download clone embed print report
  1. package adt.bst;
  2.  
  3. import static org.junit.Assert.*;
  4.  
  5. import org.junit.Before;
  6. import org.junit.Test;
  7. import adt.bt.BTNode;
  8.  
  9. import java.util.*;
  10.  
  11. public class StudentBSTTest {
  12.  
  13.     private BSTImpl<Integer> tree;
  14.     private BTNode<Integer> NIL = new BTNode<Integer>();
  15.  
  16.     private void fillTree() {
  17.         Integer[] array = { 6, 23, -34, 5, 9, 2, 0, 76, 12, 67, 232, -40 };
  18.         for (int i : array) {
  19.             tree.insert(i);
  20.         }
  21.     }
  22.  
  23.     @Before
  24.     public void setUp() {
  25.         tree = new BSTImpl<>();
  26.     }
  27.  
  28.     @Test
  29.     public void testInit() {
  30.         assertTrue(tree.isEmpty());
  31.         assertEquals(0, tree.size());
  32.         assertEquals(-1, tree.height());
  33.  
  34.         assertEquals(NIL, tree.getRoot());
  35.  
  36.         assertArrayEquals(new Integer[] {}, tree.order());
  37.         assertArrayEquals(new Integer[] {}, tree.preOrder());
  38.         assertArrayEquals(new Integer[] {}, tree.postOrder());
  39.  
  40.         assertEquals(NIL, tree.search(12));
  41.         assertEquals(NIL, tree.search(-23));
  42.         assertEquals(NIL, tree.search(0));
  43.  
  44.         assertEquals(null, tree.minimum());
  45.         assertEquals(null, tree.maximum());
  46.  
  47.         assertEquals(null, tree.sucessor(12));
  48.         assertEquals(null, tree.sucessor(-23));
  49.         assertEquals(null, tree.sucessor(0));
  50.  
  51.         assertEquals(null, tree.predecessor(12));
  52.         assertEquals(null, tree.predecessor(-23));
  53.         assertEquals(null, tree.predecessor(0));
  54.     }
  55.  
  56.     @Test
  57.     public void testMinMax() {
  58.         tree.insert(6);
  59.         assertEquals(new Integer(6), tree.minimum().getData());
  60.         assertEquals(new Integer(6), tree.maximum().getData());
  61.  
  62.         tree.insert(23);
  63.         assertEquals(new Integer(6), tree.minimum().getData());
  64.         assertEquals(new Integer(23), tree.maximum().getData());
  65.  
  66.         tree.insert(-34);
  67.         assertEquals(new Integer(-34), tree.minimum().getData());
  68.         assertEquals(new Integer(23), tree.maximum().getData());
  69.  
  70.         tree.insert(5);
  71.         assertEquals(new Integer(-34), tree.minimum().getData());
  72.         assertEquals(new Integer(23), tree.maximum().getData());
  73.  
  74.         tree.insert(9);
  75.         assertEquals(new Integer(-34), tree.minimum().getData());
  76.         assertEquals(new Integer(23), tree.maximum().getData());
  77.     }
  78.  
  79.     @Test
  80.     public void testinho(){
  81.         assertTrue(-1 == tree.height());
  82.         tree.insert(1);
  83.         assertTrue(0 == tree.height());
  84.         tree.insert(2);
  85.         assertTrue(1 == tree.height());
  86.         tree.insert(3);
  87.         assertTrue(2 == tree.height());
  88.         tree.insert(-1);
  89.         assertTrue(2 == tree.height());
  90.         tree.insert(-2);
  91.         assertTrue(2 == tree.height());
  92.  
  93.  
  94.         tree.remove(-1);
  95.         assertTrue(2 == tree.height());
  96.         tree.remove(-2);
  97.         assertTrue(2 == tree.height());
  98.  
  99.         tree.remove(1);
  100.         assertTrue(1 == tree.height());
  101.         tree.remove(2);
  102.         assertTrue(0 == tree.height());
  103.         tree.remove(3);
  104.         assertTrue(-1 == tree.height());
  105.  
  106.     }
  107.  
  108.     @Test
  109.     public void testOrder(){
  110.         tree.insert(96);
  111.         tree.insert(84);
  112.         tree.insert(97);
  113.         tree.insert(42);
  114.         tree.insert(87);
  115.         tree.insert(36);
  116.         tree.insert(57);
  117.         tree.insert(89);
  118.  
  119.         Integer[] array = {96, 84, 42, 36, 57, 87, 89, 97};
  120.  
  121.         assertArrayEquals(array, tree.preOrder());
  122.     }
  123.  
  124.     @Test
  125.     public void testSucessorPredecessor() {
  126.  
  127.         fillTree(); // -40 -34 0 2 5 6 9 12 23 67 76 232
  128.  
  129.         assertEquals(null, tree.predecessor(-40));
  130.         assertEquals(new Integer(-34), tree.sucessor(-40).getData());
  131.  
  132.         assertEquals(new Integer(-40), tree.predecessor(-34).getData());
  133.         assertEquals(new Integer(0), tree.sucessor(-34).getData());
  134.  
  135.         assertEquals(new Integer(-34), tree.predecessor(0).getData());
  136.         assertEquals(new Integer(2), tree.sucessor(0).getData());
  137.  
  138.         assertEquals(new Integer(0), tree.predecessor(2).getData());
  139.         assertEquals(new Integer(5), tree.sucessor(2).getData());
  140.  
  141.         assertEquals(new Integer(2), tree.sucessor(0).getData());
  142.         assertEquals(new Integer(-34), tree.predecessor(0).getData());
  143.  
  144.         tree.remove(2);
  145.         tree.remove(-34);
  146.  
  147.  
  148.         assertEquals(new Integer(5), tree.sucessor(0).getData());
  149.         assertEquals(new Integer(-40), tree.predecessor(0).getData());
  150.  
  151.  
  152.         tree.remove(5);
  153.         tree.remove(-40);
  154.  
  155.         assertEquals(new Integer(6), tree.sucessor(0).getData());
  156.         assertNull(tree.predecessor(0));
  157.  
  158.     }
  159.  
  160.     @Test
  161.     public void testSize() {
  162.         fillTree(); // -40 -34 0 2 5 6 9 12 23 67 76 232
  163.  
  164.         int size = 12;
  165.         assertEquals(size, tree.size());
  166.  
  167.         while (!tree.isEmpty()) {
  168.             tree.remove(tree.getRoot().getData());
  169.             assertEquals(--size, tree.size());
  170.         }
  171.     }
  172.  
  173.     @Test
  174.     public void testHeight() {
  175.         fillTree(); // -40 -34 0 2 5 6 9 12 23 67 76 232
  176.  
  177.         Integer[] preOrder = new Integer[] { 6, -34, -40, 5, 2, 0, 23, 9, 12,
  178.                 76, 67, 232 };
  179.         assertArrayEquals(preOrder, tree.preOrder());
  180.         assertEquals(4, tree.height());
  181.  
  182.         tree.remove(0);
  183.         assertEquals(3, tree.height());
  184.  
  185.         tree.remove(2);
  186.         assertEquals(3, tree.height());
  187.     }
  188.  
  189.     @Test
  190.     public void testInsert(){
  191.  
  192.         tree.insert(1);
  193.         tree.insert(2);
  194.         tree.insert(4);
  195.         tree.insert(3);
  196.         tree.insert(5);
  197.  
  198.         assertEquals(5, tree.size());
  199.         assertEquals(new Integer(1), tree.getRoot().getData());
  200.  
  201.         tree.remove(1);
  202.         assertEquals(4, tree.size());
  203.  
  204.         assertEquals(new Integer(2), tree.getRoot().getData());
  205.  
  206.     }
  207.  
  208.  
  209.     @Test
  210.     public void testRemove() {
  211.         fillTree(); // -40 -34 0 2 5 6 9 12 23 67 76 232
  212.  
  213.         Integer[] order = { -40, -34, 0, 2, 5, 6, 9, 12, 23, 67, 76, 232 };
  214.         assertArrayEquals(order, tree.order());
  215.  
  216.         tree.remove(6);
  217.         order = new Integer[] { -40, -34, 0, 2, 5, 9, 12, 23, 67, 76, 232 };
  218.         assertArrayEquals(order, tree.order());
  219.  
  220.         tree.remove(9);
  221.         order = new Integer[] { -40, -34, 0, 2, 5, 12, 23, 67, 76, 232 };
  222.         assertArrayEquals(order, tree.order());
  223.  
  224.         assertEquals(NIL, tree.search(6));
  225.         assertEquals(NIL, tree.search(9));
  226.  
  227.         Random r = new Random();
  228.         Set<Integer> elementsInTree = new TreeSet<>();
  229.         Set<Integer> elementsRemoved = new TreeSet<>();
  230.  
  231.         for(int i = 0 ; i < 1000 ; i++){
  232.             int val = r.nextInt();
  233.             tree.insert(val);
  234.             elementsInTree.add(val);
  235.         }
  236.  
  237.         List<Integer> lista = new LinkedList<>();
  238.         for(int i : elementsInTree){
  239.             lista.add(i);
  240.         }
  241.  
  242.  
  243.         for(int i : lista){
  244.  
  245.             tree.remove(i);
  246.             elementsInTree.remove(i);
  247.             elementsRemoved.add(i);
  248.  
  249.             for(int j : elementsInTree){
  250.                 assertEquals(new Integer(j), tree.search(j).getData());
  251.             }
  252.  
  253.             for(int j : elementsRemoved){
  254.                 assertEquals(NIL, tree.search(j));
  255.             }
  256.  
  257.         }
  258.  
  259.  
  260.  
  261.     }
  262.  
  263.     @Test
  264.     public void testSearch() {
  265.  
  266.         fillTree(); // -40 -34 0 2 5 6 9 12 23 67 76 232
  267.  
  268.         assertEquals(new Integer(-40), tree.search(-40).getData());
  269.         assertEquals(new Integer(-34), tree.search(-34).getData());
  270.         assertEquals(NIL, tree.search(2534));
  271.     }
  272.  
  273.     @Test
  274.     public void testEric() {
  275.         BSTImpl<Integer> bst = new BSTImpl<>();
  276.  
  277.         // Testando todos os pre-requisitos
  278.         assertTrue(bst.isEmpty());
  279.         assertEquals(bst.size(), 0);
  280.         assertEquals(bst.height(), -1);
  281.         assertNull(bst.maximum());
  282.         assertNull(bst.minimum());
  283.         assertNotNull(bst.search(1));
  284.         assertNull(bst.search(1).getData());
  285.         assertTrue(bst.search(1).isEmpty());
  286.         Integer[] vazio = {};
  287.         assertArrayEquals(bst.order(), vazio);
  288.         assertArrayEquals(bst.preOrder(), vazio);
  289.         assertArrayEquals(bst.postOrder(), vazio);
  290.         assertNotNull(bst.search(null));
  291.         assertNull(bst.predecessor(null));
  292.         assertNull(bst.sucessor(null));
  293.  
  294.         synchronized (bst) {
  295.             int[] ns = new int[] { 100, 50, 200, 250, 150, 140, 180, 75, 25, 10, 70, 60, 73, 65, 55, 71 };
  296.             int size = 0;
  297.             for (int e : ns) {
  298.                 assertEquals(bst.size(), size++);
  299.                 bst.insert(e);
  300.             }
  301.         }
  302.  
  303.         // Os pre-requisitos nao devem mais ser validos
  304.         assertFalse(bst.isEmpty());
  305.         assertNotEquals(bst.size(), 0);
  306.         assertNotEquals(bst.height(), -1);
  307.         assertNotNull(bst.maximum());
  308.         assertNotNull(bst.minimum());
  309.         // Aqui eh excecao, claro
  310.         assertNotNull(bst.search(10));
  311.         assertNotNull(bst.search(10).getData());
  312.         assertFalse(bst.search(10).isEmpty());
  313.         // birl
  314.         try {
  315.             assertArrayEquals(bst.order(), vazio);
  316.             fail();
  317.         } catch (AssertionError e) {
  318.         }
  319.         try {
  320.             assertArrayEquals(bst.preOrder(), vazio);
  321.             fail();
  322.         } catch (AssertionError e) {
  323.         }
  324.         try {
  325.             assertArrayEquals(bst.postOrder(), vazio);
  326.             fail();
  327.         } catch (AssertionError e) {
  328.         }
  329.  
  330.         // Testando as infos da arvere
  331.         assertFalse(bst.isEmpty());
  332.         assertEquals(bst.height(), 5);
  333.         assertEquals(bst.size(), 16);
  334.         assertTrue(bst.maximum().getData().equals(new Integer(250)));
  335.         assertTrue(bst.minimum().getData().equals(new Integer(10)));
  336.  
  337.         assertNull(bst.sucessor(bst.maximum().getData()));
  338.         assertNull(bst.predecessor(bst.minimum().getData()));
  339.  
  340.         assertNotNull(bst.sucessor(bst.getRoot().getData()));
  341.         assertTrue(bst.sucessor(bst.getRoot().getData()).getData().equals(new Integer(140)));
  342.         assertNotNull(bst.predecessor(bst.getRoot().getData()));
  343.         assertTrue(bst.predecessor(bst.getRoot().getData()).getData().equals(new Integer(75)));
  344.  
  345.         assertNotNull(bst.search(null));
  346.         assertTrue(bst.search(null).isEmpty());
  347.         assertNull(bst.predecessor(null));
  348.         assertNull(bst.sucessor(null));
  349.  
  350.         bst.insert(null);
  351.         assertEquals(bst.height(), 5);
  352.         assertEquals(bst.size(), 16);
  353.  
  354.         bst.remove(null);
  355.         assertEquals(bst.height(), 5);
  356.         assertEquals(bst.size(), 16);
  357.  
  358.         assertTrue(bst.predecessor(55).getData().equals(new Integer(50)));
  359.         assertTrue(bst.predecessor(71).getData().equals(new Integer(70)));
  360.         assertTrue(bst.sucessor(10).getData().equals(new Integer(25)));
  361.         assertTrue(bst.predecessor(140).getData().equals(new Integer(100)));
  362.         assertNull(bst.sucessor(250));
  363.         assertNull(bst.predecessor(10));
  364.         assertTrue(bst.sucessor(150).getData().equals(new Integer(180)));
  365.         assertTrue(bst.predecessor(50).getData().equals(new Integer(25)));
  366.  
  367.         assertTrue(bst.predecessor(50).getData().equals(new Integer(25)));
  368.         bst.remove(25);
  369.         assertEquals(bst.height(), 5);
  370.         assertEquals(bst.size(), 15);
  371.         assertTrue(bst.predecessor(50).getData().equals(new Integer(10)));
  372.  
  373.         bst.remove(50);
  374.         assertEquals(bst.height(), 5);
  375.         assertEquals(bst.size(), 14);
  376.         assertTrue(bst.sucessor(10).getData().equals(new Integer(55)));
  377.  
  378.         assertEquals(bst.height(), 5);
  379.         bst.insert(135);
  380.         assertEquals(bst.height(), 5);
  381.         bst.insert(130);
  382.         assertEquals(bst.height(), 5);
  383.         bst.insert(125);
  384.         assertEquals(bst.height(), 6);
  385.         bst.insert(120);
  386.         assertEquals(bst.height(), 7);
  387.  
  388.         assertTrue(bst.predecessor(120).getData().equals(new Integer(100)));
  389.         assertTrue(bst.sucessor(120).getData().equals(new Integer(125)));
  390.  
  391.         assertEquals(bst.size(), 18);
  392.         assertFalse(bst.search(71).isEmpty());
  393.         bst.remove(71);
  394.         assertTrue(bst.search(71).isEmpty());
  395.         bst.remove(73);
  396.         assertNull(bst.predecessor(73));
  397.         assertNull(bst.sucessor(71));
  398.         assertEquals(bst.size(), 16);
  399.         assertEquals(bst.height(), 7);
  400.  
  401.         bst.remove(55);
  402.         bst.remove(65);
  403.         assertEquals(bst.size(), 14);
  404.         assertEquals(bst.height(), 7);
  405.  
  406.         bst.remove(60);
  407.         bst.remove(75);
  408.         assertEquals(bst.size(), 12);
  409.         assertEquals(bst.height(), 7);
  410.  
  411.         assertTrue(bst.sucessor(70).getData().equals(100));
  412.         assertTrue(bst.predecessor(70).getData().equals(10));
  413.  
  414.         bst.remove(200);
  415.         assertEquals(bst.size(), 11);
  416.         assertEquals(bst.height(), 7);
  417.  
  418.         bst.remove(250);
  419.         assertEquals(bst.size(), 10);
  420.         assertEquals(bst.height(), 6);
  421.  
  422.         bst.remove(150);
  423.         assertEquals(bst.size(), 9);
  424.         assertEquals(bst.height(), 6);
  425.  
  426.         bst.remove(180);
  427.         assertEquals(bst.size(), 8);
  428.         assertEquals(bst.height(), 5);
  429.  
  430.         assertTrue(bst.sucessor(100).getData().equals(120));
  431.         assertTrue(bst.predecessor(125).getData().equals(120));
  432.         assertTrue(bst.predecessor(120).getData().equals(100));
  433.  
  434.         bst.remove(100);
  435.         assertEquals(bst.size(), 7);
  436.         assertEquals(bst.height(), 4);
  437.  
  438.         assertTrue(bst.getRoot().getData().equals(120));
  439.         assertTrue(bst.search(100).isEmpty());
  440.         assertNull(bst.predecessor(100));
  441.         assertNull(bst.sucessor(100));
  442.         assertTrue(bst.predecessor(120).getData().equals(70));
  443.         assertTrue(bst.sucessor(120).getData().equals(125));
  444.  
  445.         bst.remove(120);
  446.         assertEquals(bst.size(), 6);
  447.         assertEquals(bst.height(), 3);
  448.  
  449.         assertTrue(bst.getRoot().getData().equals(125));
  450.         assertTrue(bst.search(120).isEmpty());
  451.         assertNull(bst.predecessor(120));
  452.         assertTrue(bst.minimum().getData().equals(10));
  453.         assertTrue(bst.maximum().getData().equals(140));
  454.  
  455.         bst.remove(10);
  456.         bst.remove(135);
  457.         bst.remove(130);
  458.  
  459.         assertTrue(bst.maximum().getData().equals(140));
  460.         assertTrue(bst.minimum().getData().equals(70));
  461.         assertEquals(bst.size(), 3);
  462.         assertEquals(bst.height(), 1);
  463.         assertNull(bst.sucessor(140));
  464.         assertNull(bst.predecessor(70));
  465.         assertTrue(bst.sucessor(bst.getRoot().getData()).getData().equals(140));
  466.         assertTrue(bst.predecessor(bst.getRoot().getData()).getData().equals(70));
  467.  
  468.         bst.remove(140);
  469.         bst.remove(70);
  470.  
  471.         assertEquals(bst.height(), 0);
  472.         assertEquals(bst.size(), 1);
  473.         assertTrue(bst.maximum().equals(bst.minimum()));
  474.  
  475.         bst.remove(bst.getRoot().getData());
  476.         // Voltamos ao começo
  477.         assertTrue(bst.isEmpty());
  478.         assertEquals(bst.size(), 0);
  479.         assertEquals(bst.height(), -1);
  480.         assertNull(bst.maximum());
  481.         assertNull(bst.minimum());
  482.         assertNotNull(bst.search(1));
  483.         assertNull(bst.search(1).getData());
  484.         assertTrue(bst.search(1).isEmpty());
  485.         assertArrayEquals(bst.order(), vazio);
  486.         assertArrayEquals(bst.preOrder(), vazio);
  487.         assertArrayEquals(bst.postOrder(), vazio);
  488.         assertNotNull(bst.search(null));
  489.         assertNull(bst.predecessor(null));
  490.         assertNull(bst.sucessor(null));
  491.     }
  492.  
  493.  
  494. }
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!