A set (collection of elements without duplication) as a mathematical model is de
ID: 3809546 • Letter: A
Question
A set (collection of elements without duplication) as a mathematical model is defined by the java interface below.
public interface Set
{ public boolean isEmpty(); // Is the set empty?
public void makeEmpty(); // Make this set empty.
public boolean isMember(int x); // Is x a member of this set?
public void add(int x); // Insert an element x in this set.
public void remove(int y); // Delete an element y from this set.
public void union(Set other, Set result); // result = "this" UNION other
public void intersection (Set other, Set result); // result = "this" INTERSECTION other
public void difference (Set other, Set result); // result = "this" - other
public String toString(); // Overridden toString method that returns the set description as
// a String.
public boolean equals(Object other); // Overridden equals method to check equality of two sets.
}
makeEmpty creates an empty set.
isEmpty returns true if the set is empty, false otherwise.
isMember returns true if x is in the given set, false otherwise.
add inserts an element in the set (without duplication).
remove deletes an element from the set.
A union B is the set of all elements either in A or in B or both.
A intersection B is the set of all elements that are in both, A and B.
A difference B is the set of all elements in A but not in B.
toString returns the description of the set as a String.
equals returns true if the two sets are identical (same elements), false otherwise.
You are required to implement the mathematical model Set of integers as a class that implements the above interface. You must implement this structure as a linked list of elements kept in the increasing sequence. You must implement "isMember", "add", and “intersection” methods using recursive algorithms. Others can be implemented as you wish.
To test your implementation, write the test program to do the following. As always, all input is read from the input file and all output is produced in the output file. Prompt the user to acquire the names of input and output files.
Create an array of N sets, N is the first data in the input file. // S[0] through S[N-1]
Read commands from the input file, and execute them. After each command, output what was done (like, inserted element xxx in set n) and produce the output relevant to that command. Make sure that your output is self-explanatory and paper conserving. That means, do not output the elements of the set one per line, but output many elements on the same line.
The commands are specified in the following format:
A x n // Insert the integer x in set S[n]
R x n // Delete (Remove) x from S[n]
U n1 n2 n3 // S[n3] = S[n1] union S[n2]
N n1 n2 n3 // S[n3] = S[n1] intersection S[n2]
D n1 n2 n3 // S[n3] = S[n1] difference S[n2]
B x n // Does x belong in set S[n] ?
O n // Output the set S[n]
E n // Is set S[n] empty?
Q n1 n2 // Are two sets S[n1] and S[n2] equal?
INPUT FILE:
10 // This is the number of Sets in the array of Sets
E 0
A 24 0
A 423 0
A 76 0
A 12 0
A 8 0
A 64 0
O 0
E 0
B 76 0
R 76 0
R 68 0
B 24 0
B 12 0
B 76 0
A 111 0
O 0
A 76 1
A 55 1
A 12 1
A 43 1
A 876 1
A 98 1
A 64 1
A 34 1
O 1
B 111 1
B 76 1
U 0 1 2
O 2
N 0 1 3
Explanation / Answer
Java code for set implemertation:
public interface Set {
public boolean isEmpty(); // Is the set empty?
public void makeEmpty(); // Make this set empty.
public boolean isMember(int x); // Is x a member of this set?
public void add(int x); // Insert an element x in this set.
public void remove(int y); // Delete an element y from this set.
public void union(OrderedSet other, OrderedSet result); // result = "this" UNION other
public void intersection(OrderedSet other, OrderedSet result); // result = "this"
// INTERSECTION other
public void difference(OrderedSet other, OrderedSet result); // result = "this" - other
public String toString(); // Overridden toString method that returns the set
// description as
// a String.
public boolean equals(Object other); // Overridden equals method to check
// equality of two sets.
}
import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
public class OrderedSet implements Set {
private Cell set;
private static class Cell {
int value;
Cell next;
Cell(int value, Cell cell) {
this.value = value;
this.next = cell;
}
@Override
public String toString() {
return "Cell [first=" + value + ", next=" + next + "]";
}
}
@Override
public boolean isEmpty() {
return null == set;
}
@Override
public void makeEmpty() {
set = null;
}
@Override
public boolean isMember(int x) {
Cell ptr;
for (ptr = set; ptr != null && ptr.value < x; ptr = ptr.next) {
}
return (ptr != null && ptr.value == x);
}
@Override
public void add(int x) {
if (set == null)
set = new Cell(x, null);
else if (x < set.value)
set = new Cell(x, set);
else {
Cell ptr;
for (ptr = set; ptr.next != null && ptr.next.value < x; ptr = ptr.next) {
}
if (ptr.next == null || ptr.next.value > x)
ptr.next = new Cell(x, ptr.next);
}
}
@Override
public void remove(int y) {
if (set != null)
if (set.value == y)
set = set.next;
else {
Cell ptr;
for (ptr = set; ptr.next != null && ptr.next.value < y; ptr = ptr.next) {
}
if (ptr.next != null && ptr.next.value == y)
ptr.next = ptr.next.next;
}
}
@Override
public void union(OrderedSet other, OrderedSet result) {
Cell curr = this.set;
while (curr.next != null) {
result.add(curr.value);
curr = curr.next;
}
result.add(curr.value);
Cell otherCell = other.set;
while (otherCell.next != null) {
result.add(otherCell.value);
otherCell = otherCell.next;
}
result.add(otherCell.value);
}
@Override
public void intersection(OrderedSet other, OrderedSet result) {
Cell curr = this.set;
while (curr.next != null) {
Cell otherCell = other.set;
while (otherCell.next != null) {
if(curr.value==otherCell.value){
result.add(otherCell.value);
break;
}
otherCell = otherCell.next;
}
curr = curr.next;
}
Cell otherCell = other.set;
while (otherCell.next != null) {
if(curr.value==otherCell.value){
result.add(otherCell.value);
break;
}
otherCell = otherCell.next;
}
if(curr.value==otherCell.value){
result.add(otherCell.value);
}
}
@Override
public void difference(OrderedSet other, OrderedSet result) {
// TODO Auto-generated method stub
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
Cell curr = set;
sb.append("[");
while (curr.next != null) {
sb.append(curr.value + ",");
curr = curr.next;
}
sb.append(curr.value + "]");
return sb.toString();
}
/**
* Driver
*
* @param args
*/
public static void main(String[] args) {
if (args.length < 1) {
System.out.println("Please provide input file name");
return;
}
// Read file
File file = new File(args[0]);
try (FileReader fileReader = new FileReader(file);
BufferedReader bufferedReader = new BufferedReader(fileReader);) {
StringBuffer stringBuffer = new StringBuffer();
String line;
int lineNumber = 1;
OrderedSet[] orderedSets = null;
while ((line = bufferedReader.readLine()) != null) {
String[] inputOperations = line.split(" ");
if (1 == lineNumber) {
orderedSets = new OrderedSet[Integer.parseInt(inputOperations[0])];
}
lineNumber++;
setOperations(inputOperations, orderedSets);
}
System.out.println(stringBuffer.toString());
} catch (FileNotFoundException e) {
System.out.println("Error: Input file not found");
} catch (IOException e) {
System.out.println("Error: I/O exception");
}
}
private static void setOperations(String inputOperations[], OrderedSet[] orderedSets) {
switch (inputOperations[0]) {
case "A":
if (orderedSets[Integer.parseInt(inputOperations[2])] == null)
orderedSets[Integer.parseInt(inputOperations[2])] = new OrderedSet();
orderedSets[Integer.parseInt(inputOperations[2])].add(Integer.parseInt(inputOperations[1]));
break;
case "R":
if (orderedSets[Integer.parseInt(inputOperations[2])] != null)
orderedSets[Integer.parseInt(inputOperations[2])].remove(Integer.parseInt(inputOperations[1]));
break;
case "U":
if (orderedSets[Integer.parseInt(inputOperations[1])] != null){
if(orderedSets[Integer.parseInt(inputOperations[3])]==null){
orderedSets[Integer.parseInt(inputOperations[3])]=new OrderedSet();
}
orderedSets[Integer.parseInt(inputOperations[1])].union(orderedSets[Integer.parseInt(inputOperations[2])],
orderedSets[Integer.parseInt(inputOperations[3])]);
}
break;
case "N":
if (orderedSets[Integer.parseInt(inputOperations[1])] != null){
if(orderedSets[Integer.parseInt(inputOperations[3])]==null){
orderedSets[Integer.parseInt(inputOperations[3])]=new OrderedSet();
}
orderedSets[Integer.parseInt(inputOperations[1])].intersection(orderedSets[Integer.parseInt(inputOperations[2])],
orderedSets[Integer.parseInt(inputOperations[3])]);
}
break;
case "D":
break;
case "B":
if (orderedSets[Integer.parseInt(inputOperations[2])] != null)
System.out.println(orderedSets[Integer.parseInt(inputOperations[2])]
.isMember(Integer.parseInt(inputOperations[1])));
break;
case "O":
if (orderedSets[Integer.parseInt(inputOperations[1])] != null)
System.out.println(orderedSets[Integer.parseInt(inputOperations[1])]);
break;
case "E":
if (orderedSets[Integer.parseInt(inputOperations[1])] != null)
System.out.println(orderedSets[Integer.parseInt(inputOperations[1])].isEmpty());
else {
System.out.println("false");
}
break;
case "Q":
break;
}
}
}
Sample output screenshot output:
false
[8,12,24,64,76,423]
false
true
true
true
false
[8,12,24,64,111,423]
[12,34,43,55,64,76,98,876]
false
true
[8,12,24,34,43,55,64,76,98,111,423,876]
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.