Question

This lab serves as an intro to Java Interfaces and an Object-Oriented design strategy towards implementing data structures. We will be using Entry.java objects which are key,value pairs, with key being an integer and value being a generic parameter. We will be sorting these Entries according to their key value. The file Entry.java is given to you and does not require any modification.

As you should know by now, bucket sort works by placing items into buckets and each bucket is sorted on its own. Once all items are placed, the bucket contents are extracted in a sequence from smallest bucket to largest. In this lab, we will have a SortedBucket object which takes an item and stores it in sorted order. We will also be using a BucketList object which creates a list of SortedBucket objects, and decides which bucket each number (Entry) goes to.

Start with looking at the two Abstract Data Types:

SortedBucketADT.java: an interface that describes what functionality a bucket has. Aside from a constructor and a toString() method, these can .add(Entry) and will place the Entry in sorted order within the bucket, and they also have a getBucketContents() method which returns the contents of the bucket.

BucketListADT.java: an interface that describes the collection of buckets. The constructor takes 3 parameters: int min, int max, int n, which represent the expected minimum of Entry keys, expected maximum of Entry keys, and the number of buckets to create. It supports methods .add(Entry) and .addAll(Entries) to add one Entry or to add many Entries. The .add( ) method should decide which bucket the Entry gets placed in. It also has a way to extract the sorted order of Entries with a .getSortedOrder() method.

You do not need to modify these ADT files. Your task will be in implementing and testing them. Namely, SortedBucket.java will implement SortedBucketADT.java and BucketList.java will implement BucketListADT.java. These are partially implemented already, and contain //TODO items throughout the file to guide you in the implementation process.

Further, there is a MainClass.java present only to show you some sample intended usage of the data structure and sorting method. You can modify or delete this file as you please. Finally, there is a Test.java class file which illustrates how one can test the contents of each bucket after adding elements to the bucket list. Once again, there are //TODO items throughout this test file with more specific instructions.

Scoring: Up to 6 points for completing the implementation and up to 4 points for the additional testing you are to include in the test file.

SUBMIT: your edited .java files and a screenshot of your coverage report that shows that your tests provide at least 80% coverage of the project files. You may alternatively show your lab instructor (in lab time) your coverage report and your test cases

Answer 1

As per the problem statement I have solve the problem. Please let me know if you have any doubts or you want me to modify the answer. And if you find this answer useful then don't forget to rate my answer as thumps up. Thank you! :)

-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
import java.util.ArrayList;

public class MainClass {

    public static void main(String[] args) {

        BucketList<String> bucketList = new BucketList<String>(0,100,6);
        bucketList.add(new Entry<String>(-10 , "Bob"));
        System.out.println(bucketList);
        bucketList.add(new Entry<String>(90 , "John"));
        System.out.println(bucketList);
        bucketList.add(new Entry<String>(83 , "Vennisa"));
        System.out.println(bucketList);
        bucketList.add(new Entry<String>(78 , "Catherine"));
        System.out.println(bucketList);
        bucketList.add(new Entry<String>(62 , "Barley"));
        System.out.println(bucketList);
        bucketList.add(new Entry<String>(74 , "Angston"));
        System.out.println(bucketList);
        bucketList.add(new Entry<String>(88 , "Andrew"));
        System.out.println(bucketList);
        bucketList.add(new Entry<String>(104 , "Cathy"));
        System.out.println(bucketList);

        // add N more random students
        int N = 10;
        ArrayList<Entry<String>> allEmployee = new ArrayList<Entry<String>>();
        for (int i=1; i<=N; i++) {
            Entry<String> e = new Entry<String>((int)(45+Math.random()*50),"emp"+i);
            allEmployee.add(e);
        }

        // check add all methos
        bucketList.addAll(allEmployee);

        // method to display all buckets and their contents
        System.out.println(bucketList);

        // method to display the final sorted order
        System.out.println(bucketList.getSortedOrder());
    }

}
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
import java.util.ArrayList;
import java.util.Collection;

public class BucketList<V> implements BucketListADT<V> {

    private ArrayList<SortedBucket<V>> sortedBucketList;
    private int minimum;
    private int maximum;

    //constructor
    public BucketList(int minimum, int maximum, int number) {
        sortedBucketList = new ArrayList<>(number);
        for (int i=0; i<number; i++){
            sortedBucketList.add(new SortedBucket<>());
        }
        this.minimum = minimum;
        this.maximum = maximum;
    }

    //method to add the given Entry into the bucket

    @Override
    public void add(Entry<V> item) {
        int bucketSize = sortedBucketList.size();
        int indexToInsert = bucketSize*(item.getKey()- minimum)/(maximum - minimum +1);

        indexToInsert = Math.min(indexToInsert, this.getNumberOfBuckets() - 1);
        indexToInsert = Math.max(indexToInsert, 0);

        sortedBucketList.get(indexToInsert).add(item);

    }

    //method to add all entries in the Collection

    @Override
    public void addAll(Collection<Entry<V>> bucketEntryCollection) {
        for (Entry<V> entry : bucketEntryCollection)
            this.add(entry);
    }

    //method returns a single ArrayList of sorted order
    @Override
    public ArrayList<Entry<V>> getSortedOrder() {
        ArrayList<Entry<V>> output = new ArrayList<>();
        this.sortedBucketList.forEach(t ->
                output.addAll(t.getBucketContents()));

        return output;
    }

    //method returns the content of the bucket
    @Override
    public ArrayList<Entry<V>> getBucket(int i) {

        return this.sortedBucketList.get(i).getBucketContents();
    }

    //method return the number of buckets in this list
    @Override
    public int getNumberOfBuckets(){
        return sortedBucketList.size();
    }

    //method to show content of the bucket
    public String toString() {
        // Leave this alone
        StringBuilder output = new StringBuilder("[");
        for (SortedBucket<V> s: this.sortedBucketList) {
            output.append(s.toString());
        }
        output.append("]");
        return output.toString();

    }
}

-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
import java.util.ArrayList;
import java.util.Collection;

public interface BucketListADT<V> {

    void add(Entry<V> item);

    void addAll(Collection<Entry<V>> c);

    ArrayList<Entry<V>> getBucket(int i);

    public int getNumberOfBuckets();

    ArrayList<Entry<V>> getSortedOrder();

}
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
public class Entry <V> {
    private int key;
    private V value;

    public Entry(int k, V v) {
        key = k;
        value = v;
    }

    public int getKey() {
        return this.key;
    }

    public V getValue() {
        return this.value;
    }

    public String toString() {
        return this.getValue()+"="+this.getKey();
    }
}
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
import java.util.ArrayList;

public class SortedBucket<V> implements SortedBucketADT<V>{

    private ArrayList<Entry<V>> sortedBucket;

    //constructor
    public SortedBucket() {
        sortedBucket = new ArrayList<Entry<V>>();
    }

    //method adds entry to bucket

    @Override
    public void add(Entry<V> t) {

        boolean added = false;

        for (int i = 0; i < this.sortedBucket.size(); i++) {
            if (sortedBucket.get(i).getKey() > t.getKey()) {
                sortedBucket.add(i, t);
                added = true;
                break;
            }
        }
        if(!added) {
            sortedBucket.add(t);
        }
    }

    //method to return a sorted ArrayList of Entries in this bucket

    @Override
    public ArrayList<Entry<V>> getBucketContents() {
        return sortedBucket;
    }

    @Override
    public String toString() {
        return sortedBucket.toString();
    }
}
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
import java.util.ArrayList;

public interface SortedBucketADT<V>{

    void add(Entry<V> t);

    ArrayList<Entry<V>> getBucketContents();

}
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
import org.junit.Before;
import org.junit.Test;

import java.util.ArrayList;

import static org.junit.Assert.assertTrue;

public class TestSortedBucket {

    //Declaration of the test objects

    BucketList<String> bucketList;
    ArrayList<Entry<String>> everyone;
    Entry<String> jessica, veronica, cathy, barley, angston, angelina;

    // Instantiation of the objects */

    @Before
    public void initialize() {
        everyone = new ArrayList<>();
        jessica = new Entry<>(94 , "Jessica");
        veronica = new Entry<>(93 , "veronica");
        cathy = new Entry<>(68 , "cathy");
        barley = new Entry<>(72 , "Barley");
        angston = new Entry<>(84 , "angston");
        angelina = new Entry<>(98 , "angelina");

        everyone.add(jessica);
        everyone.add(veronica);
        everyone.add(cathy);
        everyone.add(barley);
        everyone.add(angston);
        everyone.add(angelina);

    }

    @Test
    public void test1() {
        // BucketList constructor takes (min,max,numBuckets)
        bucketList = new BucketList<String>(0,100,6);
        bucketList.addAll(everyone);
        ArrayList<Entry<String>> list4 = new ArrayList<>();
        list4.add(cathy);
        list4.add(barley);
        list4.add(angston);
        ArrayList<Entry<String>> list5 = new ArrayList<>();
        list5.add(veronica);
        list5.add(jessica);
        list5.add(angelina);
        assertTrue(bucketList.getBucket(4).equals(list4)
                && bucketList.getBucket(5).equals(list5)
                && bucketList.getBucket(0).isEmpty()
                && bucketList.getBucket(1).isEmpty()
                && bucketList.getBucket(2).isEmpty()
                && bucketList.getBucket(3).isEmpty());
    }

    @Test
    public void test2() {
        // BucketList constructor takes (min,max,numBuckets)
        bucketList = new BucketList<>(0,100,5);
        bucketList.addAll(everyone);

        ArrayList<Entry<String>> list3 = new ArrayList<>();

        list3.add(cathy);
        list3.add(barley);

        ArrayList<Entry<String>> list4 = new ArrayList<>();
        list4.add(angston);
        list4.add(veronica);
        list4.add(jessica);
        list4.add(angelina);

        assertTrue(bucketList.getBucket(0).isEmpty()
                && bucketList.getBucket(1).isEmpty()
                && bucketList.getBucket(2).isEmpty()
                && bucketList.getBucket(3).equals(list3)
                && bucketList.getBucket(4).equals(list4)
        );
    }

    @Test
    public void test3() {
        // BucketList constructor takes (min,max,numBuckets)
        bucketList = new BucketList<>(0,100,4);
        bucketList.addAll(everyone);

        ArrayList<Entry<String>> list2 = new ArrayList<>();

        list2.add(cathy);
        list2.add(barley);

        ArrayList<Entry<String>> list3 = new ArrayList<>();
        list3.add(angston);
        list3.add(veronica);
        list3.add(jessica);
        list3.add(angelina);
        assertTrue(bucketList.getBucket(0).isEmpty()
                && bucketList.getBucket(1).isEmpty()
                && bucketList.getBucket(2).equals(list2)
                && bucketList.getBucket(3).equals(list3)
        );
    }

    @Test
    public void emptyTest() {
        bucketList = new BucketList<String>(-50,50,6);
        assertTrue(bucketList.getNumberOfBuckets()==6 && bucketList.getSortedOrder().size()==0);
    }

    @Test
    public void perfectEmployeeTest() {

        bucketList = new BucketList<>(0,100,10);
        bucketList.add(new Entry<>(100,"perfect"));
        assertTrue(bucketList.getBucket(9).size()==1);
    }

    @Test
    public void outOfBoundsTest1() {
        bucketList = new BucketList<>(0,100,10);
        bucketList.add(new Entry<>(110,"superPerfect"));
        assertTrue(bucketList.getBucket(9).size()==1);
    }

    @Test
    public void outOfBoundsTest2() {
        bucketList = new BucketList<String>(0,100,10);
        bucketList.add(new Entry<>(-110,"notSoPerfect"));
        assertTrue(bucketList.getBucket(0).size()==1);
    }

    //tests that the list is in sorted order
    @Test
    public void sortedBucketTest() {
        bucketList = new BucketList<>(0,100,10);
        bucketList.addAll(everyone);

        Entry<String> bob = new Entry<>(108, "Bob");
        Entry<String> john = new Entry<>(-18, "John");

        bucketList.add(bob);
        bucketList.add(john);

        ArrayList<Entry<String>> sorted = new ArrayList<>();

        sorted.add(john);
        sorted.add(cathy);
        sorted.add(barley);
        sorted.add(angston);
        sorted.add(veronica);
        sorted.add(jessica);
        sorted.add(angelina);
        sorted.add(bob);

        assertTrue(bucketList.getSortedOrder().equals(sorted));

    }

}
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Program Output :

BucketList - MainClass.java BucketList src MainClass main Main 1 BucketListADT.java X SortedBucket.java 1 SortedBucketADT.java Entry.java TestSortedBucket.java X MainClass.java BucketList.java X public class MainClass { Project - BucketList/IdeaProjects/Bucket List ► idea ► out public static void main(String[] args) { src Structure BucketList I BucketListADT Entry MainClass SortedBucket SortedBucketADT TestSortedBucket BucketList.iml Milli External Libraries Scratches and Consoles BucketList<String> b = new BucketList<String>( min: 0, max: 100, n: 6); b.add(new Entry<String>( k: -10 , v: "Bob")); System.out.println(b); b.add(new Entry<String>( k: 90 , v: "John")); System.out.println(b); b.add(new Entry<String>( k: 83, v: "Vennisa")); System.out.println(b); b.add(new Entry<String>( k: 78, v: "Catherine")); System.out.println(b); b.add(new Entry<String>( k: 62, v: "Barley")); System.out.println(b); b.add(new Entry<String>( k: 74 , v: "Angston")); System.out.println(b); b.add(new Entry<String>( k: 88, v: "Andrew")); System.out.println(b); b.add(new Entry<String>( k: 104, v: "Cathy")); System.out.println(b); // add N more random students int N = 10; ArrayList<Entry<String>> allEmployee = new ArrayList<Entry<String>>(); for (int i=1; i<n; i++) { Entry<String> e = new Entry<String>((int) (45+Math.random()*50), v: "emp"+i); allEmployee.add(e); } // add the whole class to the buckets b.addAll(allEmployee); Run: 1 Main [[Bob=-10] [] [] [] [] []] [[Bob=-10] [] [] [] [] [John=90]] [[Bob=-10] [] [] [] [Vennisa=83] [John=90]] [[Bob=-10] [] [] [] [Catherine=78, Vennisa=83] [John=90]] [[Bob=-10] [] [] [Barley=62] (Catherine=78, Vennisa=83] [John=90]] [[Bob=-10] [] [] [Barley=62] [Angston=74, Catherine=78, Vennisa=83] [John=90]] [[Bob=-10] [] [] [Barley=62] [Angston=74, Catherine=78, Vennisa=83] [Andrew=88, John=90]] [[Bob=-10] [] [] [Barley=62] [Angston=74, Catherine=78, Vennisa=83] [Andrew=88, John=90, Cathy=104]] [[Bob--10] [] [emp1=48, emp9=49] (emp=52, emp6=53, Barley=62, emp2=63] [Angston=74, emp7=75, emp10=77, Catherine=78, emp4=81, Vennisa=83] [emp8=87, Andrew=88, John=90, emp3=94, Cathy=104]] [Bob=-10, emp1=48, emp9=49, emp5=52, emp6=53, Barley=62, emp2=63, Angston=74, emp7=75, emp10=77, Catherine=78, emp4=81, Vennisa=83, emp8=87, Andrew=88, John=90, emp3=94, Cathy=104] i Process finished with exit code 0 E Q: Messages Terminal 6: TODO 4: Run 38 occurrences changed Event Log 22:36 LF UTF-8 4 spaces 1 0