The Set implementations provided in the Java Collection Framework are clexible, but not best for all situations due to their relatively high memory needs for each object stored in that set. Most of the time in practical programming, sets and maps are used to remember the things that we have seen and done during the method's execution. If those things can never become unseen or undone, the remove operation does not need to be supported, except possibly in the form of the clear method to evacuate the entire data structure at once. In the terminology of data structures and algorithms, dynamic collections that allow adding new elements but do not allow later removals are called monotonic. Sometimes such structures be implemented more efciciently than the full versions that allow remove. Since each element removal decreases the entropy of the data structure, the remove operation necessarily involves physical work that makes it inherently more complex than the entropy-increasing add and the entropy-neutral contains. Further optimizations are possible when members of the set are known to be natural numbers. This turns out to be a rather common use case, given that everything inside a computer is made of integers anyway, as much as we like to otherwise pretend that the computer memory is full of strings, dictionaries and other entities that in reality are just as cictional as, say, hobbits and vampires. This becomes even more pronounced when these numbers tend to be added to the set in roughly ascend-ish order, which is often the case with many integer sequences whose rules to compute the next element depend on whether some particular integer has already been seen inside the sequence generated so far. For example, the Recama n's sequence that we met back in Lab 0(B). Membership information can in such cases be packed maximally tight so that each integer is represented as one bit stored inside a boolean[]. We will cleverly manage this boolean array as a sliding window so that the cield start tells which absolute position the relative zero index represents, and implement the methods add and contains to operate relative to this index. Good news is that you don't need to do any of that, since for both this lab and your possible future endeavours in Java, your instructor provides a brand new class NatSet whose objects represent monotonic sets of natural numbers. These NatSet objects start their lives as representing the empty set. To make the set grow (but again, never shrink), this class has the public method void add(int n) that adds n into the set, and the public method boolean contains(int n) to query whether n is a member of this set. No remove method exists in the public interface. Using the NatSet class as a tool to keep track of what numbers you have already seen during the construction, your mission is to implement another very interesting sequence of positive integers, found by your instructor in the book "Mathematical Diamonds" by Ross Honsberger. Since that book deals with mathematics instead of computer science, it uses the conventional counting of sequence positions starting from one, not from zero the way it always does for us propeller beanie hat computer programmers. The cirst element in the position k = 1 equals one. Each position k > 1 contains the smallest positive integer that so far has not appeared anywhere in the sequence and makes the sum of the cirst k elements of the sequence to be an integer multiple of k. For example, the second element for k = 2 is the smallest unseen integer that, when added to the cirst element 1, makes the total divisible by 2. The correct answer is 3, since 1 + 3 = 4 is divisible by k = 2. After [1, 3], the third element is again the smallest unseen integer that, when added to the previous elements 1 and 3, makes the total divisible by 3. Correct answer is 2, since 1 + 3 + 2 = 6, and the deuce is the smallest of all unseen numbers that work. The sequence starts its eternal journey as 1, 3, 2, 6, 8, 4, 11, 5, 14, 16, 7, 19, 21, 9, 24, 10, 27, 29, 12, 32, 13, 35, 37, 15, 40,... To practice writing virtual iterators that are not backed by any actual collections but who always produce the next element of the sequence in computational means, we implement this "diamond sequence" (named a bit unimaginatively due to the lack of further mathematical sophistication from this author's part), as a virtual iterator. Inside your BlueJ labs project, create the new class public class DiamondSequence implements Iterator with the instance methods promised by the interface Iterator: public boolean hasNext()public boolean next()Since this sequence is incinite, the method hasNext always returns true. For the computation performed inside the method next, this class should decine an int data cield k that keeps track of the position that the generation of this sequence is currently at. Then, there should also be another data cield sum that contains the sum of the elements generated so far. The type of this cield should be long, to ensure that adding up the elements of this sequence does not overclow even when we shall soon add up its cirst hundred million elements! Last, but decinitely not the least, this object needs an instance of NatSet to keep track of elements generated so far. The method next can should cirst increment k and perform some integer arithmetic to look for the smallest previously unseen n that, when added to the current sum, causes the total for the current position to be divisible by k. The JUnit test class DiamondSequenceTest will push your code hard to its limits by making it generate the cirst one hundred million elements of the diamond sequence. Within this range, all values in sequence still cit inside int variables without possibility of overclow, but their sum certainly will not cit inside an int. The sequence does grow in a modest linear pace, but it bounces above and below this baseline in a seemingly chaotic fashion that somehow always manages to cill in the gaps that it has left behind. (Every cilling of such a gap will then allow the NatSet data structure to move its sliding window into data that much more to the right...) The fact that no integer appears twice inside follows trivially from the constructions, but it is not equally obvious that every positive integer will eventually appear in some position, as it will. Furthermore, this sequence has a most curious form of self-referential structure in that whenever the k:th element of this sequence equals v, its v:th element equals k. For example, since the seventh element of this sequence equals eleven, its eleventh element must therefore equal seven! Let's all try to wrap our heads around that fact for a moment. (In discrete math terms, when this sequence is viewed as an incinite permutation of natural numbers to themselves, all cycles of this permutation have the same length of two!) The method testSelfReferentiality in the JUnit test class vericies this fact empirically for the cirst one million elements of this sequence.

This question must pass the tester:

import static org.junit.Assert.*;
	import org.junit.After;
	import org.junit.Before;
	import org.junit.Test;
	import java.util.Random;
	import java.io.*;
	import java.util.*;
	import java.util.zip.CRC32;
	public class DiamondSequenceTest {
	private void outputSequence() {
	Iterator it = new DiamondSequence();
	int[] a = new int[20];
	int[] b = new int[20];
	for(int i = 0; i < 20; i++) {
	a[i] = it.next();
	b[i] = a[i] + (i > 0 ? b[i-1]: 0);
	}
	System.out.printf("k:");
	for(int i = 0; i < 20; i++) {
	System.out.printf("%6d", i+1);
	}
	System.out.printf(" f:");
	for(int i = 0; i < 20; i++) {
	System.out.printf("%6d", a[i]);
	}
	System.out.printf(" F:");
	for(int i = 0; i < 20; i++) {
	System.out.printf("%6d", b[i]);
	}
	}
	@Test
	public void knownInitialPrefix() {
	Iterator it = new DiamondSequence();
	assertEquals(new Integer(1), it.next());
	assertEquals(new Integer(3), it.next());
	assertEquals(new Integer(2), it.next());
	assertEquals(new Integer(6), it.next());
	assertEquals(new Integer(8), it.next());
	assertEquals(new Integer(4), it.next());
	assertEquals(new Integer(11), it.next());
	assertEquals(new Integer(5), it.next());
	assertEquals(new Integer(14), it.next());
	assertEquals(new Integer(16), it.next());
	assertEquals(new Integer(7), it.next());
	assertEquals(new Integer(19), it.next());
	assertEquals(new Integer(21), it.next());
	assertEquals(new Integer(9), it.next());
	assertEquals(new Integer(24), it.next());
	}
	@Test
	public void testSelfReferentiality() {
	Map mustBe = new HashMap<>();
	Iterator it = new DiamondSequence();
	for(int k = 1; k < 1_000_000; k++) {
	int v = it.next();
	if(mustBe.containsKey(k)) {
	// Cast to long is necessary to disambiguate between assertEquals overloadings.
	assertEquals((long)v, (long)mustBe.get(k));
	mustBe.remove(k);
	}
	if(v > k) {
	mustBe.put(v, k);
	}
	}
	}
	@Test
	public void firstHundredMillion() {
	int count = 100_000_000;
	CRC32 check = new CRC32();
	Iterator it = new DiamondSequence();
	while(--count > 0) {
	int i = it.next();
	if(count % 1000 == 0) { check.update(i); }
	}
	assertEquals(2546749209L, check.getValue());
	}
	}