Class SBCContainerBuffer#
template <class T>
ClassList > SBCContainerBuffer
#include <SBCContainerBuffer.hpp>
Classes#
| Type | Name |
|---|---|
| class | const_iterator |
| class | const_reverse_iterator |
| class | iterator |
| class | reverse_iterator |
Public Functions#
| Type | Name |
|---|---|
| SBCContainerBuffer () Constructs an empty buffer. |
|
| SBCContainerBuffer (unsigned int i) Constructs a buffer with size i . |
|
| SBCContainerBuffer (const SBCContainerBuffer & buffer) Copy constructor. |
|
| SBCContainerBuffer (SBCContainerBuffer && buffer) Move constructor. |
|
| void | addElement (const T & t) Adds the element t to the buffer. |
| 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. |
| bool | empty () const Returns true if and only if the buffer is empty. |
| 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. |
| void | flush () Flushes the buffer. |
| bool | getChangedElementFlag (unsigned int i) const Returns true if and only if element i was changed since the last buffer flush. |
| unsigned int | getChangedElementIndex (unsigned int i) const Returns the index of the i-th changed element. |
| T const & | getElement (unsigned int i) const Returns a const reference to element i . |
| SBTime | getLastFlushTime () const Returns the last flush time. |
| unsigned int | getMemoryFootPrint () const Returns the memory footprint of the buffer. |
| unsigned int | getNumberOfChangedElements () const Returns the number of changed elements since the last buffer flush. |
| void | insertElement (unsigned int i, const T & t) Inserts element t at positioni . |
| SBCContainerBuffer & | operator= (const SBCContainerBuffer & buffer) Copy assignment. |
| SBCContainerBuffer & | operator= (SBCContainerBuffer && buffer) Move assignment. |
| T const & | operator[] (unsigned int i) const Returns a const reference to element i . |
| void | print (unsigned int offset=0) const Prints some debugging information. |
| 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. |
| void | removeElement (unsigned int i) Removes the element with index i from the buffer. |
| 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. |
| void | setElement (unsigned int i, const T & t) Sets the value of element i tot . |
| unsigned int | size () const Returns the size of the buffer. |
| virtual | ~SBCContainerBuffer () Destructs the buffer. |
Detailed Description#
This template class describes an extensible array of elements that may be incrementally changed.
Template parameters:
TThe 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 output 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:
We then initialize the buffer with the initial input values:
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:
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
See also: SB_FOR
Public Functions Documentation#
function SBCContainerBuffer [1/4]#
Constructs an empty buffer.
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).
function SBCContainerBuffer [2/4]#
Constructs a buffer with size i .
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).
function SBCContainerBuffer [3/4]#
Copy constructor.
function SBCContainerBuffer [4/4]#
Move constructor.
function addElement#
Adds the element t to the buffer.
This function appends the element t to the buffer. The new element is added to the list of changed elements.
function begin [1/2]#
Returns an iterator that points to the beginning of the vector containing the indices of the changed elements.
function begin [2/2]#
Returns an iterator that points to the beginning of the vector containing the indices of the changed elements.
function empty#
Returns true if and only if the buffer is empty.
function end [1/2]#
Returns an iterator that points to the end of the vector containing the indices of the changed elements.
function end [2/2]#
Returns an iterator that points to the end of the vector containing the indices of the changed elements.
function flush#
Flushes the buffer.
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.
See also: getNumberOfChangedElements
function getChangedElementFlag#
Returns true if and only if element i was changed since the last buffer flush.
function getChangedElementIndex#
Returns the index of the i-th changed element.
This function returns the index of the i-th changed element.
See also: getNumberOfChangedElements
function getElement#
Returns a const reference to element i .
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.
See also: setElement
function getLastFlushTime#
Returns the last flush time.
This function returns the last flush time, i.e. the time at which the flush function was called.
See also: flush
function getMemoryFootPrint#
Returns the memory footprint of the buffer.
function getNumberOfChangedElements#
Returns the number of changed elements since the last buffer flush.
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.
See also: flush, getChangedElementIndex, setElement, size
function insertElement#
Inserts element t at positioni .
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).
function operator=#
Copy assignment.
function operator=#
Move assignment.
function operator[]#
Returns a const reference to element i .
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.
See also: setElement
function print#
Prints some debugging information.
function rbegin [1/2]#
Returns a reverse iterator that points to the reverse beginning of the vector containing the indices of the changed elements.
function rbegin [2/2]#
Returns a reverse iterator that points to the reverse beginning of the vector containing the indices of the changed elements.
function removeElement#
Removes the element with index i from the buffer.
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.
function rend [1/2]#
Returns a reverse iterator that points to the reverse end of the vector containing the indices of the changed elements.
function rend [2/2]#
Returns a reverse iterator that points to the reverse end of the vector containing the indices of the changed elements.
function setElement#
Sets the value of element i tot .
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.
See also: flush, getNumberOfChangedElements, getChangedElementIndex
function size#
Returns the size of the buffer.
This function returns the number of elements in the buffer.
function ~SBCContainerBuffer#
Destructs the buffer.