// ===========================================================================
// 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:  04 January 1999
//
//<doc>
//<name stringArrayRemoveDuplicates>
//
//<synopsis>
//		string[] stringArrayRemoveDuplicates(string[] $list)
//
//<description>
//		Remove all duplicate items from a string array.  There will be 
//		only one occurrence of each string item in the returned string array.
//		The argument string array is not modified.
//
//<examples>
//  string $list[] = { "d", "b", "c", "c", "a", "a", "b" };
//  string $shorterList[] = stringArrayRemoveDuplicates($list);
//  // Result : { d, b, c, a } //
//
//<flags>
//		string[]	$list	An array of strings.
//
//<returns>
//		string[] :  New string array with all unique values.
//
//</doc>
//

global proc string [] stringArrayRemoveDuplicates(string $list[])
//Algorithm:
//Step 1 - Sort $list[], so all duplicates will be next to each other.
//         e.g. $sortList[] = { "a", "a", "b", "b", "c", "c", "d" };
//Step 2 - Create $dupL[] and $dupCountL[] to store duplicate string and duplicates count with negative number.
//         e.g. $dupL[] = { "a", "b", "c" };  $dupCountL[] = { -1, -1, -1 };
//Setp 3 - Loop each string in $list[];
//            If the string is not found in $dupL[]. Append it to $result[];
//            If the string is found in $dupL[];
//                If count is negative. First duplicate. Reverse count. Append the string to $result[];
//                If count bigger than one. Another duplicate. Recrease count 1;
//                If count equals to one. Last duplicate. Shift $dupL[] and $dupCountL[] to reduce search scope of following loops.
{
	string $result[];
	int $size = size($list);
	if($size <= 1)
	    return $list;
	
	$sortList = sort($list);
	string $dupL[];    //Duplicate elements
	int $dupCountL[];  //Repeat counts of each duplicate element
	
	for($i = 1, $j = 0; $i < $size; $i++)
	{
	    if($sortList[$i-1] == $sortList[$i])
	    {
	        if($j > 0 && $dupL[$j-1] == $sortList[$i])
			{
				$dupCountL[$j-1] = $dupCountL[$j-1]-1;
				continue;
			}
	        $dupL[$j] = $sortList[$i];
			//Save count number as negative for now
			$dupCountL[$j] = -1; 
	        $j++;
	    }
	}
	
	if(size($dupL) == 0)
		return $list;
	
	string $item;
	for($i = 0, $j = 0, $begin = 0; $i < $size; $i++)
	{
		$item = $list[$i];
	    int $dupIndex = stringArrayFind($item, $begin, $dupL);
	    if($dupIndex >= 0)
	    {
			if($dupCountL[$dupIndex] < 0)
			{
				//If count number is negative, it means this is the first time it shows up,
				//Add the string into result and reverse the count number.
				$dupCountL[$dupIndex] = -$dupCountL[$dupIndex];
				$result[$j] = $item;
				$j++;
				continue;
			}
			$dupCountL[$dupIndex] = $dupCountL[$dupIndex]-1;
			if($dupCountL[$dupIndex] == 0)
			{
				//If count number is zero, it means this element will never show up again.
				//Move element at $begin to $dupIndex, and increase $begin 1.
				$dupL[$dupIndex] = $dupL[$begin];
				$dupCountL[$dupIndex] = $dupCountL[$begin];
				$begin++;
			}			
	  	}
	  	else
	  	{
	        $result[$j] = $item;
	        $j++;
	    }
	}
	return $result;
}