CISC 3130 — Lab #1

CISC 3130
Data Structures
Lab #2
An Improved Set Container

How to Develop and Submit your Labs

Make sure you read the sections in the above on how to interpret CodeLab string comparison feedback

Lab 2.1 — A Resizeable, Generic Set Container

Overview

This is the lecture #2 equivalent of the lecture #1 lab. That is, in lecture #1 we introduced a simple Vector class and the lab had you implement a Set container with essentially the same constraints (fixed element type, dynamic fixed-size capacity)i; and in this lab (#2) you are to code a Set container that has the same properties as the last version (Version 5) of Vector, i.e., resizeable and generic (there is no exception handling for Set.

I would proceed somewhat differently than my recommendation for the Lab #1. There I suggested starting off by copying the Vector class and making modifications to it (e.g., removing get and set) to bring it in line with Set. For this lab I would recommend starting off with your working Set class of Lab #1, and then merging in the resining code (i.e., checkCapacity), and once that is working, making it generic. Again. In other words, I'm still suggesting you do one facility at a time (there is no exception handling in this version of Set since the only exception in the previous version was overflow, which no longer applies in the context of ).

Details

  • You need to add a checkCapacity method.
  • You need to introduce a type parameter
You should also create an app with the following output: 
=== Basic Functionality ===

--- Creating a Set and printing it and its initial stats ---
{} (0/10)

--- Loading it up to capacity with add ---
Adding 0 -> {0} (1/10)
Adding 1 -> {0, 10} (2/10)
Adding 2 -> {0, 10, 20} (3/10)
Adding 3 -> {0, 10, 20, 30} (4/10)
Adding 4 -> {0, 10, 20, 30, 40} (5/10)
Adding 5 -> {0, 10, 20, 30, 40, 50} (6/10)
Adding 6 -> {0, 10, 20, 30, 40, 50, 60} (7/10)
Adding 7 -> {0, 10, 20, 30, 40, 50, 60, 70} (8/10)
Adding 8 -> {0, 10, 20, 30, 40, 50, 60, 70, 80} (9/10)
Adding 9 -> {0, 10, 20, 30, 40, 50, 60, 70, 80, 90} (10/10)

--- Loading it up with the same elements  ---
Adding 0 -> {0, 10, 20, 30, 40, 50, 60, 70, 80, 90} (10/10)
Adding 1 -> {0, 10, 20, 30, 40, 50, 60, 70, 80, 90} (10/10)
Adding 2 -> {0, 10, 20, 30, 40, 50, 60, 70, 80, 90} (10/10)
Adding 3 -> {0, 10, 20, 30, 40, 50, 60, 70, 80, 90} (10/10)
Adding 4 -> {0, 10, 20, 30, 40, 50, 60, 70, 80, 90} (10/10)
Adding 5 -> {0, 10, 20, 30, 40, 50, 60, 70, 80, 90} (10/10)
Adding 6 -> {0, 10, 20, 30, 40, 50, 60, 70, 80, 90} (10/10)
Adding 7 -> {0, 10, 20, 30, 40, 50, 60, 70, 80, 90} (10/10)
Adding 8 -> {0, 10, 20, 30, 40, 50, 60, 70, 80, 90} (10/10)
Adding 9 -> {0, 10, 20, 30, 40, 50, 60, 70, 80, 90} (10/10)

--- Membership checking  ---
set does not contain -50
set does not contain -40
set does not contain -30
set does not contain -20
set does not contain -10
set contains 0
set contains 10
set contains 20
set contains 30
set contains 40
set contains 50
set contains 60
set contains 70
set contains 80
set contains 90
set does not contain 100
set does not contain 110
set does not contain 120
set does not contain 130
set does not contain 140

=== Capacity Management ===

--- Creating a Set<Double> and loading it up with 1,000 elements ---
{0.0} (1/10)
{0.0, 1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, 10.0} (11/20)
{0.0, 1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, 10.0, 11.0, 12.0, 13.0, 14.0, 15.0, 16.0, 17.0, 18.0, 19.0, 20.0} (21/40)
(41/80) ... resized
(81/160) ... resized
(161/320) ... resized
(321/640) ... resized
(641/1280) ... resized
(1000/1280)

=== Generics ===

--- Set<Double> ---
{0.0, 1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0}

--- Set<String> ---
{Str0, Str1, Str2, Str3, Str4, Str5, Str6}

--- Set<Set<Integer>> ---
{{}, {0}, {0, 1}, {0, 1, 2}, {0, 1, 2, 3}}

=== Element Order ===

--- Adding 10 random values to a Set<Integer> using a Random object with seed=12345 ---
adding 51 -> {51}
adding 80 -> {51, 80}
adding 41 -> {51, 80, 41}
adding 28 -> {51, 80, 41, 28}
adding 55 -> {51, 80, 41, 28, 55}
adding 84 -> {51, 80, 41, 28, 55, 84}
adding 75 -> {51, 80, 41, 28, 55, 84, 75}
adding 2 -> {51, 80, 41, 28, 55, 84, 75, 2}
adding 1 -> {51, 80, 41, 28, 55, 84, 75, 2, 1}
adding 89 -> {51, 80, 41, 28, 55, 84, 75, 2, 1, 89}
{51, 80, 41, 28, 55, 84, 75, 2, 1, 89}
Notes
  • Again, the challenge is to look at the output and come up with the code that generates it
    • Look at the VectorApp at the end of Lecture 2; that's what I started from
    • Also, you might consider copying my app structure, i.e., the use if methods for each functionality: capacity management, generics, etc
  • Note, there is no exception handling section: the Set of Lab #1 only had overflow, since there was no getset there was no bounds-checking exceptions. Now that the container is resizeable, the overflow exception goes away as well.
  • As before, the demo illustrates the semantics of a set (in contrast to those of a vector); in particular, the lack of duplicates and the membership (contains) properties.
  • An 'Element Order' section has been added; the reason will become more clear in the next two exercises of Lab 2, as well as in our discussions of set implementations in the JFC.
    • Note the specification of the see to be used in the constructor of the Random object; as mentioned in class, this is to ensure that the values generated match those generated by CodeLab so your output will match.
    • Please restrict the generated random numbers to the range 0 … 99
  • Note the ellipsized versions (i.e., {1, 2 ... 9, 10}) of the set (when it grew too large) is also gone. Without a get method, there is currently no way to go through the elements of the set. We will address this eventually.

Codelab Notes

Lab 2.1 has been split into 2.1.1 and 2.1.2 for the purposes of submitting to CodeLab. Lab 2.1.1 is the Set class, while 2.1.2 is the SetApp. You should develop both in IntelliJ first and then submit them separately in CodeLab. (The rationale is to have one working class provided to you, hopefully this should make any errors easier to detect and fix).
Takeaways
  • Like Lab 1, this exercise is also in close correspondence to the Vector class of the lecture notes, but it is also very similar to the Set container of Lab 1.
    • The idea THIS time is to start from Lab 1's Set and bring in the relvant code from Lecture 2's Vector.
    • Again, this is a chance for you to practice your IDE skills; copying the project of the previous lab to a new one and making modifications
  • The end result is a container class that is just about as close to proeduction-quality as we can approximate at this level.

Lab 2.2 — Working with JFC's HashSet

The basic idea of this and Lab 2.3 is to replicate app of 2.1 but using the set containers of the JFC: HashSet (Lab 2.2) and TreeSet (Lab 2.3). The spec for each of these two labs is nothing more than the output of the app. Please make sure you read the notes after each output to see what is expected.

Here is the output of Lab 2.2: 

=== Basic Functionality ===

--- Creating a HashSet<Integer> and printing it and its initial stats ---
[] (0)

--- Loading it up to 10 with add ---
Adding 0 -> [0] (1)
Adding 1 -> [0, 10] (2)
Adding 2 -> [0, 20, 10] (3)
Adding 3 -> [0, 20, 10, 30] (4)
Adding 4 -> [0, 20, 40, 10, 30] (5)
Adding 5 -> [0, 50, 20, 40, 10, 30] (6)
Adding 6 -> [0, 50, 20, 40, 10, 60, 30] (7)
Adding 7 -> [0, 50, 20, 70, 40, 10, 60, 30] (8)
Adding 8 -> [0, 80, 50, 20, 70, 40, 10, 60, 30] (9)
Adding 9 -> [0, 80, 50, 20, 70, 40, 10, 90, 60, 30] (10)

--- Loading it up with the same elements  ---
Adding 0 -> [0, 80, 50, 20, 70, 40, 10, 90, 60, 30] (10)
Adding 1 -> [0, 80, 50, 20, 70, 40, 10, 90, 60, 30] (10)
Adding 2 -> [0, 80, 50, 20, 70, 40, 10, 90, 60, 30] (10)
Adding 3 -> [0, 80, 50, 20, 70, 40, 10, 90, 60, 30] (10)
Adding 4 -> [0, 80, 50, 20, 70, 40, 10, 90, 60, 30] (10)
Adding 5 -> [0, 80, 50, 20, 70, 40, 10, 90, 60, 30] (10)
Adding 6 -> [0, 80, 50, 20, 70, 40, 10, 90, 60, 30] (10)
Adding 7 -> [0, 80, 50, 20, 70, 40, 10, 90, 60, 30] (10)
Adding 8 -> [0, 80, 50, 20, 70, 40, 10, 90, 60, 30] (10)
Adding 9 -> [0, 80, 50, 20, 70, 40, 10, 90, 60, 30] (10)

--- Membership checking  ---
set does not contain -50
set does not contain -40
set does not contain -30
set does not contain -20
set does not contain -10
set contains 0
set contains 10
set contains 20
set contains 30
set contains 40
set contains 50
set contains 60
set contains 70
set contains 80
set contains 90
set does not contain 100
set does not contain 110
set does not contain 120
set does not contain 130
set does not contain 140

=== Generics ===

--- HashSet<Double> ---
[0.0, 1.0, 2.0, 4.0, 8.0, 9.0, 5.0, 3.0, 6.0, 7.0]

--- HashSet<String> ---
[Str6, Str5, Str4, Str3, Str2, Str1, Str0]

--- HashSet<HashSet<Integer>> ---
[[], [0], [0, 1], [0, 1, 2], [0, 1, 2, 3]]

=== Element Order ===

--- Adding 10 random values to a HashSet<Integer> using a Random object with seed=12345 ---
adding 51 -> [51]
adding 80 -> [80, 51]
adding 41 -> [80, 51, 41]
adding 28 -> [80, 51, 41, 28]
adding 55 -> [80, 51, 55, 41, 28]
adding 84 -> [80, 51, 84, 55, 41, 28]
adding 75 -> [80, 51, 84, 55, 41, 75, 28]
adding 2 -> [80, 2, 51, 84, 55, 41, 75, 28]
adding 1 -> [80, 1, 2, 51, 84, 55, 41, 75, 28]
adding 89 -> [80, 1, 2, 51, 84, 55, 41, 89, 75, 28]
[80, 1, 2, 51, 84, 55, 41, 89, 75, 28]
Notes
  • Make sure you rename the app class to HashSetApp (CodeLab will probably reject it itherwise anyway)
  • Note there's no capacity management; you are using JFC's HashSet which — while it does have a capacity qconstructor, does not provide any capacity information to the user, so there's nothing for us to see (as opposed to our Set where I've requested you provide a getCapacity method).
  • Notice the order of the elements printed in the 'Element Order' section; we'll have more to say on that
    • You can also notice the strange order in the other HashSet printed by the app.
Takeaways
  • Labs 2.2 and 2.3 bring us into the JCF world and illustrate how the first two lectures translate to 'real' code.
  • One of the main points of these labs is the portion of the app that focuses on the order of the elements in the container; this is a 'symptom' of the underlying container and the corresponding reason for the different implementations.

Lab 2.3 — Working with JFC's TreeSet

Same idea as Lab 2.2, except using JFC's TreeSet 
=== Basic Functionality ===

--- Creating a TreeSet<Integer> and printing it and its initial stats ---
[] (0)

--- Loading it up to 10 with add ---
Adding 0 -> [0] (1)
Adding 1 -> [0, 10] (2)
Adding 2 -> [0, 10, 20] (3)
Adding 3 -> [0, 10, 20, 30] (4)
Adding 4 -> [0, 10, 20, 30, 40] (5)
Adding 5 -> [0, 10, 20, 30, 40, 50] (6)
Adding 6 -> [0, 10, 20, 30, 40, 50, 60] (7)
Adding 7 -> [0, 10, 20, 30, 40, 50, 60, 70] (8)
Adding 8 -> [0, 10, 20, 30, 40, 50, 60, 70, 80] (9)
Adding 9 -> [0, 10, 20, 30, 40, 50, 60, 70, 80, 90] (10)

--- Loading it up with the same elements  ---
Adding 0 -> [0, 10, 20, 30, 40, 50, 60, 70, 80, 90] (10)
Adding 1 -> [0, 10, 20, 30, 40, 50, 60, 70, 80, 90] (10)
Adding 2 -> [0, 10, 20, 30, 40, 50, 60, 70, 80, 90] (10)
Adding 3 -> [0, 10, 20, 30, 40, 50, 60, 70, 80, 90] (10)
Adding 4 -> [0, 10, 20, 30, 40, 50, 60, 70, 80, 90] (10)
Adding 5 -> [0, 10, 20, 30, 40, 50, 60, 70, 80, 90] (10)
Adding 6 -> [0, 10, 20, 30, 40, 50, 60, 70, 80, 90] (10)
Adding 7 -> [0, 10, 20, 30, 40, 50, 60, 70, 80, 90] (10)
Adding 8 -> [0, 10, 20, 30, 40, 50, 60, 70, 80, 90] (10)
Adding 9 -> [0, 10, 20, 30, 40, 50, 60, 70, 80, 90] (10)

--- Membership checking  ---
set does not contain -50
set does not contain -40
set does not contain -30
set does not contain -20
set does not contain -10
set contains 0
set contains 10
set contains 20
set contains 30
set contains 40
set contains 50
set contains 60
set contains 70
set contains 80
set contains 90
set does not contain 100
set does not contain 110
set does not contain 120
set does not contain 130
set does not contain 140

=== Generics ===

--- TreeSet<Double> ---
[0.0, 1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0]

--- TreeSet<String> ---
[Str0, Str1, Str2, Str3, Str4, Str5, Str6]

=== Element Order ===

--- Adding 10 random values to A TreeSet<Integer> using a Random object with seed=12345 ---
adding 51 -> [51]
adding 80 -> [51, 80]
adding 41 -> [41, 51, 80]
adding 28 -> [28, 41, 51, 80]
adding 55 -> [28, 41, 51, 55, 80]
adding 84 -> [28, 41, 51, 55, 80, 84]
adding 75 -> [28, 41, 51, 55, 75, 80, 84]
adding 2 -> [2, 28, 41, 51, 55, 75, 80, 84]
adding 1 -> [1, 2, 28, 41, 51, 55, 75, 80, 84]
adding 89 -> [1, 2, 28, 41, 51, 55, 75, 80, 84, 89]
[1, 2, 28, 41, 51, 55, 75, 80, 84, 89]
Notes
  • Again, please rename the app class
  • Again, there no capacity management; JFC's TreeSet doesn't even have a capacity constructor.
  • Note that there is no TreeSet<TreeSet<Integer>>; and again, we'll explain while eventually
  • Again, notice the order of the elements printed in the 'Element Order' section; we'll have more to say on that
Takeaways
  • Like Lab 1, this exercise is also in close correspondence to the Vector class of the lecture notes, but it is also very similar to the Set container of Lab 1.
    • The idea THIS time is to start from Lab 1's Set and bring in the relvant code from Lecture 2's Vector.
    • Again, this is a chance for you to practice your IDE skills; copying the project of the previous lab to a new one and making modifications
  • The end result is a container class that is just about as close to proeduction-quality as we can approximate at this level.
  • Labs 2.2 and 2.3 bring us into the JCF world and illustrate how the fiurst two lectures translate to 'real' code.