Keagansed Keagansed - 2 months ago 15
C++ Question

How to declare friend classes while using decorator and iterator design patterns

I have created a ListAsDLL class (doubly linked list) by decorating a ListAsSLL class (singly linked list). Now I would like to incorporate an Iterator class to cycle through the ListAsDLL class. My code is as follows:

#include <iostream>
using namespace std;

class ListAsSLL
{
protected:
struct node{
int i;
struct node* next;
};
node* head;
node* tail;
int listSize;

public:
ListAsSLL()
{
head = 0;
tail = 0;
listSize = 0;
}
virtual void addToBeginning(int i)
{
node * temp = new node;
temp->i = i;
if(head==0){
temp->next = 0;
tail = temp;
}else if(head == tail) {
temp->next = tail;
}
else{
temp->next = head;
}
head = temp;
listSize++;
}
virtual void print()
{
node* temp = head;
for (int i = 0; i < listSize; ++i) {
cout<<temp->i<<" "<<endl;
temp = temp->next;
}
}
};

class Decorator : public ListAsSLL
{
private:
ListAsSLL* list;
public:
Decorator(ListAsSLL* l)
{
list = l;
}
virtual void addToBeginning(int i)
{
list->addToBeginning(i);
}
virtual void print()
{
list->print();
}
};

class PreviousDecorator : public Decorator
{
protected:
struct dnode : public node
{
node* prev;
};
dnode* head;
dnode* tail;
int listSize;

public:
PreviousDecorator(ListAsSLL* l) : Decorator(l)
{
listSize = 0;
head = 0;
tail = 0;
}
virtual void addToBeginning(int i)
{
Decorator::addToBeginning(i);
dnode * temp = new dnode;
temp->i = i;
if(head==0){
temp->next = 0;
tail = temp;
}else if(head == tail) {
temp->next = tail;
tail->prev = temp;
}
else{
temp->next = head;
tail->prev = temp;
}
temp->prev = 0;
head = temp;
listSize++;
}
virtual void print()
{
Decorator::print();
node* temp = head;
for (int i = 0; i < listSize; ++i) {
cout<<temp->i<<" "<<endl;
temp = temp->next;
}
}
friend class DLLIterator;
};

class ListAsDLL : public ListAsSLL
{
public:
virtual void addToBeginning(int i){}
virtual void print(){}
};

class DLLIterator
{
private:
ListAsDLL* dll;
public:
DLLIterator(ListAsDLL* dll)
{
this->dll = dll;
}
int getFirst()
{
return dll->head->i;
}
};

int main() {
ListAsSLL* dll = new PreviousDecorator(new ListAsDLL());
dll->addToBeginning(20);
DLLIterator* it = new DLLIterator((ListAsDLL*) dll);
cout<<it->getFirst()<<endl;

delete dll;
delete it;
return 0;
}


The only problem is that because I am passing in a ListAsDLL as a parameter to the Iterator class I am unable to access the protected attributes of the class it is being decorated with. Therefore I cannot access dll->head->i.

Firstly, am I using the decorator design pattern correctly? And secondly how can I access the protected attributes of a class that a friend class has been decorated with.

Answer

Your class hierarchy is:

ListAsSSL (a first head) <- Decorator <- PreviousDecorator (another head)
    ^
    |---- ListAsDLL

You cannot cast a PreviousDecorator into a ListAsDLL even if they have a base class in common. Moreover, in the PreviousDecorator::addToBeginning method you write PreviousDecorator::head and not ListAsSSL::head that remains nullptr.

As you want to custom the cells, a solution could be just to let the type of the node open at the level of the class ListAsSLL with a virtual method like createEmptyNode. The ListAsDLL can override this method to create a double linked node as in the code below.

#include <iostream>
using namespace std;

class ListAsSLL
{
protected:
    struct node{
        int i;
        struct node* next;
    };
    node* head;
    node* tail;
    int listSize;

public:
    ListAsSLL()
    {
        head = 0;
        tail = 0;
        listSize = 0;
    }
    virtual node* createEmptyNode() const { return new node{}; }
    virtual node* addToBeginning(int i)
    {
        node * temp = createEmptyNode();
        temp->i = i;
        if(head==0){
            temp->next = 0;
            tail = temp;
        }else if(head == tail) {
            temp->next = tail;
        }
        else{
            temp->next = head;
        }
        head = temp;
        listSize++;
        return temp;
    }
    virtual void print()
    {
        node* temp = head;
        for (int i = 0; i < listSize; ++i) {
            cout<<temp->i<<" "<<endl;
            temp = temp->next;
        }
    }
};

class ListAsDLL : public ListAsSLL
{
protected:
    struct dnode : public node
    {
        dnode* prev;
    };
    virtual node* createEmptyNode() const { return new dnode{}; }

public:
    virtual node* addToBeginning(int i)
    {  node* result = ListAsSLL::addToBeginning(i);
       static_cast<dnode*>(tail)->next = static_cast<dnode*>(result);
       static_cast<dnode*>(result)->prev = static_cast<dnode*>(tail);
    }
    virtual void print(){}
    friend class DLLIterator;
};

class DLLIterator
{
private:
    ListAsDLL* dll;
public:
    DLLIterator(ListAsDLL* dll)
    {
        this->dll = dll;
    }
    int getFirst()
    {
        return dll->head->i;
    }
};

int main() {
    ListAsSLL* dll = new ListAsDLL();
    dll->addToBeginning(20);
    DLLIterator* it = new DLLIterator((ListAsDLL*) dll);
    cout<<it->getFirst()<<endl;

    delete dll;
    delete it;
    return 0;
}

The following code uses the decorator pattern with a new hierarchy level to avoid data duplication. ListAsSLL represents the implementation that can manage single linked cells and double linked cells.

The new class hierarchy is:

List <- ListAsSSL (implementation = head, tail)
  ^
  |- Decorator (SLL) <- PreviousDecorator (DLL)

I have kept the original names for the classes but you can modify them.

#include <iostream>
#include <cassert>
#include <memory>
using namespace std;

class List {
  public:
   virtual ~List() {}
   virtual void addToBeginning(int i) {}
   virtual void print() const {}
   virtual int getFirst() const { assert(false); }
};

class PreviousDecorator;
class ListAsSLL : public List
{
protected:
    struct node{
        int i;
        struct node* next;

        node(int val) : i(val), next(nullptr) {}
    };
    node* head;
    node* tail;
    int listSize;
    friend class PreviousDecorator;

public:
    ListAsSLL()
    {
        head = 0;
        tail = 0;
        listSize = 0;
    }
    virtual ~ListAsSLL()
       { node* cell = head; 
         for (int i=0; i<listSize; ++i) {
           node* temp = cell->next;
           delete cell;
           cell = temp;
         }
       }
    void addToBeginning(node* anode)
    {
        node * temp = anode;
        if(head==0){
            temp->next = 0;
            tail = temp;
        }else if(head == tail) {
            temp->next = tail;
        }
        else{
            temp->next = head;
        }
        head = temp;
        listSize++;
    }
    virtual void addToBeginning(int i) { addToBeginning(new node(i)); }
    virtual void print() const
    {
        node* temp = head;
        for (int i = 0; i < listSize; ++i) {
            cout<<temp->i<<" "<<endl;
            temp = temp->next;
        }
    }
    virtual int getFirst() const { assert(head); return head->i; }
};

class Decorator : public List
{
private:
    std::unique_ptr<ListAsSLL> list;
protected:
    ListAsSLL& getImplementation() { return *list; }
public:
    Decorator(ListAsSLL* l) : list(l) {}
    virtual void addToBeginning(int i)
    {
        list->addToBeginning(i);
    }
    virtual void print() const
    {
        list->print();
    }
    virtual int getFirst() const { return list->getFirst(); }
};

class DLLIterator;
class PreviousDecorator : public Decorator
{
protected:
    struct dnode : public ListAsSLL::node
    {
        node* prev;
        dnode(int val) : node(val), prev(nullptr) {}
    };

public:
    PreviousDecorator(ListAsSLL* l) : Decorator(l) {}
    virtual void addToBeginning(int i)
    {   dnode* anode = new dnode(i);
        getImplementation().addToBeginning(anode);
        anode->prev = static_cast<dnode*>(getImplementation().tail);
        getImplementation().tail->next = anode;
    }
    friend class DLLIterator;
};

class DLLIterator
{
private:
    PreviousDecorator* dll;
public:
    DLLIterator(PreviousDecorator* dll)
    {
        this->dll = dll;
    }
    int getFirst() const
    {   
        return dll->getFirst();
    }
};

int main() {
    PreviousDecorator* dll = new PreviousDecorator(new ListAsSLL());
    dll->addToBeginning(20);
    cout<<dll->getFirst()<<endl;

    delete dll;
    return 0;
}