In the library I'm working on, we have datasets (which may be subsets of other datasets) that are allocated in memory in three-dimensional rectangular alternating arrays. That is, an array A can be indexed as A(i,j,k) , where each index is in the range from zero to some upper bound, and the location of each element in memory is specified:
A(i,j,k) = A0 + i * A_stride_i + j * A_stride_j + k * A_stride_k
where A0 is the base pointer, and A_stride_i et al. are dimensional steps.
Now, since these data sets can be subsets of other data sets, and not each one occupying their own independent malloc'ed memory block, it is quite possible that they can overlap (when overlapping means that A(i,j,k) < B(m,n,p) not always true, always false), and if they overlap, they can alternate with each other or can collide with each other (where collide means that A(i,j,k) == B(m,n,p) for some sextet of indices).
This is the question. Some operations on two data sets (for example, a copy) are valid only if the arrays do not collide with each other, but are valid if they overlap with an alternation that does not collide with each other. I would like to add a function for two datasets when faced with two datasets.
Is there an existing algorithm for this in a reasonably reasonable and simple way?
It is easy enough to check if the data sets overlap or not, so the key question is: given the two sets of data of this form that overlap, what is an effective algorithm for determining if they intersect or collide?
Example:
As a simple example, suppose we have memory cells from 0 to F (in hexadecimal format):
0 1 2 3 4 5 6 7 8 9 ABCDEF
Here I will just consider only 2D arrays, for simplicity. Suppose we have one size 2,3 (i.e. 0 <= i < 2 and 0 <= j < 3 ), with stride_i = 1 and stride_j = 4 , at base address 2. This will occupy (with occupied places indicated by their i, j pair):
0 1 2 3 4 5 6 7 8 9 ABCDEF * * * * * *
Similarly, if we have another array of the same sizes and steps, starting at base address 4, it will look like this:
0 1 2 3 4 5 6 7 8 9 ABCDEF oooooo
In the terminology that I used to describe the problem, these arrays "overlap", but they do not collide.
Limitations and Assumptions:
We can assume that the steps are positive and, if desired, increase them. None of the things are true in a real library, but it makes sense to just change the definition of an array to get to that point.
We can assume that arrays do not alternate with each other. It is also not provided by the library, but it will be a pathological case and can be prevented separately. That is (assuming that the steps are in ascending order, and i changes from zero to max_i , etc.):
stride_j >= max_i * stride_istride_k >= max_j * stride_j
The points, of course, are for methods that do not require these assumptions, since rebuilding the array definition in the canonical order is a bit of work that perfectly avoided.
You cannot assume that two arrays have the same dimensions or steps.
I do not think that there is value in tracking things during construction - there is no information that arises during construction that is not available during the test. In addition, “building” can simply “consider a subset of this larger array with this base pointer, these steps, and these dimensions.”
Worst Probable Cases
Svick's answer reminds me that I should probably add something about some of the typical "worst" cases that I expect this to be seen. One of the worst will be when we have an array that represents a very large number of complex values stored in sequential (real, imaginary) pairs, and then we have two subarrays containing respectively the real and imaginary parts, you have several million elements in an array alternating between arrays. Since this is not an unlikely event, it should be checked with something other than insane performance.