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