Self Organizing List
Posted on 2001-09-14
I have an assignment where I need to read data from a file, and use it to grow a self-organizing list with 4 of the following methods:
Front: If an item is not already present in the list, put it at the front, else ignore it.
Rear: If an item is not already present in the list, put it at the rear, else ignore it.
Move-to-front: If an item is already present in the list, move it to the front, else add it to the rear.
Transpose: If an item is already present in the list, interchange it with the item immediately before it, else add it to the rear..
Count: If an item is already present in the list, order list items by the frequency with which they have occurred, most frequent first, else add it to the rear.
Order: Maintain the list in ascending (numeric or alphabetical) order.
What I did was derive a class from std::list and then I implemented the first 4 of these insertion methods. What I don't understand is the following: Everytime I call Front, Rear, Move-to-front, and then Transpose to insert a new item, Rear will never have any effect on the list because Front will have already placed the item at the front of the list. Or if I implemented all 6 methods, the last method called would be order which would cancel the effects of the other 5 methods. It seems like a self organizing list should only use 1 of these methods, or maybe a combination of 2 or 3 of them. Either that or I am misunderstanding everything.