// ===========================================================================
// 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.
// ===========================================================================
//
// Creation Date:  November 22, 1997
//
//<doc>
//<name listUnselected>
//
//<synopsis>
//	string[] listUnselected()
//
//<description>
//		Lists the top transform for all DAG objects that are visible and not selected.
//
//<flags>
//		None.
//
//<returns>
//      string[]: Array of transform nodes names.
//
//<examples>
//      sphere; cone; group; select -d;
//      listUnselected;
//      // Result: nurbsSphere1 group1 //
//
//</doc>
//
global proc string[] listUnselected ()
{
	string $selected[] = `ls -sl -type dagNode`;
	int    $selectedCount = size($selected);
	string $assemblies[]  = `ls -as -v`;

	if ($selectedCount == 0) {
		return $assemblies;
	} else {
		string	$item;
		string	$result[];
		string  $selectedAbove[];
	
		//	Expand selected to include objects above the selected items
		//
		$selectedAbove = $selected;
		$parents = `listRelatives -p -pa $selected`;
		while (size($parents) > 0) {
			for ($item in $parents) {
				$selectedAbove[size($selectedAbove)] = $item;
			}
			$parents = `listRelatives -p -pa $parents`;
		}
		$selected = sort($selected);
		$selectedAbove = sort($selectedAbove);
		int $selectedCount = size($selected);
		int $selectedAboveCount = size($selectedAbove);

		//	Process assemblies
		//
		int		$i, $j, $cmp;
		string	$leftOvers[];
		int		$leftOverCount;
		int		$assemblyCount = size($assemblies);

		do {
			$assemblies = sort($assemblies);

			//	Step 1: process objects not on selectedAbove list
			//
			$i = 0; $j = 0;
			while ($i < $assemblyCount && $j < $selectedAboveCount) {
				$cmp = strcmp($assemblies[$i], $selectedAbove[$j]);
				if ($cmp < 0) {
					$result[size($result)] = $assemblies[$i];
					++$i;
				} else if ($cmp > 0) {
					++$j;
				} else {
					$leftOvers[size($leftOvers)] = $assemblies[$i];
					++$i; ++$j;
				}
			}
			while ($i < $assemblyCount) {
				$result[size($result)] = $assemblies[$i];
				++$i;
			}

			//	Step 2: weed out active leftovers
			//
			$i = 0; $j = 0;
			clear($assemblies);
			$leftOverCount = size($leftOvers);
			while ($i < $leftOverCount && $j < $selectedCount) {
				$cmp = strcmp($leftOvers[$i], $selected[$j]);
				if ($cmp < 0) {
					$assemblies[size($assemblies)] = $leftOvers[$i];
					++$i;
				} else if ($cmp > 0) {
					++$j;
				} else {
					++$i; ++$j;
				}
			}
			while ($i < $leftOverCount) {
				$assemblies[size($assemblies)] = $leftOvers[$i];
				++$i;
			}
			clear($leftOvers);

			//	Process children of leftovers recursively...
			//
			$assemblies = `listRelatives -c -pa $assemblies`;
			$assemblyCount = size($assemblies);
		} while ($assemblyCount > 0);
		return $result;
	}
}