Pure functions

In the book I am reading he gives an example, for a linked list with diffrent data types.

Code:

---

class list;

class block
  {
  block  *pnext;
public:
  block(void)
      {
      pnext = NULL;
      }
  virtual void show(void)=0;
  friend class list;
};

class numbers: public block
    {
    int  num;
public:                 
    numbers(int Inum)
        {
        num = Inum;
        }
      void show(void)
        {
          cout << "num = " << num << "\n";
          }
};
 
class strings : public block
    {
    char  str[256];
public:
    strings(char *Istr)
        {
        strcpy(str, Istr);
        }
      void show(void)
        {
        cout << "str = " << str << "\n";
        }
};



class list
    {
    block  *phead;
public:
    list(void)
        {
        phead = NULL;
        }
      void add(block  *pnewb)
          {
          if ( ! phead )
            phead = pnewb;
          else
              {
              pnewb->pnext = phead;
              phead = pnewb;
              }
          }
      void show(void)
          {
          block  *ptmp ;
 
          for ( ptmp = phead; ptmp ; ptmp = ptmp->pnext)
              ptmp->show();
          }
};


int main(int argc, char *argv[])
{
char  strtbl[3][80] = { "one", "two", "three" };
numbers  *pn;
strings  *ps;
int      i;
list      l1;
 

for ( i = 0 ; i < 3 ; ++i )
  {
  pn = new numbers(i+1);
  ps = new strings(strtbl[i]);
  l1.add(pn);
  l1.add(ps);
  }
l1.show();
 

system("PAUSE");
return EXIT_SUCCESS;
}

---

The output:
str = three
num = 3
str = two
num = 2
str = one
num = 1
Press any key to continue . . .
End the output:


1 ) Is there some way to know wheter a block pointer, points to numbers or to strings ?
2 ) As a home work. I need to do :
a) function that removes a cell from the linked list. ( How do I find it ? suppose the user wants to remove the cell strings "two")
b) function that finds a cell.

I tought :
1) adding to the class block the type of the data
2) overloading the operator == in block as a pure function.

Any help

Thank you.

A block pointer never points to numbers or strings. It points to another block pointer. For your reference, your lingo is screwy here. I know you got it out of a book. I'm just letting you know. Usually the block class is called "node" and the pointer it holds is called "next". The way I've seen it, it's done with templates rather than inheritance. So you have:

Code:

---

template <class T>
class LinkedList {
    struct node {
        T data;
        struct node* next;
    };
    public:

    /* rest of implementation here */
};

---

As to your remove function, it depends on how you define it. Maybe you just want to define it as:

Code:

---

void remove(int index);

---

This way it's up to the caller--your just going to remove a zero based index from your list. Let the caller figure out which one is "two". And while we're discussing which one is two, don't you have to write a find function?

Code:

---

int find(const T& val) const;

---

Here's the prototype for the find function that returns the index into your list where the value can be found. So there you have it. Your user can just do:

Code:

---

LinkedList ll;

// some code here to add values...

int index = ll.find("two");

ll.remove(index);

---

If you define your two functions like that, those should be the only two functions that you need to write. As to the template code, if you don't quite get it, don't worry--just replace the T values in the code with "int" and get it working for integers first. I promise, if you do that and post here when you get it working, someone can explain how to make it magically work for strings also with almost zero extra work. Also, you might consider using the following for your "show" function. That way, your linked list will magically work with cout.

Code:

---

ostream& operator<<(ostream& s, const LinkedList& ll);

---

I am sorry but I havent reached yet to the templates chapter.
But I surely did'nt understand that :

Quote:

---

Originally Posted by IfYouSaySo

A block pointer never points to numbers or strings.

---

Here is my simple example :

Code:

---

#include <cstdlib>
#include <iostream>

using namespace std;

class block
    {
public:
    virtual void show(void)
      {
      cout << "I am called from the base class\n";
      }
};

class numbers : public block
    {
public:
    void show(void)
        {
        cout << "I am called from the numbers class\n";
        }
};

class strings : public block
    {
public:
    void show(void)
        {
        cout << "I am called from the strings class\n";
        }
};

int main(int argc, char *argv[])
{
block      ba1;
numbers    n1;
strings    s1;
block      *pb1;

pb1 = &ba1;
pb1->show();
pb1 = &n1;   
pb1->show();
pb1 = &s1;
pb1->show();

    system("PAUSE");
    return EXIT_SUCCESS;
}

---

the output :
I am called from the base class
I am called from the numbers class
I am called from the strings class
Press any key to continue . . .



But thanks anyway for the answer.

Ok...I admit it, I was being unfair. I don't like the way the linked list is implemented in your book. That's not a reason why I shouldn't help you with it though. So here goes again. I was half-joking when I said that a block pointer never points to a number or a string. I know what you mean when you say that. But think about it. A block pointer points to a block. That's why it's a block pointer. Ok..ok..enough playing with words. What you want to know is given some base class pointer (block pointer) can you know what is the type of the derived class. The answer is yes. The method is RTTI (run time type information). Here is how you would use it:

Code:

---


class base {

};

class derived : public base {

};

class derived1 : public base {

};

int main()
{
    base* b = new derived();
    base* b1 = new derived1();

    cout << typeid(*b).name() << endl;
    cout << typeid(*b1).name() << endl;

    return 0;
}

---

What I said previously about implementing remove and find still holds though. For the remove function, your prototype should look like this:

Code:

---

class LinkedList {
public:
    void remove(int index);
};

---

What it will do is accept a zero based index of the item to remove. So you should just be able to write a look that walks some number of elements down the list, fixes up the block pointers, and deletes the block that is removed.

To be honest, now that I think about it, writing your find method stumps me. Because how do you tell it what to find? The data type of the element to find will be different depending on the derived type (string or number). But lets take the example of the number first:

Code:

---


class LinkedList {
    public:
    int find (int value_to_find) const;
};

---

Here it should be easy to see, that you pass the value to find and return the index where it was found. You just walk the blocks, and compare the value in the derived class against the value_to_find. Maybe you could cheat and pass value_to_find as a void*, and then provide a member function
bool compare(void* data);
in your block class. But then things start getting messy.

Anyway, let me know if you have other questions. And basic templates are easy. They're perfect for things like linked lists. You should do a quick internet search on it.

Thanks alot for your repley.
I finaly got it work. Of course the user must tell me if he wants to remove a string or a number.
But I think you are right. This is a very strange solution, because I first tried to compare numbers with strings and got no warnings.

About the templates, I started with a simple example, which don't look that simple to me.

Well if anyone interstated this is the solution I found.

Code:

---

#include <cstdlib>
#include <iostream>

using namespace std;

class list;

// N_TYPE is numbers.
// S_TYPE is strings.
enum data_type { N_TYPE, S_TYPE };

class block
  {
  block  *pnext;
protected :
    int  type;
public:
  block(void)
      {
      pnext = NULL;
      }
  virtual void show(void)=0;
  virtual int get_type(void)=0;
  friend class list;
};

class numbers: public block
    {
    int  num;
public:                 
    numbers(int Inum)
        {
        num = Inum;
        type = N_TYPE;
        }
      void show(void)
        {
          cout << "num = " << num << "\n";
          }
      int get_type(void)
        {
          return(N_TYPE);
          }
      int  get_value(void)
          {
          return(num);
          }
};


class strings : public block
    {
    char  str[256];
public:
    strings(char *Istr)
        {
        strcpy(str, Istr);
        type = S_TYPE;
        }
      void show(void)
        {
        cout << "str = " << str << "\n";
        }
      int get_type(void)
        {
          return(S_TYPE);
          }
      char*  get_value(void)
          {
          return(str);
          }
};


class list
    {
    block      *phead;
    data_type    d_type;
    int          cur_num;
    char        cur_str[256];

    int  user_choice(void)
          {
          int  ans;


          cout << "Enter 1 for numbers data type. 2 for string data type";
          cin >> ans;
          if ( ans == 1 )
              {
              d_type = N_TYPE;
              cout << "Enter number to delete : ";
              cin >> cur_num;
              return(1);
              }
          else if ( ans == 2 )
              {
              d_type = S_TYPE;
              cout << "Enter string to delete : ";
              cin >> cur_str;
              return(1);
              }
          else
              {
              cout << "Invlid Option\n";
              return(0);
              }
            }
public:
    list(void)
        {
        phead = NULL;
        }
      void add(block  *pnewb)
          {
          if ( ! phead )
            phead = pnewb;
          else
              {
              pnewb->pnext = phead;
              phead = pnewb;
              }
          }
      void show(void)
          {
          block  *ptmp ;

          for ( ptmp = phead; ptmp ; ptmp = ptmp->pnext)
              ptmp->show();
          }

      void del_cell(void)
          {
          int    ans;
          block  *pbf, *pbl, *pdel;
          numbers  *pnum;
          strings  *pstr;


          if ( ! phead )
              {
              cout << "List is empty\n";
              return;
              }

          if ( user_choice() == 0 )
              return;
          if (  phead->get_type() == d_type )
              {         
              if ( d_type == N_TYPE )
                {
                  pnum = (numbers*)phead;
                  if ( pnum->get_value() == cur_num )
                    {
                      phead = phead->pnext;
                      cout << "Deleteing " << pnum->get_value() << "\n\n";
                      delete pnum;
                      return;
                      }
                }
              else
                {
                pstr = (strings*)phead;
                if ( strcmp(pstr->get_value(), cur_str) == 0 )
                    {
                      phead = phead->pnext;
                      cout << "Deleteing " << pstr->get_value() << "\n\n";
                      delete pstr;
                      return;
                      }
                }
              }         

          for ( pbl = phead, pbf = phead->pnext ;
                          pbf;
                              pbl = pbf , pbf = pbf->pnext )
                if ( pbf->get_type() == d_type )
                    {
                    if ( d_type == N_TYPE )
                        {
                        pnum = (numbers*)pbf;
                        if ( pnum->get_value() == cur_num )
                            {
                            pbl->pnext = pbf->pnext;
                            cout << "Deleteing " << pnum->get_value() << "\n\n";
                            delete pnum;
                            return;
                            }
                        }
                    else
                        {
                        pstr = (strings*)pbf;
                        if ( strcmp(pstr->get_value(), cur_str) == 0 )
                          {
                          pbl->pnext = pbf->pnext;
                          cout << "Deleteing " << pstr->get_value() << "\n\n";
                          delete pstr;
                          return;
                          }
                        }
                    }

          if ( d_type == N_TYPE )
              cout << "Failed to find the number " << cur_num << "in list\n";
          else
              cout << "Failed to find the string " << cur_str << "in list\n";
          }

      void find_cell(void)
          {
          int  ans;
          block  *ptmp;
         


          ans = 1;
          while ( ans = user_choice() )
              {
              for ( ptmp = phead ; ptmp ; ptmp = ptmp->pnext )
                  if ( ptmp->get_type() == d_type )
                      {
                      if ( d_type == N_TYPE )
                          {
                          if (((numbers*)ptmp)->get_value() == cur_num )
                              {
                              cout << "Found number : " << cur_num << "\n";
                              break;
                              }
                            }
                      else
                          {
                          if ( strcmp( ((strings*)ptmp)->get_value(), cur_str) == 0 )
                              {
                              cout << "Found string : " << cur_str << "\n";
                              break;
                              }
                          }
                      }
              if ( ! ptmp )
                  {
                  if ( d_type == N_TYPE )
                      cout << "Failed to find number : " << cur_num ;
                  else
                      cout << "Failed to find string : " << cur_str ;
                  cout << "\n";
                  }

              }
          }

};
 

   
int main(int argc, char *argv[])
{
char  strtbl[3][80] = { "one", "two", "three" };
numbers  *pn;
strings  *ps;
int      i;
list      l1;


for ( i = 0 ; i < 3 ; ++i )
  {
  pn = new numbers(i+1);
  ps = new strings(strtbl[i]);
  l1.add(pn);
  l1.add(ps);
  }
l1.show();
l1.find_cell();
l1.del_cell();
l1.show();
l1.del_cell();
l1.show();
l1.del_cell();
l1.show();
l1.del_cell();
l1.show();
l1.del_cell();
l1.show();
l1.del_cell();
l1.show();
l1.del_cell();
l1.show();
l1.del_cell();
l1.show();

system("PAUSE");
return EXIT_SUCCESS;
}

---

Well...to convince you on the template thing...Here is a simple introduction. You probably saw something similar to:

Code:

---

template <class T>
class LinkedList {
    struct node {
        T data;
        struct node* next;
    };

    void append(T& item);

    // etc.
};

---

That's the code that defines a template object. It looks kind of weird at first, but just keep this in mind: that first line where it says "template <class T>" is saying that the type defined below is basically usable for any data type--the actual data type will be substituted whereever you see T in the class definition. That substitution happens when you instantiate the object. So the way you instantiate the object is like this:

Code:

---

int main()
{
    // A list holding integers
    LinkedList<int> mylist;

    // A list holding strings
    LinkedList<string> mystrlist;

    return 0;
}

---

Instead of having to duplicate code for different data types, the compiler does it for you, behind the scenes.

So what you end up with is something that is a little harder to define (it's harder to write the actual LinkedList class) but it's way easier to use (the code in main is very simple). As it turns out, template code comes in very useful when your trying to write containers, such as linked lists, arrays, binary trees, queues, stacks, etc.

But is mylist or mystrlist capable of holding in the same list differnt data types, like ints with char [] ?

I mean suppose I have only mylist, is it capable of holding in the same list diffrent data types like ints with char[] ?

No. But that's not what is usually needed anyway. Because when you take something out of the list, how would you know what to do with it? You don't even really know what it is.

To be fair, you could have a base class type, and store pointers to it in the list, and then the objects pointed to could be any derived type. In Java, the base class for all objects is a type called Object, so you for any type you can store references to Objects in any container. But that's java...and anyway, I don't think it's really all that useful.

I will get to the template.
Thanks.

On a side note, having only an index-based remove() and a find() that returns an index is not a good idea in a container without constant-time random access. It's slow! But iterators are yet another complicated topic.