std::vector<UsdProperty>
UsdPrim::_GetPropertiesInNamespace(const std::string &namespaces,
                                   bool onlyAuthored) const
{
    // XXX Would be nice to someday plumb the prefix search down through pcp
    if (namespaces.empty())
        return onlyAuthored ? GetAuthoredProperties() : GetProperties();

    const char delim = UsdObject::GetNamespaceDelimiter();

    TfTokenVector names = _GetPropertyNames(onlyAuthored, /*applyOrder=*/false);

    // Set terminator to the expected position of the delimiter after all the
    // supplied namespaces.  We perform an explicit test for this char below
    // so that we don't need to allocate a new string if namespaces does not
    // already end with the delimiter
    const size_t terminator = namespaces.size() -
        (*namespaces.rbegin() == delim);

    // Prune out non-matches before we sort
    size_t insertionPt = 0;
    for (const auto& name : names) {
        const std::string &s = name.GetString();
        if (s.size() > terminator               &&
            TfStringStartsWith(s, namespaces)   && 
            s[terminator] == delim) {

            names[insertionPt++] = name;
        }
    }
    names.resize(insertionPt);
    sort(names.begin(), names.end(), TfDictionaryLessThan());
    _ApplyOrdering(GetPropertyOrder(), &names);
    return _MakeProperties(names);
}

HdRenderPassSharedPtr const &
Hd_TestDriver::GetRenderPass(bool withGuides)
{
    if (withGuides) {
        if (!_geomAndGuidePass) {
            TfTokenVector renderTags;
            renderTags.push_back(HdTokens->geometry);
            renderTags.push_back(HdTokens->guide);
            
            HdRprimCollection col = HdRprimCollection(
                                     HdTokens->geometry,
                                     _reprSelector);
            col.SetRenderTags(renderTags);
            _geomAndGuidePass = HdRenderPassSharedPtr(
                new Hd_UnitTestNullRenderPass(&_sceneDelegate->GetRenderIndex(), col));
        }
        return _geomAndGuidePass;
    } else {
        if (!_geomPass) {
            TfTokenVector renderTags;
            renderTags.push_back(HdTokens->geometry);

            HdRprimCollection col = HdRprimCollection(
                                        HdTokens->geometry,
                                        _reprSelector);
            col.SetRenderTags(renderTags);
            _geomPass = HdRenderPassSharedPtr(
                new Hd_UnitTestNullRenderPass(&_sceneDelegate->GetRenderIndex(), col));
        }
        return _geomPass;
    }
}

GlfTextureHandleRefPtr
GlfTextureRegistry::GetTextureHandle(const TfTokenVector &textures)
{
    if (textures.empty()) {
        TF_WARN("Attempting to register arrayTexture with empty token vector.");
        return GlfTextureHandlePtr();
    }

    const size_t numTextures = textures.size();
    // We register an array texture with the
    // path of the first texture in the array
    TfToken texture = textures[0];
    GlfTextureHandleRefPtr textureHandle;

    _TextureMetadata md(textures);

    // look into exisiting textures
    std::map<TfToken, _TextureMetadata>::iterator it =
        _textureRegistry.find(texture);
    
    if (it != _textureRegistry.end() && it->second.IsMetadataEqual(md)) {
        textureHandle = it->second.GetHandle();
    } else {
        // if not exists, create it
        textureHandle = _CreateTexture(textures, numTextures);
        md.SetHandle(textureHandle);
        _textureRegistry[texture] = md;
    }

    return textureHandle;
}

TfTokenVector
HdPerfLog::GetCacheNames()
{
    _Lock lock(_mutex);
    TfTokenVector names;
    names.reserve(_cacheMap.size());
    TF_FOR_ALL(tokCacheIt, _cacheMap) {
        names.push_back(tokCacheIt->first);
    }

void
HdPoints::_PopulateVertexPrimVars(HdDrawItem *drawItem,
                                  HdChangeTracker::DirtyBits *dirtyBits)
{
    HD_TRACE_FUNCTION();
    HD_MALLOC_TAG_FUNCTION();

    SdfPath const& id = GetId();
    HdSceneDelegate* delegate = GetDelegate();
    HdResourceRegistry *resourceRegistry = &HdResourceRegistry::GetInstance();

    // The "points" attribute is expected to be in this list.
    TfTokenVector primVarNames = delegate->GetPrimVarVertexNames(id);
    TfTokenVector const& vars = delegate->GetPrimVarVaryingNames(id);
    primVarNames.insert(primVarNames.end(), vars.begin(), vars.end());

    HdBufferSourceVector sources;
    sources.reserve(primVarNames.size());

    int pointsIndexInSourceArray = -1;

    TF_FOR_ALL(nameIt, primVarNames) {
        if (not HdChangeTracker::IsPrimVarDirty(*dirtyBits, id, *nameIt))
            continue;

        // TODO: We don't need to pull primvar metadata every time a value
        // changes, but we need support from the delegate.

        //assert name not in range.bufferArray.GetResources()
        VtValue value = delegate->Get(id, *nameIt);

        if (!value.IsEmpty()) {
            // Store where the points will be stored in the source array
            // we need this later to figure out if the number of points is changing
            // and we need to force a garbage collection to resize the buffer
            if (*nameIt == HdTokens->points) {
                pointsIndexInSourceArray = sources.size();
            }

            // XXX: do we need special treatment for width as basicCurves?

            HdBufferSourceSharedPtr source(new HdVtBufferSource(*nameIt, value));
            sources.push_back(source);
        }
    }

    // return before allocation if it's empty.
    if (sources.empty())
        return;

    if (not drawItem->GetVertexPrimVarRange() or
            not drawItem->GetVertexPrimVarRange()->IsValid()) {
        // initialize buffer array
        HdBufferSpecVector bufferSpecs;
        TF_FOR_ALL(it, sources) {
            (*it)->AddBufferSpecs(&bufferSpecs);
        }

TfTokenVector
UsdMayaShadingModeRegistry::_ListImporters() {
    TfRegistryManager::GetInstance().SubscribeTo<UsdMayaShadingModeImportContext>();
    TfTokenVector ret;
    ret.reserve(_importReg.size());
    for (const auto& e : _importReg) {
        ret.push_back(e.first);
    }
    return ret;
}

std::string
SdfPath::JoinIdentifier(const TfTokenVector& names)
{
    std::vector<std::string> tmp;
    tmp.reserve(names.size());
    for (size_t i = 0, n = names.size(); i != n; ++i) {
        if (!names[i].IsEmpty()) {
            tmp.push_back(names[i].GetString());
        }
    }
    return TfStringJoin(tmp, SdfPathTokens->namespaceDelimiter.GetText());
}

UsdImaging_TestDriver::UsdImaging_TestDriver(UsdStageRefPtr const& usdStage)
 : _engine()
 , _renderDelegate()
 , _renderIndex(nullptr)
 , _delegate(nullptr)
 , _geometryPass()
 , _renderPassState()
 , _stage()
{
    TfTokenVector renderTags;
    renderTags.push_back(HdTokens->geometry);
    _Init(usdStage, HdTokens->geometry, HdTokens->hull, renderTags);
}

TfTokenVector
UsdMayaAdaptor::SchemaAdaptor::GetAttributeNames() const
{
    if (!*this) {
        return TfTokenVector();
    }

    TfTokenVector attrNames;
    for (const SdfAttributeSpecHandle attr : _schemaDef->GetAttributes()) {
        attrNames.push_back(attr->GetNameToken());
    }

    return attrNames;
}

UsdMayaAdaptor::SchemaAdaptor
UsdMayaAdaptor::ApplySchemaByName(
    const TfToken& schemaName,
    MDGModifier& modifier)
{
    if (!*this) {
        TF_CODING_ERROR("Adaptor is not valid");
        return SchemaAdaptor();
    }

    // Get the schema's TfType; its name should be registered as an alias.
    const TfType schemaType =
            TfType::Find<UsdSchemaBase>().FindDerivedByName(schemaName);

    // Make sure that this is an API schema. Only API schemas can be applied.
    if (!schemaType.IsA<UsdAPISchemaBase>()) {
        TF_CODING_ERROR("'%s' is not a registered API schema",
                schemaName.GetText());
        return SchemaAdaptor();
    }

    // Make sure that this is an "apply" schema.
    if (!UsdSchemaRegistry::GetInstance().IsAppliedAPISchema(schemaType)) {
        TF_CODING_ERROR("'%s' is not an applied API schema",
                schemaName.GetText());
        return SchemaAdaptor();
    }

    // Get the schema definition. If it's registered, there should be a def.
    SdfPrimSpecHandle primDef =
            UsdSchemaRegistry::GetInstance().GetPrimDefinition(schemaName);
    if (!primDef) {
        TF_CODING_ERROR("Can't find schema definition for name '%s'",
                schemaName.GetText());
        return SchemaAdaptor();
    }

    // Add to schema list (if not yet present).
    TfTokenVector currentSchemas = GetAppliedSchemas();
    if (std::find(currentSchemas.begin(), currentSchemas.end(), schemaName) ==
            currentSchemas.end()) {
        currentSchemas.push_back(schemaName);
        SetMetadata(
                UsdTokens->apiSchemas,
                _GetListOpForTokenVector(currentSchemas),
                modifier);
    }

    return SchemaAdaptor(_handle.object(), primDef);
}

GlfTextureHandleRefPtr
GlfTextureRegistry::_CreateTexture(const TfTokenVector &textures,
                                   const size_t numTextures)
{
    GlfTextureRefPtr result;
    TfToken filename = textures.empty() ? TfToken() : textures.front();
    if (GlfTextureFactoryBase* factory = _GetTextureFactory(filename)) {
        result = factory->New(textures);
        if (!result) {
            TF_CODING_ERROR("[PluginLoad] Cannot construct texture for "
                            "type '%s'\n",
                            TfStringGetSuffix(filename).c_str());
        }
    }
    return result ? GlfTextureHandle::New(result) : TfNullPtr;
}

// Change the order of items in 'names' so that all the things in 'order' that
// are also in 'names' are at the beginning in the order that they appear in
// 'order', followed by any remaining items in 'names' in their existing order.
static void
_ApplyOrdering(const TfTokenVector &order, TfTokenVector *names)
{
    // If order is empty or names is empty, nothing to do.
    if (order.empty() || names->empty())
        return;

    // Perf note: this walks 'order' and linear searches 'names' to find each
    // element, for O(M*N) operations, where M and N are the lengths of 'order'
    // and 'names'.  We hope 1) that propertyOrder stmts are relatively rare and
    // 2) that property lists are relatively short.  If those assumptions fail,
    // this may need revisiting.  In some quick microbenchmarking, this linear
    // search seems to outperform binary search up to about 5000 names.  We
    // suspect this is because linear search does TfToken pointer comparisons,
    // while binary search has to dereference and do string comparisons.

    typedef TfTokenVector::iterator Iter;

    Iter namesRest = names->begin(), namesEnd = names->end();
    for (const TfToken &oName: order) {
        // Look for this name from 'order' in the rest of 'names'.
        Iter i = std::find(namesRest, namesEnd, oName);
        if (i != namesEnd) {
            // Found.  Move to the front by rotating the sub-range.  Using
            // std::rotate invokes swap(), which avoids TfToken refcounting.
            // Also advance 'namesRest' to the next element.
            std::rotate(namesRest++, i, i+1);
        }
    }
}

/* static */
UsdUISceneGraphPrimAPI
UsdUISceneGraphPrimAPI::Apply(const UsdStagePtr &stage, const SdfPath &path)
{
    // Ensure we have a valid stage, path and prim
    if (!stage) {
        TF_CODING_ERROR("Invalid stage");
        return UsdUISceneGraphPrimAPI();
    }

    if (path == SdfPath::AbsoluteRootPath()) {
        TF_CODING_ERROR("Cannot apply an api schema on the pseudoroot");
        return UsdUISceneGraphPrimAPI();
    }

    auto prim = stage->GetPrimAtPath(path);
    if (!prim) {
        TF_CODING_ERROR("Prim at <%s> does not exist.", path.GetText());
        return UsdUISceneGraphPrimAPI();
    }

    TfToken apiName("SceneGraphPrimAPI");  

    // Get the current listop at the edit target
    UsdEditTarget editTarget = stage->GetEditTarget();
    SdfPrimSpecHandle primSpec = editTarget.GetPrimSpecForScenePath(path);
    SdfTokenListOp listOp = primSpec->GetInfo(UsdTokens->apiSchemas)
                                    .UncheckedGet<SdfTokenListOp>();

    // Append our name to the prepend list, if it doesnt exist locally
    TfTokenVector prepends = listOp.GetPrependedItems();
    if (std::find(prepends.begin(), prepends.end(), apiName) != prepends.end()) { 
        return UsdUISceneGraphPrimAPI();
    }

    SdfTokenListOp prependListOp;
    prepends.push_back(apiName);
    prependListOp.SetPrependedItems(prepends);
    auto result = listOp.ApplyOperations(prependListOp);
    if (!result) {
        TF_CODING_ERROR("Failed to prepend api name to current listop.");
        return UsdUISceneGraphPrimAPI();
    }

    // Set the listop at the current edit target and return the API prim
    primSpec->SetInfo(UsdTokens->apiSchemas, VtValue(*result));
    return UsdUISceneGraphPrimAPI(prim);
}

std::vector<GfBBox3d>
PxrUsdKatanaUsdInArgs::ComputeBounds(
        const UsdPrim& prim)
{
    std::vector<GfBBox3d> ret;

    std::vector<UsdGeomBBoxCache>& bboxCaches = _bboxCaches.local();

    // Initialize the bounding box cache if it hasn't yet been initialized.
    //
    bool needsInit = bboxCaches.size() != _motionSampleTimes.size();
    if (needsInit)
    {
        // XXX: selected purposes should be driven by the UI. 
        // See usdGeom/imageable.h GetPurposeAttr() for allowed values. 
        TfTokenVector includedPurposes;  
        includedPurposes.push_back(UsdGeomTokens->default_); 
        includedPurposes.push_back(UsdGeomTokens->render); 
    
        bboxCaches.resize(_motionSampleTimes.size(),  
            UsdGeomBBoxCache(
                _currentTime, includedPurposes, /* useExtentsHint */ true)); 
        
        for (size_t index = 0; index < _motionSampleTimes.size(); ++index)
        {
            double relSampleTime = _motionSampleTimes[index];
            double time = _currentTime + relSampleTime;
            bboxCaches[index].SetTime(time);
        }
    }

    FnKat::DoubleBuilder boundBuilder(6);

    // There must be one bboxCache per motion sample, for efficiency purposes.
    if (not TF_VERIFY(bboxCaches.size() == _motionSampleTimes.size()))
    {
        return ret;
    }

    for (size_t i = 0; i < _motionSampleTimes.size(); i++)
    {
        ret.push_back(bboxCaches[i].ComputeUntransformedBound(prim));
    }

    return ret;
}

UsdRelationshipVector
UsdPrim::_GetRelationships(bool onlyAuthored, bool applyOrder) const
{
    const TfTokenVector names = _GetPropertyNames(onlyAuthored, applyOrder);
    UsdRelationshipVector rels;

    // PERFORMANCE: This is sloppy, since property names are a superset of
    // relationship names, however this vector is likely short lived and worth
    // the trade off of repeated reallocation.
    rels.reserve(names.size());
    for (const auto& propName : names) {
        if (UsdRelationship rel = GetRelationship(propName)) {
            rels.push_back(rel);
        }
    }

    return rels;
}

void
Hd_PrimTypeIndex<PrimType>::InitPrimTypes(const TfTokenVector &primTypes)
{
    size_t primTypeCount = primTypes.size();
    _entries.resize(primTypeCount);

    for (size_t typeIdx = 0; typeIdx < primTypeCount; ++typeIdx) {
        _index.emplace(primTypes[typeIdx], typeIdx);
    }
}

TfTokenVector
UsdPrim::_GetPropertyNames(bool onlyAuthored, bool applyOrder) const
{
    TfTokenVector names;

    // If we're including unauthored properties, take names from definition, if
    // present.
    if (!onlyAuthored) {
        UsdSchemaRegistry::HasField(GetTypeName(), TfToken(),
                                    SdfChildrenKeys->PropertyChildren, &names);
    }

    // Add authored names, then sort and apply ordering.
    GetPrimIndex().ComputePrimPropertyNames(&names);
    if (applyOrder) {
        sort(names.begin(), names.end(), TfDictionaryLessThan());
        _ApplyOrdering(GetPropertyOrder(), &names);
    }
    return names;
}

 virtual GlfTextureRefPtr New(const TfTokenVector& texturePaths,
                              GlfImage::ImageOriginLocation originLocation = 
                                             GlfImage::OriginUpperLeft) const
 {
     return GlfArrayTexture::New(texturePaths, 
                                 texturePaths.size(), 
                                 /*cropTop*/ 0,
                                 /*cropBottom*/ 0,
                                 /*cropLeft*/ 0,
                                 /*cropRight*/ 0,
                                 originLocation);
 }

std::vector<UsdProperty>
UsdPrim::_MakeProperties(const TfTokenVector &names) const
{
    std::vector<UsdProperty> props;
    UsdStage *stage = _GetStage();
    props.reserve(names.size());
    for (auto const &propName : names) {
        SdfSpecType specType = stage->_GetDefiningSpecType(*this, propName);
        if (specType == SdfSpecTypeAttribute) {
            props.push_back(GetAttribute(propName));
        } else if (TF_VERIFY(specType == SdfSpecTypeRelationship)) {
            props.push_back(GetRelationship(propName));
        }
    }
    return props;
}

GlfTextureRegistry::_TextureMetadata::_TextureMetadata(
    const TfTokenVector &textures)
    : _TextureMetadata(textures.data(), textures.size())
{}