# 代写Data Structures|Project代做|作业Racket|Data Structure|Java – Union of Intervals

### CPS 305 project One: Union of Intervals

Your code in IntervalUnion. java must be your own work. You are allowed to discuss the problem and solution ideas with each other on a purely theoretical level as long as no actual code is shown to other students or changes hands. The project submissions are checked

#### The Problem To Solve

##### represent unions of intervals of positive integers.

An integer interval is defined by its start and end values so that start <= end, and it contains all integers x for which start <= x <= end, start and end of the interval both being inclusive. An object that represents a union of intervals can contain any number of such individual intervals. However, inside this union, two integer intervals that either are contiguous or that overlap partially or in full are supposed to meld into a single integer interval. Between any two intervals that are part of this union, there must exist at least one integer value that is between

##### them but not part of either interval.

For example, using the canonical string representation (as defined below in the section "Required

##### "[]"

where the first instance consists of four separate intervals (1-5, 10-12, 27-27, 33-40), the second instance consists of three such intervals (4-15, 20-31, 35-42), and the third instance represents

##### an empty union that contains nothing.

The intersection of two unions of intervals contains the integers that are included in both, encoded in the same representation. For example, the intersection of the first two example

##### "[4-5,10-12,27,35-40]"

Similarly, the union of two unions of intervals contains the integers that are included in either

#### Automated Tester

##### java IntervalUnionTest SEED N M EXPECTED

where SEED is the seed to initialize the pseudorandom number generator that produces the test cases, N is the number of initial single intervals to generate as test data, M is the number of

##### operations to perform on these intervals.

If given, EXPECTED is the CRC- 32 checksum computed from the results of the operations performed by your code. If EXPECTED is not given, the tester runs in verbose mode useful for debugging during development so that you can eyeball whether the results computed by your methods are correct. If EXPECTED is given, the tester runs silently and verifies that the computed checksum of the actual results equals the expected checksum. The tester will then print only the last line whose first item is the number of milliseconds elapsed in the test. If the computed and expected checksums are different, the running time does not matter ("If my program does not have to work correctly, I can make it run in zero time", as the famous retort once put it) and is

##### defined to be 99999999 milliseconds.

An example run ( UPDATED SEP 16 ) using ten pseudorandomly created (using SEED of 98765) intervals followed by twenty operations performed on them, without giving the EXPECTED checksum, looks like this, with the instructor’s command line prompt in green followed by the

##### 202 123456789 Kokkarinen, Ilkka

When grading your submissions, the TA will use much bigger values of N and M, along with our

##### 1200 123456789 Kokkarinen, Ilkka

In the instructor’s home computer, the above test using one million operations took a total of 1200 milliseconds. This includes all the string conversions and the bookkeeping work by the test environment, especially the CRC-32 checksum calculation. However, since all this bookkeeping work adds the exact same constant offset for everybody’s running time, the resulting running

##### times can be used to rank your project submissions fairly.

(Please do note that if you wanted to cut the reported total running time in half, you need to speed up your program to be way more than twice as fast, since the bookkeeping time is the same constant regardless of the speed of your program. Even if you could make your code infinitely fast

##### by some magic, the reported running time would still not be zero.)

This programming project is graded for correctness and execution time. First, to receive any marks at all, your project must work correctly in that it passes our tests with the expected checksums. To check whether your solution is passing the automated tester, you can try out the

##### 123456 100000 500000 1376321519

Here are some outputs from the instructors’ model solution that you can compare the outputs of

##### 103 100 10000 s103n100m10000.txt

(On the Unix command line, the diff tool is your powerful little friend to find the first line where the output of your code and the model solution are different, to help you discover what your code is doing wrong.) Note also that the methods getPieceCount and contains are also part of the

##### final checksum calculation, even though their results are not printed out by the automated tester.

When grading your project submissions, the TA will use a different secret SEED and its corresponding CHECKSUM to verify that your project submission is working correctly. The values used for N and M will be 100000 and 500000. Your code has a time limit of thirty seconds to complete that test. If the execution of the automated tester has not terminated by that time, your project code is considered to be too slow (or even worse, has a bug that causes your code to get

##### stuck in an infinite loop) and will be rejected with a zero mark.

The projects that pass this first hurdle of working correctly are sorted based on their running time. This list is then reasonably divided into six portions based on the general clustering of these running times. The projects in these six portions will receive a project mark of 10, 9, 8, 7, 6 and 5

##### points, respectively.

As an added incentive and reward, for whatever it is worth, prof. Kokkarinen will write a letter of recommendation to the student whose project submission is the fastest. The winner is also entitled to refer to him- or herself with the title of "The Fastest Gun East of Mississauga" for the duration of the Fall 2018 term. In case that several project submissions are too close to call, this

#### Required Methods

Your submission must consist of exactly one source code file IntervalUnion.java and no other files whatsoever. (Defining nested classes inside the class IntervalUnion is acceptable.) Your code is freely allowed to use all Data Structures and algorithms available in the Java 8 standard

library so that you don’t need to reinvent any of these wheels. Any attempt to interfere with the behaviour and results of the automated tester is considered cheating and will be punished by the

##### forfeiture of all project marks in this course.

Your class must have the following exact methods so that the tester can compile and run. How you choose to implement these methods, and whatever private data fields you choose to store whatever information you use to encode and represent a union of intervals, is entirely up to you.

##### public static IntervalUnion create(int start, int end)

A static factory method to create and return an IntervalUnion object that contains a single interval from start to end. The automated tester does not assume the existence of any kind of public constructor, but will always call this factory method whenever it needs to create a new IntervalUnion object. (Since the IntervalUnion class is designed to be immutable, this method could theoretically return an existing object to save memory, if a suitable object with the

##### @Override public String toString()

Returns the string representation for the IntervalUnion object this. To allow automated testing, this string representation must follow the exact format of listing the intervals in sorted order between square b racket character pair so that the start and end values of each interval are separated by a minus sign. If the start and end values are equal, only one number is used. The individual intervals contained in the union must be separated by single commas, with no silly trailing comma allowed. Whitespace and other extraneous characters should not be used

##### @Override public boolean equals(Object other)

The equality comparison between two Java objects. An IntervalUnion object can only be equal to other IntervalUnion objects and nothing else, and two interval unions are considered equal if and only if they contain the exact same integer intervals. It is essential that you implement this method to do this instead of using the automatically inherited version that merely compares the two objects for memory address equality, since this method is implicitly part of the checksum

computation in the automated tester, in the part where the IntervalUnion objects are added

##### @Override public int hashCode()

Returns an integer hash code for the IntervalUnion object this. You can compute this hash code any way you want, as long as it satisfies the semantic requirement expected by the Java language that a.hashCode() == b.hashCode() holds whenever a.equals(b), where a and b can be any IntervalUnion objects. Try to make this method spread the hash codes all over the possible integer values to make the hash table Data structure run faster, since the automated tester will use both methods hashCode and equals as it builds up a HashSet

##### public boolean contains(int x)

Checks whether the IntervalUnion object this contains the integer x. Note that the automated tester calls this method as part of checksum computation, but the results do not show up in the

##### public IntervalUnion union(IntervalUnion other)

Computes the union of this and other, returning the result as an IntervalUnion object. Note

##### public IntervalUnion intersection(IntervalUnion other)

Computes the intersection of this and other, returning the result as an IntervalUnion object.

##### public int getPieceCount()

Returns the number of disjoint interval pieces contained in the IntervalUnion object this. Note that the automated tester calls this method as part of checksum computation, but the results