Step 1: Write a program that reads a list of names from a file and constructs an
ID: 3594901 • Letter: S
Question
Step 1: Write a program that reads a list of names from a file and constructs an ordered list. For example, if the input text file is: Shai Tom Jim Aaron Barbara Beth Fred Jack Jarred Jill Amar Ralph Jill Hillary it should create the following ordered list. Print the contents of the list: [Aaron, Amar, Barbara, Beth, Fred, Hillary, Jack, Jarred, Jill, Jim, Ralph, Shai, Tom] Note: Although Jill is repeated in the input list, the ordered list does not have repeated items.
Step 2: Modify the above program so that it reads two text files each containing a list of names and constructs two ordered lists.
Step 3: Add a method to the above program that takes as input two ordered lists and returns a third list that is a merger of the two ordered lists. Use the two-finger walking algorithm discussed in class. For example, if list1 is: Amar Boris Charlie Dan Fujian Inder Travis and list2 is: Alex Ben Betty Charlie Dan Pei Travis Zola Zulu the method should create the following new ordered list and return it: Alex Amar Ben Betty Boris Charlie Dan Fujian Inder Pei Travis Zola Zulu Note: The header of the method should be written as follows: public static > OrderedList merge (OrderedList list1, OrderedList list2) { //your code here } Your final code should be one java class file that reads two files containing random names, creates two ordered lists from these names, merges them and displays the three lists
Java Ordered List Program
Explanation / Answer
/* package whatever; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
import java.util.Scanner;
import java.util.ArrayList;
class OrderedList<T extends Comparable<T>>
{
private ArrayList<T> elements;
private int cursor;
public OrderedList(int cap)
{
elements = new ArrayList<T>(cap);
cursor=-1;
}
public OrderedList()
{
elements = new ArrayList<T>();
cursor=-1;
}
public int size()
{
return elements.size();
}
public boolean isEmpty()
{
return elements.isEmpty();
}
public void clear()
{
elements.clear();
}
public T get(int pos)
{
if (pos<0||pos>=elements.size())
{
System.out.println("Index out of bounds");
//System.exit(0);
return null;
}
return elements.get(pos);
}
public T first()
{
if (elements.size()==0)
return null;
cursor=0;
return elements.get(cursor);
}
public T next()
{
if (cursor<0||cursor==(elements.size()-1))
return null;
cursor++;
return elements.get(cursor);
}
public void enumerate()
{
System.out.println(elements);
}
public int binarySearch(T item)
{
if (elements.size()==0)
return -1;
int lo=0, hi=elements.size()-1, mid=0;
while (lo<=hi)
{
mid = (lo+hi)/2;
int c = item.compareTo(elements.get(mid));
if (c==0) return mid;
if (c<0) hi = mid-1;
if (c>0) lo = mid+1;
}
if (item.compareTo(elements.get(mid))<0)
return (-(mid+1));
else
return (-(mid+2));
}
public void add(int pos, T item)
{
elements.add(item);
}
public void insert(T item)
{
if (elements.size()==0)
{
elements.add(item);
return;
}
int pos = binarySearch(item);
if (pos>=0)
{
System.out.println("Item " + item + " already present");
return;
}
else
elements.add(-pos-1, item);
}
public void remove(T item)
{
int pos = binarySearch(item);
if (pos<0)
{
System.out.println("No such element");
//System.exit(0);
return;
}
else
elements.remove(pos);
}
public T remove(int pos)
{
return elements.remove(pos);
}
}
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
public static <T extends Comparable<T>> OrderedList<T> merge(OrderedList<T> l1, OrderedList<T> l2)
{
int i=0,j=0,size1=l1.size(),size2=l2.size();
OrderedList<T> list3 = new OrderedList<T>();
while(i<size1 && j<size2)
{
if(l1.get(i).compareTo(l2.get(j)) <= 0)
{
list3.insert(l1.get(i));
i++;
}
else
{
list3.insert(l2.get(j));
j++;
}
}
if(i==size1)
{
while(j!=size2)
{
list3.insert(l2.get(j));
j++;
}
}
else
{
while(i!=size1)
{
list3.insert(l1.get(i));
i++;
}
}
return list3;
}
public static void main (String[] args) throws java.lang.Exception
{
OrderedList<String> list1 = new OrderedList<String>();
OrderedList<String> list2 = new OrderedList<String>();
OrderedList<String> list3 = new OrderedList<String>();
Scanner sc1 = new Scanner(new File("input1.txt"));
Scanner sc2 = new Scanner(new File("input2.txt"));
while (sc1.hasNext())
{
String s = sc1.next();
list1.insert(s);
}
list1.enumerate();
while (sc2.hasNext())
{
String s = sc2.next();
list2.insert(s);
}
list2.enumerate();
list3 = merge(list1,list2);
list3.enumerate();
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.