// ===========================================================================
// Copyright 2018 Autodesk, Inc. All rights reserved.
//
// Use of this software is subject to the terms of the Autodesk license
// agreement provided at the time of installation or download, or which
// otherwise accompanies this software in either electronic or hard copy form.
// ===========================================================================

//
//
//	Description:
//
//		Given an object, list all history (or all future), not including any
//	nodes that can only be reached by traversing a node of the given prune
//	types. 	The list of candidate nodes is restricted to the list of nodes that
//	would be returned by listHistory in the level 0 mode.
//
//

global proc string[] pruneSearch(	string $obj, int $doFuture,
									string $pruneTypes[])
//
//	Description:
//		Starting from $obj, list all history (or all future if $doFuture is
//	true), not including any nodes that can only be reached by traversing a
//	node of the given prune types.
//		The list of candidate nodes is restricted to the list of nodes that
//	would be returned by listHistory in the default mode. This guarantees that
//	the outer loop will eventually terminate, since we'll eventually run out
//	of nodes to add to the "nextBatch" array.
//
{
	string $currBatch[];
	string $candidates[];
	int $pruneTypeSize = size( $pruneTypes );
	if( $obj != "" && `objExists $obj` ){
		// Get the level 1 nodes, as well as the list of candidates.
		//
		$currBatch = `listHistory -f $doFuture -bf -af -lv 1 $obj`;
		$candidates = `listHistory -f $doFuture -bf -af $obj`;
	}
	string $nextBatch[];
	string $allNodes[];
	int $currBatchSize = size($currBatch);
	while( $currBatchSize > 0 ){
		int $index = 0;
		while( $index < $currBatchSize ){
			string $currNode = $currBatch[$index];
			if( stringArrayContains( $currNode, $candidates ) &&
			    !stringArrayContains( $currNode, $allNodes ) ){
				// Add the node to the $allNodes array
				//
				$allNodes[size($allNodes)] = $currNode;
				string $currType = `nodeType $currNode`;
				int $isPruneType = false;
				int $pruneTypeIndex = 0;
				while( $pruneTypeIndex < $pruneTypeSize ){
					if( $currType == $pruneTypes[$pruneTypeIndex] ){
						$isPruneType = true;
						break;
					}
					$pruneTypeIndex++;
				}
				if( !$isPruneType ){
					// If this node is not a prune node, look for more nodes
					// to process one level from here.
					//
					string $newNodes[] =
						`listHistory -f $doFuture -bf -af -lv 1 $currNode`;
					int $newNodesCount = size($newNodes);
					int $newNodesIndex = 0;
					while( $newNodesIndex < $newNodesCount ){
						string $newNode = $newNodes[$newNodesIndex];
						if( !stringArrayContains( $newNode, $nextBatch ) &&
							!stringArrayContains( $newNode, $allNodes ) ){
							// We found a node that we hadn't added yet to the
							// next batch of nodes to process, nor to any of
							// the batches before that.
							//
							$nextBatch[size($nextBatch)] = $newNode;
						}
						$newNodesIndex++;
					}
				}
			}
			$index++;
		}
		clear $currBatch;
		$currBatch = $nextBatch;
		$currBatchSize = size($currBatch);
		clear $nextBatch;
	}
	return( $allNodes );
}