Self Organizing List

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.
Who is Participating?

Improve company productivity with a Business Account.Sign Up

imladrisConnect With a Mentor Commented:
Yes, I agree. The first line reads "WITH 4 of the following methods". I would assume that means they have to be available. Which is used, would depend on some selection by the user of the list, perhaps in the constructor.
nidanAuthor Commented:
Here are the actual instructions which I don't understand:

Using the STL for list, add any four of the above six insertion methods, each corresponding to one of the methods above.  
Build a self-organizing list with the first 1000 numbers in Numbers and then insert TestNumbers into it.  Repeat for 2000, 4000, 8000, and 16000 numbers. ( Numbers and TestNumbers are data files which I have already ).

Then I have to explain what the theoretical complexity of each of the implemented methods is and why, and what the empirical complexity of each method is.

I don't need any code for this.  I want to know if you think I should create all 5 lists with a combination of the 4 methods:

while ( cin >> number )

or if I should use the standard list class to create the first list, and then use different methods to create the other 4 and then compare results.  Or should I create the 5 lists using the same method?  
Stand back from the problem and it make a little more sense...

Some random data comes in to your program and you put it into a list.  Later you begin to access that data, and it turns out that some of the random elements are accessed more often than others.  So it would be convenient/expedient if those often-used data items were closer to the front of the list.

Or in another light, as more an more copies of a particular datum come in, you don't want to insert duplicates, you just want to increase a counter.  Then you want to reorganize so that the items with the highest count appear earlier in the list.

So really, you just need one insertion fn -- it places the item at the end of list or, if it is already in the list, it just bumps the count for that item and optionally moves it closer to the front of the list.

Because this is classwork, your prof wants you to write several insert functions and discuss them.  In real life, you would only use one at a time.

Front: Badly named -- call this fn UpdateOnly.  You would use this for a pre-built list.  Not an insert fn at all.

Rear: Call this fn AddNewOrUpdate.  It can be called for random items while you are building the list.

Move-to-front: Irrelevant excercise -- You would use this if you had a gut-feeling that the new item would eventually have a high count.  I'd call it ForcedInsertToFront.

Transpose: Irrelevant excercise -- I guess it could be used as a helper fn for the case when you happen to know that adding this datum would normally force a reorganization.  And to avoid that, you postpone the full reorg by moving it forward one notch immediately.  It will be closer to where you eventually want it to be.  I'd call it UpdateAndBumpForward

Count: Who thinks of these names?  This should be called AddNewOrUpdateAndForceReorder.  Like AddNewOrUpdate, this would be called while building the list.  However, it forces a reorganization with each new irem.  By using this, you ensure that the list is always in order, but performance would suck.  I'd use this fn every 10 or 100 inserts (or never; just call Order periodically).

Order: Not an insert operator - a helper fn.  It is called by AddNewOrUpdateAndForceReorder.

I hope that helps.

-- Dan
Free Tool: IP Lookup

Get more info about an IP address or domain name, such as organization, abuse contacts and geolocation.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

nidanAuthor Commented:
I agree with what you're saying, but my dilemna is the instructions which say using the STL for list, add any four of the above 6 insertion methods, and build a self organizing list...  I have implemented 4 of the insertion methods.  How do I use these methods to create the lists?  Do I use all 4 of them together to add an item?  
Or do I use a different insertion method for every different list? Or should I use the same insertion method for every list?  The experiment is to create several kinds of self - organizing lists and compare their performance to the original list.  I am unsure of what the original list is.

>>How do I use these methods to create the lists?  Do I
>>use all 4 of them together to add an item?  

No, you would not use all 4 together.
Each insertion method has it's own function, and depending on the calling functions's requirements, will depend on which function is called.

For example, if you had a function that took 10 names from a user's input, and the function had to put the names in a list, and then sort the list, you could make the function put all names that begin with letters A-M use the mylist.front() function, and all names that begin with letters N-Z use the mylist.rear() function.

This is not the greatest example in the world, but it might point you in the right direction.

I'm probably too late to help you with your work, but I think this will shed light on your problem.  You should create six list classes, each a subclass of std::list, that have different implementations of insert ().

Then you create six empty lists and put the same data into each list. You could do this with a method called insert_all ():

void insert_all (integer item)
   bobby.insert (item);
   peter.insert (item)
   greg.insert (item);
   cindy.insert (item);
   jan.insert (item);
   marsha.insert (item);

I think you forgot this question. I will ask Community Support to close it unless you finalize it within 7 days. Unless there is objection or further activity,  I will suggest to accept "imladris, DanRollins. Axter" comment(s) as an answer.

If you think your question was not answered at all, you can post a request in Community support (please include this link) to refund your points.
The link to the Community Support area is:

Force-accepted by
CS Moderator

DanRollins: points for you at
Axter: points for you at
Force accepted

** Mindphaser - Community Support Moderator **
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

All Courses

From novice to tech pro — start learning today.