4. Self-Organizing Lists Assignment

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 authors 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

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.

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:

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

Print out

the total number of words in your list,

the total number of compares, and

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 Ive assigned you, so the values you see are not the same as those you should be seeing):

SelfOrderedListADT Functions:

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).

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

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

Size returns the size of the list.

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.

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().

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

// list.h

#ifndef LIST_H #define LIST_H

template class List { // List ADT

public: List() {} // Default constructor virtual ~List() {} // Base destructor

// Clear contents from the list, to make it empty. virtual void clear() = 0;

// Insert an element at the current location. // item: The element to be inserted virtual void insert(const E& item) = 0;

// Append an element at the end of the list. // item: The element to be appended. virtual void append(const E& item) = 0;

// Remove and return the current element. // Return: the element that was removed. virtual E remove() = 0;

// Set the current position to the start of the list virtual void moveToStart() = 0;

// Set the current position to the end of the list virtual void moveToEnd() = 0;

// Move the current position one step left. No change // if already at beginning. virtual void prev() = 0;

// Move the current position one step right. No change // if already at end. virtual void next() = 0;

// Return: The number of elements in the list. virtual int length() const = 0;

// Return: The position of the current element. virtual int currPos() const = 0;

// Set current position. // pos: The position to make current. virtual void moveToPos(int pos) = 0;

// Return: The current element. virtual const E& getValue() const = 0; };

#endif

-----------------------------------------------------------------------------------------------------------------------

// link.h

#ifndef LINK_H #define LINK_H

#include

// Singly linked list node template class Link { public: E element; // Value for this node Link *next; // Pointer to next node in list // Constructors Link(const E& elemval, Link* nextval =NULL) { element = elemval; next = nextval; } Link(Link* nextval =NULL) { next = nextval; } };

#endif

-------------------------------------------------------------------------------------------------------------------------------------

// book.h

// A collection of various macros, constants, and small functions // used for the software examples.

// First, include all the standard headers that we need #ifndef BOOK_H #define BOOK_H

#include #include #include #include // Used by timing functions

// Now all the standard names that we use using std::cout; using std::endl; using std::string; using std::ostream;

const int defaultSize = 10; // Default size

// Return true iff "x" is even inline bool EVEN(int x) { return (x % 2) == 0; }

// Return true iff "x" is odd inline bool ODD(int x) { return (x % 2) != 0; }

// Assert: If "val" is false, print a message and terminate // the program void Assert(bool val, string s) { if (!val) { // Assertion failed -- close the program cout << "Assertion Failed: " << s << endl; exit(-1); } }

// Swap two elements in a generic array template inline void swap(E A[], int i, int j) { E temp = A[i]; A[i] = A[j]; A[j] = temp; } // Random number generator functions

inline void Randomize() // Seed the generator { srand(1); }

// Return a random value in range 0 to n-1 inline int Random(int n) { return rand() % (n); }

// Swap two integers inline void swap(int& i, int& j) { int temp = i; i = j; j = temp; }

// Swap two char*'s inline void swap(char* i, char* j) { char* temp = i; i = j; j = temp; }

// Big enough for simple testing #define INFINITY 9999

// Timing variables and functions unsigned tstart = 0; // Time at beginning of timed section

// Initialize the program timer void Settime() { tstart = (unsigned) clock(); }

// Return the elapsed time since the last call to Settime double Gettime() { unsigned tcurr = (unsigned) clock(); return (double)(tcurr - tstart)/(double)CLOCKS_PER_SEC; }

// Your basic int type as an object. class Int { private: int val; public: Int(int input=0) { val = input; } // The following is for those times when we actually // need to get a value, rather than compare objects. int key() const { return val; } // Overload = to support Int foo = 5 syntax Int operator= (int input) { val = input; return val; } };

// Let us print out Ints easily ostream& operator<<(ostream& s, const Int& i) { return s << i.key(); } ostream& operator<<(ostream& s, const Int* i) { return s << i->key(); }

#endif //end of BOOK_H

----------------------------------------------------------------------------------------------------------------------------------------------

// llist.h

#ifndef LLIST_H #define LLIST_H

#include "book.h" #include "link.h" #include "list.h"

// This is the file to include in your code if you want access to the // complete LList template class

// First, get the declaration for the base list class #include "list.h"

// This is the declaration for LList. It is split into two parts // because it is too big to fit on one book page // Linked list implementation template class LList: public List { private: Link* head; // Pointer to list header Link* tail; // Pointer to last element Link* curr; // Access to current element int cnt; // Size of list

void init() { // Intialization helper method curr = tail = head = new Link; cnt = 0; }

void removeall() { // Return link nodes to free store while(head != NULL) { curr = head; head = head->next; delete curr; } }

public: LList() { init(); } // Constructor ~LList() { removeall(); } // Destructor void print() const; // Print list contents void clear() { removeall(); init(); } // Clear list

// Insert "it" at current position void insert(const E& it) { curr->next = new Link(it, curr->next); if (tail == curr) tail = curr->next; // New tail cnt++; }

void append(const E& it) { // Append "it" to list tail = tail->next = new Link(it, NULL); cnt++; }

// Remove and return current element E remove() { Assert(curr->next != NULL, "No element"); E it = curr->next->element; // Remember value Link* ltemp = curr->next; // Remember link node if (tail == curr->next) tail = curr; // Reset tail curr->next = curr->next->next; // Remove from list delete ltemp; // Reclaim space cnt--; // Decrement the count return it; }

void moveToStart() // Place curr at list start { curr = head; }

void moveToEnd() // Place curr at list end { curr = tail; }

// Move curr one step left; no change if already at front void prev() { if (curr == head) return; // No previous element Link* temp = head; // March down list until we find the previous element while (temp->next!=curr) temp=temp->next; curr = temp; }

// Move curr one step right; no change if already at end void next() { if (curr != tail) curr = curr->next; }

int length() const { return cnt; } // Return length

// Return the position of the current element int currPos() const { Link* temp = head; int i; for (i=0; curr != temp; i++) temp = temp->next; return i; }

// Move down list to "pos" position void moveToPos(int pos) { Assert ((pos>=0)&&(pos<=cnt), "Position out of range"); curr = head; for(int i=0; inext; }

const E& getValue() const { // Return current element Assert(curr->next != NULL, "No value"); return curr->next->element; } };

#endif

------------------------------------------------------------------------------------------------------------------------

// SelfOrderedListADT.h

#ifndef SELFORDEREDLISTADT_HPP #define SELFORDEREDLISTADT_HPP

template class SelfOrderedListADT { public: //Default constructor/destructor SelfOrderedListADT(){} virtual ~SelfOrderedListADT() {} //Look for 'it'. If found return true and execute the self-ordering //heuristic used for ordering the list: count, move-to-front, or transpose. //Increments the compare instance variable every time it compares 'it' to //other members of the list. Returns true if 'it' is found. virtual bool find(const E& it) = 0; //Called by find if 'it' is not in the list. Adds the new 'it' to the list //Can also be called independently when initially loading the list with //unique values and when you want to load the list in the order 'it' is //read without your re-order method being called (or the number of compares //being incremented. virtual void add(const E& it) = 0; //Add new 'it' to the list

virtual int getCompares() const = 0; //Returns the number of accumulated compares virtual int size() const = 0; //Returns the size of the list //Print the list //In order print of the list. printlist() prints the entire list //whereas printlist(n) prints n nodes. virtual void printlist() const = 0; virtual void printlist(int n) const = 0; };

#endif /* SELFORDEREDLISTADT_HPP */

------------------------------------------------------------------------------------------------------------------------------------------------------------