API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Oct 1st, 2016
75
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 13.54 KB | None | 0 0
raw download clone embed print report
  1. package adt.skipList;
  2.  
  3. import static org.junit.Assert.*;
  4.  
  5. import java.util.ArrayList;
  6. import java.util.Arrays;
  7. import java.util.List;
  8.  
  9. import org.junit.Before;
  10. import org.junit.Test;
  11.  
  12. public class StudentSkipListTest {
  13.  
  14.     SkipList<String> skip;
  15.     SkipListNode<String>[] array;
  16.  
  17.     @Before
  18.     public void setUp() {
  19.         skip = new SkipListImpl<String>(4);
  20.  
  21.         // TODO ajuste o valor de acordo com o exercicio de sua turma
  22.         ((SkipListImpl<String>) skip).USE_MAX_HEIGHT_AS_HEIGHT = true;
  23.     }
  24.  
  25.     @Test
  26.     public void testInsert() {
  27.         skip.insert(10, "A", 2);
  28.         skip.insert(20, "B", 1);
  29.         skip.insert(0, "C", 1);
  30.         skip.insert(15, "D", 3);
  31.         skip.insert(5, "E", 3);
  32.  
  33.         assertEquals(5, skip.size());
  34.  
  35.         array = skip.toArray();
  36.         if (((SkipListImpl<String>) skip).USE_MAX_HEIGHT_AS_HEIGHT) {
  37.             assertEquals(
  38.                     "[<ROOT,4,4>, <0,1>, <5,3>, <10,2>, <15,3>, <20,1>, <NIL,4>]",
  39.                     Arrays.toString(array));
  40.         } else {
  41.             assertEquals(
  42.                     "[<ROOT,4,3>, <0,1>, <5,3>, <10,2>, <15,3>, <20,1>, <NIL,4>]",
  43.                     Arrays.toString(array));
  44.         }
  45.         assertEquals(0, array[0].getForward(0).getKey());
  46.         assertEquals(5, array[0].getForward(1).getKey());
  47.         assertEquals(5, array[0].getForward(2).getKey());
  48.         //assertNull(array[0].getForward(3));
  49.         assertEquals(5, array[1].getForward(0).getKey());
  50.         assertEquals(10, array[2].getForward(0).getKey());
  51.         assertEquals(10, array[2].getForward(1).getKey());
  52.         assertEquals(15, array[2].getForward(2).getKey());
  53.         assertEquals(15, array[3].getForward(0).getKey());
  54.         assertEquals(15, array[3].getForward(1).getKey());
  55.         assertEquals(20, array[4].getForward(0).getKey());
  56.         assertEquals(Integer.MAX_VALUE, array[4].getForward(1).getKey());
  57.         assertEquals(Integer.MAX_VALUE, array[4].getForward(2).getKey());
  58.         assertEquals(Integer.MAX_VALUE, array[5].getForward(0).getKey());
  59.  
  60.  
  61.         List<String> aux = new ArrayList<>();
  62.         for (int i = 1; i < array.length - 1; ++i)
  63.             aux.add(array[i].getValue());
  64.  
  65.         assertEquals("[C, E, A, D, B]", aux.toString());
  66.  
  67.         skip.insert(0, "A", 1);
  68.         skip.insert(5, "B", 3);
  69.         skip.insert(10, "C", 2);
  70.         skip.insert(15, "D", 3);
  71.         skip.insert(20, "E", 1);
  72.  
  73.         assertEquals(5, skip.size());
  74.  
  75.         array = skip.toArray();
  76.         if (((SkipListImpl<String>) skip).USE_MAX_HEIGHT_AS_HEIGHT) {
  77.             assertEquals(
  78.                     "[<ROOT,4,4>, <0,1>, <5,3>, <10,2>, <15,3>, <20,1>, <NIL,4>]",
  79.                     Arrays.toString(array));
  80.         } else {
  81.             assertEquals(
  82.                     "[<ROOT,4,3>, <0,1>, <5,3>, <10,2>, <15,3>, <20,1>, <NIL,4>]",
  83.                     Arrays.toString(array));
  84.         }
  85.  
  86.         assertEquals(0, array[0].getForward(0).getKey());
  87.         assertEquals(5, array[0].getForward(1).getKey());
  88.         assertEquals(5, array[0].getForward(2).getKey());
  89.         assertEquals(5, array[1].getForward(0).getKey());
  90.         assertEquals(10, array[2].getForward(0).getKey());
  91.         assertEquals(10, array[2].getForward(1).getKey());
  92.         assertEquals(15, array[3].getForward(0).getKey());
  93.         assertEquals(20, array[4].getForward(0).getKey());
  94.         assertEquals(Integer.MAX_VALUE, array[4].getForward(1).getKey());
  95.         assertEquals(Integer.MAX_VALUE, array[5].getForward(0).getKey());
  96.  
  97.         aux.clear();
  98.         for (int i = 1; i < array.length - 1; ++i)
  99.             aux.add(array[i].getValue());
  100.  
  101.         assertEquals("[A, B, C, D, E]", aux.toString());
  102.     }
  103.  
  104.     @Test
  105.     public void testSearch() {
  106.         skip.insert(10, "A", 2);
  107.         skip.insert(20, "B", 1);
  108.         skip.insert(0, "C", 1);
  109.         skip.insert(15, "D", 3);
  110.         skip.insert(5, "E", 2);
  111.  
  112.         assertEquals("A", skip.search(10).getValue());
  113.         assertEquals("B", skip.search(20).getValue());
  114.         assertEquals("C", skip.search(0).getValue());
  115.         assertEquals("D", skip.search(15).getValue());
  116.         assertEquals("E", skip.search(5).getValue());
  117.  
  118.         assertEquals(null, skip.search(-10));
  119.         assertEquals(null, skip.search(30));
  120.         assertEquals(null, skip.search(9));
  121.     }
  122.  
  123.     @Test
  124.     public void testRemove() {
  125.         skip.insert(10, "A", 1);
  126.         skip.insert(20, "B", 2);
  127.         skip.insert(0, "C", 2);
  128.         skip.insert(15, "D", 3);
  129.         skip.insert(5, "E", 1);
  130.  
  131.         skip.insert(-10, "F", 1);
  132.         skip.insert(30, "G", 3);
  133.         skip.insert(9, "H", 2);
  134.         skip.insert(17, "I", 2);
  135.         skip.insert(-2, "J", 1);
  136.  
  137.         assertEquals(10, skip.size());
  138.  
  139.         skip.remove(10);
  140.         skip.remove(20);
  141.         skip.remove(0);
  142.         skip.remove(15);
  143.         skip.remove(5);
  144.  
  145.         assertEquals(5, skip.size());
  146.  
  147.         array = skip.toArray();
  148.         if (((SkipListImpl<String>) skip).USE_MAX_HEIGHT_AS_HEIGHT) {
  149.             assertEquals(
  150.                     "[<ROOT,4,4>, <-10,1>, <-2,1>, <9,2>, <17,2>, <30,3>, <NIL,4>]",
  151.                     Arrays.toString(array));
  152.         } else {
  153.             assertEquals(
  154.                     "[<ROOT,4,3>, <-10,1>, <-2,1>, <9,2>, <17,2>, <30,3>, <NIL,4>]",
  155.                     Arrays.toString(array));
  156.         }
  157.         assertEquals(-10, array[0].getForward(0).getKey());
  158.         assertEquals(9, array[0].getForward(1).getKey());
  159.         assertEquals(30, array[0].getForward(2).getKey());
  160.         assertEquals(-2, array[1].getForward(0).getKey());
  161.         assertEquals(9, array[2].getForward(0).getKey());
  162.         assertEquals(17, array[3].getForward(0).getKey());
  163.         assertEquals(17, array[3].getForward(1).getKey());
  164.         assertEquals(30, array[4].getForward(0).getKey());
  165.         assertEquals(30, array[4].getForward(1).getKey());
  166.         assertEquals(Integer.MAX_VALUE, array[5].getForward(0).getKey());
  167.         assertEquals(Integer.MAX_VALUE, array[5].getForward(1).getKey());
  168.         assertEquals(Integer.MAX_VALUE, array[5].getForward(2).getKey());
  169.  
  170.         skip.remove(-10);
  171.         skip.remove(30);
  172.         skip.remove(9);
  173.         skip.remove(17);
  174.         skip.remove(-2);
  175.  
  176.         assertEquals(0, skip.size());
  177.  
  178.         array = skip.toArray();
  179.         if (((SkipListImpl<String>) skip).USE_MAX_HEIGHT_AS_HEIGHT) {
  180.             assertEquals("[<ROOT,4,4>, <NIL,4>]", Arrays.toString(array));
  181.         } else {
  182.             assertEquals("[<ROOT,4,1>, <NIL,4>]", Arrays.toString(array));
  183.         }
  184.         assertEquals(Integer.MAX_VALUE, array[0].getForward(0).getKey());
  185.     }
  186.  
  187.     @Test
  188.     public void dinizTest1() {
  189.  
  190.         assertEquals(0, skip.size());
  191.         skip.insert(3, "B", 3);
  192.         assertEquals(1, skip.size());
  193.         skip.insert(1, "A", 2);
  194.         assertEquals(2, skip.size());
  195.         skip.insert(4, "C", 1);
  196.         assertEquals(3, skip.size());
  197.  
  198.         ((SkipListImpl<String>) skip).USE_MAX_HEIGHT_AS_HEIGHT = true;
  199.         array = skip.toArray();
  200.         assertEquals("[<ROOT,4,4>, <1,2>, <3,3>, <4,1>, <NIL,4>]", Arrays.toString(array));
  201.  
  202.         List<String> aux = new ArrayList<>();
  203.         for(SkipListNode<String> node : array){
  204.             aux.add(node.getValue());
  205.         }
  206.  
  207.         assertEquals("[null, A, B, C, null]", aux.toString());
  208.         assertEquals(4,skip.height());
  209.  
  210.  
  211.         ((SkipListImpl<String>) skip).USE_MAX_HEIGHT_AS_HEIGHT = false;
  212.         array = skip.toArray();
  213.         assertEquals("[<ROOT,4,3>, <1,2>, <3,3>, <4,1>, <NIL,4>]", Arrays.toString(array));
  214.  
  215.         aux.clear();
  216.         for(SkipListNode<String> node : array){
  217.             aux.add(node.getValue());
  218.         }
  219.  
  220.         assertEquals("[null, A, B, C, null]", aux.toString());
  221.         assertEquals(3,skip.height());
  222.  
  223.  
  224.         skip.insert(5, "D", 2);
  225.         assertEquals(4, skip.size());
  226.  
  227.         ((SkipListImpl<String>) skip).USE_MAX_HEIGHT_AS_HEIGHT = true;
  228.         array = skip.toArray();
  229.         assertEquals("[<ROOT,4,4>, <1,2>, <3,3>, <4,1>, <5,2>, <NIL,4>]", Arrays.toString(array));
  230.  
  231.         aux.clear();
  232.         for(SkipListNode<String> node : array){
  233.             aux.add(node.getValue());
  234.         }
  235.  
  236.         assertEquals("[null, A, B, C, D, null]", aux.toString());
  237.         assertEquals(4,skip.height());
  238.  
  239.  
  240.         ((SkipListImpl<String>) skip).USE_MAX_HEIGHT_AS_HEIGHT = false;
  241.         array = skip.toArray();
  242.         assertEquals("[<ROOT,4,3>, <1,2>, <3,3>, <4,1>, <5,2>, <NIL,4>]", Arrays.toString(array));
  243.  
  244.         aux.clear();
  245.         for(SkipListNode<String> node : array){
  246.             aux.add(node.getValue());
  247.         }
  248.  
  249.         assertEquals("[null, A, B, C, D, null]", aux.toString());
  250.         assertEquals(3,skip.height());
  251.  
  252.         skip.remove(4);
  253.         assertEquals(3, skip.size());
  254.  
  255.         ((SkipListImpl<String>) skip).USE_MAX_HEIGHT_AS_HEIGHT = true;
  256.         array = skip.toArray();
  257.         assertEquals("[<ROOT,4,4>, <1,2>, <3,3>, <5,2>, <NIL,4>]", Arrays.toString(array));
  258.  
  259.         aux.clear();
  260.         for(SkipListNode<String> node : array){
  261.             aux.add(node.getValue());
  262.         }
  263.  
  264.         assertEquals("[null, A, B, D, null]", aux.toString());
  265.         assertEquals(4,skip.height());
  266.  
  267.  
  268.         ((SkipListImpl<String>) skip).USE_MAX_HEIGHT_AS_HEIGHT = false;
  269.         array = skip.toArray();
  270.         assertEquals("[<ROOT,4,3>, <1,2>, <3,3>, <5,2>, <NIL,4>]", Arrays.toString(array));
  271.  
  272.         aux.clear();
  273.         for(SkipListNode<String> node : array){
  274.             aux.add(node.getValue());
  275.         }
  276.  
  277.         assertEquals("[null, A, B, D, null]", aux.toString());
  278.         assertEquals(3,skip.height());
  279.  
  280.  
  281.         skip.remove(1);
  282.         skip.remove(5);
  283.         assertEquals(1,skip.size());
  284.  
  285.         ((SkipListImpl<String>) skip).USE_MAX_HEIGHT_AS_HEIGHT = true;
  286.         array = skip.toArray();
  287.         assertEquals("[<ROOT,4,4>, <3,3>, <NIL,4>]", Arrays.toString(array));
  288.  
  289.         aux.clear();
  290.         for(SkipListNode<String> node : array){
  291.             aux.add(node.getValue());
  292.         }
  293.  
  294.         assertEquals("[null, B, null]", aux.toString());
  295.         assertEquals(4,skip.height());
  296.         assertEquals(1,skip.size());
  297.  
  298.  
  299.         ((SkipListImpl<String>) skip).USE_MAX_HEIGHT_AS_HEIGHT = false;
  300.         array = skip.toArray();
  301.         assertEquals("[<ROOT,4,3>, <3,3>, <NIL,4>]", Arrays.toString(array));
  302.  
  303.         aux.clear();
  304.         for(SkipListNode<String> node : array){
  305.             aux.add(node.getValue());
  306.         }
  307.  
  308.         assertEquals("[null, B, null]", aux.toString());
  309.         assertEquals(3,skip.height());
  310.         assertEquals(1,skip.size());
  311.  
  312.  
  313.  
  314.  
  315.         skip.remove(3);
  316.  
  317.         assertEquals(0,skip.size());
  318.  
  319.         ((SkipListImpl<String>) skip).USE_MAX_HEIGHT_AS_HEIGHT = true;
  320.         array = skip.toArray();
  321.         assertEquals("[<ROOT,4,4>, <NIL,4>]", Arrays.toString(array));
  322.  
  323.         aux.clear();
  324.         for(SkipListNode<String> node : array){
  325.             aux.add(node.getValue());
  326.         }
  327.  
  328.         assertEquals("[null, null]", aux.toString());
  329.         assertEquals(4,skip.height());
  330.         assertEquals(0,skip.size());
  331.  
  332.  
  333.         ((SkipListImpl<String>) skip).USE_MAX_HEIGHT_AS_HEIGHT = false;
  334.         array = skip.toArray();
  335.         assertEquals("[<ROOT,4,1>, <NIL,4>]", Arrays.toString(array));
  336.  
  337.         aux.clear();
  338.         for(SkipListNode<String> node : array){
  339.             aux.add(node.getValue());
  340.         }
  341.  
  342.         assertEquals("[null, null]", aux.toString());
  343.         assertEquals(1,skip.height());
  344.         assertEquals(0,skip.size());
  345.  
  346.  
  347.     }
  348.  
  349.     @Test
  350.     public void insertComSuperposicao() {
  351.  
  352.         SkipList<String> bugTree = new SkipListImpl<String>(5);
  353.  
  354.         //max altura interna = 4
  355.         bugTree.insert(5, "A", 1);
  356.         bugTree.insert(2, "C", 3);
  357.         bugTree.insert(6, "D", 2);
  358.         bugTree.insert(4, "R", 4);
  359.         bugTree.insert(8, "AAsS", 1);
  360.         bugTree.insert(9, "12", 2);
  361.  
  362.  
  363.         if(((SkipListImpl<String>) bugTree).USE_MAX_HEIGHT_AS_HEIGHT) {
  364.             assertEquals(5, bugTree.height());
  365.             change(bugTree);
  366.             assertEquals(4, bugTree.height());
  367.  
  368.         } else {
  369.             assertEquals(4, bugTree.height());
  370.             change(bugTree);
  371.             assertEquals(5, bugTree.height());
  372.         }
  373.     }
  374.  
  375.     @Test
  376.     public void brainFuck() {
  377.  
  378.         SkipList<String> bugTree = new SkipListImpl<String>(0);
  379.  
  380.  
  381.         if(((SkipListImpl<String>) bugTree).USE_MAX_HEIGHT_AS_HEIGHT) {
  382.             assertEquals(0, bugTree.height());
  383.             change(bugTree);
  384.             assertEquals(1, bugTree.height());
  385.  
  386.         } else {
  387.             assertEquals(1, bugTree.height());
  388.             change(bugTree);
  389.             assertEquals(0, bugTree.height());
  390.  
  391.         }
  392.  
  393.     }
  394.  
  395.     @Test
  396.     public void testInsertRandom(){
  397.  
  398.         ((SkipListImpl<String>) skip).USE_MAX_HEIGHT_AS_HEIGHT = false;
  399.  
  400.         ((SkipListImpl<String>)skip).insert(1,"a");
  401.         ((SkipListImpl<String>)skip).insert(2,"b");
  402.         ((SkipListImpl<String>)skip).insert(3,"c");
  403.  
  404.         assertTrue(skip.height() <= ((SkipListImpl<String>) skip).maxHeight);
  405.         assertEquals(3, skip.size());
  406.  
  407.     }
  408.  
  409.     @Test
  410.     public void testInsertRandom2(){
  411.  
  412.         ((SkipListImpl<String>) skip).USE_MAX_HEIGHT_AS_HEIGHT = false;
  413.  
  414.         for(int i = 0 ; i < 27 ; i++){
  415.             ((SkipListImpl<String>)skip).insert(i,"a" + i);
  416.  
  417.             assertTrue(skip.height() <= ((SkipListImpl<String>) skip).maxHeight);
  418.             assertEquals(i + 1, skip.size());
  419.         }
  420.  
  421.     }
  422.  
  423.     @Test
  424.     public void finalTest(){
  425.         ((SkipListImpl<String>) skip).USE_MAX_HEIGHT_AS_HEIGHT = false;
  426.  
  427.         assertEquals(1, skip.height());
  428.         skip.insert(1,"a",1);
  429.         assertEquals(1, skip.height());
  430.         skip.insert(2,"a",2);
  431.         assertEquals(2, skip.height());
  432.         skip.insert(3,"a",3);
  433.         assertEquals(3, skip.height());
  434.  
  435.         skip.remove(3);
  436.         assertEquals(2, skip.height());
  437.         skip.remove(2);
  438.         assertEquals(1, skip.height());
  439.         skip.remove(1);
  440.         assertEquals(1, skip.height());
  441.     }
  442.  
  443.     @Test
  444.     public void testFinal2(){
  445.         ((SkipListImpl<String>) skip).USE_MAX_HEIGHT_AS_HEIGHT = false;
  446.         assertNull(((SkipListImpl<String>) skip).root.getForward(1));
  447.         assertNull(((SkipListImpl<String>) skip).root.getForward(2));
  448.         assertNull(((SkipListImpl<String>) skip).root.getForward(3));
  449.         assertEquals(((SkipListImpl<String>) skip).root.getForward(0).getKey(), Integer.MAX_VALUE);
  450.  
  451.         ((SkipListImpl<String>) skip).USE_MAX_HEIGHT_AS_HEIGHT = true;
  452.         skip.insert(1,"a",1);
  453.         assertEquals(((SkipListImpl<String>) skip).root.getForward(0).getKey(), 1);
  454.         assertEquals(((SkipListImpl<String>) skip).root.getForward(1).getKey(), Integer.MAX_VALUE);
  455.         assertEquals(((SkipListImpl<String>) skip).root.getForward(2).getKey(), Integer.MAX_VALUE);
  456.         assertEquals(((SkipListImpl<String>) skip).root.getForward(3).getKey(), Integer.MAX_VALUE);
  457.  
  458.         ((SkipListImpl<String>) skip).USE_MAX_HEIGHT_AS_HEIGHT = false;
  459.         skip.remove(1);
  460.         assertNull(((SkipListImpl<String>) skip).root.getForward(1));
  461.         assertNull(((SkipListImpl<String>) skip).root.getForward(2));
  462.         assertNull(((SkipListImpl<String>) skip).root.getForward(3));
  463.         assertEquals(((SkipListImpl<String>) skip).root.getForward(0).getKey(), Integer.MAX_VALUE);
  464.     }
  465.  
  466.     private void change(SkipList<String> bugTree) {
  467.         ((SkipListImpl<String>) bugTree).USE_MAX_HEIGHT_AS_HEIGHT = !((SkipListImpl<String>) bugTree).USE_MAX_HEIGHT_AS_HEIGHT;
  468.     }
  469.  
  470.  
  471.  
  472. }
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!