C#:

Using C#, I need help with the following code. I am attaching the instructions and also attaching the code that is done. What I need help with has //TODO . The ListNode.cs and Patient.cs does not need any fixing. The only ones that has the //TODO's in them are Program.cs, PatientData.cs, and SimpleLinkedList.cs. I also need to answer the questions at the end of the Instructions.

Instructions:

We want our structure to hold a group of Patients. We don't need to sort them, but we do need to look them up. In our little program, we will have a way to assign ids to our patients based on their name. (In real life, this could be problematic since our names may end up generating the same id. The list of names you will be working with do not have such a problem.) Our patient information will consist of first and last names, patient id and the cost of their most recent procedure.

As was mentioned above, we will be using two different data structures. The first of these is simply an array. (The old-fashioned kind with a fixed length, no automatic update of a counter, etc.) The second will be the linked-list we have been working on. The array will be an array of these linked-lists; the linked lists will hold patients. Not all of the entries in the array will have a linked list. This will depend on the size of the array, the number of patients among other things. Here is a diagram of what the lists will resemble.

Your program needs to be able to add entries into this rather odd data structure in the following way:

The top row is the array. Some of the elements are empty (i.e. have a null reference), others have a linked list. The linked lists are represented by the grey sentinel element and the blue data-containing elements. Note that these can be different lengths depending on how many patient ids map to a given slot in the array. Some may be empty. In fact, initially all will be empty.

When a patient is added, the code will retrieve the id from the Patient object. It will then mod (%) the patient id by the length of the array. Because of the way mod works, this will give you a number between zero and the length of the array; for example, if the array has a length of 500, mod will give some number from zero up to, but not including, 500. Hopefully you can see that this number can be used as an index into the array. If the entry at that index is null, create a new linked list and place it in the array at that index. At this point, you simply need to add the patient to the linked-list. You do this whether there was already a list or not.

Once the list has been built, the PatientData class will need the ability to retrieve a given Patient from the list. The FindPatientByName method will be passed a patient name. Just as before, this id should be used to determine which slot in the array is used. (You can use the static method in the Patient class or you can instantiate a Patient object using the name passed to the method. The latter approach may be easier since you can then use this dummy object when you call Find. Since CompareTo in the Patient class doesnt use the ProcedureCost, it can be any value. Once the slot is found, the code should use the SimpleLinkedList class at that location to find the given patient. Make certain there is a list there; you should not crash if a non-existent patient id is entered. In addition to returning the Patient object, if found, the code will also keep track of the number of times the CompareTo method is called in the Patient class. This code is already built into the Patient class; you might want to check that code to make certain you understand how it works. We may find a need to keep track of this type of information in future assignments.

An existing project is attached to this assignment. This project has a SimpleLinkedList class and a Patient class. The beginning of the PatientData class is also included. Most of the work that you do will need to be in this class. You will also need to add code to the Main method. For a grade of C or B you will not need to modify the SimpleLinkedList; for an A, you will since there is no method that removes entries from the linked-list. You will find that there is a loadPatients method that reads in the patients and adds them to the PatientData object. The method that actually adds the patient is a stub since this is part of what you will be implementing.

For a starting grade of C:

Implement the above structure. Modify the loop in Main so that it will retrieve the patient from the PatientData object. If the patient does not exist, the user should be informed. If the patient does exist, the user should be shown the patient's name, id and procedure cost. The user should be able to continue entering patients names until typing 'quit'. For our purposes, the program should also indicate how many compares were made to find a given patient. (This means you need to reset the count before calling your find method.)

For a starting grade of B:

Modify the loop in Main to present the user with a menu showing (F)ind, (S)tatistics, (Q)uit. The Statistics menu item should report four values (appropriately labeled): The number of slots in the array, the percentage of used slots in the array (be careful of integer division), the maximum length of the linked lists of your PatientData, and the average length of your linked lists (again, be careful of integer division; also, do not count empty slots when calculating the average, only slots that have a list). The average length can be calculated easily or somewhat more complexly. Think about it.

For a starting grade of A:

Add the ability to remove a patient. Add a (R)emove option to your menu. If a user is removed, Find should report that the user does not exist. As mentioned above, this will involve adding code to the SimpleLinkedList class. Your book can help you with an algorithm to remove items. Make certain you keep the first pointer in your list up-to-date. The remove method does not need to remove a linked-list from the array if it becomes empty, though you may do so if you like.

Questions:

Answer these in a separate document that you submit along with your program.

Run the program several times, using the following values for the size of the array: 3, 200, 1000, 1500. Pick three names that are in the list. Search for them and not how many comparisons each search takes. Make a chart similar to the following:

Name/Size	3	200	1000	1500
name 1
name 2
name 3

What do you notice about the number of comparisons it takes as the size of the array increases? Why is this true?

For a small array size, what is the Big-O for finding an element in this data structure? What about for large array sizes?

If you did work for a B or above:

Add three more entries to the above array capturing the maximum and average lengths of the linked lists and the percent full.

What do you observe about the average lengths? the percentage of slots that are used? Comments on why this is so?

What would the size of the array need to be so that no list had a length greater than one?

Here are the different parts of the program that I already have code for. Like I said, I just need help fixing the parts where it has a //TODO.

ListNode.cs: (nothing needs to be done in this part)

using System;

namespace SimpleLinkedList { public class ListNode { ///

/// The field that hold the data for the node. ///

public T Data { get; set; }

///

/// Pointer to the next node in the list, if applicable. ///

public ListNode Next { get; set; }

///

/// noarg constructor ///

public ListNode(){}

///

/// Constructor sets the Data property from its argument. ///

/// Data for this node. public ListNode(T data) { Data = data; } }

Patient.cs: (nothing needs to be done on this section)

using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks;

namespace PatentData { public class Patient : IComparable { static public int Comparisons { get; set; }

public int Id { get; set; } public string FirstName { get; set; } public string LastName { get; set; } public double ProcedureCost { get; }

public Patient(string first, string last, double cost, int id) { FirstName = first; LastName = last; ProcedureCost = cost; Id = id; }

public Patient(string first, string last, double cost) : this(first, last, cost, -1 ) { Id = genPatientId(first, last); }

public static int genPatientId(string first, string last) { int id = Math.Abs((last.ToUpper() + first.ToUpper()).GetHashCode())%799993; if (id < 100000) id += 99997;

return id; }

public int CompareTo(Patient other) { Comparisons++; return Id - other.Id; } } }

Program.cs:(There are //TODO's in the section of the program, all //TODO's are bold in the code.)

using System; using System.Collections.Generic; using System.IO; using System.Linq; using System.Text; using System.Threading.Tasks;

namespace PatentData { class Program { private const int LIST_SIZE = 3;

static void showPatient(Patient p) {

// TODO put code to display the patient's name, id and procedure cost here. }

static void Main(string[] args) { PatientData data = new PatientData(LIST_SIZE); data.LoadPatients("c:/CPT244/patientList.csv");

Console.WriteLine("Enter first and last name:"); string name = Console.ReadLine(); while (!name.ToLower().StartsWith("quit")) { String[] names = name.Split(); if (names.Length != 2) { // TODO -- you may need to modify where you put the end brace // You may also want to change the sense of the boolean expression in the 'if' above // There are multiple ways to handle bad input, // but you shouldn't let bad input crash your program }

Patient.Comparisons = 0; Patient pat = data.FindPatientByName(names[0], names[1]); if (pat != null) { showPatient(pat); } else { Console.WriteLine("Patient not found"); } Console.WriteLine("Comparisions: {0}", Patient.Comparisons); Console.WriteLine("Enter a name:"); name = Console.ReadLine(); }

Console.ReadLine(); } } }

PatientData.cs:(There are //TODO's in the section as well, all //TODO's are bold in the code.)

using SimpleLinkedList; using System; using System.IO;

namespace PatentData { class PatientData { private SimpleLinkedList[] list;

///

/// Constructor. Instantiates the array based on the size passed to the constructor. ///

/// The size of the array. public PatientData(int size) { list = new SimpleLinkedList[size]; }

///

/// Loads patients into the data structure from the filename passed as a parameter. ///

/// Path to the file where the patient data is kept. The format is: first,last,procedureCost public void LoadPatients(string filename) { FileStream fs = new FileStream(filename, FileMode.Open); StreamReader input = new StreamReader(fs);

while (!input.EndOfStream) { string line = input.ReadLine(); string[] fields = line.Split(",".ToCharArray()); // TODO create the new patient // TODO add the patatient to the list } }

///

/// Adds a patient to the data structure. ///

/// The patient to be added. public void AddPatient(Patient patient) { // TODO add code needed to add a patient // Find the correct index // Add the patient to the linked list // Create a new list if there isn't one at this index }

public Patient FindPatientByName(string first, string last) { Patient pat = null; // TODO // create a patient using the names; the cost can be zero since it isn't used in the comparison // use the patient you created to get the id, slot in the array and finally the data in the linked list return pat; } public int FindLongestLength() { int max = 0; // TODO for 'B' grade return max; }

public Patient RemovePatientById(int id) { Patient pat = null; // TODO for 'A' grade // remove the patient // return the data return pat; } } }

SimpleLinkedList.cs:(There are //TODO's in this section as well, all //TODO's are bold in the code.)

using System; using System.Text;

namespace SimpleLinkedList { public class SimpleLinkedList where T : IComparable { private ListNode head; public int Count { get; private set; }

///

/// Constructor simply creates the sentinel node. ///

public SimpleLinkedList() { head = new ListNode(); }

///

/// Adds an entry to the head of the list. A node is created with the object passed in as its data. ///

/// The data to be added. public void AddAtHead(T element) { ListNode node = new ListNode(); node.Data = element; node.Next = head.Next; head.Next = node; Count++; }

///

/// Remove the first entry in the list and return its data. ///

/// public T RemoveFromHead() { ListNode node = head.Next; T data; if (head.Next != null) { head.Next = head.Next.Next; } Count--;

data = node.Data; node.Data = default(T); // probably not needed since result is no longer accessible

return data; }

///

/// Walks through the list looking for the node that preceeds the node containing the target. /// The object's CompareTo method is used to determine equality. ///

/// The object to be found. /// The node prior to the node containing the target, or null if it is not found. private ListNode FindNodeBefore(T target) { ListNode prev = null; prev = head; while (prev.Next != null) { if (prev.Next.Data.CompareTo(target) == 0) { return prev; } prev = prev.Next; }

// never found return null; }

///

/// Find the specified target. The object is considered 'found' if the object's CompareTo method returns zero. ///

/// The object to be found. /// public T Find(T target) { ListNode result = FindNodeBefore(target); if (result == null) return default(T);

// advance result to the one we are looking for. result = result.Next; return result.Data; }

///

/// Removes the specified target if the target's CompareTo method returns zero. ///

/// The object to be removed. /// public T Remove(T target) { T data = default(T); // TODO needed for 'A' work return data; } } }