arrayEdit.h

Go to the documentation of this file.

//
// Copyright 2025 Pixar
//
// Licensed under the terms set forth in the LICENSE.txt file available at
// https://openusd.org/license.
//
 
#ifndef PXR_BASE_VT_ARRAY_EDIT_H
#define PXR_BASE_VT_ARRAY_EDIT_H
 
 
#include "pxr/pxr.h"
#include "pxr/base/vt/api.h"
#include "pxr/base/vt/array.h"
#include "pxr/base/vt/arrayEditOps.h"
#include "pxr/base/vt/streamOut.h"
#include "pxr/base/vt/traits.h"
 
#include "pxr/base/arch/hints.h"
#include "pxr/base/tf/diagnostic.h"
#include "pxr/base/tf/functionRef.h"
#include "pxr/base/tf/hash.h"
#include "pxr/base/tf/span.h"
#include "pxr/base/trace/trace.h"
 
#include <iosfwd>
#include <type_traits>
 
PXR_NAMESPACE_OPEN_SCOPE
 
template <class ELEM>
class VtArrayEditBuilder; // fwd
 
template <class ELEM>
class VtArrayEdit
{
public:
    using Array = VtArray<ELEM>;
 
    using ElementType = typename Array::ElementType;
 
    VtArrayEdit() = default;
 
    friend bool operator==(VtArrayEdit const &x, VtArrayEdit const &y) {
        return std::tie(x._literals, x._ops) == std::tie(y._literals, y._ops);
    }
    friend bool operator!=(VtArrayEdit const &x, VtArrayEdit const &y) {
        return !(x == y);
    }
    
    bool IsIdentity() const {
        return _ops.IsEmpty();
    }
 
    TfSpan<const ElementType> GetLiterals() const {
        return _literals;
    }
 
    TfSpan<ElementType> GetMutableLiterals() {
        return _literals;
    }
 
    VtArrayEdit ComposeOver(VtArrayEdit const &weaker) && {
        if (IsIdentity()) {
            return weaker;
        }
        return _ComposeEdits(weaker);
    }
 
    VtArrayEdit ComposeOver(VtArrayEdit &&weaker) && {
        if (IsIdentity()) {
            return std::move(weaker);
        }
        return _ComposeEdits(std::move(weaker));
    }
 
    VtArrayEdit ComposeOver(VtArrayEdit const &weaker) const & {
        if (IsIdentity()) {
            return weaker;
        }
        return _ComposeEdits(weaker);
    };
    
    VtArrayEdit ComposeOver(VtArrayEdit &&weaker) const & {
        if (IsIdentity()) {
            return std::move(weaker);
        }
        return _ComposeEdits(std::move(weaker));
    }
 
    Array ComposeOver(Array const &weaker) const {
        if (IsIdentity()) {
            return weaker;
        }
        return _ApplyEdits(weaker);
    }
 
    Array ComposeOver(Array &&weaker) const {
        if (IsIdentity()) {
            return std::move(weaker);
        }
        return _ApplyEdits(std::move(weaker));
    }
 
    friend std::ostream &
    operator<<(std::ostream &out, const VtArrayEdit self) {
        auto streamElem = [&](int64_t index) -> std::ostream & {
            return VtStreamOut(self._literals[index], out);
        };
        return Vt_ArrayEditStreamImpl(
            self._ops, self._literals.size(), streamElem, out);
    }
 
    template <class UnaryOp>
    std::ostream &
    StreamCustom(std::ostream &out, UnaryOp &&unaryOp) const {
        auto streamElem = [&](int64_t index) -> std::ostream & {
            return VtStreamOut(
                std::forward<UnaryOp>(unaryOp)(_literals[index]),
                out);
        };
        return Vt_ArrayEditStreamImpl(_ops, _literals.size(), streamElem, out);
    }
 
private:
    friend class VtArrayEditBuilder<ELEM>;
    friend struct Vt_ArrayEditHashAccess;
 
    VT_API friend
    std::ostream &Vt_ArrayEditStreamImpl(
        Vt_ArrayEditOps const &ops, size_t literalsSize,
        TfFunctionRef<std::ostream &(int64_t index)> elemToStr,
        std::ostream &out);
    
    using _Ops = Vt_ArrayEditOps;
    
    Array _ApplyEdits(Array &&weaker) const;
    Array _ApplyEdits(Array const &weaker) const {
        return _ApplyEdits(Array {weaker});
    }
 
    VtArrayEdit _ComposeEdits(VtArrayEdit &&weaker) &&;
    VtArrayEdit _ComposeEdits(VtArrayEdit const &weaker) &&;
    
    VtArrayEdit _ComposeEdits(VtArrayEdit &&weaker) const & {
        return VtArrayEdit(*this)._ComposeEdits(std::move(weaker));
    }
    VtArrayEdit _ComposeEdits(VtArrayEdit const &weaker) const & {
        return VtArrayEdit(*this)._ComposeEdits(weaker);
    }
    
    Array _literals;
    _Ops _ops;
};
 
VT_API
std::ostream &Vt_ArrayEditStreamImpl(
    Vt_ArrayEditOps const &ops, size_t literalsSize,
    TfFunctionRef<std::ostream &(int64_t index)> streamElem,
    std::ostream &out);
 
struct Vt_ArrayEditHashAccess
{
    template <class HashState, class Edit>
    static void Append(HashState &h, Edit const &edit) {
        h.Append(edit._literals, edit._ops);
    }
};
 
template <class HashState, class ELEM>
std::enable_if_t<VtIsHashable<ELEM>()>
TfHashAppend(HashState &h, VtArrayEdit<ELEM> const &edit) {
    Vt_ArrayEditHashAccess::Append(h, edit);
}
 
template <class ELEM>
VtArray<ELEM>
VtArrayEdit<ELEM>::_ApplyEdits(Array &&weaker) const
{
    TRACE_FUNCTION();
 
    // weaker is an array that we edit.
    Array result = std::move(weaker);
    Array const &cresult = result;
 
    Array const &literals = _literals;
    const auto numLiterals = literals.size();
 
    // Each insert and erase below shifts the elements that follow it, so an
    // edit containing k of them costs O(k * n).  Writes and insert & erase at
    // the end are cheap.  Measured on a 100k-element array with 1000 inserts at
    // index 0: about 7 ms for int elements and about 220 ms for 128-byte
    // elements.  With k in the tens it is well under a millisecond even for
    // large arrays, so this has not been worth addressing yet.
    //
    // Two approaches were considered.  Batching a run of inserts or erases into
    // a single pass only works when the indexes within the run are monotone,
    // since otherwise each index is relative to a different intermediate array.
    // Removing the O(k * n) behavior in general requires constant-time indexing
    // together with constant-time positional insertion, which is not possible;
    // the achievable bound is O(n + k log n) using an order-statistic structure
    // over the insert positions, and OpWriteRef and OpInsertRef complicate that
    // because they read array contents at intermediate points in the editing
    // sequence.  Either is worth revisiting if an insert/erase edit pattern
    // appears with k in the hundreds or more over a large array.
 
    _ops.ForEachValid(numLiterals, cresult.size(),
    [&](_Ops::Op op, int64_t a1, int64_t a2) {
        switch (op) {
        case _Ops::OpWriteLiteral:
            result[a2] = literals[a1];
            break;
        case _Ops::OpWriteRef: // a1: result index -> a2: result index.
            result[a2] = cresult[a1];
            break;
        case _Ops::OpInsertLiteral: // a1: literal index -> a2: result index.
            result.insert(result.cbegin() + a2, literals[a1]);
            break;
        case _Ops::OpInsertRef: // a1: result index -> a2: result index.
            result.insert(result.cbegin() + a2, cresult[a1]);
            break;
        case _Ops::OpEraseRef: // a1: result index, (a2: unused)
            result.erase(result.cbegin() + a1);
            break;
        case _Ops::OpMinSize:  // a1: minimum size, (a2: unused)
            if (result.size() < static_cast<size_t>(a1)) {
                result.resize(a1);
            }
            break;
        case _Ops::OpMinSizeFill:  // a1: minimum size, a2: literal index.
            if (result.size() < static_cast<size_t>(a1)) {
                result.resize(a1, literals[a2]);
            }
            break;
        case _Ops::OpSetSize:  // a1: explicit size, (a2: unused)
            result.resize(a1);
            break;
        case _Ops::OpSetSizeFill:  // a1: explicit size, a2: literal index.
            result.resize(a1, literals[a2]);
            break;
        case _Ops::OpMaxSize:  // a1: maximum size, a2: unused
            if (result.size() > static_cast<size_t>(a1)) {
                result.resize(a1);
            }
            break;
        };
    });
    return result;
}
 
template <class ELEM>
VtArrayEdit<ELEM>
VtArrayEdit<ELEM>::_ComposeEdits(VtArrayEdit const &weaker) &&
{
    TRACE_FUNCTION();
 
    // Both this and weaker consist of edits. We compose the edits and we can
    // steal our resources.
 
    // Composing an edit over itself: we move from *this below, which would
    // leave weaker moved-from before we read it.  Compose over a copy instead.
    if (ARCH_UNLIKELY(this == &weaker)) {
        VtArrayEdit weakerCopy = weaker;
        return std::move(*this)._ComposeEdits(std::move(weakerCopy));
    }
 
    // Composition is a plain concatenation: weaker's ops run first, then ours.
    // Deduplicating literals, dropping unreferenced literals and merging
    // adjacent op runs are all done by VtArrayEditBuilder::Optimize(), which
    // callers may invoke on the result.  They are deliberately not done here,
    // since composing N edits would then rescan the whole accumulated op stream
    // N times.
 
    VtArrayEdit result = std::move(*this);
 
    // Place weaker's literals ahead of ours, so weaker's literal indexes remain
    // valid and only ours need adjusting.
    const int64_t numWeakerLiterals = weaker._literals.size();
    result._literals.insert(
        result._literals.begin(),
        weaker._literals.begin(), weaker._literals.end());
    result._ops.OffsetLiteralIndexes(numWeakerLiterals);
 
    result._ops._ins.insert(result._ops._ins.begin(),
                            weaker._ops._ins.begin(),
                            weaker._ops._ins.end());
 
    return result;
}
 
template <class ELEM>
VtArrayEdit<ELEM>
VtArrayEdit<ELEM>::_ComposeEdits(VtArrayEdit &&weaker) &&
{
    TRACE_FUNCTION();
    
    // Both this and weaker consist of edits. We compose the edits and we can
    // steal both our resources and weaker's.
 
    // As in the other overload, composing an edit over itself has to go through
    // a copy, since we move from *this below.
    if (ARCH_UNLIKELY(this == &weaker)) {
        VtArrayEdit weakerCopy = weaker;
        return std::move(*this)._ComposeEdits(std::move(weakerCopy));
    }
 
    // Composition is a plain concatenation: weaker's ops run first, then ours.
    // See the comment in the other _ComposeEdits() overload regarding why no
    // further optimization happens here.
 
    VtArrayEdit result = std::move(*this);
 
    const int64_t numWeakerLiterals = weaker._literals.size();
 
    // Append our literals to weaker's, so weaker's literal indexes remain valid
    // and only ours need adjusting.
    weaker._literals.insert(
        weaker._literals.end(),
        std::make_move_iterator(result._literals.begin()),
        std::make_move_iterator(result._literals.end()));
 
    result._ops.OffsetLiteralIndexes(numWeakerLiterals);
 
    // Append the stronger ops to weaker.
    weaker._ops._ins.insert(
        weaker._ops._ins.end(),
        std::make_move_iterator(result._ops._ins.begin()),
        std::make_move_iterator(result._ops._ins.end()));
 
    return std::move(weaker);
}
 
// Specialize traits for VtArrayEdit.
template <typename T>
struct VtIsArrayEdit<VtArrayEdit<T>> : public std::true_type {};
 
// VtArrayEdit can transform if the underlying element type can.
template <class ELEM>
struct VtValueTypeCanTransform<VtArrayEdit<ELEM>> :
    VtValueTypeCanTransform<ELEM> {};
 
// VtArrayEdit can compose over itself, VtArray, and the VtBackground.
template <class T>
struct VtValueTypeCanCompose<VtArrayEdit<T>> : std::true_type {};
 
PXR_NAMESPACE_CLOSE_SCOPE
 
#endif // PXR_BASE_VT_ARRAY_EDIT_H