Self-Organizing Lists

Assignment

Implement the three self-organizing list heuristics:

• Count - Whenever a record is accessed it may move toward the front of the list if its number of accesses becomes greater than the record(s) in front of it.
• Move-to-front - Whenever a record is accessed it is moved to the front of the list. This heuristic only works well with linked-lists; because, in arrays the cost of shifting all the records down one spot every time you move a record to the front is too expensive.
• Transpose - whenever the record is accessed swap it with the record immediately in front of it.

Compare the cost of each heuristic by keeping track of the number of compares required when searching the list.

Additional Instructions

Use the SelfOrderedListADT abstract data type and the linked-list files I have provided to implement your self-ordered lists. You may incorporate the author's linked list implementation via inheritance or composition, which ever makes the most sense to you (I will not evaluate that aspect of your implementation). You are allowed to make changes to any of the files I have provided, except SelfOrderedListADT and test.txt, to make your implementation of SelfOrderedListADT cleaner. The same applies to the link.h (the link node implementation). You may not change SelfOrderedListADT or test.txt files.

I want you to run two tests

1.The first test is with char types. Use the add() function to build a list in the following order: A B C D E F G H (do not add 'I' here). After you have built that initial list I want you to use the find function to input the following characters: F D F G E G F A D F G E H I (note that I is not in the initial list; I want to see what your program does when it searches for an item that is not already in the list). For each heuristic display the order of the final list and the number of compares.

2.The second test is using the test.txt file I have provided using the data type string. Do not modify the test text file; because, I am going to compare your results with my own and modifying the test file will throw your results off. For this test I want you to do the following for each heuristic:

a.Read into your program the test.txt file adding words to your list using your find() function, and then

b.Print out

i.the total number of words in your list,
ii.the total number of compares, and
iii.the first 10 words in your list along with their frequency.

Here is a sample of a test run using strings (this sample was not run using the test file I've assigned you, so the values you see are not the same as those you should be seeing): see image.

Make sure that you give me enough screen shots so that I can see your entire run. You will be penalized if you do not.

SelfOrderedListADT Functions:

1.find() - finds a value in the list and, if found, increments the frequency. If not found then find() calls add() to append the value to the end of the list (initial frequency of an item added this way is 0). In either case find() calls your reorder function (see below) to reorder the list in accordance to the heuristic being used and find() increments the number of compares made (whereas add() (see below) does not).

2.add - appends the value to the end of the list without doing any compares or adjusting frequencies.

3.getCompares - returns the total number of compares done by find when searching for values in the list.

4.Size - returns the size of the list.

5.printlist - prints the list in the following format: value-## where "value" is the actual value of the node (either a char or a string) and ## is the frequency of that value. You will need a printlist() and a printlist(n) method because for your char tests you will print the entire list but for the string test I only want the first 10 nodes printed.

6.reorder - you can call this method whatever you want but what I am looking for is a method or methods that reorders your list as appropriate based on the heuristic you are using. This method is typically called by find().