Wrap-Around Array (wa-array, aka Cyclic Array)

Environment:

Wrap-around array is implemented in the form of a class template (Warr class) and thus allows elements of any type. The idea of such an array is to have it in the form of a loop.

If S - size of the wa-array, then indices 0,1,2...,S-1 point to all elements of that array. But unlike a normal array, indices beyond this range are also valid. This is modulo S arithmetic. Indices S,S+1,S+2,... point to the same elements as 0,1,2.... Negative indices are also valid. -1,-2,-3,... point to the same elements as S-1,S-2,S-3,....

In addition to normal index operations, wa-array allows you to work with a special, continuous subarray of elements using four basic methods: AddBeg(), AddEnd(), RemBeg(), and RemEnd(). The first and last indices of this subarray are identified by the BegI() and EndI() methods. From this point of view, wa-array should be considered as a container that can be filled with elements using the above methods. Elements can be added either to the beginning of a subarray or to its end. Also, either the first or the last element can be removed from a subarray, decreasing its size.

When a subarray occupies the entire wa-array, adding a new element to the beginning would result in overwriting the last element of a subarray, and, conversly, adding to the end would overwrite the first element of a subarray. No special action is performed when an array element is removed using RemBeg() or RemEnd(); rather, internal indexes specifying the beginning/end of subarray are corrected.

About memory management. There are two options: to have an external buffer for array elements or to let an object constructor allocate a buffer of the appropriate size. An automatically allocated buffer is always deallocated when wa-array is deleted.

Following is a description of the Warr class methods.

Constructors/destructor and related methods

Warr()

This is the default constructor. It creates an empty container that is a non-valid wa-array. Memory is not allocated for the array (that's why it is non-valid). The Reconstruct() method should be used to allocate (or assign) memory of a specified size.

Warr(SZ arr_size, _T *arr=NULL)

This constructor creates a wa-array of arr_size size. If pointer .arr. is equal to NULL, the constructor allocates its own buffer to keep arr_size elements of type _T; otherwise (arr is not equal NULL), this address specifies an external buffer with the assumed size of arr_size elements. If the buffer allocation fails, an exception will be thrown. If the program executes in the environment where a new operator returns a NULL pointer instead of throwing an exception, failure to allocate the buffer would result in a non-valid object.

virtual ~Warr()

The destructor deallocates a buffer if it was allocated by the constructor.

bool Reconstruct(SZ arr_size, _T *arr=NULL)

This method reconstructs the object to the new wa-array. The old buffer is deallocated if necessary and a new one is allocated (if necessary). This method is similar to the second constructor. If buffer allocation is not necessary or it is allocated successfully, Reconstruct() will return true. In the case of a buffer allocation failure, either an exception will be thrown or Reconstruct will return false and the object will be invalid.

void Init()

This method deletes all elements a subarray identified by the BegI(),EndI() indices. After this method, Num() will return 0 and BegI()>EndI(). No special action is performed to delete the elements of the subarray; rather, an initialization of indices is performed.

bool isValid(void) const

Validity of wa-array means that a buffer for its elements exists.

Methods and operators

_T& operator[](IND i)
const _T& operator[](IND i) const

These operators allow you to use an index to address any element of wa-array. Any number of the IND type is valid and points to some element of wa-array as described above. This element may either belong to a subarray identified by BegI(), EndI(), or lay outside it.

void AddBeg(const _T& elem)

Adds an element to the beginning of a subarray by assigning it to the previous element of wa-array.

void AddEnd(const _T& elem)

Adds an element to the end of a subarray by assigning it to the next element of wa-array.

void RemBeg(void)

Removes the first element of a subarray.

void RemEnd(void)

Removes the last element of a subarray.

bool CheckI(IND i) const

Checks if the index points to the element of a subarray. Even when CheckI returns true, index i may not fall within the range of BegI(),EndI(), but the following will be always true:

BegI()<=LoopI(i)<=EndI()

IND LoopI(IND i) const

Adjusts index i to the range of indices BegI(),EndI() that specify a subarray. If index i points to an element that belongs to a subarray, then BegI()<=LoopI(i)<=EndI(); otherwise, LoopI(i) falls outside the range of BegI(),EndI().

IND NormI(IND i) const

Index normalization. The method returns a non-negative index from 0,1,2,...Size()-1, where Size() is a size of the wrap-around array. The returned index points to the same element as an argument i.

IND BegI(void) const
IND EndI(void) const

These methods return the range of indices that identify a subarry. EndI() is always normalized. BegI() may be either positive or negative. The following is true:

if Num()==0 then BegI()>EndI()
if Num()==1 then BegI()==EndI()
if Num()>1 then BegI()<EndI()

SZ Num(void) const

The method returns the number of elements in a subarray. This can be any number from 0 to Size().

SZ Size(void) const
Returns the size of wa-array.

Examples

One of the primary utilizations of wa-array is a work with dynamical subarray, using the AddBeg(), AddEnd(), RemBeg(), and RemEnd() methods.

One thing that should be noted is that when a subarray grows using the AddBeg(),AddEnd() methods, indices BegI(),EndI() may not change sequentially. Due to modulo arithmetic, they may "jump" from time to time.

Warr<int> a(3); // a.BegI()==1, a.EndI()==0, a.Num()==0
a.AddEnd(-45);  // a.BegI()==1, a.EndI()==1, a.Num()==1
a.AddBeg(100);  // a.BegI()==0, a.EndI()==1, a.Num()==2
a.AddBeg(200);  // a.BegI()==-1, a.EndI()==1, a.Num()==3
a.AddEnd(444);  // a.BegI()==0, a.EndI()==2, a.Num()==3
a.AddBeg(600);  // a.BegI()==-1, a.EndI()==1, a.Num()==3
a.AddBeg(222);  // a.BegI()==-2, a.EndI()==0, a.Num()==3
a.AddBeg(333);  // a.BegI()==0, a.EndI()==2, a.Num()==3

That means the BegI(),EndI() method should always be used for correct subarray indices:

typedef Warr<int>::IND WAInd;
typedef Warr<int>::SZ WASize;

for(WAInd i=a.BegI();i<=a.EndI();i++)
  a[i] = -1; // initialization of all elements of a subarray

In the following example, as the subarray grows, it is checked that a particular element of an array is overwritten.

WAInd i=elem_ind; // assuming that a.BegI()<=a.LoopI(i)<=a.EndI()

while(a.NormI(i)!=a.NormI(a.End()))
   // indices are normalized to make correct comparison
   a.AddEnd(<some value>);

Template for wrap-around array

*/
// Copyright © 2002 Nikolai Borissov
// Permission is granted to use and distribute this software for free,
// as long as the copyright and this notice appear.

#ifndef __TL__
#define __TL__

#include <new>

template <typename _T>
class Warr
{ public:
    typedef short SZ;
    typedef int IND;
  private:
    _T *_arr; // array of elements of any type
    SZ _size; // size of the array
    bool _is_alloc; // indicates that array is
                    // allocated and should be freed
    SZ bi,ei; // begin, end indices of inserted elements
              // subarray
    void free() {if(_is_alloc) delete[]_arr;};
  public:
    // Constructors and related methods
    Warr():_arr(NULL),_size(0),_is_alloc(false) {Init();};
   explicit
    Warr(SZ arr_size, _T *arr=NULL) {new(this)Warr();
        Reconstruct(arr_size,arr);};
    virtual ~Warr() {free();};
    bool Reconstruct(SZ arr_size, _T *arr=NULL)
      { _T *p;
      if(arr_size<=0) return false;
      if((p=arr)==NULL) { p = new _T[arr_size];
                            if(p==NULL) return false;
                        };
        free();
        _arr = p;
        _size = arr_size;
        _is_alloc = arr==NULL;
        Init();
        return true;
      }
    void Init() {bi=1;ei=0;};
    bool isValid(void) const {return _arr!=NULL;};
    // Methods and operators; should be used for a valid
    // object only (no check)
    _T& operator[](IND i) {return _arr[NormI(i)];};
    const _T& operator[](IND i) const {return _arr[NormI(i)];};
    void AddBeg(const _T& elem) { ei-=ei-(--bi)==_size;
                                  if(ei==-1) {bi=0;ei=_size-1;};
                                  _arr[bi>=0?bi:bi+_size]=elem;
                                };
    void AddEnd(const _T& elem) { bi+=++ei-bi==_size;
                                  if(ei==_size) {bi-=_size;ei=0;};
                                  _arr[ei]=elem;
                                };
    void RemBeg(void) {bi+=bi<=ei;};
    void RemEnd(void) {ei-=bi<=ei;if(ei==-1){bi+=_size;
        ei=_size-1;}};
    bool CheckI(IND i) const {i=NormI(i);return(i>=bi&&
        (i<=ei||i-_size>=bi));};
    IND LoopI(IND i) const {i=NormI(i);return(i<=ei?i:i-_size);};
    IND NormI(IND i) const {i%=_size;return(i>=0?i:i+_size);};
    IND BegI(void) const {return bi;};
    IND EndI(void) const {return ei;};
    SZ Num(void) const {return ei-bi+1;};
    SZ Size(void) const {return _size;};
};

#endif



Comments

  • grid in mfc

    Posted by conluanho on 07/07/2006 10:41pm

    i don't know how to use database in visual c++ mfc,can you help me? thanhks

    Reply
  • use of this

    Posted by Legacy on 10/31/2003 12:00am

    Originally posted by: D. Robinson

    i am using this in a multi-threaded state machine. the wrap around feature allow threads to cycle through the array without having to pay much attention to how many elements. Threads can continously "wrap" through the items until all processing is "complete" (no more elements).

    Reply
  • Use?

    Posted by Legacy on 07/26/2002 12:00am

    Originally posted by: Bill

    Could you give an example of what such a class could/would be used for?

    Reply
Leave a Comment
  • Your email address will not be published. All fields are required.

Top White Papers and Webcasts

  • As all sorts of data becomes available for storage, analysis and retrieval - so called 'Big Data' - there are potentially huge benefits, but equally huge challenges...
  • The agile organization needs knowledge to act on, quickly and effectively. Though many organizations are clamouring for "Big Data", not nearly as many know what to do with it...
  • Cloud-based integration solutions can be confusing. Adding to the confusion are the multiple ways IT departments can deliver such integration...

Most Popular Programming Stories

More for Developers

RSS Feeds

Thanks for your registration, follow us on our social networks to keep up-to-date