Using Java, (Array-Approach, DeleteByte-Approach, and Link-Approach) either one.
ID: 3875183 • Letter: U
Question
Using Java, (Array-Approach, DeleteByte-Approach, and Link-Approach) either one.
Project #2: Bag 2 – Array Approach
Introduction:
We continue with the Bag data structure. However, in this project we focus on the representation of the Bag structure using array as described in your textbook.
Inventory of an online shopping mall is very dynamic. Some items come and go in no time. So, in this project we are going to simulate the dynamic state of an inventory. In order to save time, we are going to use a file called “p2changes.txt”. The file, tab delimited, contains two types of record and each record contains two fields as following:
Action
ID or Name
A or a
Artist Name
D or d
Artist ID
Where ‘A’ means “Add” and ‘D’ means “Delete”.
Details:
1) Description:
To help you understand why we care how data is structured, we are going to use 3 different ways to maintain data while it is being changed.
Assume that we start with the following records (Table-1):
ArtistID
Artist Name
1
Acconci
2
Ames
3
Aserty
4
Baron
5
Battenberg
Later on, the file needs to be updated according to the following (Table-2):
Action
ArtistID
Artist Name
A
6
Bindner
A
7
Blain
D
2
A
8
Blum
D
4
A
9
Budd
D
8
(NOTE: For Add, the Artist ID is assigned by the program. In this case, we simply use the number continuous from the last ID number. The number that has been deleted is not reassigned.)
Using Array structure the 3 different approaches will end up with the following:
(1. Without Gap)
ArtistID
Artist Name
1
Acconci
3
Aserty
5
Battenberg
6
Bindner
7
Blain
9
Budd
(2. Use Delete Field)
ArtistID
Artist Name
Delete
1
Acconci
F
2
Ames
T
3
Aserty
F
4
Baron
T
5
Battenberg
F
6
Bindner
F
7
Blain
F
8
Blum
T
9
Budd
F
(3. Use Next Field)
ArtistID
Artist Name
Next
1
Acconci
3
2
Ames
0
3
Aserty
5
4
Baron
0
5
Battenberg
6
6
Bindner
7
7
Blain
9
8
Blum
0
9
Budd
-1
2)Assignment:
1) Use Excel to trace every change that Table-2 makes to Tble-1. Name this file p2transition (Your name).xlsx.
2) Write a program that uses the 3 different approaches mentioned above to produce the updated version of “p1artists.txt” through the use of “p2changes.txt”. Let’s call the output files “p2artists2a.txt”, “p2artists2b.txt”, and “p2artistis2c.txt”. Compare the files and they should be same.
3) Use System.nanoTime() as following to find the time spent on each approach:
long startTime = System.nanoTime();
methodToTime(); //This is your code to be measured.
long endTime = System.nanoTime();
long duration = (endTime - startTime);
You are encouraged to try System.currentTimeMillis() to see the difference.
Write a summary to compare the 3 different approaches and then combine the result from the next project. Submit the report with project 3.
-----------------------------------------------------------------------------------------------------------------
p1artists.txt
-------------------------------------------------
------------------------------------------------------------
p2changes.txt
----------------------------------------
Action
ID or Name
A or a
Artist Name
D or d
Artist ID
Explanation / Answer
TestProjectTwo_MethodOne.java
-----------------------------------------------
import java.util.ArrayList;
public class TestProjectTwo_MethodOne {
public static void main(String[] args) {
String artistFile = "p1artists.txt";
String changesFile = "p2changes.txt";
ArrayList<Artist> artistTable = new ArrayList<Artist>();
CreateFile fileA = new CreateFile();
fileA.openFile("p2artists2a.txt");
LineReader reader = new LineReader(artistFile);
LineReader reader2 = new LineReader(changesFile);
//***THE READER IS CLOSED DURING THIS METHOD***//
long startTime = System.nanoTime();
readFile(reader, artistTable);
readFile(reader2, artistTable);
long endTime = System.nanoTime();
long duration = (endTime - startTime);
//**********CREATE FILE A*************
makeFile(artistTable, fileA);
fileA.addRecords(" "+"Duration of method: " + duration + " nano seconds.");
fileA.closeFile();
//********FILE A IS CLOSED************
}
public static void readFile(LineReader reader, ArrayList<Artist> artistTable){
Artist catalog;
String line;
int index = (artistTable.size());
int ID;
int position;
int deletions = 0;
while ((line = reader.readLine()) != null) {
//split each line at the tabbed space and place in and array
String splitArray[] = line.split(" ");
String firstEntry = splitArray[0];
//this block handles the changes
if (firstEntry.equalsIgnoreCase("a") || firstEntry.equalsIgnoreCase("D")) {
String value = splitArray[1];
//firstEntry is the action, either add or delete
if (firstEntry.equalsIgnoreCase("a")) { //***add section
ID = index + 1;
catalog = new Artist(ID, value);
artistTable.add(catalog);
index++;
// System.out.println("Artist Added: " + catalog.toString());
} else if (firstEntry.equalsIgnoreCase("d")) { //**delete section
ID = Integer.valueOf(value);
position = (ID - 1);
artistTable.remove(position - deletions);
deletions++;
}
}
//this block handles the creation of the artist objects
else {
try {
//convert the string to an integer
ID = (Integer.valueOf(firstEntry));
String artistName = splitArray[1];
//create a new Artist object
catalog = createArtist(ID,artistName);
artistTable.add(catalog);
} catch (NumberFormatException ex) {
ex.printStackTrace();
}
}
}
//close reader
reader.close();
}
private static Artist createArtist(int ID, String name){
return( new Artist(ID, name));
}
private static void makeFile(ArrayList<Artist> aList, CreateFile aFile)
{
String records;
Object[] listArray = aList.toArray();
for (Object aListArray : listArray) {
records = (aListArray.toString()+ " ");
aFile.addRecords(records);
}
}
}
----------------------------------------------------------------------------------
TestProjectTwo_MethodTwo.java
-----------------------------------------------
import java.util.ArrayList;
public class TestProjectTwo_MethodTwo {
public static void main(String[] args) {
String artistFile = "p1artists.txt";
String changesFile = "p2changes.txt";
ArrayList<Artist> artistTable = new ArrayList<Artist>();
CreateFile fileB = new CreateFile();
fileB.openFile("p2artists2b.txt");
LineReader reader3 = new LineReader(artistFile);
LineReader reader4 = new LineReader(changesFile);
//***THE READER IS CLOSED DURING THIS METHOD***//
long startTime = System.nanoTime();
readFile(reader3, artistTable); //create the Artist objects
readFile(reader4, artistTable); //add or delete objects
long endTime = System.nanoTime();
long duration = (endTime - startTime);
//**********CREATE FILE B*************
makeFile(artistTable, fileB);
fileB.addRecords(" "+"Duration of method two: " + duration + " nano seconds.");
fileB.closeFile();
//********FILE B IS CLOSED************
}
public static void readFile(LineReader reader, ArrayList<Artist> artistTable){
Artist catalog;
String line;
int index = (artistTable.size());
int ID;
int position;
while ((line = reader.readLine()) != null) {
//split each line at the tabbed space and place in and array
String splitArray[] = line.split(" ");
String firstEntry = splitArray[0];
//this block handles the changes
if (firstEntry.equalsIgnoreCase("a") || firstEntry.equalsIgnoreCase("D")) {
String value = splitArray[1];
//firstEntry is the action, either add or delete
if (firstEntry.equalsIgnoreCase("a")) { //***add section
ID = index + 1;
catalog = new Artist(ID, value, false);
artistTable.add(catalog);
index++;
}
else if (firstEntry.equalsIgnoreCase("d")) { //**delete section
ID = Integer.valueOf(value);
position = (ID - 1);
artistTable.get(position).setDelete(true);
}
}
//this block handles the creation of the artist objects
else {
try {
//convert the string to an integer
ID = (Integer.valueOf(firstEntry));
String artistName = splitArray[1];
catalog = createArtist(ID, artistName, false); //create object with delete field
artistTable.add(catalog);
} catch (NumberFormatException ex) {
ex.printStackTrace();
}
}
}
//close reader
reader.close();
}
private static Artist createArtist(int ID, String name, Boolean delete){
return(new Artist(ID, name, delete));
}
private static void makeFile(ArrayList<Artist> aList, CreateFile aFile)
{
String records;
for (Artist artist : aList) {
if(artist.getDelete().equals(true)){
System.out.print("");
}
else {
records = (artist.toString() + " ");
System.out.print(records);
aFile.addRecords(records);
}
}
}
}
---------------------------------------------------------------------------------------
TestProjectTwo_MethodThree.java
--------------------------------------------
import java.util.ArrayList;
public class TestProjectTwo_MethodThree {
public static void main(String[] args) {
String artistFile = "p1artists.txt";
String changesFile = "p2changes.txt";
ArrayList<Artist> artistTable = new ArrayList<Artist>();
CreateFile fileC = new CreateFile();
fileC.openFile("p2artists2c.txt");
LineReader reader5 = new LineReader(artistFile);
LineReader reader6 = new LineReader(changesFile);
//***THE READER IS CLOSED DURING THIS METHOD***//
long startTime = System.nanoTime();
readFile(reader5, artistTable);
readFile(reader6, artistTable);
long endTime = System.nanoTime();
long duration = (endTime-startTime);
//**********CREATE FILE C*************
makeFile(artistTable, fileC);
fileC.addRecords(" "+"Duration of method three: " + duration + " nano seconds.");
fileC.closeFile();
//********FILE C IS CLOSED************
}
public static void readFile(LineReader reader, ArrayList<Artist> artistTable){
Artist catalog;
String line;
int index;
index = (artistTable.size());
int ID;
int position;
int next;
while ((line = reader.readLine()) != null) {
//split each line at the tabbed space and place in and array
String splitArray[] = line.split(" ");
String firstEntry = splitArray[0];
//this block handles the changes
if (firstEntry.equalsIgnoreCase("a") || firstEntry.equalsIgnoreCase("D")) {
String value = splitArray[1];
//firstEntry is the action, either add or delete
if (firstEntry.equalsIgnoreCase("a")) { //***add section
ID = index + 1;
next = (ID + 1);
catalog = new Artist(ID, value, next);
artistTable.add(catalog);
index++;
}
// System.out.println("Artist Added: " + catalog.toString());
else if (firstEntry.equalsIgnoreCase("d")) { //**delete section
ID = Integer.valueOf(value);
position = (ID - 1);
next = (ID + 1);
artistTable.get(position - 1).setNext(next);
artistTable.get(position).setNext(0);
}
}
//this block handles the creation of the artist objects
else {
try {
//convert the string to an integer
ID = (Integer.valueOf(firstEntry));
String artistName = splitArray[1];
next = (ID + 1);
catalog = createArtist(ID,artistName, next); //create object with hasNext field
artistTable.add(catalog);
} catch (NumberFormatException ex) {
ex.printStackTrace();
}
}
}
//close reader
reader.close();
}
private static Artist createArtist(int ID, String name, int next){
return(new Artist(ID, name, next));
}
private static void makeFile(ArrayList<Artist> aList, CreateFile aFile)
{
String records;
for (Artist artist : aList) {
if(artist.getNext()==0){
System.out.print("");
}
else {
records = (artist.toString() + " ");
System.out.print(records);
aFile.addRecords(records);
}
}
}
}
-----------------------------------------------------------------------------
Artist.java
--------------------------------
public class Artist {
private int artistID;
private String artistName;
private Boolean delete;
private int next;
public Artist(int artistID, String artistName) {
this.artistID = artistID;
this.artistName = artistName;
}
public Artist(int artistID, String artistName, int nextPosition) {
setID(artistID);
setName(artistName);
setNext(nextPosition);
}
public Artist(int artistID, String artistName, Boolean delete) {
setID(artistID);
setName(artistName);
setDelete(delete);
}
public int getID() {
return artistID;
}
public void setID(int artistID) {
this.artistID = artistID;
}
public String getName() {
return artistName;
}
public void setName(String artistName) {
this.artistName = artistName;
}
public String getNameById(int artistID) {
return this.artistName;
}
//@Override
public String toString() {
return getID() + " " + getName();
}
public Boolean getDelete() {
return delete;
}
public void setDelete(Boolean delete) {
this.delete = delete;
}
public int getNext() {
return next;
}
public void setNext(int next) {
this.next = next;
}
}
---------------------------------------------------------------------
CreateFile.java
----------------------------------
import java.util.Formatter;
public class CreateFile {
private Formatter file;
//creates a file accepting a string representation of the path
public void openFile(String filePath) {
try {
file = new Formatter(filePath);
} catch (Exception e) {
System.out.println("An error has occurred.");
}
}
public void addRecords(String record) {
file.format("%S", record);
}
public void closeFile() {
file.close();
}
}
-------------------------------------------------------------------
LineReader.java
--------------------------------------
import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
public class LineReader {
BufferedReader bufferedReader;
LineReader(String file){
FileReader reader;
try{reader = new FileReader(file);
bufferedReader = new BufferedReader(reader);
}
catch (FileNotFoundException e){
System.err.println("LineReader can't find input file: "+ file);
e.printStackTrace();
}
}
String readLine(){
try {
return bufferedReader.readLine();
}
catch (IOException e){
e.printStackTrace();
}
return null;
}
void close(){
try {
bufferedReader.close();
}
catch (IOException e){
e.printStackTrace();
}
}
}
----------------------------------------------------------------------------------
p1artists.txt
-----------------------------
1 Acconci
2 Ames
3 Aserty
4 Baron
5 Battenberg
6 Bindner
7 Blain
8 Blum
9 Budd
10 Cardenas
11 Carpenter
12 Chico
13 Colvin
14 Cox
15 Cridler
16 Curtis
17 Dawson
18 DiGrigoro
19 Dill
20 Edwards
21 Fleming
22 Fratt
23 Garber
24 Garin
25 Giama
26 Gilhooly
27 Gonzales
28 Guys
29 Hamend
30 Higgins
31 Hofmann
32 Ibe
33 Indiana
34 Ingraham
35 Irvin
36 Kerrihard
37 Kollasch
38 Kritz
39 Lerman
40 Long
41 Lowney
42 Lundquist
43 Lutes
44 Maglich
45 McGraw
46 McIver
47 Meglech
48 Metz
49 Miller
50 Mogan
51 Motherwell
52 Novarre
53 Odiezma
54 Ortega
55 Parker
56 Penn
57 Pierobon
58 Prinzen
59 Quiroz
60 Rath
------------------------------------------------------------
p2artists2a.txt
-----------------------------------
1 ACCONCI
2 AMES
3 ASERTY
4 BARON
5 BATTENBERG
6 BINDNER
7 BLAIN
8 BLUM
9 BUDD
10 CARDENAS
12 CHICO
13 COLVIN
14 COX
15 CRIDLER
17 DAWSON
18 DIGRIGORO
19 DILL
20 EDWARDS
22 FRATT
23 GARBER
24 GARIN
25 GIAMA
26 GILHOOLY
27 GONZALES
28 GUYS
29 HAMEND
30 HIGGINS
32 IBE
33 INDIANA
34 INGRAHAM
35 IRVIN
36 KERRIHARD
37 KOLLASCH
38 KRITZ
39 LERMAN
40 LONG
42 LUNDQUIST
43 LUTES
44 MAGLICH
45 MCGRAW
47 MEGLECH
48 METZ
49 MILLER
50 MOGAN
52 NOVARRE
53 ODIEZMA
54 ORTEGA
56 PENN
57 PIEROBON
58 PRINZEN
59 QUIROZ
60 REED
61 RISSMAN
62 ROGERS
63 ROMAN
64 SCHENCK
65 SCHERZEL
66 SCHOLDER
67 SENIOR
68 SHENAL
69 STATOM
70 SWARTZ
71 TIDWELL
72 TURRELL
73 UDINOTTI
74 VAN COLLER
75 WAID
76 WERNER
77 WITTNER
78 WRIGHT
79 XIE
80 YASAMI
DURATION OF METHOD: 7499928 NANO SECONDS.
--------------------------------------------------------------------------------------
p2artists2b.txt
------------------------------
1 ACCONCI
2 AMES
3 ASERTY
4 BARON
5 BATTENBERG
6 BINDNER
7 BLAIN
8 BLUM
9 BUDD
10 CARDENAS
12 CHICO
13 COLVIN
14 COX
15 CRIDLER
17 DAWSON
18 DIGRIGORO
19 DILL
20 EDWARDS
22 FRATT
23 GARBER
24 GARIN
25 GIAMA
26 GILHOOLY
27 GONZALES
28 GUYS
29 HAMEND
30 HIGGINS
32 IBE
33 INDIANA
34 INGRAHAM
35 IRVIN
36 KERRIHARD
37 KOLLASCH
38 KRITZ
39 LERMAN
40 LONG
42 LUNDQUIST
43 LUTES
44 MAGLICH
45 MCGRAW
47 MEGLECH
48 METZ
49 MILLER
50 MOGAN
52 NOVARRE
53 ODIEZMA
54 ORTEGA
56 PENN
57 PIEROBON
58 PRINZEN
59 QUIROZ
60 RATH
61 REED
62 RISSMAN
63 ROGERS
64 ROMAN
65 SCHENCK
66 SCHERZEL
67 SCHOLDER
68 SENIOR
69 SHENAL
70 STATOM
71 SWARTZ
72 TIDWELL
73 TURRELL
74 UDINOTTI
75 VAN COLLER
76 WAID
77 WERNER
78 WITTNER
79 WRIGHT
80 XIE
81 YASAMI
82 ZISCHKE
DURATION OF METHOD TWO: 3791264 NANO SECONDS
-----------------------------------------------------------------
p2artists2c.txt
--------------------------------------
1 ACCONCI
2 AMES
3 ASERTY
4 BARON
5 BATTENBERG
6 BINDNER
7 BLAIN
8 BLUM
9 BUDD
10 CARDENAS
12 CHICO
13 COLVIN
14 COX
15 CRIDLER
17 DAWSON
18 DIGRIGORO
19 DILL
20 EDWARDS
22 FRATT
23 GARBER
24 GARIN
25 GIAMA
26 GILHOOLY
27 GONZALES
28 GUYS
29 HAMEND
30 HIGGINS
32 IBE
33 INDIANA
34 INGRAHAM
35 IRVIN
36 KERRIHARD
37 KOLLASCH
38 KRITZ
39 LERMAN
40 LONG
42 LUNDQUIST
43 LUTES
44 MAGLICH
45 MCGRAW
47 MEGLECH
48 METZ
49 MILLER
50 MOGAN
52 NOVARRE
53 ODIEZMA
54 ORTEGA
56 PENN
57 PIEROBON
58 PRINZEN
59 QUIROZ
60 RATH
61 REED
62 RISSMAN
63 ROGERS
64 ROMAN
65 SCHENCK
66 SCHERZEL
67 SCHOLDER
68 SENIOR
69 SHENAL
70 STATOM
71 SWARTZ
72 TIDWELL
73 TURRELL
74 UDINOTTI
75 VAN COLLER
76 WAID
77 WERNER
78 WITTNER
79 WRIGHT
80 XIE
81 YASAMI
82 ZISCHKE
DURATION OF METHOD THREE: 4160831 NANO SECONDS.
--------------------------------------------------------------
p2changes.txt
------------------------------
A Reed
A Rissman
D 11
A Rogers
A Roman
A Schenck
D 16
A Scherzel
A Scholder
D 21
D 31
A Senior
D 41
A Shenal
A Statom
A Swartz
A Tidwell
D 46
A Turrell
A Udinotti
A Van Coller
A Waid
D 51
A Werner
A Wittner
D 55
A Wright
A Xie
A Yasami
A Zischke
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.