SHARE
TWEET

Untitled

a guest Dec 12th, 2019 113 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. public class BinarySearchTree extends LinkedList {
  2.  
  3.     public BinarySearchTree(){
  4.         totalLists++;
  5.     }
  6.  
  7.     BSTNode head;
  8.     BSTNode previous;
  9.     int distintcVocab;
  10.  
  11.     public void newEntry( String word ){ //new entry method
  12.  
  13.         totalCount++;
  14.  
  15.         if (head == null){ //if head is nonexistant then crate
  16.  
  17.             distintcVocab++;
  18.             BSTNode newNode = new BSTNode(word);
  19.             head = newNode;
  20.             head.right = null;
  21.             head.left = null;
  22.  
  23.         } else {
  24.  
  25.             BSTNode transverse = this.lookThrough( word ); //looks through to see if it exists
  26.  
  27.             if ( transverse != null && transverse.word.equals(word) ) {
  28.  
  29.                 transverse.count = transverse.count + 1;
  30.  
  31.             } else { //make new node if it does not exist
  32.  
  33.                 distintcVocab++;
  34.  
  35.                 BSTNode newNode = new BSTNode(word);
  36.                 newNode.parent = previous;
  37.                 totalReferenceChanges++;
  38.  
  39.                 if (previous.word.compareTo(word) > 0 ) {
  40.  
  41.                     previous.left = newNode;
  42.                     totalReferenceChanges++;
  43.  
  44.                     return;
  45.  
  46.                 }
  47.  
  48.                 previous.right = newNode;
  49.                 totalReferenceChanges++;
  50.  
  51.             }
  52.  
  53.         }
  54.  
  55.     }
  56.  
  57.     public BSTNode lookThrough(String word ){ // looks through  list and returns rather it a word exists or not
  58.  
  59.         BSTNode transpose = head;
  60.         previous = null;
  61.  
  62.         while (transpose != null) {
  63.  
  64.             totalComparisons++;
  65.             int compInt;
  66.  
  67.             if ( transpose == null || (compInt = transpose.word.compareTo(word)) == 0 ) {
  68.  
  69.                 return transpose;
  70.  
  71.             } else if ( compInt > 0 ) { //less then
  72.  
  73.                 previous = transpose;
  74.                 transpose = transpose.left;
  75.  
  76.             } else { //greater then
  77.  
  78.                 previous = transpose;
  79.                 transpose = transpose.right;
  80.  
  81.             }
  82.  
  83.         }
  84.  
  85.         return null;
  86.  
  87.     }
  88.  
  89.     public BSTNode Successor( BSTNode node ) {
  90.  
  91.         BSTNode transverse = node;
  92.         BSTNode x = node;
  93.  
  94.         if ( transverse.right != null ) {
  95.  
  96.             transverse = transverse.right;
  97.  
  98.             while ( transverse.left != null ) transverse = transverse.left ;
  99.  
  100.             return transverse;
  101.  
  102.         }
  103.  
  104.         transverse = node.parent;
  105.  
  106.         while ( transverse != null && x == transverse.right ) {
  107.  
  108.             x = transverse;
  109.             transverse = transverse.parent;
  110.  
  111.         }
  112.  
  113.         return transverse;
  114.  
  115.     }
  116.  
  117.     public BSTNode minumum( BSTNode node ) {
  118.  
  119.         BSTNode transveral = node;
  120.  
  121.         while ( transveral.left != null ) transveral = transveral.left;
  122.  
  123.         return  transveral;
  124.  
  125.     }
  126.  
  127.     public int Height (BSTNode node) {
  128.  
  129.         if (node == null) return 0;
  130.  
  131.         int leftHeight = Height(node.left);
  132.         int rightHeight = Height(node.right);
  133.  
  134.         if (leftHeight > rightHeight) return leftHeight + 1;
  135.  
  136.         return rightHeight + 1;
  137.  
  138.     }
  139.  
  140.     public void displayFirst100() {
  141.  
  142.         BSTNode p = minumum( head );
  143.  
  144.         System.out.println("First 100 entries:");
  145.         System.out.println();
  146.  
  147.         for (int i = 0; i < 100; i++) {
  148.             if (p != null) {
  149.                 System.out.println(p.word + " " + p.count);
  150.                 p = Successor(p);
  151.             }
  152.  
  153.         }
  154.  
  155.         System.out.println();
  156.  
  157.     }
  158.  
  159.     public void Traverse(BSTNode node) {
  160.         if (node == null) return;
  161.         Traverse(node.left);
  162.  
  163.         new PrintFunction().noob(node, 0);
  164.  
  165.         Traverse(node.right);
  166.     }
  167.  
  168.  
  169.     public int iterateThrough ( ) { //looping through to return counter
  170.  
  171.         int total = 0;
  172.  
  173.         displayFirst100();
  174.  
  175.         height = Height( head );
  176.  
  177.         BSTNode transpose = head;
  178.  
  179.         average = totalCount;
  180.         minNumbers = totalCount;
  181.         maxNumbers = totalCount;
  182.  
  183.         Traverse(transpose);
  184.  
  185.         return distintcVocab;
  186.  
  187.     }
  188.  
  189.     public void delete(String word) {}
  190.  
  191.  
  192.  
  193. }
  194.  
  195. ^^binary search tree
  196.  
  197.  
  198. public class BSTNode extends NodeParent {
  199.  
  200.  
  201.     BSTNode right = null;
  202.     BSTNode left = null;
  203.     BSTNode parent = null;
  204.  
  205.     BSTNode(String word){
  206.  
  207.         this.word = word;
  208.  
  209.     }
  210.  
  211.  
  212. }
  213.  
  214. ^^BST Node
  215.  
  216.  
  217. public class HashC extends LinkedList{
  218.  
  219.     SelfAdjustingListOne[] listArray = new SelfAdjustingListOne[ 256 ];
  220.  
  221.     public int hashFunction( String word ) {
  222.  
  223.         int key = 0;
  224.  
  225.         char[] wordArray = word.toCharArray();
  226.  
  227.         for (char i : wordArray)  key = key * 31 + i;
  228.  
  229.         key = key % 256;
  230.  
  231.         return Math.abs(key);
  232.  
  233.     }
  234.  
  235.     public void newEntry( String word ) {
  236.  
  237.         totalCount++;
  238.  
  239.         int key = this.hashFunction( word );
  240.  
  241.         if ( listArray [ key ] == null ) {
  242.             totalLists++;
  243.             listArray [ key ] = new SelfAdjustingListOne();
  244.         }
  245.  
  246.         listArray [ key ].newEntry( word );
  247.  
  248.     }
  249.  
  250.     public int iterateThrough( ) {
  251.  
  252.         int total = 1;
  253.  
  254.         minNumbers = Long.MAX_VALUE;
  255.         maxNumbers = Long.MIN_VALUE;
  256.  
  257.         average = totalCount / totalLists;
  258.  
  259.         long std = 0;
  260.  
  261.         for ( int i = 0; i < 256; i++ ) {
  262.  
  263.             if ( listArray[ i ] != null ) {
  264.  
  265.                 total = total + listArray[ i ].iterateThrough();
  266.                 totalComparisons = totalComparisons + listArray [ i ].totalComparisons;
  267.                 totalReferenceChanges = totalReferenceChanges + listArray [ i ].totalReferenceChanges;
  268.                 if ( minNumbers > listArray[ i ].totalCount ) minNumbers = listArray[ i ].totalCount;
  269.                 if ( maxNumbers < listArray [ i ].totalCount ) maxNumbers = listArray[ i ].totalCount;
  270.                 std = std + Math.abs( listArray[ i ].totalCount - average ) ^ 2 ;
  271.  
  272.             }
  273.  
  274.         }
  275.  
  276.         std = std / 256;
  277.  
  278.         standardDeviation = (float) Math.sqrt( (float) std );
  279.  
  280.         return total;
  281.  
  282.     }
  283.  
  284.     public Node lookThrough( String word ) { return null; }
  285.  
  286.     public void delete( String word ){ }
  287.  
  288.  
  289. }
  290.  
  291. ^^Hash C
  292.  
  293. abstract public class LinkedList { //abstract class, all lists extend this class
  294.  
  295.     Node head;
  296.     Node previous;
  297.     Node secondPrevious;
  298.     long totalCount;
  299.     long totalComparisons;
  300.     long totalReferenceChanges;
  301.     Float totalTime;
  302.     int totalLists;
  303.     int height = 1;
  304.     long minNumbers = 0;
  305.     long maxNumbers = 0;
  306.     long average = 0;
  307.     float standardDeviation = 0;
  308.  
  309.     abstract void newEntry( String word );
  310.  
  311.     abstract NodeParent lookThrough(String word );
  312.  
  313.     abstract int iterateThrough ( );
  314.  
  315.     abstract void delete( String word);
  316.  
  317.     public void hi(){
  318.         System.out.println("hit");
  319.     }
  320.  
  321.  
  322. }
  323.  
  324. ^^Linked List
  325.  
  326.  
  327. import java.io.File;
  328. import java.util.Scanner;
  329.  
  330. public class main {
  331.  
  332.     public static void main(String[] args) throws Exception{
  333.  
  334.         File FILE_NAME = new File( "/Users/nextyear/Downloads/All Test Files/Green eggs and ham.txt" ); //file path
  335.  
  336.         Scanner readableScannedFile = new Scanner(FILE_NAME); //scanner for file
  337.         while (readableScannedFile.hasNext() && readableScannedFile.nextLine() != null) ; // run through the file
  338.         readableScannedFile.close(); // closing file
  339.  
  340.         readableScannedFile = new Scanner(FILE_NAME); // opening file
  341.         float overhead = BasicFunctions.overhead(readableScannedFile); // getting overhead
  342.         readableScannedFile.close();
  343.  
  344.  
  345.         System.out.println("Binary Search Tree Build Up Analytics");
  346.  
  347.         readableScannedFile = new Scanner(FILE_NAME); // opens file
  348.         BinarySearchTree binarySearchTree = new BinarySearchTree();// list instance
  349.         BasicFunctions.loopThrough(readableScannedFile, binarySearchTree); // parse file and build up list
  350.         BasicFunctions.report(binarySearchTree, overhead); // prints out analytics
  351.  
  352.         readableScannedFile.close(); // closes file
  353.  
  354.  
  355.         System.out.println("Skip List Build Up Analytics");
  356.  
  357.         readableScannedFile = new Scanner(FILE_NAME); // opens file
  358.         SkipList skipList = new SkipList();// list instance
  359.         BasicFunctions.loopThrough(readableScannedFile, skipList); // parse file and build up list
  360.         BasicFunctions.report(skipList, overhead); // prints out analytics
  361.  
  362.         readableScannedFile.close(); // closes file
  363.  
  364.  
  365.         System.out.println("HashTable C List Build Up Analytics");
  366.  
  367.         readableScannedFile = new Scanner(FILE_NAME); // opening file
  368.         HashC hashC = new HashC(); // unsorted list instance
  369.         BasicFunctions.loopThrough(readableScannedFile, hashC); // parses file and builds up list
  370.         BasicFunctions.report(hashC, overhead); // prints out analytics
  371.  
  372.         readableScannedFile.close(); // closes file
  373.  
  374.  
  375.         System.out.println("Self Adjusting List One Build Up Analytics");
  376.  
  377.         readableScannedFile = new Scanner(FILE_NAME); // opening file
  378.         SelfAdjustingListOne selfAdjustingListOne = new SelfAdjustingListOne(); // SAOne list instance
  379.         BasicFunctions.loopThrough(readableScannedFile, selfAdjustingListOne); // parses file and builds up list
  380.         BasicFunctions.report(selfAdjustingListOne, overhead); // prints out analytics
  381.  
  382.         readableScannedFile.close(); // closes file
  383.  
  384.     }
  385.  
  386. }
  387.  
  388.  
  389. class BasicFunctions {
  390.  
  391.     static String parseThrough( Scanner readableScannedFile ){ // string parser
  392.  
  393.         String word = readableScannedFile.next();
  394.         char[] charArray = word.toLowerCase().toCharArray();
  395.  
  396.         word = "";
  397.  
  398.         for (char c: charArray){  // searches char array for words and splits them up
  399.  
  400.             if ( Character.isLetter( c ) || ( word.length() > 0 && c == '-' && Character.isLetter( word.charAt( 0 ) ) ) ) {
  401.  
  402.                 word = word + c;
  403.  
  404.             }
  405.  
  406.         }
  407.  
  408.         return word;
  409.  
  410.     }
  411.  
  412.     static void loopThrough ( Scanner readableScannedFile, LinkedList list ) { // loops through the file and also gets the total time it take sto finish
  413.  
  414.         long startingTime = System.currentTimeMillis();
  415.  
  416.         while ( readableScannedFile.hasNext() ) {  //looping through file and getting results
  417.  
  418.             String word = BasicFunctions.parseThrough( readableScannedFile );
  419.  
  420.             if ( !word.equals("") ) {
  421.  
  422.                 list.newEntry( word );
  423.  
  424.             }
  425.  
  426.         }
  427.  
  428.         long f = System.currentTimeMillis();
  429.  
  430.         list.totalTime = ((f - startingTime) / 1000.0f); //setting total time
  431.  
  432.     }
  433.  
  434.     static void tearDown ( Scanner readableScannedFile, LinkedList list ) { // loops through the file and also gets the total time it take sto finish
  435.  
  436.         list.totalComparisons = 0;
  437.         list.totalTime = 0.0f;
  438.         list.totalReferenceChanges = 0;
  439.  
  440.         long startingTime = System.currentTimeMillis();
  441.  
  442.         while ( readableScannedFile.hasNext() ) {  //looping through file and getting results
  443.  
  444.             String word = BasicFunctions.parseThrough( readableScannedFile );
  445.  
  446.             if ( !word.equals("") ) {
  447.  
  448.                 list.delete( word );
  449.  
  450.             }
  451.  
  452.         }
  453.  
  454.         if ( list.head != null ) {
  455.  
  456.             list.delete( list.head.word );
  457.  
  458.         }
  459.  
  460.         long f = System.currentTimeMillis();
  461.  
  462.         list.totalTime = ((f - startingTime) / 1000.0f); //setting total time
  463.  
  464.     }
  465.  
  466.     static void deleteTwoTearDown ( Scanner readableScannedFile, SelfAdjustingListOne list ) { // loops through the file and also gets the total time it take sto finish
  467.  
  468.         list.totalComparisons = 0;
  469.         list.totalTime = 0.0f;
  470.         list.totalReferenceChanges = 0;
  471.  
  472.         long startingTime = System.currentTimeMillis();
  473.  
  474.         while ( readableScannedFile.hasNext() ) {  //looping through file and getting results
  475.  
  476.             String word = BasicFunctions.parseThrough( readableScannedFile );
  477.  
  478.             if ( !word.equals("") ) {
  479.  
  480.                 list.deleteTwo( word );
  481.  
  482.             }
  483.  
  484.         }
  485.  
  486.         if ( list.head != null ) {
  487.  
  488.             list.delete( list.head.word );
  489.  
  490.         }
  491.  
  492.         long f = System.currentTimeMillis();
  493.  
  494.         list.totalTime = ((f - startingTime) / 1000.0f); //setting total time
  495.  
  496.     }
  497.  
  498.     static void report (LinkedList list, float overHead ) { //printing report
  499.  
  500.         System.out.println();
  501.         System.out.println("Distinct Vocabulary: " + list.iterateThrough());
  502.         System.out.println("Total Amount of Lists: " + list.totalLists);
  503.         System.out.println("Total Count: " + list.totalCount);
  504.         System.out.println("Height: " + list.height);
  505.         //System.out.println("Minimum Amount of Words in a List: " + list.minNumbers);
  506.         //System.out.println("Maximum Amount of Words in a List: " + list.maxNumbers);
  507.         //System.out.println("Average Amount of Words in a List: " + list.average);
  508.         //System.out.println("(For Hash Tables Only) Standard Deviation: " + list.standardDeviation);
  509.         System.out.println("Total Comparisons: " + list.totalComparisons);
  510.         System.out.println("Reference Changes: " + list.totalReferenceChanges);
  511.         System.out.print("Time Taken: "  );
  512.         System.out.format("%.3f", Math.max(0, list.totalTime - overHead));
  513.         System.out.print(" in seconds");
  514.         System.out.println("\n" + "\n");
  515.  
  516.     }
  517.  
  518.     static float overhead ( Scanner readableScannedFile ) { // getting the overhead time
  519.  
  520.         long starterTime = System.currentTimeMillis();
  521.  
  522.         while ( readableScannedFile.hasNext() ) {
  523.             BasicFunctions.parseThrough( readableScannedFile );
  524.         }
  525.  
  526.         System.out.println("Second Read");
  527.  
  528.         long f = System.currentTimeMillis();
  529.  
  530.         float overHead = (f - starterTime) / 1000.0f;
  531.  
  532.         System.out.println("\n");
  533.  
  534.         System.out.print("Overhead Time: " );//+ + " seconds");
  535.  
  536.         System.out.format("%.3f", overHead);
  537.  
  538.         System.out.print(" seconds");
  539.  
  540.         System.out.println("\n" + "\n");
  541.  
  542.         return overHead;
  543.  
  544.     }
  545.  
  546. }
  547.  
  548.  
  549. ^^main
  550.  
  551.  
  552. public class Node extends NodeParent { // node class, has word, link and count information
  553.  
  554.     Node link;
  555.  
  556.     Node(String word){
  557.  
  558.         this.word = word;
  559.  
  560.     }
  561.  
  562. }
  563.  
  564.  
  565.  
  566. ^^node
  567.  
  568.  
  569. abstract public class NodeParent {
  570.  
  571.     String word;
  572.     int count = 1;
  573.  
  574. }
  575.  
  576. ^^node parent
  577.  
  578.  
  579. public class PrintFunction { // was being used to print words, and add total, but kept to keep to add to total
  580.     int noob(NodeParent transpose, int total) {
  581.  
  582.         //System.out.println("Word: " + transpose.word);
  583.         //System.out.println("Count: " + transpose.count);
  584.  
  585.         return total + 1;
  586.  
  587.     }
  588.  
  589.  
  590. }
  591.  
  592. ^^print function
  593.  
  594.  
  595. public class SelfAdjustingListOne extends LinkedList {
  596.  
  597.     public SelfAdjustingListOne(){
  598.         totalLists++;
  599.     }
  600.  
  601.     public void newEntry(String word ){ // new entry method
  602.  
  603.         totalCount++;
  604.  
  605.         if (head == null){ // checks to see if head is null, if it it then set up head
  606.  
  607.             Node newNode = new Node(word);
  608.             head = newNode;
  609.             head.link = null;
  610.  
  611.         } else {
  612.  
  613.             previous = null;
  614.  
  615.             Node transverse = this.lookThrough( word ); // transversing through to see if word exists
  616.  
  617.             totalComparisons++;
  618.  
  619.             if ( transverse != null ) {
  620.  
  621.                 if ( previous != null ) {
  622.  
  623.                     previous.link = transverse.link;
  624.                     Node newNode = head;
  625.                     head = transverse;
  626.                     head.link = newNode;
  627.  
  628.                     totalReferenceChanges++;
  629.                     totalReferenceChanges++;
  630.                     totalReferenceChanges++;
  631.  
  632.                 }
  633.  
  634.                 head.count = head.count + 1;
  635.  
  636.             } else { // if not then make a new node and set it to head
  637.  
  638.                 Node newNode = new Node(word);
  639.                 Node oldHead = head;
  640.                 head = newNode;
  641.                 head.link = oldHead;
  642.                 totalReferenceChanges++;
  643.                 totalReferenceChanges++;
  644.  
  645.             }
  646.  
  647.         }
  648.  
  649.     }
  650.  
  651.     public Node lookThrough(String word ){ //loops through the list
  652.  
  653.         Node transpose = head;
  654.  
  655.         previous = null;
  656.  
  657.         while (transpose.link != null) {
  658.  
  659.             totalComparisons++;
  660.  
  661.             if ( transpose.word.equals(word) ) return transpose;
  662.  
  663.             previous = transpose;
  664.             transpose = transpose.link;
  665.  
  666.         }
  667.  
  668.         totalComparisons++;
  669.  
  670.         if (transpose.word.equals( word ) ) return transpose;
  671.  
  672.         return null;
  673.  
  674.     }
  675.  
  676.     public void delete(String word) {
  677.  
  678.         previous = null;
  679.  
  680.         Node node = this.lookThrough(word);
  681.  
  682.         totalComparisons++;
  683.  
  684.         if ( node != null && node.word.equals(word) ) {
  685.  
  686.             totalCount --;
  687.  
  688.             if (node.count > 1) {
  689.  
  690.                 node.count = node.count - 1;
  691.  
  692.                 return;
  693.  
  694.             }
  695.  
  696.             if (previous != null) {
  697.  
  698.                 Node rightNode = node.link;
  699.                 Node leftNode = previous;
  700.  
  701.                 leftNode.link = rightNode;
  702.  
  703.                 totalReferenceChanges++;
  704.  
  705.                 return;
  706.  
  707.             }
  708.  
  709.             head = node.link;
  710.             totalReferenceChanges++;
  711.  
  712.         }
  713.  
  714.     }
  715.  
  716.     public void deleteTwo(String word) {
  717.  
  718.         previous = null;
  719.  
  720.         Node node = this.lookThrough(word);
  721.  
  722.         totalComparisons++;
  723.  
  724.         if ( node != null && node.word.equals(word) ) {
  725.  
  726.             totalCount --;
  727.  
  728.             if (node.count > 1) {
  729.  
  730.                 node.count = node.count - 1;
  731.  
  732.                 if (previous == null)  return;
  733.  
  734.                 previous.link = node.link;
  735.                 Node newNode = head;
  736.                 head = node;
  737.                 head.link = newNode;
  738.  
  739.                 totalReferenceChanges++;
  740.                 totalReferenceChanges++;
  741.  
  742.                 return;
  743.  
  744.             }
  745.  
  746.             if (previous != null) {
  747.  
  748.                 Node rightNode = node.link;
  749.                 Node leftNode = previous;
  750.                 leftNode.link = rightNode;
  751.  
  752.                 totalReferenceChanges++;
  753.  
  754.                 return;
  755.  
  756.             }
  757.  
  758.             Node rightNode = node.link;
  759.             head = rightNode;
  760.  
  761.             totalReferenceChanges++;
  762.  
  763.         }
  764.  
  765.     }
  766.  
  767.     public int iterateThrough ( ) { //gets count back
  768.  
  769.         int total = 0;
  770.  
  771.         Node transpose = head;
  772.         average = totalCount;
  773.         minNumbers = totalCount;
  774.         maxNumbers = totalCount;
  775.  
  776.         if (transpose != null) {
  777.  
  778.             while (transpose.link != null) {
  779.                 total = new PrintFunction().noob(transpose, total);
  780.  
  781.                 transpose = transpose.link;
  782.  
  783.             }
  784.  
  785.             total = new PrintFunction().noob(transpose, total);
  786.  
  787.         }
  788.  
  789.         return total;
  790.  
  791.     }
  792.  
  793. }
  794.  
  795.  
  796. ^^self adjusting list one
  797.  
  798.  
  799. import java.util.Random;
  800.  
  801. public class SkipList extends LinkedList {
  802.  
  803.     SkipNode head;
  804.     SkipNode tail;
  805.     Random random = new Random();
  806.  
  807.     public SkipList(){
  808.         totalLists++;
  809.     }
  810.  
  811.     public void newEntry(String word) {
  812.  
  813.         totalCount++;
  814.  
  815.         if (head == null) { // if head does not exist then make a new head
  816.  
  817.             SkipNode newNode = new SkipNode(word, false, false);
  818.  
  819.             SkipNode sentinalLeft = new SkipNode(null, false, true);
  820.             SkipNode sentinalRight = new SkipNode(null, true, false);
  821.  
  822.             newNode.leftLink = sentinalLeft;
  823.             newNode.rightLink = sentinalRight;
  824.  
  825.             totalReferenceChanges++;
  826.             totalReferenceChanges++;
  827.  
  828.             sentinalLeft.rightLink = newNode;
  829.             sentinalRight.leftLink = newNode;
  830.  
  831.             totalReferenceChanges++;
  832.             totalReferenceChanges++;
  833.  
  834.             head = sentinalLeft;
  835.             tail = sentinalRight;
  836.  
  837.             totalReferenceChanges++;
  838.             totalReferenceChanges++;
  839.  
  840.         } else { // else look through the list and if it already exists add to counter
  841.  
  842.             SkipNode transverse = this.lookThrough(word);
  843.  
  844.             totalComparisons++;
  845.  
  846.             if ( transverse.word != null && transverse.word.equals(word)) {
  847.  
  848.                 transverse.count = transverse.count + 1;
  849.  
  850.             } else { // and sort alphabetically
  851.  
  852.                 SkipNode newNode = new SkipNode(word, false, false);
  853.                 SkipNode target = this.alphabetize(newNode, transverse);
  854.                 this.coinFlip(target);
  855.  
  856.             }
  857.  
  858.         }
  859.  
  860.     }
  861.  
  862.     public SkipNode lookThrough(String word) { // looks through  list and returns rather it a word exists or not
  863.  
  864.         SkipNode transpose = head; //head;
  865.  
  866.         while ( true ) {
  867.  
  868.             while ( !transpose.rightLink.sentinalRight && transpose.rightLink.word.toLowerCase().compareTo(word.toLowerCase()) <= 0 ) {
  869.  
  870.                 totalComparisons++;
  871.                 totalComparisons++;
  872.  
  873.                 if ( transpose.rightLink.word.equals( word ) ) {
  874.  
  875.                     transpose = transpose.rightLink;
  876.  
  877.                     while ( transpose.downLink != null ) {
  878.  
  879.                         transpose = transpose.downLink;
  880.  
  881.                     }
  882.  
  883.                     return transpose;
  884.  
  885.                 }
  886.  
  887.                 transpose = transpose.rightLink;
  888.  
  889.             }
  890.  
  891.             if ( transpose.rightLink.downLink == null ) return transpose;
  892.  
  893.             transpose = transpose.downLink;
  894.  
  895.         }
  896.  
  897.     }
  898.  
  899.     public SkipNode alphabetize(SkipNode target, SkipNode placement) { // handles alphabetizing the node
  900.  
  901.  
  902.         target.rightLink = placement.rightLink;
  903.         target.leftLink = placement;
  904.         placement.rightLink.leftLink = target;
  905.         placement.rightLink = target;
  906.  
  907.         totalReferenceChanges++;
  908.         totalReferenceChanges++;
  909.         totalReferenceChanges++;
  910.         totalReferenceChanges++;
  911.  
  912.         return target;
  913.  
  914.     }
  915.  
  916.     public void coinFlip(SkipNode target) {
  917.  
  918.  
  919.         int currentHeight = 1;
  920.  
  921.         while (random.nextBoolean()) {
  922.  
  923.             if (currentHeight == height) {
  924.  
  925.                 SkipNode newSentinalLeft = new SkipNode(null, false, true);
  926.                 SkipNode newSentinalRight = new SkipNode( null, true, false);
  927.  
  928.                 head.upLink = newSentinalLeft;
  929.                 tail.upLink = newSentinalRight;
  930.  
  931.                 totalReferenceChanges++;
  932.                 totalReferenceChanges++;
  933.  
  934.                 newSentinalLeft.downLink = head;
  935.                 newSentinalRight.downLink = tail;
  936.  
  937.                 totalReferenceChanges++;
  938.                 totalReferenceChanges++;
  939.  
  940.                 SkipNode newLaneTargetNode = new SkipNode(target.word, false, false);
  941.  
  942.                 newLaneTargetNode.rightLink = newSentinalRight;
  943.                 newLaneTargetNode.leftLink = newSentinalLeft;
  944.                 newLaneTargetNode.downLink = target;
  945.  
  946.                 totalReferenceChanges++;
  947.                 totalReferenceChanges++;
  948.                 totalReferenceChanges++;
  949.  
  950.                 target.upLink = newLaneTargetNode;
  951.                 target = newLaneTargetNode;
  952.  
  953.                 totalReferenceChanges++;
  954.  
  955.                 newSentinalLeft.rightLink = newLaneTargetNode;
  956.                 newSentinalRight.leftLink = newLaneTargetNode;
  957.  
  958.                 totalReferenceChanges++;
  959.                 totalReferenceChanges++;
  960.  
  961.                 head = newSentinalLeft;
  962.                 tail = newSentinalRight;
  963.  
  964.                 totalReferenceChanges++;
  965.                 totalReferenceChanges++;
  966.  
  967.  
  968.                 currentHeight++;
  969.                 this.height++;
  970.  
  971.  
  972.             } else {
  973.  
  974.                 SkipNode transpose = target;
  975.  
  976.                 while (transpose.upLink == null) {
  977.                     transpose = transpose.leftLink;
  978.                 }
  979.  
  980.                 SkipNode nextLaneNode = transpose.upLink;
  981.                 SkipNode nextLaneRightNode = nextLaneNode.rightLink;
  982.  
  983.                 SkipNode newLaneTargetNode = new SkipNode(target.word, false, false);
  984.                 newLaneTargetNode.rightLink = nextLaneRightNode;
  985.                 newLaneTargetNode.leftLink = nextLaneNode;
  986.  
  987.                 totalReferenceChanges++;
  988.                 totalReferenceChanges++;
  989.  
  990.                 nextLaneNode.rightLink = newLaneTargetNode;
  991.                 nextLaneRightNode.leftLink = newLaneTargetNode;
  992.  
  993.                 totalReferenceChanges++;
  994.                 totalReferenceChanges++;
  995.  
  996.                 newLaneTargetNode.downLink = target;
  997.                 target.upLink = newLaneTargetNode;
  998.  
  999.                 totalReferenceChanges++;
  1000.                 totalReferenceChanges++;
  1001.  
  1002.                 target = newLaneTargetNode;
  1003.  
  1004.                 currentHeight++;
  1005.  
  1006.             }
  1007.         }
  1008.  
  1009.     }
  1010.  
  1011.     public void delete(String word) {
  1012.  
  1013.        SkipNode node = this.lookThrough(word);
  1014.  
  1015.         totalComparisons++;
  1016.  
  1017.        if ( node != null && node.word.equals(word) ) {
  1018.  
  1019.            totalCount --;
  1020.  
  1021.            if ( node.count > 1 ) {
  1022.  
  1023.                node.count = node.count - 1;
  1024.                return;
  1025.  
  1026.            }
  1027.  
  1028.            SkipNode rightNode = node.rightLink;
  1029.            SkipNode leftNode = node.leftLink;
  1030.  
  1031.            rightNode.leftLink = leftNode;
  1032.            leftNode.rightLink = rightNode;
  1033.  
  1034.            totalReferenceChanges++;
  1035.            totalReferenceChanges++;
  1036.            totalReferenceChanges++;
  1037.            totalReferenceChanges++;
  1038.  
  1039.            while ( node.upLink != null ) {
  1040.  
  1041.                node = node.upLink;
  1042.  
  1043.                rightNode = node.rightLink;
  1044.                leftNode = node.leftLink;
  1045.  
  1046.                rightNode.leftLink = leftNode;
  1047.                leftNode.rightLink = rightNode;
  1048.  
  1049.                totalReferenceChanges++;
  1050.                totalReferenceChanges++;
  1051.                totalReferenceChanges++;
  1052.                totalReferenceChanges++;
  1053.  
  1054.  
  1055.            }
  1056.  
  1057.        }
  1058.  
  1059.     }
  1060.  
  1061.  
  1062.     public int iterateThrough() { //looping through to return counter
  1063.  
  1064.         SkipNode transpose = head;
  1065.         int total = 0;
  1066.  
  1067.         average = totalCount;
  1068.         minNumbers = totalCount;
  1069.         maxNumbers = totalCount;
  1070.  
  1071.         while (transpose.downLink != null) transpose = transpose.downLink;
  1072.         transpose = transpose.rightLink;
  1073.  
  1074.         while (!transpose.sentinalRight) {
  1075.             total = new PrintFunction().noob( transpose, total );
  1076.             transpose = transpose.rightLink;
  1077.  
  1078.         }
  1079.         return total;
  1080.  
  1081.     }
  1082.  
  1083. }
  1084.  
  1085.  
  1086. ^^skip list
  1087.  
  1088.  
  1089.  
  1090. public class SkipNode extends NodeParent {
  1091.  
  1092.     boolean sentinalRight = false;
  1093.     boolean sentinalLeft = false;
  1094.  
  1095.     SkipNode rightLink = null;
  1096.     SkipNode leftLink = null;
  1097.     SkipNode upLink = null;
  1098.     SkipNode downLink = null;
  1099.  
  1100.     SkipNode(String word, boolean sentRight, boolean sentLeft){
  1101.  
  1102.         this.word = word;
  1103.         this.sentinalLeft = sentLeft;
  1104.         this.sentinalRight = sentRight;
  1105.  
  1106.     }
  1107.  
  1108.  
  1109. }
  1110.  
  1111.  
  1112. ^^ SKip Node
RAW Paste Data
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
 
Top