public class BinarySearchTree extends LinkedList {

    public BinarySearchTree(){
        totalLists++;
    }

    BSTNode head;
    BSTNode previous;
    int distintcVocab;

    public void newEntry( String word ){ //new entry method

        totalCount++;

        if (head == null){ //if head is nonexistant then crate

            distintcVocab++;
            BSTNode newNode = new BSTNode(word);
            head = newNode;
            head.right = null;
            head.left = null;

        } else {

            BSTNode transverse = this.lookThrough( word ); //looks through to see if it exists

            if ( transverse != null && transverse.word.equals(word) ) {

                transverse.count = transverse.count + 1;

            } else { //make new node if it does not exist

                distintcVocab++;

                BSTNode newNode = new BSTNode(word);
                newNode.parent = previous;
                totalReferenceChanges++;

                if (previous.word.compareTo(word) > 0 ) {

                    previous.left = newNode;
                    totalReferenceChanges++;

                    return;

                }

                previous.right = newNode;
                totalReferenceChanges++;

            }

        }

    }

    public BSTNode lookThrough(String word ){ // looks through  list and returns rather it a word exists or not

        BSTNode transpose = head;
        previous = null;

        while (transpose != null) {

            totalComparisons++;
            int compInt;

            if ( transpose == null || (compInt = transpose.word.compareTo(word)) == 0 ) {

                return transpose;

            } else if ( compInt > 0 ) { //less then

                previous = transpose;
                transpose = transpose.left;

            } else { //greater then

                previous = transpose;
                transpose = transpose.right;

            }

        }

        return null;

    }

    public BSTNode Successor( BSTNode node ) {

        BSTNode transverse = node;
        BSTNode x = node;

        if ( transverse.right != null ) {

            transverse = transverse.right;

            while ( transverse.left != null ) transverse = transverse.left ;

            return transverse;

        }

        transverse = node.parent;

        while ( transverse != null && x == transverse.right ) {

            x = transverse;
            transverse = transverse.parent;

        }

        return transverse;

    }

    public BSTNode minumum( BSTNode node ) {

        BSTNode transveral = node;

        while ( transveral.left != null ) transveral = transveral.left;

        return  transveral;

    }

    public int Height (BSTNode node) {

        if (node == null) return 0;

        int leftHeight = Height(node.left);
        int rightHeight = Height(node.right);

        if (leftHeight > rightHeight) return leftHeight + 1;

        return rightHeight + 1;

    }

    public void displayFirst100() {

        BSTNode p = minumum( head );

        System.out.println("First 100 entries:");
        System.out.println();

        for (int i = 0; i < 100; i++) {
            if (p != null) {
                System.out.println(p.word + " " + p.count);
                p = Successor(p);
            }

        }

        System.out.println();

    }

    public void Traverse(BSTNode node) {
        if (node == null) return;
        Traverse(node.left);

        new PrintFunction().noob(node, 0);

        Traverse(node.right);
    }


    public int iterateThrough ( ) { //looping through to return counter

        int total = 0;

        displayFirst100();

        height = Height( head );

        BSTNode transpose = head;

        average = totalCount;
        minNumbers = totalCount;
        maxNumbers = totalCount;

        Traverse(transpose);

        return distintcVocab;

    }

    public void delete(String word) {}



}

^^binary search tree


public class BSTNode extends NodeParent {


    BSTNode right = null;
    BSTNode left = null;
    BSTNode parent = null;

    BSTNode(String word){

        this.word = word;

    }


}

^^BST Node


public class HashC extends LinkedList{

    SelfAdjustingListOne[] listArray = new SelfAdjustingListOne[ 256 ];

    public int hashFunction( String word ) {

        int key = 0;

        char[] wordArray = word.toCharArray();

        for (char i : wordArray)  key = key * 31 + i;

        key = key % 256;

        return Math.abs(key);

    }

    public void newEntry( String word ) {

        totalCount++;

        int key = this.hashFunction( word );

        if ( listArray [ key ] == null ) {
            totalLists++;
            listArray [ key ] = new SelfAdjustingListOne();
        }

        listArray [ key ].newEntry( word );

    }

    public int iterateThrough( ) {

        int total = 1;

        minNumbers = Long.MAX_VALUE;
        maxNumbers = Long.MIN_VALUE;

        average = totalCount / totalLists;

        long std = 0;

        for ( int i = 0; i < 256; i++ ) {

            if ( listArray[ i ] != null ) {

                total = total + listArray[ i ].iterateThrough();
                totalComparisons = totalComparisons + listArray [ i ].totalComparisons;
                totalReferenceChanges = totalReferenceChanges + listArray [ i ].totalReferenceChanges;
                if ( minNumbers > listArray[ i ].totalCount ) minNumbers = listArray[ i ].totalCount;
                if ( maxNumbers < listArray [ i ].totalCount ) maxNumbers = listArray[ i ].totalCount;
                std = std + Math.abs( listArray[ i ].totalCount - average ) ^ 2 ;

            }

        }

        std = std / 256;

        standardDeviation = (float) Math.sqrt( (float) std );

        return total;

    }

    public Node lookThrough( String word ) { return null; }

    public void delete( String word ){ }


}

^^Hash C

abstract public class LinkedList { //abstract class, all lists extend this class

    Node head;
    Node previous;
    Node secondPrevious;
    long totalCount;
    long totalComparisons;
    long totalReferenceChanges;
    Float totalTime;
    int totalLists;
    int height = 1;
    long minNumbers = 0;
    long maxNumbers = 0;
    long average = 0;
    float standardDeviation = 0;

    abstract void newEntry( String word );

    abstract NodeParent lookThrough(String word );

    abstract int iterateThrough ( );

    abstract void delete( String word);

    public void hi(){
        System.out.println("hit");
    }


}

^^Linked List


import java.io.File;
import java.util.Scanner;

public class main {

    public static void main(String[] args) throws Exception{

        File FILE_NAME = new File( "/Users/nextyear/Downloads/All Test Files/Green eggs and ham.txt" ); //file path

        Scanner readableScannedFile = new Scanner(FILE_NAME); //scanner for file
        while (readableScannedFile.hasNext() && readableScannedFile.nextLine() != null) ; // run through the file
        readableScannedFile.close(); // closing file

        readableScannedFile = new Scanner(FILE_NAME); // opening file
        float overhead = BasicFunctions.overhead(readableScannedFile); // getting overhead
        readableScannedFile.close();


        System.out.println("Binary Search Tree Build Up Analytics");

        readableScannedFile = new Scanner(FILE_NAME); // opens file
        BinarySearchTree binarySearchTree = new BinarySearchTree();// list instance
        BasicFunctions.loopThrough(readableScannedFile, binarySearchTree); // parse file and build up list
        BasicFunctions.report(binarySearchTree, overhead); // prints out analytics

        readableScannedFile.close(); // closes file


        System.out.println("Skip List Build Up Analytics");

        readableScannedFile = new Scanner(FILE_NAME); // opens file
        SkipList skipList = new SkipList();// list instance
        BasicFunctions.loopThrough(readableScannedFile, skipList); // parse file and build up list
        BasicFunctions.report(skipList, overhead); // prints out analytics

        readableScannedFile.close(); // closes file


        System.out.println("HashTable C List Build Up Analytics");

        readableScannedFile = new Scanner(FILE_NAME); // opening file
        HashC hashC = new HashC(); // unsorted list instance
        BasicFunctions.loopThrough(readableScannedFile, hashC); // parses file and builds up list
        BasicFunctions.report(hashC, overhead); // prints out analytics

        readableScannedFile.close(); // closes file


        System.out.println("Self Adjusting List One Build Up Analytics");

        readableScannedFile = new Scanner(FILE_NAME); // opening file
        SelfAdjustingListOne selfAdjustingListOne = new SelfAdjustingListOne(); // SAOne list instance
        BasicFunctions.loopThrough(readableScannedFile, selfAdjustingListOne); // parses file and builds up list
        BasicFunctions.report(selfAdjustingListOne, overhead); // prints out analytics

        readableScannedFile.close(); // closes file

    }

}


class BasicFunctions {

    static String parseThrough( Scanner readableScannedFile ){ // string parser

        String word = readableScannedFile.next();
        char[] charArray = word.toLowerCase().toCharArray();

        word = "";

        for (char c: charArray){  // searches char array for words and splits them up

            if ( Character.isLetter( c ) || ( word.length() > 0 && c == '-' && Character.isLetter( word.charAt( 0 ) ) ) ) {

                word = word + c;

            }

        }

        return word;

    }

    static void loopThrough ( Scanner readableScannedFile, LinkedList list ) { // loops through the file and also gets the total time it take sto finish

        long startingTime = System.currentTimeMillis();

        while ( readableScannedFile.hasNext() ) {  //looping through file and getting results

            String word = BasicFunctions.parseThrough( readableScannedFile );

            if ( !word.equals("") ) {

                list.newEntry( word );

            }

        }

        long f = System.currentTimeMillis();

        list.totalTime = ((f - startingTime) / 1000.0f); //setting total time

    }

    static void tearDown ( Scanner readableScannedFile, LinkedList list ) { // loops through the file and also gets the total time it take sto finish

        list.totalComparisons = 0;
        list.totalTime = 0.0f;
        list.totalReferenceChanges = 0;

        long startingTime = System.currentTimeMillis();

        while ( readableScannedFile.hasNext() ) {  //looping through file and getting results

            String word = BasicFunctions.parseThrough( readableScannedFile );

            if ( !word.equals("") ) {

                list.delete( word );

            }

        }

        if ( list.head != null ) {

            list.delete( list.head.word );

        }

        long f = System.currentTimeMillis();

        list.totalTime = ((f - startingTime) / 1000.0f); //setting total time

    }

    static void deleteTwoTearDown ( Scanner readableScannedFile, SelfAdjustingListOne list ) { // loops through the file and also gets the total time it take sto finish

        list.totalComparisons = 0;
        list.totalTime = 0.0f;
        list.totalReferenceChanges = 0;

        long startingTime = System.currentTimeMillis();

        while ( readableScannedFile.hasNext() ) {  //looping through file and getting results

            String word = BasicFunctions.parseThrough( readableScannedFile );

            if ( !word.equals("") ) {

                list.deleteTwo( word );

            }

        }

        if ( list.head != null ) {

            list.delete( list.head.word );

        }

        long f = System.currentTimeMillis();

        list.totalTime = ((f - startingTime) / 1000.0f); //setting total time

    }

    static void report (LinkedList list, float overHead ) { //printing report

        System.out.println();
        System.out.println("Distinct Vocabulary: " + list.iterateThrough());
        System.out.println("Total Amount of Lists: " + list.totalLists);
        System.out.println("Total Count: " + list.totalCount);
        System.out.println("Height: " + list.height);
        //System.out.println("Minimum Amount of Words in a List: " + list.minNumbers);
        //System.out.println("Maximum Amount of Words in a List: " + list.maxNumbers);
        //System.out.println("Average Amount of Words in a List: " + list.average);
        //System.out.println("(For Hash Tables Only) Standard Deviation: " + list.standardDeviation);
        System.out.println("Total Comparisons: " + list.totalComparisons);
        System.out.println("Reference Changes: " + list.totalReferenceChanges);
        System.out.print("Time Taken: "  );
        System.out.format("%.3f", Math.max(0, list.totalTime - overHead));
        System.out.print(" in seconds");
        System.out.println("\n" + "\n");

    }

    static float overhead ( Scanner readableScannedFile ) { // getting the overhead time

        long starterTime = System.currentTimeMillis();

        while ( readableScannedFile.hasNext() ) {
            BasicFunctions.parseThrough( readableScannedFile );
        }

        System.out.println("Second Read");

        long f = System.currentTimeMillis();

        float overHead = (f - starterTime) / 1000.0f;

        System.out.println("\n");

        System.out.print("Overhead Time: " );//+ + " seconds");

        System.out.format("%.3f", overHead);

        System.out.print(" seconds");

        System.out.println("\n" + "\n");

        return overHead;

    }

}


^^main


public class Node extends NodeParent { // node class, has word, link and count information

    Node link;

    Node(String word){

        this.word = word;

    }

}



^^node


abstract public class NodeParent {

    String word;
    int count = 1;

}

^^node parent


public class PrintFunction { // was being used to print words, and add total, but kept to keep to add to total
    int noob(NodeParent transpose, int total) {

        //System.out.println("Word: " + transpose.word);
        //System.out.println("Count: " + transpose.count);

        return total + 1;

    }


}

^^print function


public class SelfAdjustingListOne extends LinkedList {

    public SelfAdjustingListOne(){
        totalLists++;
    }

    public void newEntry(String word ){ // new entry method

        totalCount++;

        if (head == null){ // checks to see if head is null, if it it then set up head

            Node newNode = new Node(word);
            head = newNode;
            head.link = null;

        } else {

            previous = null;

            Node transverse = this.lookThrough( word ); // transversing through to see if word exists

            totalComparisons++;

            if ( transverse != null ) {

                if ( previous != null ) {

                    previous.link = transverse.link;
                    Node newNode = head;
                    head = transverse;
                    head.link = newNode;

                    totalReferenceChanges++;
                    totalReferenceChanges++;
                    totalReferenceChanges++;

                }

                head.count = head.count + 1;

            } else { // if not then make a new node and set it to head

                Node newNode = new Node(word);
                Node oldHead = head;
                head = newNode;
                head.link = oldHead;
                totalReferenceChanges++;
                totalReferenceChanges++;

            }

        }

    }

    public Node lookThrough(String word ){ //loops through the list

        Node transpose = head;

        previous = null;

        while (transpose.link != null) {

            totalComparisons++;

            if ( transpose.word.equals(word) ) return transpose;

            previous = transpose;
            transpose = transpose.link;

        }

        totalComparisons++;

        if (transpose.word.equals( word ) ) return transpose;

        return null;

    }

    public void delete(String word) {

        previous = null;

        Node node = this.lookThrough(word);

        totalComparisons++;

        if ( node != null && node.word.equals(word) ) {

            totalCount --;

            if (node.count > 1) {

                node.count = node.count - 1;

                return;

            }

            if (previous != null) {

                Node rightNode = node.link;
                Node leftNode = previous;

                leftNode.link = rightNode;

                totalReferenceChanges++;

                return;

            }

            head = node.link;
            totalReferenceChanges++;

        }

    }

    public void deleteTwo(String word) {

        previous = null;

        Node node = this.lookThrough(word);

        totalComparisons++;

        if ( node != null && node.word.equals(word) ) {

            totalCount --;

            if (node.count > 1) {

                node.count = node.count - 1;

                if (previous == null)  return;

                previous.link = node.link;
                Node newNode = head;
                head = node;
                head.link = newNode;

                totalReferenceChanges++;
                totalReferenceChanges++;

                return;

            }

            if (previous != null) {

                Node rightNode = node.link;
                Node leftNode = previous;
                leftNode.link = rightNode;

                totalReferenceChanges++;

                return;

            }

            Node rightNode = node.link;
            head = rightNode;

            totalReferenceChanges++;

        }

    }

    public int iterateThrough ( ) { //gets count back

        int total = 0;

        Node transpose = head;
        average = totalCount;
        minNumbers = totalCount;
        maxNumbers = totalCount;

        if (transpose != null) {

            while (transpose.link != null) {
                total = new PrintFunction().noob(transpose, total);

                transpose = transpose.link;

            }

            total = new PrintFunction().noob(transpose, total);

        }

        return total;

    }

}


^^self adjusting list one


import java.util.Random;

public class SkipList extends LinkedList {

    SkipNode head;
    SkipNode tail;
    Random random = new Random();

    public SkipList(){
        totalLists++;
    }

    public void newEntry(String word) {

        totalCount++;

        if (head == null) { // if head does not exist then make a new head

            SkipNode newNode = new SkipNode(word, false, false);

            SkipNode sentinalLeft = new SkipNode(null, false, true);
            SkipNode sentinalRight = new SkipNode(null, true, false);

            newNode.leftLink = sentinalLeft;
            newNode.rightLink = sentinalRight;

            totalReferenceChanges++;
            totalReferenceChanges++;

            sentinalLeft.rightLink = newNode;
            sentinalRight.leftLink = newNode;

            totalReferenceChanges++;
            totalReferenceChanges++;

            head = sentinalLeft;
            tail = sentinalRight;

            totalReferenceChanges++;
            totalReferenceChanges++;

        } else { // else look through the list and if it already exists add to counter

            SkipNode transverse = this.lookThrough(word);

            totalComparisons++;

            if ( transverse.word != null && transverse.word.equals(word)) {

                transverse.count = transverse.count + 1;

            } else { // and sort alphabetically

                SkipNode newNode = new SkipNode(word, false, false);
                SkipNode target = this.alphabetize(newNode, transverse);
                this.coinFlip(target);

            }

        }

    }

    public SkipNode lookThrough(String word) { // looks through  list and returns rather it a word exists or not

        SkipNode transpose = head; //head;

        while ( true ) {

            while ( !transpose.rightLink.sentinalRight && transpose.rightLink.word.toLowerCase().compareTo(word.toLowerCase()) <= 0 ) {

                totalComparisons++;
                totalComparisons++;

                if ( transpose.rightLink.word.equals( word ) ) {

                    transpose = transpose.rightLink;

                    while ( transpose.downLink != null ) {

                        transpose = transpose.downLink;

                    }

                    return transpose;

                }

                transpose = transpose.rightLink;

            }

            if ( transpose.rightLink.downLink == null ) return transpose;

            transpose = transpose.downLink;

        }

    }

    public SkipNode alphabetize(SkipNode target, SkipNode placement) { // handles alphabetizing the node


        target.rightLink = placement.rightLink;
        target.leftLink = placement;
        placement.rightLink.leftLink = target;
        placement.rightLink = target;

        totalReferenceChanges++;
        totalReferenceChanges++;
        totalReferenceChanges++;
        totalReferenceChanges++;

        return target;

    }

    public void coinFlip(SkipNode target) {


        int currentHeight = 1;

        while (random.nextBoolean()) {

            if (currentHeight == height) {

                SkipNode newSentinalLeft = new SkipNode(null, false, true);
                SkipNode newSentinalRight = new SkipNode( null, true, false);

                head.upLink = newSentinalLeft;
                tail.upLink = newSentinalRight;

                totalReferenceChanges++;
                totalReferenceChanges++;

                newSentinalLeft.downLink = head;
                newSentinalRight.downLink = tail;

                totalReferenceChanges++;
                totalReferenceChanges++;

                SkipNode newLaneTargetNode = new SkipNode(target.word, false, false);

                newLaneTargetNode.rightLink = newSentinalRight;
                newLaneTargetNode.leftLink = newSentinalLeft;
                newLaneTargetNode.downLink = target;

                totalReferenceChanges++;
                totalReferenceChanges++;
                totalReferenceChanges++;

                target.upLink = newLaneTargetNode;
                target = newLaneTargetNode;

                totalReferenceChanges++;

                newSentinalLeft.rightLink = newLaneTargetNode;
                newSentinalRight.leftLink = newLaneTargetNode;

                totalReferenceChanges++;
                totalReferenceChanges++;

                head = newSentinalLeft;
                tail = newSentinalRight;

                totalReferenceChanges++;
                totalReferenceChanges++;


                currentHeight++;
                this.height++;


            } else {

                SkipNode transpose = target;

                while (transpose.upLink == null) {
                    transpose = transpose.leftLink;
                }

                SkipNode nextLaneNode = transpose.upLink;
                SkipNode nextLaneRightNode = nextLaneNode.rightLink;

                SkipNode newLaneTargetNode = new SkipNode(target.word, false, false);
                newLaneTargetNode.rightLink = nextLaneRightNode;
                newLaneTargetNode.leftLink = nextLaneNode;

                totalReferenceChanges++;
                totalReferenceChanges++;

                nextLaneNode.rightLink = newLaneTargetNode;
                nextLaneRightNode.leftLink = newLaneTargetNode;

                totalReferenceChanges++;
                totalReferenceChanges++;

                newLaneTargetNode.downLink = target;
                target.upLink = newLaneTargetNode;

                totalReferenceChanges++;
                totalReferenceChanges++;

                target = newLaneTargetNode;

                currentHeight++;

            }
        }

    }

    public void delete(String word) {

       SkipNode node = this.lookThrough(word);

        totalComparisons++;

       if ( node != null && node.word.equals(word) ) {

           totalCount --;

           if ( node.count > 1 ) {

               node.count = node.count - 1;
               return;

           }

           SkipNode rightNode = node.rightLink;
           SkipNode leftNode = node.leftLink;

           rightNode.leftLink = leftNode;
           leftNode.rightLink = rightNode;

           totalReferenceChanges++;
           totalReferenceChanges++;
           totalReferenceChanges++;
           totalReferenceChanges++;

           while ( node.upLink != null ) {

               node = node.upLink;

               rightNode = node.rightLink;
               leftNode = node.leftLink;

               rightNode.leftLink = leftNode;
               leftNode.rightLink = rightNode;

               totalReferenceChanges++;
               totalReferenceChanges++;
               totalReferenceChanges++;
               totalReferenceChanges++;


           }

       }

    }


    public int iterateThrough() { //looping through to return counter

        SkipNode transpose = head;
        int total = 0;

        average = totalCount;
        minNumbers = totalCount;
        maxNumbers = totalCount;

        while (transpose.downLink != null) transpose = transpose.downLink;
        transpose = transpose.rightLink;

        while (!transpose.sentinalRight) {
            total = new PrintFunction().noob( transpose, total );
            transpose = transpose.rightLink;

        }
        return total;

    }

}


^^skip list



public class SkipNode extends NodeParent {

    boolean sentinalRight = false;
    boolean sentinalLeft = false;

    SkipNode rightLink = null;
    SkipNode leftLink = null;
    SkipNode upLink = null;
    SkipNode downLink = null;

    SkipNode(String word, boolean sentRight, boolean sentLeft){

        this.word = word;
        this.sentinalLeft = sentLeft;
        this.sentinalRight = sentRight;

    }


}


^^ SKip Node