CodeGuru content and product recommendations are editorially independent. We may make money when you click on links to our partners. Learn More.
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
