1 //
2 // Copyright 2016 Pixar
3 //
4 // Licensed under the Apache License, Version 2.0 (the "Apache License")
5 // with the following modification; you may not use this file except in
6 // compliance with the Apache License and the following modification to it:
7 // Section 6. Trademarks. is deleted and replaced with:
8 //
9 // 6. Trademarks. This License does not grant permission to use the trade
10 //    names, trademarks, service marks, or product names of the Licensor
11 //    and its affiliates, except as required to comply with Section 4(c) of
12 //    the License and to reproduce the content of the NOTICE file.
13 //
14 // You may obtain a copy of the Apache License at
15 //
16 //     http://www.apache.org/licenses/LICENSE-2.0
17 //
18 // Unless required by applicable law or agreed to in writing, software
19 // distributed under the Apache License with the above modification is
20 // distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
21 // KIND, either express or implied. See the Apache License for the specific
22 // language governing permissions and limitations under the Apache License.
23 //
24 
25 #include "pxr/pxr.h"
26 #include "pxr/usd/sdf/listOp.h"
27 #include "pxr/usd/sdf/path.h"
28 #include "pxr/usd/sdf/payload.h"
29 #include "pxr/usd/sdf/reference.h"
30 #include "pxr/usd/sdf/types.h"
31 #include "pxr/base/tf/diagnostic.h"
32 #include "pxr/base/tf/iterator.h"
33 #include "pxr/base/tf/registryManager.h"
34 #include "pxr/base/tf/type.h"
35 #include "pxr/base/tf/token.h"
36 #include "pxr/base/trace/trace.h"
37 
38 #include <boost/optional.hpp>
39 
40 #include <ostream>
41 
42 using std::string;
43 using std::vector;
44 
45 PXR_NAMESPACE_OPEN_SCOPE
46 
TF_REGISTRY_FUNCTION(TfType)47 TF_REGISTRY_FUNCTION(TfType)
48 {
49     TfType::Define<SdfTokenListOp>()
50         .Alias(TfType::GetRoot(), "SdfTokenListOp");
51     TfType::Define<SdfPathListOp>()
52         .Alias(TfType::GetRoot(), "SdfPathListOp");
53     TfType::Define<SdfStringListOp>()
54         .Alias(TfType::GetRoot(), "SdfStringListOp");
55     TfType::Define<SdfReferenceListOp>()
56         .Alias(TfType::GetRoot(), "SdfReferenceListOp");
57     TfType::Define<SdfPayloadListOp>()
58         .Alias(TfType::GetRoot(), "SdfPayloadListOp");
59     TfType::Define<SdfIntListOp>()
60         .Alias(TfType::GetRoot(), "SdfIntListOp");
61     TfType::Define<SdfUIntListOp>()
62         .Alias(TfType::GetRoot(), "SdfUIntListOp");
63     TfType::Define<SdfInt64ListOp>()
64         .Alias(TfType::GetRoot(), "SdfInt64ListOp");
65     TfType::Define<SdfUInt64ListOp>()
66         .Alias(TfType::GetRoot(), "SdfUInt64ListOp");
67     TfType::Define<SdfUnregisteredValueListOp>()
68         .Alias(TfType::GetRoot(), "SdfUnregisteredValueListOp");
69 
70     TfType::Define<SdfListOpType>();
71 }
72 
TF_REGISTRY_FUNCTION(TfEnum)73 TF_REGISTRY_FUNCTION(TfEnum)
74 {
75     TF_ADD_ENUM_NAME(SdfListOpTypeExplicit);
76     TF_ADD_ENUM_NAME(SdfListOpTypeAdded);
77     TF_ADD_ENUM_NAME(SdfListOpTypePrepended);
78     TF_ADD_ENUM_NAME(SdfListOpTypeAppended);
79     TF_ADD_ENUM_NAME(SdfListOpTypeDeleted);
80     TF_ADD_ENUM_NAME(SdfListOpTypeOrdered);
81 }
82 
83 
84 template <typename T>
SdfListOp()85 SdfListOp<T>::SdfListOp()
86     : _isExplicit(false)
87 {
88 }
89 
90 template <typename T>
91 SdfListOp<T>
CreateExplicit(const ItemVector & explicitItems)92 SdfListOp<T>::CreateExplicit(
93     const ItemVector& explicitItems)
94 {
95     SdfListOp<T> listOp;
96     listOp.SetExplicitItems(explicitItems);
97     return listOp;
98 }
99 
100 template <typename T>
101 SdfListOp<T>
Create(const ItemVector & prependedItems,const ItemVector & appendedItems,const ItemVector & deletedItems)102 SdfListOp<T>::Create(
103     const ItemVector& prependedItems,
104     const ItemVector& appendedItems,
105     const ItemVector& deletedItems)
106 {
107     SdfListOp<T> listOp;
108     listOp.SetPrependedItems(prependedItems);
109     listOp.SetAppendedItems(appendedItems);
110     listOp.SetDeletedItems(deletedItems);
111     return listOp;
112 }
113 
114 template <typename T>
115 void
Swap(SdfListOp<T> & rhs)116 SdfListOp<T>::Swap(SdfListOp<T>& rhs)
117 {
118     std::swap(_isExplicit, rhs._isExplicit);
119     _explicitItems.swap(rhs._explicitItems);
120     _addedItems.swap(rhs._addedItems);
121     _prependedItems.swap(rhs._prependedItems);
122     _appendedItems.swap(rhs._appendedItems);
123     _deletedItems.swap(rhs._deletedItems);
124     _orderedItems.swap(rhs._orderedItems);
125 }
126 
127 template <typename T>
128 bool
HasItem(const T & item) const129 SdfListOp<T>::HasItem(const T& item) const
130 {
131     if (IsExplicit()) {
132         return std::find(_explicitItems.begin(), _explicitItems.end(), item)
133             != _explicitItems.end();
134     }
135 
136     return
137         (std::find(_addedItems.begin(), _addedItems.end(), item)
138             != _addedItems.end()) ||
139         (std::find(_prependedItems.begin(), _prependedItems.end(), item)
140             != _prependedItems.end()) ||
141         (std::find(_appendedItems.begin(), _appendedItems.end(), item)
142             != _appendedItems.end()) ||
143         (std::find(_deletedItems.begin(), _deletedItems.end(), item)
144             != _deletedItems.end()) ||
145         (std::find(_orderedItems.begin(), _orderedItems.end(), item)
146             != _orderedItems.end());
147 }
148 
149 template <typename T>
150 const typename SdfListOp<T>::ItemVector &
GetItems(SdfListOpType type) const151 SdfListOp<T>::GetItems(SdfListOpType type) const
152 {
153     switch(type) {
154     case SdfListOpTypeExplicit:
155         return _explicitItems;
156     case SdfListOpTypeAdded:
157         return _addedItems;
158     case SdfListOpTypePrepended:
159         return _prependedItems;
160     case SdfListOpTypeAppended:
161         return _appendedItems;
162     case SdfListOpTypeDeleted:
163         return _deletedItems;
164     case SdfListOpTypeOrdered:
165         return _orderedItems;
166     }
167 
168     TF_CODING_ERROR("Got out-of-range type value: %d", type);
169     return _explicitItems;
170 }
171 
172 template <typename T>
173 void
SetExplicitItems(const ItemVector & items)174 SdfListOp<T>::SetExplicitItems(const ItemVector &items)
175 {
176     _SetExplicit(true);
177     _explicitItems = items;
178 }
179 
180 template <typename T>
181 void
SetAddedItems(const ItemVector & items)182 SdfListOp<T>::SetAddedItems(const ItemVector &items)
183 {
184     _SetExplicit(false);
185     _addedItems = items;
186 }
187 
188 template <typename T>
189 void
SetPrependedItems(const ItemVector & items)190 SdfListOp<T>::SetPrependedItems(const ItemVector &items)
191 {
192     _SetExplicit(false);
193     _prependedItems = items;
194 }
195 
196 template <typename T>
197 void
SetAppendedItems(const ItemVector & items)198 SdfListOp<T>::SetAppendedItems(const ItemVector &items)
199 {
200     _SetExplicit(false);
201     _appendedItems = items;
202 }
203 
204 template <typename T>
205 void
SetDeletedItems(const ItemVector & items)206 SdfListOp<T>::SetDeletedItems(const ItemVector &items)
207 {
208     _SetExplicit(false);
209     _deletedItems = items;
210 }
211 
212 template <typename T>
213 void
SetOrderedItems(const ItemVector & items)214 SdfListOp<T>::SetOrderedItems(const ItemVector &items)
215 {
216     _SetExplicit(false);
217     _orderedItems = items;
218 }
219 
220 template <typename T>
221 void
SetItems(const ItemVector & items,SdfListOpType type)222 SdfListOp<T>::SetItems(const ItemVector &items, SdfListOpType type)
223 {
224     switch(type) {
225     case SdfListOpTypeExplicit:
226         SetExplicitItems(items);
227         break;
228     case SdfListOpTypeAdded:
229         SetAddedItems(items);
230         break;
231     case SdfListOpTypePrepended:
232         SetPrependedItems(items);
233         break;
234     case SdfListOpTypeAppended:
235         SetAppendedItems(items);
236         break;
237     case SdfListOpTypeDeleted:
238         SetDeletedItems(items);
239         break;
240     case SdfListOpTypeOrdered:
241         SetOrderedItems(items);
242         break;
243     }
244 }
245 
246 template <typename T>
247 void
_SetExplicit(bool isExplicit)248 SdfListOp<T>::_SetExplicit(bool isExplicit)
249 {
250     if (isExplicit != _isExplicit) {
251         _isExplicit = isExplicit;
252         _explicitItems.clear();
253         _addedItems.clear();
254         _prependedItems.clear();
255         _appendedItems.clear();
256         _deletedItems.clear();
257         _orderedItems.clear();
258     }
259 }
260 
261 template <typename T>
262 void
Clear()263 SdfListOp<T>::Clear()
264 {
265     // _SetExplicit will clear all items and set the explicit flag as specified.
266     // Temporarily change explicit flag to bypass check in _SetExplicit.
267     _isExplicit = true;
268     _SetExplicit(false);
269 }
270 
271 template <typename T>
272 void
ClearAndMakeExplicit()273 SdfListOp<T>::ClearAndMakeExplicit()
274 {
275     // _SetExplicit will clear all items and set the explicit flag as specified.
276     // Temporarily change explicit flag to bypass check in _SetExplicit.
277     _isExplicit = false;
278     _SetExplicit(true);
279 }
280 
281 template <typename T>
282 void
ApplyOperations(ItemVector * vec,const ApplyCallback & cb) const283 SdfListOp<T>::ApplyOperations(ItemVector* vec, const ApplyCallback& cb) const
284 {
285     if (!vec) {
286         return;
287     }
288 
289     TRACE_FUNCTION();
290 
291     // Apply edits.
292     // Note that our use of _ApplyMap in the helper functions below winds up
293     // quietly ensuring duplicate items aren't processed in the ItemVector.
294     _ApplyList result;
295     if (IsExplicit()) {
296         _ApplyMap search;
297         _AddKeys(SdfListOpTypeExplicit, cb, &result, &search);
298     }
299     else {
300         size_t numToDelete = _deletedItems.size();
301         size_t numToAdd = _addedItems.size();
302         size_t numToPrepend = _prependedItems.size();
303         size_t numToAppend = _appendedItems.size();
304         size_t numToOrder = _orderedItems.size();
305 
306         if (!cb &&
307             ((numToDelete+numToAdd+numToPrepend+numToAppend+numToOrder) == 0)) {
308             // nothing to do, so avoid copying vectors
309             return;
310         }
311 
312         // Make a list of the inputs.  We can efficiently (O(1)) splice
313         // these elements later.
314         result.insert(result.end(), vec->begin(), vec->end());
315 
316         // Make a map of keys to list iterators.  This avoids O(n)
317         // searches within O(n) loops below.
318         _ApplyMap search;
319         for (typename _ApplyList::iterator i = result.begin();
320              i != result.end(); ++i) {
321             search[*i] = i;
322         }
323 
324         _DeleteKeys (SdfListOpTypeDeleted, cb, &result, &search);
325         _AddKeys(SdfListOpTypeAdded, cb, &result, &search);
326         _PrependKeys(SdfListOpTypePrepended, cb, &result, &search);
327         _AppendKeys(SdfListOpTypeAppended, cb, &result, &search);
328         _ReorderKeys(SdfListOpTypeOrdered, cb, &result, &search);
329     }
330 
331     // Copy the result back to vec.
332     vec->clear();
333     vec->insert(vec->end(), result.begin(), result.end());
334 }
335 
336 template <typename T>
337 boost::optional<SdfListOp<T>>
ApplyOperations(const SdfListOp<T> & inner) const338 SdfListOp<T>::ApplyOperations(const SdfListOp<T> &inner) const
339 {
340     if (IsExplicit()) {
341         // Explicit list-op replaces the result entirely.
342         return *this;
343     }
344     if (GetAddedItems().empty() && GetOrderedItems().empty()) {
345         if (inner.IsExplicit()) {
346             ItemVector items = inner.GetExplicitItems();
347             ApplyOperations(&items);
348             SdfListOp<T> r;
349             r.SetExplicitItems(items);
350             return r;
351         }
352         if (inner.GetAddedItems().empty() &&
353             inner.GetOrderedItems().empty()) {
354 
355              ItemVector del = inner.GetDeletedItems();
356              ItemVector pre = inner.GetPrependedItems();
357              ItemVector app = inner.GetAppendedItems();
358 
359              // Apply deletes
360              for (const auto &x: GetDeletedItems()) {
361                 pre.erase(std::remove(pre.begin(), pre.end(), x), pre.end());
362                 app.erase(std::remove(app.begin(), app.end(), x), app.end());
363                 if (std::find(del.begin(), del.end(), x) == del.end()) {
364                     del.push_back(x);
365                 }
366              }
367              // Apply prepends
368              for (const auto &x: GetPrependedItems()) {
369                 del.erase(std::remove(del.begin(), del.end(), x), del.end());
370                 pre.erase(std::remove(pre.begin(), pre.end(), x), pre.end());
371                 app.erase(std::remove(app.begin(), app.end(), x), app.end());
372              }
373              pre.insert(pre.begin(),
374                         GetPrependedItems().begin(),
375                         GetPrependedItems().end());
376              // Apply appends
377              for (const auto &x: GetAppendedItems()) {
378                 del.erase(std::remove(del.begin(), del.end(), x), del.end());
379                 pre.erase(std::remove(pre.begin(), pre.end(), x), pre.end());
380                 app.erase(std::remove(app.begin(), app.end(), x), app.end());
381              }
382              app.insert(app.end(),
383                         GetAppendedItems().begin(),
384                         GetAppendedItems().end());
385 
386             SdfListOp<T> r;
387             r.SetDeletedItems(del);
388             r.SetPrependedItems(pre);
389             r.SetAppendedItems(app);
390             return r;
391         }
392     }
393 
394     // The result is not well-defined, in general.  There is no way
395     // to express the combined result as a single SdfListOp.
396     //
397     // Example for ordered items:
398     // - let A have ordered items [2,0]
399     // - let B have ordered items [0,1,2]
400     // then
401     // - A over B over [2,1  ] -> [1,2  ]
402     // - A over B over [2,1,0] -> [2,0,1]
403     // and there is no way to express the relative order dependency
404     // between 1 and 2.
405     //
406     // Example for added items:
407     // - let A have added items [0]
408     // - let B have appended items [1]
409     // then
410     // - A over B over [   ] -> [1,0]
411     // - A over B over [0,1] -> [0,1]
412     // and there is no way to express the relative order dependency
413     // between 0 and 1.
414     //
415     return boost::optional<SdfListOp<T>>();
416 }
417 
418 template <class ItemType, class ListType, class MapType>
419 static inline
_InsertIfUnique(const ItemType & item,ListType * result,MapType * search)420 void _InsertIfUnique(const ItemType& item, ListType* result, MapType* search)
421 {
422     if (search->find(item) == search->end()) {
423         (*search)[item] = result->insert(result->end(), item);
424     }
425 }
426 
427 template <class ItemType, class ListType, class MapType>
428 static inline
_InsertOrMove(const ItemType & item,typename ListType::iterator pos,ListType * result,MapType * search)429 void _InsertOrMove(const ItemType& item, typename ListType::iterator pos,
430                    ListType* result, MapType* search)
431 {
432     typename MapType::iterator entry = search->find(item);
433     if (entry == search->end()) {
434         (*search)[item] = result->insert(pos, item);
435     } else if (entry->second != pos) {
436         result->splice(pos, *result, entry->second, std::next(entry->second));
437     }
438 }
439 
440 template <class ItemType, class ListType, class MapType>
441 static inline
_RemoveIfPresent(const ItemType & item,ListType * result,MapType * search)442 void _RemoveIfPresent(const ItemType& item, ListType* result, MapType* search)
443 {
444     typename MapType::iterator j = search->find(item);
445     if (j != search->end()) {
446         result->erase(j->second);
447         search->erase(j);
448     }
449 }
450 
451 template <class T>
452 void
_AddKeys(SdfListOpType op,const ApplyCallback & callback,_ApplyList * result,_ApplyMap * search) const453 SdfListOp<T>::_AddKeys(
454     SdfListOpType op,
455     const ApplyCallback& callback,
456     _ApplyList* result,
457     _ApplyMap* search) const
458 {
459     TF_FOR_ALL(i, GetItems(op)) {
460         if (callback) {
461             if (boost::optional<T> item = callback(op, *i)) {
462                 // Only append if the item isn't already present.
463                 _InsertIfUnique(*item, result, search);
464             }
465         }
466         else {
467             _InsertIfUnique(*i, result, search);
468         }
469     }
470 }
471 
472 template <class T>
473 void
_PrependKeys(SdfListOpType op,const ApplyCallback & callback,_ApplyList * result,_ApplyMap * search) const474 SdfListOp<T>::_PrependKeys(
475     SdfListOpType op,
476     const ApplyCallback& callback,
477     _ApplyList* result,
478     _ApplyMap* search) const
479 {
480     const ItemVector& items = GetItems(op);
481     if (callback) {
482         for (auto i = items.rbegin(), iEnd = items.rend(); i != iEnd; ++i) {
483             if (boost::optional<T> mappedItem = callback(op, *i)) {
484                 _InsertOrMove(*mappedItem, result->begin(), result, search);
485             }
486         }
487     } else {
488         for (auto i = items.rbegin(), iEnd = items.rend(); i != iEnd; ++i) {
489             _InsertOrMove(*i, result->begin(), result, search);
490         }
491     }
492 }
493 
494 template <class T>
495 void
_AppendKeys(SdfListOpType op,const ApplyCallback & callback,_ApplyList * result,_ApplyMap * search) const496 SdfListOp<T>::_AppendKeys(
497     SdfListOpType op,
498     const ApplyCallback& callback,
499     _ApplyList* result,
500     _ApplyMap* search) const
501 {
502     const ItemVector& items = GetItems(op);
503     if (callback) {
504         for (const T& item: items) {
505             if (boost::optional<T> mappedItem = callback(op, item)) {
506                 _InsertOrMove(*mappedItem, result->end(), result, search);
507             }
508         }
509     } else {
510         for (const T& item: items) {
511             _InsertOrMove(item, result->end(), result, search);
512         }
513     }
514 }
515 
516 template <class T>
517 void
_DeleteKeys(SdfListOpType op,const ApplyCallback & callback,_ApplyList * result,_ApplyMap * search) const518 SdfListOp<T>::_DeleteKeys(
519     SdfListOpType op,
520     const ApplyCallback& callback,
521     _ApplyList* result,
522     _ApplyMap* search) const
523 {
524     TF_FOR_ALL(i, GetItems(op)) {
525         if (callback) {
526             if (boost::optional<T> item = callback(op, *i)) {
527                 _RemoveIfPresent(*item, result, search);
528             }
529         }
530         else {
531             _RemoveIfPresent(*i, result, search);
532         }
533     }
534 }
535 
536 template <class T>
537 void
_ReorderKeys(SdfListOpType op,const ApplyCallback & callback,_ApplyList * result,_ApplyMap * search) const538 SdfListOp<T>::_ReorderKeys(
539     SdfListOpType op,
540     const ApplyCallback& callback,
541     _ApplyList* result,
542     _ApplyMap* search) const
543 {
544     // Make a vector and set of the source items.
545     ItemVector order;
546     std::set<ItemType, _ItemComparator> orderSet;
547     TF_FOR_ALL(i, GetItems(op)) {
548         if (callback) {
549             if (boost::optional<T> item = callback(op, *i)) {
550                 if (orderSet.insert(*item).second) {
551                     order.push_back(*item);
552                 }
553             }
554         }
555         else {
556             if (orderSet.insert(*i).second) {
557                 order.push_back(*i);
558             }
559         }
560     }
561     if (order.empty()) {
562         return;
563     }
564 
565     // Move the result aside for now.
566     _ApplyList scratch;
567     std::swap(scratch, *result);
568 
569     // Find each item from the order vector in the scratch list.
570     // Then find the next item in the scratch list that's also in
571     // in the order vector.  All of these items except the last
572     // form the next continuous sequence in the result.
573     TF_FOR_ALL(i, order) {
574         typename _ApplyMap::const_iterator j = search->find(*i);
575         if (j != search->end()) {
576             // Find the next item in both scratch and order.
577             typename _ApplyList::iterator e = j->second;
578             do {
579                 ++e;
580             } while (e != scratch.end() && orderSet.count(*e) == 0);
581 
582             // Move the sequence to result.
583             result->splice(result->end(), scratch, j->second, e);
584         }
585     }
586 
587     // Any items remaining in scratch are neither in order nor after
588     // anything in order.  Therefore they must be first in their
589     // current order.
590     result->splice(result->begin(), scratch);
591 }
592 
593 template <typename T>
594 static inline
595 bool
_ModifyCallbackHelper(const typename SdfListOp<T>::ModifyCallback & cb,std::vector<T> * itemVector)596 _ModifyCallbackHelper(const typename SdfListOp<T>::ModifyCallback& cb,
597                       std::vector<T>* itemVector)
598 {
599     bool didModify = false;
600 
601     std::vector<T> modifiedVector;
602     TF_FOR_ALL(item, *itemVector) {
603         boost::optional<T> modifiedItem = cb(*item);
604         if (!modifiedItem) {
605             didModify = true;
606         }
607         else if (*modifiedItem != *item) {
608             modifiedVector.push_back(*modifiedItem);
609             didModify = true;
610         } else {
611             modifiedVector.push_back(*item);
612         }
613     }
614 
615     if (didModify) {
616         itemVector->swap(modifiedVector);
617     }
618 
619     return didModify;
620 }
621 
622 template <typename T>
623 bool
ModifyOperations(const ModifyCallback & callback)624 SdfListOp<T>::ModifyOperations(const ModifyCallback& callback)
625 {
626     bool didModify = false;
627 
628     if (callback) {
629         didModify |= _ModifyCallbackHelper(callback, &_explicitItems);
630         didModify |= _ModifyCallbackHelper(callback, &_addedItems);
631         didModify |= _ModifyCallbackHelper(callback, &_prependedItems);
632         didModify |= _ModifyCallbackHelper(callback, &_appendedItems);
633         didModify |= _ModifyCallbackHelper(callback, &_deletedItems);
634         didModify |= _ModifyCallbackHelper(callback, &_orderedItems);
635     }
636 
637     return didModify;
638 }
639 
640 template <typename T>
641 bool
ReplaceOperations(const SdfListOpType op,size_t index,size_t n,const ItemVector & newItems)642 SdfListOp<T>::ReplaceOperations(const SdfListOpType op, size_t index, size_t n,
643                                const ItemVector& newItems)
644 {
645     bool needsModeSwitch =
646         (IsExplicit() && op != SdfListOpTypeExplicit) ||
647         (!IsExplicit() && op == SdfListOpTypeExplicit);
648 
649     // XXX: This behavior was copied from GdListEditor, which
650     //      appears to have been copied from old Sd code...
651     //      the circle is now complete.
652     //
653     // XXX: This is to mimic old Sd list editor behavior.  If
654     //      we insert into a list we should automatically change
655     //      modes, but if we replace or remove then we should
656     //      silently ignore the request.
657     if (needsModeSwitch && (n > 0 || newItems.empty())) {
658         return false;
659     }
660 
661     ItemVector itemVector = GetItems(op);
662 
663     if (index > itemVector.size()) {
664         TF_CODING_ERROR("Invalid start index %zd (size is %zd)",
665                         index, itemVector.size());
666         return false;
667     }
668     else if (index + n > itemVector.size()) {
669         TF_CODING_ERROR("Invalid end index %zd (size is %zd)",
670                         index + n - 1, itemVector.size());
671         return false;
672     }
673 
674     if (n == newItems.size()) {
675         std::copy(newItems.begin(), newItems.end(), itemVector.begin() + index);
676     }
677     else {
678         itemVector.erase(itemVector.begin() + index,
679                          itemVector.begin() + index + n);
680         itemVector.insert(itemVector.begin() + index,
681                           newItems.begin(), newItems.end());
682     }
683 
684     SetItems(itemVector, op);
685     return true;
686 }
687 
688 template <typename T>
689 void
ComposeOperations(const SdfListOp<T> & stronger,SdfListOpType op)690 SdfListOp<T>::ComposeOperations(const SdfListOp<T>& stronger, SdfListOpType op)
691 {
692 
693     SdfListOp<T> &weaker = *this;
694 
695     if (op == SdfListOpTypeExplicit) {
696         weaker.SetItems(stronger.GetItems(op), op);
697     }
698     else {
699         const ItemVector &weakerVector = weaker.GetItems(op);
700         _ApplyList weakerList(weakerVector.begin(), weakerVector.end());
701         _ApplyMap weakerSearch;
702         for (typename _ApplyList::iterator i = weakerList.begin();
703                 i != weakerList.end(); ++i) {
704             weakerSearch[*i] = i;
705         }
706 
707         if (op == SdfListOpTypeOrdered) {
708             stronger._AddKeys(op, ApplyCallback(),
709                                  &weakerList, &weakerSearch);
710             stronger._ReorderKeys(op, ApplyCallback(),
711                                   &weakerList, &weakerSearch);
712         } else if (op == SdfListOpTypeAdded) {
713             stronger._AddKeys(op,
714                                  ApplyCallback(),
715                                  &weakerList,
716                                  &weakerSearch);
717         } else if (op == SdfListOpTypeDeleted) {
718             stronger._AddKeys(op,
719                                  ApplyCallback(),
720                                  &weakerList,
721                                  &weakerSearch);
722         } else if (op == SdfListOpTypePrepended) {
723             stronger._PrependKeys(op,
724                                  ApplyCallback(),
725                                  &weakerList,
726                                  &weakerSearch);
727         } else if (op == SdfListOpTypeAppended) {
728             stronger._AppendKeys(op,
729                                  ApplyCallback(),
730                                  &weakerList,
731                                  &weakerSearch);
732         }
733 
734         weaker.SetItems(ItemVector(weakerList.begin(), weakerList.end()), op);
735     }
736 }
737 
738 ////////////////////////////////////////////////////////////////////////
739 // Free functions
740 
741 template <class ItemType>
SdfApplyListOrdering(std::vector<ItemType> * v,const std::vector<ItemType> & order)742 void SdfApplyListOrdering(std::vector<ItemType>* v,
743                          const std::vector<ItemType>& order)
744 {
745     if (!order.empty() && !v->empty()) {
746         // XXX: This is lame, but just for now...
747         SdfListOp<ItemType> tmp;
748         tmp.SetOrderedItems(order);
749         tmp.ApplyOperations(v);
750     }
751 }
752 
753 ////////////////////////////////////////////////////////////////////////
754 // Stream i/o
755 
756 template <typename T>
757 static void
_StreamOutItems(std::ostream & out,const string & itemsName,const std::vector<T> & items,bool * firstItems,bool isExplicitList=false)758 _StreamOutItems(
759     std::ostream &out,
760     const string &itemsName,
761     const std::vector<T> &items,
762     bool *firstItems,
763     bool isExplicitList = false)
764 {
765     if (isExplicitList || !items.empty()) {
766         out << (*firstItems ? "" : ", ") << itemsName << " Items: [";
767         *firstItems = false;
768         TF_FOR_ALL(it, items) {
769             out << *it << (it.GetNext() ? ", " : "");
770         }
771         out << "]";
772     }
773 }
774 
775 template <typename T>
776 static std::ostream &
_StreamOut(std::ostream & out,const SdfListOp<T> & op)777 _StreamOut(std::ostream &out, const SdfListOp<T> &op)
778 {
779     const std::vector<std::string>& listOpAliases =
780         TfType::GetRoot().GetAliases(TfType::Find<SdfListOp<T>>());
781     TF_VERIFY(!listOpAliases.empty());
782 
783     out << listOpAliases.front() << "(";
784     bool firstItems = true;
785     if (op.IsExplicit()) {
786         _StreamOutItems(
787             out, "Explicit", op.GetExplicitItems(), &firstItems,
788             /* isExplicitList = */ true);
789     }
790     else {
791         _StreamOutItems(out, "Deleted", op.GetDeletedItems(), &firstItems);
792         _StreamOutItems(out, "Added", op.GetAddedItems(), &firstItems);
793         _StreamOutItems(out, "Prepended", op.GetPrependedItems(), &firstItems);
794         _StreamOutItems(out, "Appended", op.GetAppendedItems(), &firstItems);
795         _StreamOutItems(out, "Ordered", op.GetOrderedItems(), &firstItems);
796     }
797     out << ")";
798     return out;
799 }
800 
801 template <typename ITEM_TYPE>
operator <<(std::ostream & out,const SdfListOp<ITEM_TYPE> & op)802 std::ostream & operator<<( std::ostream &out, const SdfListOp<ITEM_TYPE> &op)
803 {
804     return _StreamOut(out, op);
805 }
806 
807 ////////////////////////////////////////////////////////////////////////
808 // Traits
809 
810 template<>
811 struct Sdf_ListOpTraits<TfToken>
812 {
813     typedef TfTokenFastArbitraryLessThan ItemComparator;
814 };
815 
816 template<>
817 struct Sdf_ListOpTraits<SdfPath>
818 {
819     typedef SdfPath::FastLessThan ItemComparator;
820 };
821 
822 template<>
823 struct Sdf_ListOpTraits<SdfUnregisteredValue>
824 {
825     struct LessThan {
operator ()Sdf_ListOpTraits::LessThan826         bool operator()(const SdfUnregisteredValue& x,
827                         const SdfUnregisteredValue& y) const {
828             const size_t xHash = hash_value(x);
829             const size_t yHash = hash_value(y);
830             if (xHash < yHash) {
831                 return true;
832             }
833             else if (xHash > yHash || x == y) {
834                 return false;
835             }
836 
837             // Fall back to comparing the string representations if
838             // the hashes of x and y are equal but x and y are not.
839             return TfStringify(x) < TfStringify(y);
840         }
841     };
842 
843     typedef LessThan ItemComparator;
844 };
845 
846 ////////////////////////////////////////////////////////////////////////
847 // Template instantiation.
848 
849 #define SDF_INSTANTIATE_LIST_OP(ValueType)                       \
850     template class SdfListOp<ValueType>;                         \
851     template SDF_API std::ostream&                               \
852     operator<<(std::ostream &, const SdfListOp<ValueType> &)     \
853 
854 SDF_INSTANTIATE_LIST_OP(int);
855 SDF_INSTANTIATE_LIST_OP(unsigned int);
856 SDF_INSTANTIATE_LIST_OP(int64_t);
857 SDF_INSTANTIATE_LIST_OP(uint64_t);
858 SDF_INSTANTIATE_LIST_OP(string);
859 SDF_INSTANTIATE_LIST_OP(TfToken);
860 SDF_INSTANTIATE_LIST_OP(SdfUnregisteredValue);
861 SDF_INSTANTIATE_LIST_OP(SdfPath);
862 SDF_INSTANTIATE_LIST_OP(SdfReference);
863 SDF_INSTANTIATE_LIST_OP(SdfPayload);
864 
865 template
866 SDF_API void SdfApplyListOrdering(std::vector<string>* v,
867                           const std::vector<string>& order);
868 template
869 SDF_API void SdfApplyListOrdering(std::vector<TfToken>* v,
870                           const std::vector<TfToken>& order);
871 
872 PXR_NAMESPACE_CLOSE_SCOPE
873