This is a C++ problem that I have mostly completed with a couple of 
areas I'm unsure on. I will be as detailed as possible. 
 
The goal is to implement a class called List that uses a dynamic array
to
store the items (some value type) of the List.  I will now provide the
complete code for the header file, list2.h: 
 
FILE:  list2.h 
CLASS PROVIDED: List (A container class for a List of items, where
each List may have a designated item called the current item)
 
List::DEFAULT_CAPACITY is the initial capacity of a List that is
created by the default constructor.
 
Typedef_______ value_type 
List::value_type is the data type of the items in the List. It 
may be any of the C++ built-in types, or a class with a default 
constructor,  an assignment operator, and a copy constructor. 
 
CONSTRUCTOR  for the List class: 
     List(size_t initial_capacity=DEFAULT_CAPACITY) 
     Postcondition: The List has been initialized as an empty 
     list. The insert/attach functions will work efficiently (without 
        allocating new memory) until this capacity is reached.
 
MODIFICATION MEMBER FUNCTIONS for the List class: 

     Void resize(size_t new_capacity)
          Postcondition: The List’s current capacity is changed to the
  new_capacity (but not less than the number of items already on the
List). The insert/attach functions will will work efficiently (without
allocating new memory) until this new capacity is reached.

     
     Void start() 
          Postcondition: The first item on the List becomes the 
          current item (but if the List is empty, then there 
          is no current item). 
 
     Void advance() 
          Precondition: is_item returns true.  
          Postcondition: If the currentitem was already the last item
          on the List, then there is no longer any 
          current item. Otherwise, the new current item is the is the
          item immediately after the original current 
          item.  
 
     Void insert (const value_type& entry) 
          Postcondition: A new copy of entry has been inserted in the
          List before the current item. If there was 
          no current item, then the new entry has been inserted at 
          the front of the List. In either case, the newly 
          inserted item is now the current item of the list. 
 
     Void  attach(const value_type & entry) 
          Postcondtion: A new copy of entry has been inserted in the 
          List after the current item. If there was no 
          current item, then the new entry has been attached to the 
          end of the list. In either case, the newly 
          inserted item is now the current item of the list. 
 
     Void remove_current() 
          Precondition: is_item returns true. 
          Postcondition: The current item has been removed from the 
          List, and the item after this (if there is 
          one) is now the current item of the List.    
 
     CONSTANT MEMBER FUNCTIONS for the List class: 
 
     Size_t size() const 
          Postcondition: The return value is the number of items on 
          the List. 
 
     bool is_item() const 
    Postcondition: A true return value indicates that there is a valid
    “current” item that may be retrieved by activating the  current   
                                                                      
member function (listed below). A false return value indicates that 
there is no valid current item.
 
 
     List::value_type current() const 
     Precondition: is_item returns true.  
     Postcondition: The item returned is the current item on the List.
 
VALUE SEMANTICS for the List class: 
      Assignments and the copy constructor may be used with List 
objects. 


DYNAMIC MEMORY USAGE by the List
     If there is insufficient dynamic memory, then the following
functions call new_handler: The constructors, insert, attach.
 
PRIVATE DATA MEMBERS: 
value_type* data; 
size_t used; 
size_t current_index; 
size_t capacity;
 
 
I won’t bore you with the entire implementation file. There are
several  functions that I’m struggling with:
The Copy Constructor is giving me some problems. I believe that this
fragment is correct:

List::List(const List& source)
{
     data=new value_type[source.capacity];
     capacity=source.capacity;
     used=source.used;
     copy(source.data, source.data+used, data);

     //The problem then arises that current_index is not maintained.  
    //I’m thinking about doing it this way:
     
     current_index=source.current_index;
     for(i=0; i,used; i++)
     {
          data[i]=source.data[i];
     }
     Is this correct?
}      
     

What I have listed for Insert is as follows. It will insert at the end
of the List in the case when the list is not empty, but is_item is
false. I’m not quite sure where to go on this one.

void List::insert(const value_type& entry) 
{
     size_t i; 
 
 
     if(used==capacity) 
          resize( (size_t) (capacity*1.1+1)); 
     for(i=used; i>current_index; --i) 
          data[i]=data[i-1]; 
     data[current_index]=entry; 
     ++used; 
} 
 
My best guess for attach is as follows. I don’t know if I need to use
an else statement, but I’m not sure how else to do it.
 
void List::attach(const value_type& entry) 
{ 
      size_t i; 
 
     if(used==capacity) 
          resize(size_t)(capacity*1.1+1));
     else 
     { 
          for(i=used; i>(current_index+1);i--) 
               data[i]=data[i-1]; 
         data[current_index+1]=entry; 
         data[current_index]=data[current_index+1];
     } 
     used++ 
} 
 
remove_current is another one not quite working correctly. I can’t
find problems in the code, but it seems as if it’s moving data in the
wrong direction. Here is what I have so  far:
{ 
 
assert(is_item()); 
size_t i; 
 
for(i=(current_index+1);i<used-1;i++) 
{ 
      data[i]=data[i+1]; 
} 
--used; 
} 


I am also wondering the best way to maintain current_index in void
List::operator =(const List& source)


 
Any info is appreciated. If you need more input please let me know.

Hello martim07-ga,

Let's tackle your questions one at a time.  Note that one important
detail you have left out of your value semantics is how current_index,
capacity, and used are used.  In what follows, I am assuming
current_index is zero-based, and capacity and used are one-based.  So,
a list that can hold ten items, and has one item, will have
current_index = 0, capacity = 10, and used = 1.

1. Copy constructor

In your question, you allude to problems with the constructor, but not
what is specifically the issue.  So let me just walk through your
code.  The first thing that jumps out to me is the unusual use of the
copy() function.  As I know that function, you need to pass iterators
in so that it can copy the sequence correctly, and yet you are not
doing that.  That just doesn't look right, and furthermore, you are
doing your own copying later in the function. I personally would
dispense with using copy() and do it explicitly since it is so easy to
do.

You are correct that current_index also needs to be assigned, and just
assigning it the way you did looks fine.

What is left is the copying of elements in your data array. I am not
sure if this is just a typo as you were transposing your code into the
question, but I am not understanding your for loop condition:
"i,used"???  I would think you want to iterate from 0 to used-1:

for (size_t i = 0; i < used; i++)
    data[i] = source.data[i];

Of course, this relies on your value_type to have a proper assignment
operator, or else you will have two lists that refer to common data
which, if you are not expecting it, is a recipe for disaster.

2. insert(...)

I think what you want to do here is deal with the is_item condition
first, then code the rest of the function generally.  So, if there is
no current item, then is_item returns false, in which case you want to
insert at the front of the list.  Since you are always inserting
before the current item, this is the same as if the current item was
the first item.  I would do something like this:

void List::insert(const value_type& entry)  
{ 
     size_t i;

     // make sure we have enough room...is 10% increase enough?
     if (used == capacity)  
          resize( (size_t) (capacity*1.1+1));

     // if there is no current item, go to the front of the line
     if (!is_item())
         current_index = 0;

     // shuffle every element down the list...note I changed your
array indexing
     // to be a little clearer as to what is going on
     for (i = used - 1; i >= current_index; i--)  
          data[i + 1] = data[i];
  
     data[current_index] = entry;  
     used++;  
}  

3. attach(...)

I see a couple of problems here.  First, if the list is full, you
resize but don't copy the new element in!  Oops.  I think the else
should not be there.  As for the rest of the function, it is
notionally similar to insert, so I would code it the same way:

void List::attach(const value_type& entry)  
{  
     size_t i;  

     // make sure we have enough room...is 10% increase enough?
     if (used == capacity)  
          resize(size_t)(capacity*1.1+1)); 

     // if there is no current item, simply append to the list
     if (!is_item())
        current_index = used;
     else  
     {  
         // shuffle every element down the list...note I changed your
array
         // indexing to be a little clearer as to what is going on
         for (i = used - 1; i > current_index; i--)  
             data[i + 1] = data[i];

         // current index will be new element
         current_index++;
     }  

     data[current_index] = entry;
     used++  
}

4. remove_current()

The first issue here is that you are using an assert to trap the "no
current item" condition, which is great in debug mode, but won't
defend against someone calling this function inappropriately.  So, you
definitely need to have some conditional code here.  Next, you mention
that is seems like items are moving in the wrong direction.  Well, I
don't see that, but your loop indexes are not quite right, so that may
contribute to what you are seeing.  I would suggest the following:

void List::remove_current()
{
    size_t i;

    if (is_item()) {
        // simply bubble-up each element from current index on down
        for (i = current_index; i < used; i++)
            data[i] = data[i + 1];
    }
}


5. Assignment operator

You specifically ask how to maintain current_index in the assignment
operator.  I think that simply copying the value is sufficient,
because the net result of assigning one List to another should be an
equivalent List.  Since you rely on current_index to do certain other
things, you must copy this value if the two List objects are going to
be semantically the same.

Another suggestion is that your function names are a little bit
misleading; particularly insert and attach.  Without reading the
description, I would have assumed attach as being like an append, and
I would also expect insert to allow me to specify where to insert. 
Something like insertBeforeCurrent and insertAfterCurrent would be
much clearer to the end-user.

I hope that I have helped you with your List class.  If you require
any further clarifications, please don't hesitate to ask.

Search strategy:
None

References use:
Personal knowledge
Bjarne Stroustrup, "C++ Programming Language - 3rd edition",
Addison-Wesley, 1997.

-- tomo-ga

---

Request for Answer Clarification by martim07-ga on 12 Nov 2002 18:40 PST

Thanks for the help. You are a wonderful human being to wade through
this stuff. There are a couple of areas that I need some clarification
on:

When the Attach function is used alone, the most recent number appears
as the dreaded -6.27744e+066. If another number is entered, the
previous number is returned to normal and the most recent number
becomes -6.27744e+066, etc.

If Attach is used after the Insert function is called, it works fine.
It appears that Attach cannot be used first or by itself.

Another issue is with remove_current:

If I use Insert with 1,2,3,4,5 i get a List like this:

5
4
3
2
1

with 5 being the current_item. If I call remove_current, it removes
the item but all of the remaining items become 5's. This happens in
all occurences.

Thanks for your help!
martim07-ga

---

Clarification of Answer by tomo-ga on 13 Nov 2002 04:47 PST

Hi martim07,

With respect to your first problem, the issue could be one of two
things.  First, there could be some uninitialized data members in your
constructor.  Since you did not show the code for that, I cannot say
for certain.  Another, and probably more likely, cause might be that
you are using an inconsistent scheme for indexing into your list.  Be
very careful that you keep the same semantics throughout your class
for identifying elements.  So, current() should return
data[current_index] as long as current_index is between 0 and
(used-1), otherwise it should return NULL.  Only stepping through your
compiled code will tell you the definitive cause of the problem.

As to the "insert 1, 2, 3, 4, 5" resulting in the sequence "5, 4, 3,
2, 1", that is by design of your class.  Remember the confusing method
names?  Well, you have defined insert to add to the list before the
current index, so starting from an empty list, successive inserts will
add to the front of the list.

The remove_current problem is odd.  I am not sure if you coded it
exactly like I suggested in my answer, but it looks like you are
setting each data element in the list equal to data[current_index]. 
Again, stepping through that loop in detail should rapidly give you
the answer...look closely at the index values you are using in your
assignment!

Hope this helps.

-- tomo-ga

Excellent attention to detail and quick responses.