Record some algorithms related to intervals operations used in recent work.

Code

Check overlap

Receive two intervals and return whether these two intervals overlap.

If the end point of interval A is to the left of the start point of interval B, or the start point of interval A is to the right of the end point of interval B, then the two intervals do not overlap.

// check overlap
// return true if overlap
// otherwise false
bool CheckOverlap(const std::pair<int, int> &pairInterval1,
   const std::pair<int, int> &pairInterval2)
{
    if (pairInterval2.second < pairInterval1.first || pairInterval2.first > pairInterval1.second)
    {
        return false;
    }
    return true;
}

Compare two buffers and identify intervals where the values differ

The diff table records the bytes between which the data in the two buffers are different, indicating the start and end bytes of these intervals.

void GenerateDiffTable(std::vector<std::pair<int, int>> &vecTable,
    void *pBuffer1, void *pBuffer2, const int BYTE_SIZE, const int SKIP_BYTE)
{
    vecTable.clear();

    const unsigned char *pBytePtr1 = static_cast<const unsigned char *>(pBuffer1);
    const unsigned char *pBytePtr2 = static_cast<const unsigned char *>(pBuffer2);

    int nIndex = SKIP_BYTE;
    const int TOTAL_SIZE = BYTE_SIZE;

    // record intervals with different data
    while(nIndex < TOTAL_SIZE)
    {
        if (pBytePtr1[nIndex] != pBytePtr2[nIndex])
        {
            int nStart = nIndex;
            while (nIndex < TOTAL_SIZE && pBytePtr1[nIndex] != pBytePtr2[nIndex])
            {
                ++nIndex;
            }
            vecTable.push_back({nStart, nIndex - 1});
        }
        else
        {
            ++nIndex;
        }
    }
}

Copy specified interval data to a buffer

vecInterval contains many intervals, and the data within these intervals are copied from pSource to pDest.

void CopyBytesInRange(const std::vector<std::pair<int, int>> &vecInterval,
    void *pDest, void *pSource, const int TOTAL_SIZE)
{
    unsigned char *pBytePtr1 = static_cast<unsigned char *>(pDest);
    const unsigned char *pBytePtr2 = static_cast<const unsigned char *>(pSource);

    for (const auto &item : vecInterval)
    {
        // boundary check
        if (item.second >= TOTAL_SIZE)
        {
            AfxMessageBox("Invalid Table Size!");
            return;
        }

        for (int i = item.first; i <= item.second; ++i)
        {
            pBytePtr1[i] = pBytePtr2[i];
        }
    }
}

Generate intersecting intervals of two sets of intervals

Take two vectors containing multiple intervals and returns the intersections.

For example, if the two vectors are {{1, 3}, {5, 7}} and {{2, 5}}, this function would return {{2, 3}, {5, 5}}.

void GenerateIntervalIntersection(const std::vector<std::pair<int, int>> &vec1,
    const std::vector<std::pair<int, int>> &vec2)
{
    vecEditInterval.clear();
    
    for (const auto &interval1 : vec1)
    {
        for (const auto &interval2 : vec2)
        {
            int nStart = interval1.first > interval2.first ? interval1.first : interval2.first;     // max(interval1.first, interval2.first)
            int nEnd = interval1.second < interval2.second ? interval1.second : interval2.second;   // min(interval1.second, interval.second)

            if (nStart <= nEnd)
            {
                vecEditInterval.push_back({nStart, nEnd});
            }
        }
    }
}

Append vector

template <typename T>
void AppendVector(std::vector<T> &vecDest, const std::vector<T> &vecSource)
{
    vecDest.insert(vecDest.end(), vecSource.begin(), vecSource.end());
}

Compute the size of a fixed-size array

Determine the number of elements in a statically allocated array.

NOTE: This function is specifically designed for arrays with a size determined at compile time. It is not suitable for dynamically allocated arrays or standard library containers like std::vector.

template <typename T, size_t N>
size_t CDialog_EditBatchConfig::GetMemberSize(const T(&)[N])
{
    return N;
}
Outline