Exercise 08.05.01

The text for this exercise reads:

(*2.5) Write a doubly-linked list of string module in the style of the Stack module from 2.4. Exercise it by creating a list of names of programming languages. Provide a sort() function for that list, and provide a function which reverses the order of the strings in it.

I didn't really do the exercise, I did a list class and not module. I couldn't do a module even if I wanted, as I lack namespace support. But converting between them is very easy. Just a matter of changing names. No actual code needs to be corrected.

If you want to, download the whole thing. It consists of a zip file with all the sources plus a makefile and the Rhide project files.

Here is the interface for the list class:

class list
{
 public:

 list();
 ~list();

 void add_str(string);
 void sorted_add(string);
 string get_str(size_t) const;

 size_t size() const;

 void sort();
 void reverse();

 private:

 class list_imp;

 list_imp* pImpl;
};

I used the pImpl idiom just to try it out (I had just gotten really tired of long rebuilds in another little thing I was working on). Every list function is of the form:

void list::func()
{
 return pImpl->func();
}

The list::list_imp class consists of the following:

class list::list_imp
{
 public:
 list_imp();
 ~list_imp();

 string get_str(size_t) const;
 size_t size() const { return m_size;}

 void sort();
 void reverse();

 void add_str(string);
 void sorted_add(string);

 private:

 struct Node;
 Node* m_data;
 size_t m_size;
 bool m_sorted;
};


struct list::list_imp::Node
{
 Node(Node* _next, Node* _prev):next(_next), previous(_prev) {}
 Node():next(0), previous(0) {}
 Node* next;
 Node* previous;
 string dat;
};

The add_str(string) function

void list::list_imp::add_str(string str)
{
 // add to the front
 Node* p = new Node;
 m_size++;
 if (m_data)
    {
     p->next = m_data;
     m_data->previous = p;
    }
 m_data = p;
 m_data->dat = str;
 m_sorted = false;

 return;
}

The get_str(int) function

string list::list_imp::get_str(size_t pos) const
{
 if (pos >= m_size)
    return "";

 Node* p = m_data;

 unsigned i = 0;
 while (i++ < pos) // pos can be 0!
       {
        p = p->next;
       }

 return p->dat;
}

The sort() function

void list::list_imp::sort()
{
 // a kind of bubble sort

 if (m_sorted || !m_size)
    return;

 Node* cur = m_data;

 while (cur->next)
     {
      if (cur->dat > cur->next->dat)
         {
          swap(cur->dat, cur->next->dat);
          cur = m_data; // restart the loop
          continue;
         }
      cur = cur->next;
     }
 m_sorted = true;

 return;
}

The reverse() function

void list::list_imp::reverse()
{

 if (!m_size)
    return;

 Node* p = m_data;

 while (p->next)
       {
        swap(p->next, p->previous);
        p = p->previous; // p-next is now p->previous
       }
 swap(p->next, p->previous);
 m_data = p;
 m_sorted = false;

 return;
}

The sorted_add(string) function

void list::list_imp::sorted_add(string str)
{
 if (!m_sorted)
    {
     add_str(str);
     return;
    }
 m_size++;

 Node* found = new Node(m_data, 0);
 found->dat = str;

 while (found->next && found->dat < str)
       found = found->next;

 if (found->next == m_data)
     m_data = found;
 return;
}

Back to the Exercise Page
Back to my Home Page