#include <iostream>
#include <stdlib.h>

using namespace std;

////////////////////////////////////////////////////////////////////////////////

template <class Type>

class RingLink
{
////////////////////////////////////////////////////////////////////////////////

protected:

    RingLink * next;
    Type value;
    int position;

////////////////////////////////////////////////////////////////////////////////

public:

    RingLink()
    {
        next     = this;
        value    = 0;
        position = 0;
    }
    RingLink(int v1, int p1)
    {
        next     = this;
        value    = v1;
        position = p1;
    }

    ////////////////////////////////////////////////////////////////////////////

    Type & GetValue()
    {
        return value;
    }

    void SetValue(Type p1)
    {
        value = p1;
    }

    int GetPos()
    {
        return position;
    }

    void SetPos(int p1)
    {
        position = p1;
    }

    RingLink * GetNext()
    {
        return next;
    }

    RingLink * SetNext(RingLink * p1)
    {
        next = p1;
        return p1;
    }

    RingLink * Add(RingLink * p1)
    {
        p1->next = next;
        next = p1;
        return p1;
    }

    void RemoveNext()
    {
        RingLink * rem = next;
        next = next->next;
        delete rem;
    }

};

////////////////////////////////////////////////////////////////////////////////

template <class Type>

class VirtualArray
{

protected:

    RingLink< Type > * ring;
    int linkCount;
    int maxLinkCount;

    RingLink< Type > * CreateLink(int pos)
    {
        linkCount++;
        return new RingLink< Type >(0, pos);
    }

    void RemoveNextLink(RingLink< Type > * link)
    {
        linkCount--;
        link->RemoveNext();
    }

public:

    VirtualArray()
    {
        ring = NULL;
        linkCount = 0;
        maxLinkCount = 0;
    }

    int GetLenght()
    {
        return linkCount;
    }

    Type & operator[](int pos)
    {
        RingLink< Type > * curr = ring, * prev = NULL;

        if (ring)
        {
            do
            {

                if (curr->GetPos() == pos)
                    return curr->GetValue();

                prev = curr;
                curr = curr->GetNext();

                if (curr->GetValue() == 0)
                {
                    if (curr != ring)
                    {
                        RemoveNextLink(prev);
                        curr = prev->GetNext();
                    }
                    else
                    {
                        RemoveNextLink(prev);
                        curr = prev->GetNext();
                        ring = curr;
                    }
                }
            }
            while (curr != ring);

            return ring->Add(CreateLink(pos))->GetValue();
        }
        else
        {
            ring = CreateLink(pos);
            return ring->GetValue();
        }
    }


    void Clear()
    {
        RingLink< Type > * curr = ring->GetNext(), * prev = NULL;

        while (curr != ring)
        {
            prev = curr;
            curr = (curr->GetNext());
            delete prev;
        }

        linkCount = 0;
        delete ring;
        ring = NULL;
    }

    void Shift(int p1, int m1 = 0)
    {
        RingLink< Type > * curr = ring;
        int sc = 0;

        if (m1 && (m1 < linkCount))
            m1 = linkCount;

        do
        {
            if (m1 && ((curr->GetPos() + p1) >= m1))
                curr->SetPos(sc++);
            else
                curr->SetPos(curr->GetPos() + p1);
            curr = curr->GetNext();
        }
        while (curr != ring);
    }

    void Print()
    {
        RingLink< Type > * curr = NULL;
        if (ring)
        {
            curr = ring->GetNext();
            cout << "[" << ring->GetValue();
            while (curr != ring)
            {
                cout << ", " << curr->GetValue();
                curr = curr->GetNext();
            }
            cout << "]" << endl;
        }
    }
};

int main()
{
    VirtualArray< int > va1;
    srandomdev();

    for (int i=0; i<20; i++)
    {
        va1[i] = random() % 100;
    }

    cout << "A: " << endl;
    for (int i=0; i<20; i++)
        cout << "a[" << i << "] = " << va1[i] << endl;
    cout << "A = ";
    va1.Print();

    cout << "Shift on 1 element toward:" << endl;

    va1.Shift(1, 20);

    cout << "A: " << endl;
    for (int i=0; i<20; i++)
        cout << "a[" << i << "] = " << va1[i] << endl;
    cout << "A = ";
    va1.Print();

    cout << "Count of elements = " << va1.GetLenght();
    getchar();
    return 0;
}