Linked List Templates and Object Types

Hi, this is quite a long problem which im sure can be solved quite easily.

I have a linked list data structure, which roughly represents a Hexagonal lattice (6 sided figure). For the project im doing each hexagon represents a Cell. Now i have a several different types of Cells (Morphogen & Juxtacrine to be exact - these are derived from the base class Cell)

For my data structure im using a similar construct, using templates, to create an lattice.

Code:

---

Lattice<Juxtacrine,500> lat;

---

Where Juxtacrine is the derived object type and 500 is the number of elements in the lattice.

Im working on a function to be able to replace an Object at [i,j] in the lattice with a different object type (eg Morphogen) eg

Code:

---

Lattice<Juxtacrine,500> lat;

Morphogen *m = new Morphogen();

lat.replace(25,43,m);

---

Thus replacing 25,43 with a new Morphogen object as apposed to a Juxtacrine object.

This is the LatticeNode object which a Lattice is made of:

Code:

---

template <class T> class LatticeNode {

        public:
                T t;

                void set(int i, int j);
                void setI(int x) { i = x; }
                void setJ(int x) { j = x; }
                void setNum(int i) { num = i; }
                void inc();
                void dec();

                void inc_i() { i++; }
                void inc_j() { j++; }

                LatticeNode<T> *next;
                LatticeNode<T> *prev;
       
                T* getCell() { return &t; }

                //default constructor
                LatticeNode();

                int getI() { return i; }
                int getJ() { return j; }
                int getNum() { return num; }

        private:
                                int num;
                int i;
                int j;
};

---

This is the function:

Code:

---

template <class T, int size>void Lattice<T, size>::replace(int i, int j, T *t)
{
        remove(i,j);
       
        int r = calc(i,j);

        LatticeNode<T> *n = new LatticeNode<T>;

        if(r < this->length())
        {
                current = head;

                for(int k = 0; k < size; k++)
                {
                        if(current->getI() == i && current->getJ() == j)
                        {       
                                n->next = current->next;
                                n->prev = current->next->prev;

                                current->next = n;
                                n->next->prev = n;
                       
                                n->setNum(current->next->next->getNum());
                                n->set(i,j);

                                current = n;
                                incLength();

                                for(int l = k; l < length(); l++)
                                {
                                        if(current->next != NULL)
                                        {
                                                current->next->inc();
                                                current = current->next;
                                        }
                                }
                        }

                        if(current->next != NULL)
                                current = current->next;
                }
        }
        else
        {
                //add to end of list
                current = tail;

                current->next = new LatticeNode<T>;
                current->next->prev = current;
                incLength();
                current->num = length();
        }

        reset_coords();

}

---

How do i get the passed parameter to T *t be used instead of the templated T?

Is this a good way to go about this problem? I was thinking of not using a Template on the lattice object, although i would need to re-code a lot... does anyone have any ideas or clues to whether im going about this in the right direction? Do i need to do some form of casting to the object, to make it into the right object?

So you have a hierarchy like so:

Code:

---

        Cell
      /    \
    /        \
Morphogen  Juxtacrine

---

Which means you could solve your problem by using Cell* as you the template type (aka. polymorphism).

gg

Hi Codeplug, thanks for the reply, ive been away for the past week and unable to get a connection to the internet.

Yes thats the heirarchy im using.

Yea i could use that method, but the only problem i get is the LatticeNode objects are only of the derived types, eg they cannot be of Cell type only its derived classes.

Basically the only hacky way i can think of to get around this is pass a string in and compare it for MORPH or JUXT say and then create them this way, only thing being i would have a problem when this prev and next pointers in the list.

For example

we have a linear list of LatticeNodes all of type Juxtacrine, and i wish to change item 10 in the list to a LatticeNode object with type Morphogen.

The current pointer would be of the new type (Morphogen), but the prev and next would point to incorrect types (Juxtacrine), thus falls my a question : Can the prev and next point to the LatticeNode object

eg n is the new type, and current is the old type.

Code:

---

n->next = current->next;
n->prev = current->next->prev;

current->next = n;
n->next->prev = n;

---

If i hard code the n's type to be Morphogen, and use a Juxtacrine T type, the above code requires a copy constructor to compile, but im assuming this doesnt meet my requirements, as this would require all the linked list to change its LatticeNode object type?

I would need a copy constructor to do the assignments, but would the pointers be ok pointing ? If you get what i mean.

AH i just thought a little about your reply, ive been so stupid!

If i change the definition of LatticeNode class to not use T but instead Cell - this was what you meant?

DOh!

Hm Codeplug, im having a little trouble understanding how to go about the polymorphism suggestion, i was thinking of using a cast to convert the objects? is this correct? eg im trying this:

Code:

---

template <class T, int size>void Lattice<T, size>::replace(int i, int j, const char *s)
{
        LatticeNode<T> *n = new LatticeNode<T>;

        if(strcmp(s,"J") == 0)
                dynamic_cast<LatticeNode<Juxtacrine> *>(n);

        if(strcmp(s,"M") == 0)
                dynamic_cast<LatticeNode<Morphogen> *>(n);

       
        remove(i,j);
       
        int r = calc(i,j);

        if(r < this->length())
        {
                current = head;

                for(int k = 0; k < size; k++)
                {
                        if(current->getI() == i && current->getJ() == j)
                        {       
                                n->next = current->next;
                                n->prev = current->next->prev;

                                current->next = n;
                                n->next->prev = n;
                       
                                n->setNum(current->next->next->getNum());
                                n->set(i,j);

                                current = n;
                                incLength();

                                for(int l = k; l < length(); l++)
                                {
                                        if(current->next != NULL)
                                        {
                                                current->next->inc();
                                                current = current->next;
                                        }
                                }
                        }

                        if(current->next != NULL)
                                current = current->next;
                }
        }
        else
        {
                //add to end of list
                current = tail;

                current->next = n;
                current->next->prev = current;
                incLength();
                current->num = length();
        }

        reset_coords();

}

---

But im getting this error:

Code:

---

c:\documents and settings\work\code\pcp2\lattice.cpp(520) : error C2683: dynamic_cast : 'LatticeNode<class Juxtacrine>' is not a polymorphic type
        c:\program files\microsoft visual studio\vc98\include\xmemory(59) : while compiling class-template member function 'void __thiscall Lattice<class Juxtacrine,100>::replace(int,int,const char *)'
c:\documents and settings\work\code\pcp2\lattice.cpp(523) : error C2683: dynamic_cast : 'LatticeNode<class Juxtacrine>' is not a polymorphic type
        c:\program files\microsoft visual studio\vc98\include\xmemory(59) : while compiling class-template member function 'void __thiscall Lattice<class Juxtacrine,100>::replace(int,int,const char *)'
Error executing cl.exe.

---

Note: the following code has not been compiled and/or verified, but is based on my understanding/memory of how to implement the solution proposed by Codeplug.

Code:

---

class Cell
{
  public:
          virtual display() { cout << "Cell" << endl;}
};
 
class Foo : public Cell
{
  public:
        display() {cout << "Foo" << endl;}
};
 
class Bar : public Cell
{
  public:
        display() { cout << "Bar" << endl;}
}; 
 
int main()
{
  Cell c;
  Foo f;
  Bar b;
  list<Cell *> myList;
  myList.push_back(& c);
  myList.push_back(& f);
  myList.push_back(& b);
 
  list<Cell *>::iterator start = myList.begin();
  list<Cell *>::iterator stop = myList.end();
  for(  ; start != stop; ++start)
        cout << (*start)->display << endl;
 
  start = myList.begin();
  ++start;
 
  list<Cell *>::iterator temp;
  temp = myList.erase(start);
  myList.insert(temp, &b);
 
  start = myList.begin();
 
  for(  ; start != stop; ++start)
        cout << (*start)->display << endl;
 
}

---

Cell is the base class from which Foo and Bar are derived. The display function is virtual in the Cell class and overwritten in both the Foo and Bar classes to provide results specific for each class. In main an instance of each class is decalred and a list of base class pointers is declared. The address of each instance added to the list and then polymorphism is used to display the information in each of the items in the list based on what class each item is. Then the second item in the class is identified, erased, and replaced with an instance of the other derived class. Finally, the information in the modified list is redisplayed.

You need to always hold Cell* in the LatticeNode (I'm not sure it is even necessary to make it a template). Then always assume you have a Cell* in each node. Any behavior that is different between a Juxtacrine and a Morphogen should be implemented in a virtual function that can be called from a Cell*. Then, the appropriate derived class version of that virtual function will be what is actually executed.

The only time you would need to know whether it is a Juxtacrine or a Morphogen is when you create a new object. In that case, you just create the new object and pass it into the replace function as a Cell* (or as a T if you keep the templated version). Here's a quick example of that concept inside your code.

Code:

---

class Cell {
    // ...
    virtual void DoSomething() = 0;
    // ...
};

class Juxtacrine {
    // ...
    virtual void DoSomething();
    // ...
};

class Morphogen {
    // ...
    virtual void DoSomething();
    // ...
};

class LatticeNode {
    Cell* t;
public:
    // ...
};

void somefunc() {
    // ...
    Lattice lat(CELL_TYPE_JUXTRACRINE, 500);
    // ...
    Morphogen *m = new Morphogen(); // Don't forget to delete
    lat.replace(25, 43, m)
    // ...
}

void Lattice::replace(int i, int j, Cell* t)
{
    LatticeNode *n = new LatticeNode(t); // Don't forget to delete
    remove(i,j);
    int r = calc(i,j);
    // ...
}

---

PS. elad's example is better than mine at showing polymorphism, but hopefully the combination will help you.

Yeah, what elad and jlou said :)

gg

great thanks! cheers for the responses.

ill take a look at this, and hopefully this answers my questions!

Hi ive been trying to implement to a simple virtual function to test out virtual functions, but im running into an exception when calling it. its called print() and is implemented the same as in elads reply. Im using the below code to call it:

Code:

---

cout << current->getCell().print << endl;

---

Where getCell is defined as:

Code:

---

Cell *t;
Cell& getCell() { return *t; }

---

Now when it calls the print() function its should print "im a cell" etc. but instead prints a value 1.

If i call this function like so:

Code:

---

current->getCell.print();

---

Then i get an exception. Do i have to call it as in elads each time? or am i doing something wrong?

Oh and by the way ive re-implemented the LatticeNode class to not use a Template, now, and hopefully when this print() thing works, i can test out the replace function.

Cheers for all help!

Actually elad's code has an error (it wasn't compiled and tested). That code should say:

cout << (*start)->display() << endl;

So your code should probably be:

Code:

---

cout << current->getCell().print() << endl;

---