Tom Brodhead

Greenhorn
+ Follow
since Jan 02, 2011
Cows and Likes
Cows
Total received
0
In last 30 days
0
Total given
0
Likes
Total received
0
Received in last 30 days
0
Total given
0
Given in last 30 days
0
Forums and Threads
Scavenger Hunt
expand Ranch Hand Scavenger Hunt
expand Greenhorn Scavenger Hunt

Recent posts by Tom Brodhead

With apologies for the length of the thing, here is the assignment. As you'll see, it only talks *around* the things that need to be done, leaving it as a puzzle of sorts to figure out what precisely is to be done. I'm constrained to using the classes posted above. The SList and DList have insertFront() and insertBack() methods, but no more. My guess is that the Collections.sort() method, which is method made possible by implementing Comparable, is the means to sort the resulting Set object as items are added to it, but that must be done as the items are added.

And, yes, there's the whole issue of non-duplicating items, but I'll cross that bridge once I've found the solution to the first and fundamental problem to this exercise.

Here's the assignment text--let me know if you have an "aha!" moment while reading it; that's not happening to me as I re-read it:

===============

Your main assignment is to implement a Set ADT in Set.java. Your Set class
must use a List to store the elements of the set. Your Sets should behave like
mathematical sets, which means they should not contain duplicate items. To
make set union and intersection operations run quickly, your Sets will contain
only Comparable elements, and you will keep them sorted in order from least to
greatest element. (You will want to review the Comparable interface on the
Java API Web page.)

You will need to decide on fields and implement the following methods.

public Set() // Constructs an empty Set.
public int cardinality() // Number of elements in this Set.
public void insert(Comparable c) // Insert c into this Set.
public void union(Set s) // Assign this = (this union s).
public void intersect(Set s) // Assign this = (this intersect s).
public String toString() // Express this Set as a String.

Unlike in previous assignments, each method comes with prescribed time bounds
that you must meet when your Set uses DLists (but not when it uses SLists).

For example, union() and intersect() must run in time proportional to
this.cardinality() + s.cardinality(). This means you don’t have time to make a
pass through "this" list for every element of s; that would take time
proportional to this.cardinality() * s.cardinality(). You must take advantage
of the fact that Sets are sorted to achieve this time bound. This time bound
is one reason why Sets may not store duplicate items in their Lists.

On the other hand, insert() need not run in constant time. Since each Set uses
a sorted representation, insert() may need time proportional to the cardinality
of the Set to find the right place to insert a new element, and to ensure that
the new element doesn’t duplicate an old one.

Another constraint is that union() and intersect() may NOT change the Set s.
Furthermore, intersect() may not create any new ListNodes (it only needs to
remove ListNodes from "this" List), and union() should reuse all the ListNodes
in the Set "this", creating new nodes only for elements of s that "this" List
lacks. We will deduct points for failing to meet the time bounds or failing to
obey these constraints.

Be sure to declare variables of static type List and ListNode in Set.java, not
variables of type DList, DListNode, SList, or SListNode. Set.java should be
able to switch between using DLists and using SLists by changing one
constructor call in the Set() constructor. (In fact, you can use SList to help
you debug Set if you have trouble getting DList working. But be sure to use a
DList in your final submission unless you can’t get it working.)

Do not modify List.java, ListNode.java, SList.java, or SListNode.java. Do not
modify the prototypes in Set.Java, DList.java, or DListNode.java.
11 years ago
Thanks, Matthew, although the problem is that I'm restricted to using the insertFront() method of the SList class...insert() will call it rather than implementing an original routine (this is so I can switch between a singly-linked list and doubly-linked list just be changing one line in the constructor for the Set class.) So all insertions into the SList will be at the front of the list.

My guess is that I should then be able to call the Collections.sort method on the resulting Set, but that really can only be done in the routine that instantiates a Set object...i.e. in some other Main() routine. So I'm still baffled.

~~Tom
11 years ago
According to the Java specs, compareTo() returns one of 3 integers: -1, 1, 0: -1 if the item is less than the compared item, 1 if the item is greater than the compared item, and 0 if the items are equal. Apparently, you *must* write a compareTo() method in your class if you implement the Comparable interface. This is where I'm confused on fundamentals, because I'm unclear on how I should write such a method.

I'm not sure how I'd utilize the compareTo() method to ensure a sorted Set at all times...

compareTo() is used by the Collections.sort() method, which may be used on an object of the class itself, which doesn't actually help me insure that the inserted objects are in fact sorted as they go in.

I believe that the only purpose to having compareTo() is so that Collections.sort() can do its work for you. But that doesn't help me within an object of the Set class as defined here.
11 years ago
Already the insert() method uses a Comparable as the object parameter, which surprised me because I thought we'd have to add "implements Comparable" in the Set class name to be able to use it. Eclipse does issue the warning:

Comparable is a raw type. References to generic type Comparable<T> should be parameterized

...on the line:

public void insert(Comparable c) {

But how do I ensure that the elements inserted into the Set using this method are in fact sorted? My spec says "...each Set uses a sorted representation..." and "Sets will contain only Comparable elements, and you will keep them sorted in order from least to greatest element." How would I achieve that?

~~Tom




11 years ago
Perhaps I've misstated the problem, or have misunderstood it. The spec says "Sets will contain only Comparable elements, and you will keep them sorted in order from least to greatest element. You will want to review the Comparable interface on the Java API Web page."

So the elements/nodes in each internal list of the Set should be of like type (i.e. Comparable). But if I'm implementing Comparable on the Set class itself, how would I use that to ensure that items inserted into the Set are comparable? The Set uses an internal single-linked list for storing the data (which should be switchable to a doubly-linked list just by modifying the constructor...to that end I'm instructed to declare variables List and ListNode as static type in Set, and then use the constructor to initialize them either as singly or doubly-linked lists [e.g. the SList/SListNode definition.])

So I'm very puzzled by this...it's not that I need to ensure that Set objects are Comparable one to the next, which is what the Comparable implementation would ensure, but rather that items inserted into a given Set are Comparable. But the Comparable implementation only affects the Set class itself and objects of that class. Right?

Many thanks in advance for your help,
~~Tom
11 years ago
I'm having to make an original "Set" ADT that employs single and doubly-linked lists, and one of the constraints is that the Set class must implement the Comparable interface.

The relevant code is in a different posting of mine: https://coderanch.com/t/530379/java/java/Null-Pointer-Exception-set-class

I can't get my head around the correct implementation of the compareTo() method, which is apparently required when Comparable is implemented on the Set class. The Set class initializes a list where data is stored; I don't understand how I'd implement a compareTo() on the list itself; it would seem that the compareTo() method would rightfully compare elements of the list *items* themselves, so I'm baffled at how to go about this.

Here is the code again:


11 years ago
Thanks!

I'm a bit confused about the Comparable item type that I'm using for the insert() method. Do I not have to implement Comparable in the main Set class? If so, how would I compose the compareTo() method that's apparently required for the implementation? By that I mean I don't understand how I would perform greater-than/less-than comparisons on Set objects themselves; I can only imagine comparing the items within the various SListNodes...

Many thanks
~~Tom
11 years ago
I'm receiving a null pointer exception when I try to perform a simple insertion into a list.

First, here are abbreviated listings of the 3 classes my main class references:




Here is the code I'm writing. I'm constrained to make mySet of type List, and then initialize it to type SList in the constructor of Set(). The problem is that I can't seem to use the insertFront() method except in the constructor:



Many thanks for your help,
~~Tom
11 years ago
I'm trying to construct an algorithm for iterating over sets and their subsets, so as a simple case I constructed the following scenario:



"d" stores the sets a, b, and c. When I iterate over d, I can in fact establish that d[i] is an array, but I can't retrieve its length or access it as an array for further operations.

I'm trying not to rely on built-it, higher-level facilities in Java; what am I doing wrong here, and is there a better way to store sets of sets of sets, etc.?

~~Tom
11 years ago
I'm making a generic stack using an array S[], and I don't understand why I have to initialize the S[] array in two steps. Here's my code (which works); questions and commentary below:




What I don't understand is why I can't initialize the array in one pass, like this:



Why must I create a local array (here simply named "array") and then assign S[] to the array?



If I don't do this, I receive a runtime error. But why?

~~Tom
11 years ago
I puzzled over this far longer than I should have, but it's not my nature to give up. And I've found a solution. There's one sacrifice: you *must* instantiate your class as an anonymous class; by doing so, type erasure doesn't happen. Then you may add this method to your generic class and you'll have access to the type.

If anyone can see a way to simplify this (especially with regards to getting the actual short name of the type from the longer, complete class name), I'd be very interested:



11 years ago
I'm trying to retrieve the type of a Generic object. Code like this:



...doesn't work. What is the magic formula for retrieving the type in use for a generic object off of the "this" keyword?

(I'd ideally like to construct a method that returns a string stating the type in use...Integer, float, etc.)

~~Tom
11 years ago
Wow, thanks! However, the IDE underlines the word "add" in this line:



...and produces the following error code:

The method add(T, T) in the type Addition<T> is not applicable for the arguments (Object, Object)

I'm also confused by the syntax in the add method signature:



Are you casting a GenericMatrix<T> as type <T>?

Finally, I'm not clear how I would call this method. For generic matrices A and B, this command produces a slew of error messages:



(Inserting <Integer> into the command in different locations produced no reduction of error messages.)

Somehow I feel I'm well out of my water in trying to tackle this seemingly straightforward problem, or else my luck has brought me to one of the thornier issues of Java programming. It seems like there are a lot of subtleties here that I'm not grasping...

Thanks in advance for your help!

11 years ago
Ah! Thank you! I'm closer now, but I've run into a problem in the next step, adding together two matrices.

I'm not clear on how to cast references to the arrays for arithmetic operations; the IDE complains:

The operator + is undefined for the argument type(s) java.lang.Object, java.lang.Object

How do I reference the generic type that being employed? I've tried pre-pending (T) before each array reference, but it doesn't work. Here's my code:



Also, am I right to use <?> when the type isn't known?
11 years ago
Sadly, the nice-looking suggestion:

data = (T[][])new Object[rows][columns];

...does not work; I can't run the example code with that modification without getting "Unresolved compilation problems".

Eclipse has this info about the problem with that code:

Multiple markers at this line
- Type mismatch: cannot convert from T to int
- Type safety: Unchecked cast from Object[][]
to T[][]
- Type mismatch: cannot convert from T to int


"rows" and "columns" get red squiggly underlines.

11 years ago