Guest User

Untitled

a guest
Dec 12th, 2019
136
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