1 Mikagar

Unchecked Assignment Java Util Arraylist Contains

Programming Assignment 2 Checklist: Randomized Queues and Deques

Frequently Asked Questions

Should I use arrays or linked lists in my implementations? In general we don't tell you how to implement your data structures—you can use arrays, linked lists, or maybe even invent your own new structure provided you abide by the specified time and space requirements.

How serious are you about not calling external library functions (other than those that are specifically permitted)? You will receive a substantial deduction. The goal of this assignment is to implement data types from first principles, using resizing arrays and linked lists—feel free to use java.util.LinkedList and java.util.ArrayList on future programming assignments. We also require you to use (instead of java.util.Scanner) because we will intercept the calls to in our testing.

Can I add extra public methods to the or APIs? Can I use different names for the methods? No, you must implement the API exactly as specified.

What does"uniformly at random" mean? If there are N items in the randomized queue, then you should choose each one with probability 1/N, up to the randomness of , independent of past decisions. You can generate a pseudo-random integer between 0 and N − 1 using .

Given an array, how can I rearrange the entries in random order? Use —it implements the Knuth shuffle discussed in lecture and runs in linear time. Note that depending on your implementation, you may not need to call this method.

Can repeated calls to sample() in a randomized queue return the same item more than once? Yes, since you are sampling without removing the item. This is also known as "sampling with replacement."

Should two iterators to the same randomized queue return the items in the same order? No, each iterator should have a different random order. This is what "independent iterators" means.

Why is it called a randomized queue if the items are not removed in FIFO? This is a common name used in queueing theory.

What should the next() method return if the iterator has no more items? According to the API for java.util.Iterator, it should throw a .

What should my deque (or randomized queue) iterator do if the deque (or randomized queue) is structurally modified at any time after the iterator is created (but before it is done iterating)? You don't need to worry about this in your solution. An industrial-strength solution (used in the Java libraries) is to make the iterator fail-fast: throw a as soon as this is detected.

Why does the following code lead to a compile-time error when is a generic type parameter?

Item[] a = new Item[1];
Java prohibits the creation of arrays of generic types. See the Q+A in Section 1.3 for a brief discussion. Instead, use a cast.
Item[] a = (Item[]) new Object[1];
Unfortunately, this leads to an unavoidable compiler warning.

The compiler says that my program uses unchecked or unsafe operations and to recompile with -Xlint:unchecked for details. Usually this means you did a potentially unsafe cast. When implementing a generic stack with an array, this is unavoidable since Java does not allow generic array creation. For example, the compiler outputs the following warning with ResizingArrayStack.java:

% javac ResizingArrayStack.java Note: ResizingArrayStack.java uses unchecked or unsafe operations. Note: Recompile with -Xlint:unchecked for details. % javac -Xlint:unchecked ResizingArrayStack.java ResizingArrayStack.java:25: warning: [unchecked] unchecked cast found : java.lang.Object[] required: Item[] a = (Item[]) new Object[2]; ^ ResizingArrayStack.java:36: warning: [unchecked] unchecked cast found : java.lang.Object[] required: Item[] Item[] temp = (Item[]) new Object[capacity]; ^ 2 warnings

You should not receive any other compiler warnings on this assignment (and you should not receive any compiler warnings on any other assignment).

Checkstyle complains that my nested class' instance variables must be private and have accessor methods that are not private. Do I need to make them private? No, but there's no harm in doing so. The access modifier of a nested class' instance variable is irrelevant—regardless of its access modifier, it can be accessed anywhere in the file. (Of course, the enclosing class' instance variables should be private.)

Can a nested class have a constructor? Yes.

What assumptions can I make about the input to ? Standard input can contain any sequence of strings. You may assume that there is one integer command-line argument k and it is between 0 and the number of strings on standard input.

Will I lose points for loitering? Yes. See p. 137 of the textbook for a discussion of loitering. Loitering is maintaining a useless reference to an object that could otherwise be garbage collected.

Develop unit tests as you write each method and constructor to allow for testing. As an example for , you know that if you call with the numbers 1 through N in ascending order, then call N times, you should see the numbers 1 through N in ascending order. As soon as you have those two methods written, you can write a unit test for these methods. In addition use randomized unit tests (which we employ heavily in our correctness testing).

Test intermixed sequence of operations. Sometimes you want to test two methods in isolation, as above. But, you also need to make sure that all of the methods work together with one another.

Test your iterator. And make sure to test that multiple iterators can be used simultaneously. You can test this with a nested foreach loop. The iterators should operate independently of one another.

Make sure to test what happens when your data structures are emptied. One very common bug is for something to go wrong when your data structure goes from non-empty to empty and then back to non-empty. Make sure to include this in your tests.

Don't rely on our automated tests for debugging. As suggested above, write your own unit tests; it's good practice.

These are purely suggestions for how you might make progress. You do not have to follow these steps. These same steps apply to each of the two data types that you will be implementing.

  1. Getting started. Review Section 1.3 of the textbook for generic stacks and queues with iterators. If you adapt our code, you must include a citation to the original source from either the textbook or the booksite.
  2. Make sure you understand the performance requirements for both and . They are summarized in the table below. Every detail in these performance requirements is important. Do not proceed until you understand them.
    DequeRandomized Queue
    Non-iterator operationsConstant worst-case timeConstant amortized time
    Iterator constructorConstant worst-case timelinear in current # of items
    Other iterator operationsConstant worst-case timeConstant worst-case time
    Non-iterator memory useLinear in current # of itemsLinear in current # of items
    Memory per iteratorConstantLinear in current # of items
  3. Decide whether you want to use an array, linked list, or your own data structure. This choice should be made based on the performance requirements discussed above. You may make different choices for and . Make sure that your memory use is linear in the current number of items, as opposed to the greatest number of items that has ever been in the data structure since its instantiation. If you're using a resizing array, you must resize the array when it becomes sufficiently empty. You must also take care to avoid loitering anytime you remove an item.
  4. Use our example programs as a guide when implementing your methods. There are many new ideas in this programming assignment, including resizing arrays, linked lists, iterators, the foreach keyword, and generics. If you are not familiar with these topics, our example code should make things much easier. ResizingArrayStack.java uses a resizing array; LinkedStack.java uses a singly-linked list. Both examples use iterators, foreach, and generics.

A video is provided for those wishing additional assistance. Be forewarned that video was made in early 2014 and is somewhat out of date. For example the API has changed.

CollectionIncompatibleType
Incompatible type as argument to Object-accepting Java collections method

Severity
ERROR
Has Fix?
REQUIRES_HUMAN_ATTENTION

The problem

Querying a collection for an element it cannot possibly contain is almost certainly a bug.

In a generic collection type, query methods such as and accept a parameter that identifies a potential element to look for in that collection. This check reports cases where this element cannot be present because its type and the collection’s generic element type are “incompatible.” A typical example:

This code looks reasonable, but there’s a problem: The contains instances, but the argument to is an . Because no instance can be of type and of type at the same time, the check always fails. This is clearly not what the developer intended.

Why does the collection API permit this kind of mistake? Why not declare the method as ? After all, that is what the collections API does for methods that store an element in the collection: They require that passed type be strictly assignable to the collection’s element type. For example:

The code above rightly won’t compile, because might be a (for example) , and adding an value would corrupt it.

But this restriction is necessary only for methods that insert elements. Methods that only query or remove elements cannot corrupt the collection:

In this case, the might be contained in , and should be removed if it is, but if is a , no harm is done.

We’d like to define in a way that rejects the bad call but permits the good one. But Java’s type system is not powerful enough. Our solution is static analysis.

The specific restriction we would like to express for the two types is not assignability, but “compatibility”. Informally, we mean that it must at least be possible for some instance to be of both types. Formally, we require that a “casting conversion” exist between the types as defined by [JLS 5.5.1] (https://docs.oracle.com/javase/specs/jls/se7/html/jls-5.html#jls-5.5.1).

The result is that the method can be defined as , permitting the “good” call above, but that Error Prone will give errors for incompatible arguments, preventing the “bad.”

We might say: Sure, a buggy call can’t corrupt a collection. And sure, someone might want to pass an reference that happens to contain an . But isn’t that a low standard for an API? We don’t normally write code that way:

Such code would invite bugs. To avoid that, we require a . Users who have an reference that might be a can test and cast. So why not require the same thing in the collections API?

Of course, we can’t really change the API of . But if we were designing a similar API, what would we do – require or accept any ?

The burden of proof falls on accepting , since doing so permits buggy code. And we’re not going to settle for “it occasionally saves users a cast.”

The main reason to accept is to permit a fast, type-safe implementation.

( is actually just one example of the general problem, which arises with many uses of wildcards wildcards. Once you’ve read the following, consider the problem of implementing without . Then consider how the problem would exist even if the signature were . The problem is at least “solvable” by changing the signature to , but that signature may reject useful calls.)

Here’s how: necessarily accepts a plain . It can test whether that is a , but it can’t know the element type it was originally declared with. In short, has to operate on a .

If were to require an , would be in trouble because it doesn’t know what is. In particular, it wouldn’t be able to call for any of its elements.

It would have only two options: It could copy the entire other into a , or it could perform an unchecked cast. Copying is wasteful, so in practice, would need an unchecked cast. This is probably acceptable, but we might feel strange for defining an API that can be implemented only by performing unchecked casts.

Does a cleaner implementation (and occasional convenience to callers) outweigh the bugs that accepting enables? That’s a tough question. The good news is that this Error Prone check gives you some of the best of both worlds.

It is technically possible for a to contain a element, but only if an warning was earlier ignored or improperly suppressed. Such practice should never be treated as acceptable, so it makes no practical difference to our arguments above.

Suppression

Suppress false positives by adding the suppression annotation to the enclosing element.


Positive examples

CollectionIncompatibleTypePositiveCases.java

Negative examples

CollectionIncompatibleTypeNegativeCases.java

Leave a Comment

(0 Comments)

Your email address will not be published. Required fields are marked *