SBCContainerBuffer< T > Class Template Reference

This template class describes an extensible array of elements that may be incrementally changed. More...

## Constructors and destructors

SBCContainerBuffer ()
Constructs an empty buffer. More...

SBCContainerBuffer (unsigned int i)
Constructs a buffer with size i. More...

SBCContainerBuffer (const SBCContainerBuffer &buffer)
Copy constructor.

SBCContainerBuffer (SBCContainerBuffer &&buffer)
Move constructor.

virtual ~SBCContainerBuffer ()
Destructs the buffer.

## Basic operations

SBCContainerBufferoperator= (const SBCContainerBuffer &buffer)
Copy assignment.

SBCContainerBufferoperator= (SBCContainerBuffer &&buffer)
Move assignment.

T const & operator[] (unsigned int i) const
Returns a const reference to element i. More...

T const & getElement (unsigned int i) const
Returns a const reference to element i. More...

unsigned int size () const
Returns the size of the buffer. More...

bool empty () const
Returns true if and only if the buffer is empty.

## Buffer management

Adds the element t to the buffer. More...

void insertElement (unsigned int i, const T &t)
Inserts element t at position i. More...

void removeElement (unsigned int i)
Removes the element with index i from the buffer. More...

SBTime getLastFlushTime () const
Returns the last flush time. More...

void flush ()
Flushes the buffer. More...

## Change operations

unsigned int getNumberOfChangedElements () const
Returns the number of changed elements since the last buffer flush. More...

unsigned int getChangedElementIndex (unsigned int i) const
Returns the index of the i-th changed element. More...

bool getChangedElementFlag (unsigned int i) const
Returns true if and only if element i was changed since the last buffer flush.

void setElement (unsigned int i, const T &t)
Sets the value of element i to t. More...

## Iterators

iterator begin ()
Returns an iterator that points to the beginning of the vector containing the indices of the changed elements.

const_iterator begin () const
Returns an iterator that points to the beginning of the vector containing the indices of the changed elements.

iterator end ()
Returns an iterator that points to the end of the vector containing the indices of the changed elements.

const_iterator end () const
Returns an iterator that points to the end of the vector containing the indices of the changed elements.

reverse_iterator rbegin ()
Returns a reverse iterator that points to the reverse beginning of the vector containing the indices of the changed elements.

const_reverse_iterator rbegin () const
Returns a reverse iterator that points to the reverse beginning of the vector containing the indices of the changed elements.

reverse_iterator rend ()
Returns a reverse iterator that points to the reverse end of the vector containing the indices of the changed elements.

const_reverse_iterator rend () const
Returns a reverse iterator that points to the reverse end of the vector containing the indices of the changed elements.

## Debugging

void print (unsigned int offset=0) const
Prints some debugging information.

unsigned int getMemoryFootPrint () const
Returns the memory footprint of the buffer.

## Detailed Description

### template<class T> class SBCContainerBuffer< T >

Template Parameters
 T The type of the elements contained in the buffer

Consider a classical force-field. Typically, many terms in the potential energy function only depend on a few atoms positions. For example, a bond term may only depend on the relative positions of two atoms. Whatever the size of the molecular system, if only a few atoms moved between two subsequent time steps, then only some energy terms and some forces need to be updated. An algorithm which manages to update only those terms that need to change is called incremental, and is typically much more efficient than a non-incremental algorithm that would update all energy terms and all forces when only a few atoms have moved.

In general, assume a group of output values (e.g. the forces in the example above) depend on a group of input values (the atomic positions in the example above), Assume moreover that these output values need to be updated at successive update times (for example at each time step of a simulation). Incremental algorithms manage to maintain up-to-date all output values, by updating only those ouput values that need to be changed, based on changes in the input values that occurred since the last update time.

One important task that all incremental algorithms have to achieve is thus to determine which input values changed since the last update time. This is what buffers do: they store values in an array, and track which values changed since a given time.

Assume for example that we want to incrementally maintain the sum of a group of 100 double values, without having to recompute the sum from scratch at each update time. One possibility is thus to store these values in a buffer of double:

SBBuffer<double> buffer;

We then initialize the buffer with the initial input values:

// initialize the buffer
for (unsigned int i=0; i < 100; i++) buffer.addElement(0.0);

In general, a buffer may actually be created and stored in a different object, and we simply have access to it. For example, a particle system maintains a position buffer which stores the cartesian coordinates of all particles, and an interaction model may use this position buffer to perform incremental updates of energies and forces.

It is thus frequently useful, on the client side, to store a copy of the values contained in the buffer, in order to have access to the previous values. This copy is typically performed during a (non-incremental) initialization:

// compute the initial value of the sum
double sum = 0.0;
double previousValueArray[100];
for (unsigned int i=0; i < 100; i++) {
sum += buffer[i];
previousValueArray[i] = buffer[i];
}
buffer.flush();

Note the call to the flush function, which empties the list of changed elements.

We may now enter a cycle of incremental updates of the sum, where some buffer values change:

buffer.setElement(17, 1.0); // set buffer[17] to 1.0
buffer.setElement(8, 2.0); // set buffer[8] to 2.0
buffer.setElement(75, 3.0); // set buffer[75] to 3.0
buffer.setElement(99, 4.0); // set buffer[99] to 4.0
buffer.setElement(75, 5.0); // set buffer[75] to 5.0
buffer.flush();

In this example, the value of buffer[75] is changed twice, but the buffer only stores the fact that this value changed, and not the number of times it changed between two flushes. As a result, the list of changed elements only contains four indices: 17, 8, 75 and 99.

In this simple example, we could incrementally update the sum whenever we are notified that one value in the buffer changed. For example, assuming the value of buffer[17] changed from oldValue to newValue, we could do:

sum += newValue - oldValue; // incrementally update the sum

In general, though, updating output values may be computationally expensive, and it may thus be preferable to compute the required changes only when needed, based on the list of changed input values:

// incrementally update the value of the sum
for (unsigned int i=0; i < buffer.getNumberOfChangedElements(); i++) {
unsigned int changedElementIndex = buffer.getChangedElementIndex(i);
sum += buffer[changedElementIndex] - previousValueArray[changedElementIndex];
previousValueArray[changedElementIndex] = buffer[changedElementIndex];
}
buffer.flush();

In this example, the function getNumberOfChangedElements returns 4, and the function getChangedElementIndex successively returns 17, 8, 75 and 99. Note how the array of previous values is updated once each previous value has been used to incrementally update the sum. The complexity of the sum update is linear in the number of changed elements, which may be significantly faster than re-computing the sum from scratch when the number of changed elements is small compared to the total number of elements.

Short name: SBBuffer

SB_FOR

## ◆ SBCContainerBuffer() [1/2]

template<class T >
 SBCContainerBuffer< T >::SBCContainerBuffer ( )
inline

This constructs creates an empty buffer. Note that this assumes that the template parameter T has a constructor that takes no parameter (i.e. it is possible to initialize an array of elements of type T).

## ◆ SBCContainerBuffer() [2/2]

template<class T >
 SBCContainerBuffer< T >::SBCContainerBuffer ( unsigned int i )
inline

This constructor fills the buffer with default values of the template type T. Note that this assumes that the template parameter T has a constructor that takes no parameter (i.e. it is possible to initialize an array of elements of type T).

## Member Function Documentation

template<class T >
 void SBCContainerBuffer< T >::addElement ( const T & t )
inline

This function appends the element t to the buffer. The new element is added to the list of changed elements.

## ◆ flush()

template<class T >
 void SBCContainerBuffer< T >::flush ( )
inline

This function flushes the buffer, i.e. clears the list of changed elements and sets the last flush time to the current time. After a call to flush, getNumberOfChangedElements returns 0.

getNumberOfChangedElements

## ◆ getChangedElementIndex()

template<class T >
 unsigned int SBCContainerBuffer< T >::getChangedElementIndex ( unsigned int i ) const
inline

This function returns the index of the i-th changed element.

getNumberOfChangedElements

## ◆ getElement()

template<class T >
 T const& SBCContainerBuffer< T >::getElement ( unsigned int i ) const
inline

This function returns a const reference to element i. Since the buffer needs to track changes to the array elements, this function cannot be used to modify the value of an element. Instead, use the setElement function.

setElement

## ◆ getLastFlushTime()

template<class T >
 SBTime SBCContainerBuffer< T >::getLastFlushTime ( ) const
inline

This function returns the last flush time, i.e. the time at which the flush function was called.

flush

## ◆ getNumberOfChangedElements()

template<class T >
 unsigned int SBCContainerBuffer< T >::getNumberOfChangedElements ( ) const
inline

Whenever an element of the buffer is set to a new value (i.e. a call to setElement actually changes the value of the element), the buffer memorizes the index of the changed element. This function returns the total number of changed elements since the last buffer flush.

Note that the buffer does not memorize the number of times an element has been changed since the last buffer flush, but only the fact that it has been changed. As a result, the number of changed elements is always between 0 and the size of the buffer.

flush
getChangedElementIndex
setElement
size

## ◆ insertElement()

template<class T >
 void SBCContainerBuffer< T >::insertElement ( unsigned int i, const T & t )
inline

This function inserts element t at position i. If i is strictly larger than the size of the buffer, the function does nothing.

Important: when i is strictly smaller than the size of the buffer, the inserted element displaces an element, which moves to the last position of the buffer. If this displaced element had been changed since the last buffer flush, the corresponding index is changed in the list of changed elements.

Example: assume a buffer contains 99 elements (these elements could be integers, strings, positions, forces, etc.), and the list of changed elements contains the indices 17, 8, 75 and 97. If an element is inserted at position 97, then element 97 is moved to the end of the buffer (position 99), and the list of changed elements now contains the indices 17, 8, 75, 99 (corresponding to the moved element), and 97 (corresponding to the new element).

## ◆ operator[]()

template<class T >
 T const& SBCContainerBuffer< T >::operator[] ( unsigned int i ) const
inline

This operator returns a const reference to element i. Since the buffer needs to track changes to the array elements, this operator cannot be used to modify the value of an element. Instead, use the setElement function.

setElement

## ◆ removeElement()

template<class T >
 void SBCContainerBuffer< T >::removeElement ( unsigned int i )
inline

This function removes the element with index i from the buffer.

Important: when the removed element i is not the last element of the array, the last element of the array is moved to position i. In effect, this amounts to changing the index of the last element. If this last element had been changed since the last buffer flush, the corresponding index is changed in the list of changed elements.

Example: assume a buffer contains 100 elements, indexed from 0 to 99 (these elements could be integers, strings, positions, forces, etc.), and the list of changed elements contains the indices 17, 8, 75 and 99. If element 97 is removed from the buffer, then element 99 is moved to position 97, and the list of changed elements now contains the indices 17, 8, 75 and 97.

## ◆ setElement()

template<class T >
 void SBCContainerBuffer< T >::setElement ( unsigned int i, const T & t )
inline

This functions sets the value of element i to t. If the previous value of element i was different from t, the index i is inserted in the set of changed elements.

Note: the index of a changed element is inserted at most once between two calls to the flush function.