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

  • Fake Oakley Commit SQ sale for cheap

    Posted by fyqzvfweo on 06/26/2013 05:10am

    Oakley Sunglasses Sale ,From 1975 to 1980, the Oakley team has been protective glasses produced wild racing into the mainstream. Cannot be denied the truth is how the market equipment and items for girls is far higher than men's accessories market Japanese products. fake oakley sunglasses ,Today, the concept of Oakley sunglasses has occurred a fundamental change, because such glasses being a fashion accessory than whatever else. Every second on the fashion-savvy people, you'll discover that there should be a few Oakley sunglasses, usually the favourite and affordable cheap Oakley sunglasses continues to be provided a fresh meaning of the glasses. OAkley Frogskins ,No doub it is a primary and dissemination of solar ultraviolet radiation. Therefore, especially UVB rays of greater damage, can be quite appealing to ultraviolet light. This can be an unavoidable trendy shapes greatly marked early in the year and hot summer time, many fashion brand masters, design taste, with no intent to streamline the full sense of glasses. Incorrect storage are easily scratched or damaged sunglasses, experts recommend sunglasses are best kept in the drawer of the corresponding glasses box or challenging wet. Men's sporting activities, sunglasses, designer women's sunglasses pilots display usually the favourite faces inside the entertainment business - a message and Oakley will be dependent upon it. From to reside in a sun isn't going to take away the hazard, but nevertheless marked complexion and eyes in the proliferation of lengthy, long-term harm to ultraviolet light to scale back a persons vision, which turned out to be stop the harm towards eye compared to amount of ultraviolet illumination with the individual's life may be great for. Note can not see ultraviolet illumination, the application form Oakley sun block lotion, to lose the sun's ultraviolet radiation power, for example, might be more harmful ultraviolet light, is of interest. The integration of science and art Oakley won over 600 patents worldwide. Today, Jannard's brand has become a prominent symbol of success. Amazing women Armani Sunglasses EA9739 / S, features a beautiful compliment towards large circular cone hinge and sleek metal hinges accent the frame. Information regarding Oakley sunglasses supplier sources could get from the complete network. Use analysis and print to become a member of the exhibition because of the level of data associated with an on-line site. Remember the custom features. Pick-up a little extra color of the icon, and with a few seconds to improve your thing. You want to have your personal unique fashion style, Oakley sunglasses sale is your best option!

    Reply
  • 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

  • Java developers know that testing code changes can be a huge pain, and waiting for an application to redeploy after a code fix can take an eternity. Wouldn't it be great if you could see your code changes immediately, fine-tune, debug, explore and deploy code without waiting for ages? In this white paper, find out how that's possible with a Java plugin that drastically changes the way you develop, test and run Java applications. Discover the advantages of this plugin, and the changes you can expect to see …

  • Cisco and Intel have harnessed flash memory technology and truly innovative system software to blast through the boundaries of today's I/O-bound server/storage architectures. See how they are bringing real-time responsiveness to data-intensive applications—for unmatched business advantage. Sponsored by Cisco and Intel® Partnering in Innovation

Most Popular Programming Stories

More for Developers

Latest Developer Headlines

RSS Feeds