2
\$\begingroup\$

I was practicing C++ and data structures and wrote my own implementation of a doubly linked ring. I would love to improve my code a little bit more and would need help from the community.

Here is the implementation I have:

#ifndef BIRING_H_INCLUDED
#define BIRING_H_INCLUDED

#include<iostream>
#include<string>

using namespace std;

template<typename Key, typename Value>
class Ring
{

private:

    struct Element
    {
        Key key;
        Value value;
        Element* next;
        Element* prev;
    };

    Element* head;
    Element* tail;


public:
    class iterator
    {

    private:
        Element* ptr;

    public:

        iterator()
        {
            ptr=NULL;
        };

        iterator(const iterator & copy)
        {
            ptr=copy.ptr;
        };

        iterator(Element* copy)
        {
            ptr=copy;
        };

        ~iterator() {};



        iterator& operator=(iterator & copy)
        {
            ptr=copy.ptr;
        };

        iterator& operator=(Element* copy)
        {
            ptr=copy;
            return *this;
        };

        Key & operator*()
        {
            return ptr->key;
        };

        const Key & getKey()
        {
            return ptr->key;
        };

        const Value & getValue()
        {
            return ptr->value;
        };

        iterator operator+(const int i)const
        {
            iterator newthis = *this;
            for(int j=0; j<i; j++)
                newthis++;
            return newthis;
        };

        iterator& operator+=(const int i)
        {
            for(int j=0; j<i; j++)
                ptr=ptr->next;
            return *this;
        };

        iterator& operator++()
        {
            iterator a(*this);
            ptr=ptr->next;
            return a;
        };

        iterator operator++(int)
        {
            ptr=ptr->next;
            return *this;
        };

        iterator operator-(const int i)const
        {
            iterator newthis = *this;
            for(int j=0; j<i; j++)
                newthis--;
            return newthis;
        };

        iterator& operator-=(const int i)
        {
            for(int j=0; j<i; j++)
                ptr=ptr->prev;
            return *this;
        };

        iterator& operator--()
        {
            iterator a(*this);
            ptr=ptr->prev;
            return a;
        };

        iterator operator--(int)
        {
            ptr=ptr->prev;
            return *this;
        };

        bool operator==(const iterator & comp)const
        {
            return ptr==comp.ptr;
        };

        bool operator!=(const iterator & comp)const
        {
            return ptr!=comp.ptr;
        };

        bool isNull()const
        {
            return !ptr;
        };
    };


    Ring();
    ~Ring();

    Ring(const Ring<Key,Value> & copy);
    Ring<Key,Value> & operator=(const Ring<Key,Value> & copy);

    Ring<Key,Value> operator+(const Ring<Key,Value> & add)const;
    Ring<Key,Value> operator-(const Ring<Key,Value> & subtract)const;

    Ring<Key,Value>& operator++();
    Ring<Key,Value> operator++(int);

    Ring<Key,Value>& operator--();
    Ring<Key,Value> operator--(int);

    Ring<Key,Value> & operator+=(const Ring<Key,Value> & add)
    {
        *this=*this+add;
        return *this;
    };
    Ring<Key,Value> & operator-=(const Ring<Key,Value> & subtract)
    {
        *this=*this-subtract;
        return *this;
    };

    void clear();
    void reverse();


    iterator begin() const
    {
        return iterator(head);
    };


    iterator end() const
    {
        return iterator(tail);
    };

    unsigned int size() const;
    bool empty()const
    {
        return !head;
    };

    bool insertAt(unsigned int pos, const Key&key, const Value &value);
    bool insertAfter(const Key&keypos, const Key&key, const Value &value);
    bool insertAfter(const iterator & iter, const Key&key, const Value &value);

    void push_front(const Key&key, const Value &value);
    void push_back(const Key&key, const Value &value);
    void pop_front()
    {
        iterator a(begin());
        remove(a);
    };
    void pop_back()
    {
        iterator a(end());
        remove(a);
    };

    bool remove(const Key&key);
    bool remove(iterator & iter);
    bool removeAllOf(const Key&key);

    bool exists(const Key&key);

    bool operator==(const Ring<Key,Value> & check)const;
    bool operator!=(const Ring<Key,Value> & check)const;


    template<typename u, typename i>
    friend ostream & operator<< (ostream & os, const Ring<u,i> & toprint);


    iterator find(const Key &where) const;//move to the position of the designated ID
    iterator findPlace(int place) const;//move to the position of designated startindex
    bool findNodePlace(int place) const;

};



template <typename Key, typename Value>
unsigned int Ring<Key, Value>::size() const
{
    int length=0;
    if(head!=NULL)
    {
        Element *current = head->next;
        length=1;
        while(current!=head)
        {
            length++;
            current=current->next;
        }
    }
    return length;
}


template<typename Key, typename Value>
Ring<Key,Value>::Ring()
{
    head=tail=NULL;
}

template<typename Key, typename Value>
Ring<Key,Value>::Ring(const Ring<Key,Value> & copy)
{
    head=tail=NULL;
    Element * temp = copy.head;
    while (temp)
    {
        this->push_back(temp->key, temp->value);
        if(temp==copy.tail)
            break;
        temp=temp->next;
    }
}

template<typename Key, typename Value>
Ring<Key,Value>::~Ring()
{
    clear();
}


template<typename Key, typename Value>
Ring<Key,Value> & Ring<Key,Value>::operator=(const Ring<Key,Value> & copy)
{
    if(&copy==this)
        return *this;

    clear();

    Element * temp = copy.head;
    while (temp)
    {
        this->push_back(temp->key, temp->value);
        if(temp==copy.tail)
            break;
        temp=temp->next;
    }

    return *this;
}


template<typename Key, typename Value>
bool Ring<Key,Value>::operator==(const Ring<Key,Value> & check)const
{
    bool same = true;
    Element * temp1 = head;
    Element * temp2 = check.head;
    while(temp1&&temp2)
    {
        if(temp1->key!=temp2->key || temp1->value!=temp2->value)
            same = false;
        if(temp1==tail||temp2==check.tail)
            break;
        temp1=temp1->next;
        temp2=temp2->next;
    }
    return same;
}

template<typename Key, typename Value>
bool Ring<Key,Value>::operator!=(const Ring<Key,Value> & check)const
{
    return !(*this==check);
};


template<typename Key, typename Value>
Ring<Key,Value> Ring<Key,Value>::operator+(const Ring<Key,Value> & added)const
{
    Ring<Key,Value> tempseq;
    Element * temp = head;
    while(temp)
    {
        tempseq.push_back(temp->key,temp->value);
        if(temp==tail)
            break;
        temp=temp->next;
    }
    temp = added.head;
    while(temp)
    {
        tempseq.push_back(temp->key,temp->value);
        if(temp==added.tail)
            break;
        temp=temp->next;
    }
    return tempseq;
}

template<typename Key, typename Value>
Ring<Key,Value> Ring<Key,Value>::operator-(const Ring<Key,Value> & subtract)const
{
    Ring<Key,Value> tempseq;
    Element * temp = head;
    while(temp)
    {
        tempseq.push_back(temp->key,temp->value);
        if(temp==tail)
            break;
        temp=temp->next;
    }
    temp = subtract.head;
    while(temp)
    {
        tempseq.removeAllOf(temp->key);
        if(temp==subtract.tail)
            break;
        temp=temp->next;
    }
    return tempseq;
}

template<typename Key, typename Value>
Ring<Key,Value>& Ring<Key,Value>::operator++()
{
    if(head)
    {
        head=head->next;
        tail=tail->next;
    }
    return *this;
}

template<typename Key, typename Value>
Ring<Key,Value> Ring<Key,Value>::operator++(int)
{
    Ring a(*this);
    if(head)
    {
        head=head->next;
        tail=tail->next;
    }
    return a;
}

template<typename Key, typename Value>
Ring<Key,Value>& Ring<Key,Value>::operator--()
{
    if(head)
    {
        head=head->prev;
        tail=tail->prev;
    }
    return *this;
}

template<typename Key, typename Value>
Ring<Key,Value> Ring<Key,Value>::operator--(int)
{
    Ring a(*this);
    if(head)
    {
        head=head->prev;
        tail=tail->prev;
    }
    return a;
}


template<typename u, typename i>
ostream & operator<<(ostream & os, const Ring<u,i> & toprint)
{
    typename Ring<u,i>::Element* temp;
    temp = toprint.head;
    while(temp)
    {
        os << "Key: " << temp->key << endl << "Value: " << temp->value << endl;
        if(temp==toprint.tail)
            break;
        temp = temp->next;
    }
    return os;
}



template<typename Key,typename Value>
void Ring<Key,Value>::clear()
{
    Element * temp;
    temp=head;
    if(tail)
        tail->next=NULL;
    while(temp)
    {
        temp = temp->next;
        delete head;
        head = temp;
    }
    head=tail=NULL;

}

template<typename Key,typename Value>
void Ring<Key,Value>::reverse()
{
    Ring<Key,Value> tempseq;
    Element * temp = head;
    while(temp)
    {
        tempseq.push_front(temp->key,temp->value);
        if(temp==tail)
            break;
        temp=temp->next;
    }
    *this=tempseq;
}

template<typename Key,typename Value>
bool Ring<Key,Value>::insertAt(unsigned int pos, const Key&key, const Value &value)
{
    if(pos>size())
        return false;

    Element * temp = head;

    for(unsigned int i = 0; i<pos; i++)
    {
        temp=temp->next;
    }

    Element * newElement;
    newElement = new Element;

    newElement->key=key;
    newElement->value=value;
    newElement->next=newElement;
    newElement->prev=newElement;

    if(!temp)
    {
        head=tail=newElement;
    }
    else
    {
        newElement->next=temp;
        newElement->prev=temp->prev;

        temp->prev->next=newElement;
        temp->prev=newElement;
    }

    if(pos==0){
        head=newElement;
   }else if(pos==size()){
        tail=newElement;
   }
    return true;
}

template<typename Key,typename Value>
bool Ring<Key,Value>::insertAfter(const Key&keypos, const Key&key, const Value &value)
{
    Element * temp = head;
    bool found = false;

    while(temp)
    {
        if(temp->key==keypos)
        {
            found=true;
            break;
        }
        if(temp==tail)
            break;
        temp=temp->next;
    }

    if(!found)
        return false;

    Element * newElement;
    newElement = new Element;
    newElement->key=key;
    newElement->value=value;

    newElement->next=temp->next;
    newElement->prev=temp;

    temp->next->prev=newElement;
    temp->next=newElement;

    if(head==tail){
        head=tail=newElement;
    }else if(temp==tail){
        tail=newElement;
    }
    return true;
}

template<typename Key,typename Value>
bool Ring<Key,Value>::insertAfter(const iterator & iter, const Key&key, const Value &value)
{
    Element * temp = head;
    bool found = false;
    iterator comp;

    while(temp)
    {
        comp=temp;
        if(comp==iter)
        {
            found=true;
            break;
        }
        if(temp==tail)
            break;
        temp=temp->next;
    }

    if(!found)
        return false;

    Element * newElement;
    newElement = new Element;
    newElement->key=key;
    newElement->value=value;

    newElement->next=temp->next;
    newElement->prev=temp;

    temp->next->prev=newElement;
    temp->next=newElement;

    if(head==tail)
        head=tail=newElement;
    else if(temp==tail)
        tail=newElement;

    return true;
}


template<typename Key, typename Value>
void Ring<Key,Value>::push_front(const Key&key, const Value &value)
{
    Element * newElement;

    newElement = new Element;
    newElement->key = key;
    newElement->value = value;

    if(head)
    {
        newElement->next = head;
        newElement->prev = tail;
        tail->next=newElement;
        head->prev=newElement;
        head=newElement;
    }
    else
    {
        newElement->next = newElement;
        newElement->prev = newElement;
        head=tail=newElement;
    }
}

template<typename Key, typename Value>
void Ring<Key,Value>::push_back(const Key&key,  const Value &value)
{
    Element * newElement;

    newElement = new Element;
    newElement->key = key;
    newElement->value = value;

    if(head)
    {
        newElement->next = head;
        newElement->prev = tail;
        tail->next=newElement;
        head->prev=newElement;
        tail=newElement;
    }
    else
    {
        newElement->next = newElement;
        newElement->prev = newElement;
        head=tail=newElement;
    }
}


template<typename Key, typename Value>
bool Ring<Key,Value>::remove(const Key&key)
{
    Element* temp = head;
    while(temp)
    {
        if(temp->key==key)
        {
            if(head==tail)
            {
                delete temp;
                head = tail = NULL;
                size--;
                return;
            }
            else
            {
                temp->next->prev=temp->prev;
                temp->prev->next=temp->next;
                size--;
                delete temp;
                return;
            }
        }
        if(temp==tail)
            break;
        temp=temp->next;
    }
}

template<typename Key, typename Value>
bool Ring<Key,Value>::remove(iterator& iter)
{
    if(iter.isNull())
        return false;
    Element* temp = head;
    iterator comp;
    while(temp)
    {
        comp = temp;
        if(comp==iter)
        {
            iter++;
            if(head==tail)
            {
                delete temp;
                head = tail = NULL;
                return true;
            }
            else
            {
                if(temp==head)
                    head=temp->next;
                else if(temp==tail)
                    tail=temp->prev;
                temp->next->prev=temp->prev;
                temp->prev->next=temp->next;
                delete temp;
                return true;
            }
        }
        if(temp==tail)
            break;
        temp=temp->next;
    }
    return false;
}

template<typename Key, typename Value>
bool Ring<Key,Value>::removeAllOf(const Key&key)
{
    Element* temp = head;
    bool deleted = false;
    while(temp)
    {
        if(temp->key==key)
        {
            deleted=true;
            if(head==tail)
            {
                delete temp;
                head = tail = NULL;
                return deleted;
            }
            else
            {
                if(temp==head)
                    head=temp->next;
                else if(temp==tail)
                    tail=temp->prev;
                temp->next->prev=temp->prev;
                temp->prev->next=temp->next;
                delete temp;
            }
        }
        if(temp==tail)
            break;
        temp=temp->next;
    }
    return deleted;
}




template<typename Key, typename Value>
bool Ring<Key,Value>::exists(const Key&key)
{
    Element * temp = head;
    while(temp)
    {
        if(temp->key==key)
            return true;
        temp=temp->next;
    }
    return false;
}


template<typename Key, typename Info>
typename Ring<Key, Info>::iterator Ring<Key, Info>::find(const Key &where) const
{
    iterator iter = begin();
    if (head != NULL)
    {
        do
        {
            if (iter.getKey() == where)
            {
                return iter;
            }
            iter++;
        }
        while (iter != begin());
    }
    return NULL;
}


template <typename Key, typename Info>
typename Ring<Key, Info>::iterator Ring<Key, Info>::findPlace(int place) const
{
    iterator iter = begin();
    int position = 0;
    if (head != NULL)
    {

        do
        {
            if (position == place)
            {
                return iter;
            }
            iter++;
            position++;
        }
        while (iter != begin());
    }
    return NULL;
}


template <typename Key, typename Info>
bool Ring<Key, Info>::findNodePlace(int place) const
{
    iterator iter = find(place);
    if (iter == NULL)
    {
        return false;
    }
    else
    {
        return true;
    }
}


#endif // BIRING_H_INCLUDED
\$\endgroup\$
  • \$\begingroup\$ ("Coming" from CLASS SIMSET, I'd love to see a contemporary take.) Can you please summarise, as an introduction to the longish code, a) interface (/envisioned usage) b) your goal in coding this? (I appreciate the hint in tagging reinventing-the-wheel - tell me more) \$\endgroup\$ – greybeard May 25 at 6:23
  • \$\begingroup\$ I just would like to learn from my mistakes and have a perfect implementation of the this \$\endgroup\$ – segipiw104 May 25 at 7:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.