/*
 * Copyright (C) 2015 Imran Mammadli
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package sorting.strings.duplicates;

import java.util.Arrays;

public class Solution2
{
	/**
	 * Removes duplicate first names from the array of full names
	 * 
	 * @param array the given array of full names
	 * @return the array of full names with distinct first names
	 * 
	 * @time <i>O(n • log(n))</i>
	 * @space <i>O(n)</i>
	 **/
	public static Pair[] removeDuplicateNames(Pair[] array)
	{
		if (array != null)
		{
			Arrays.sort(array);
			int position = 0;
			
			for (int i = 1; i< array.length; i++)
			{
				String currFirstName = array[position].first;
				String nextFirstName = array[i].first;
				
				if (!currFirstName.equals(nextFirstName))
				{
					array[++position] = array[i];
				}
			}
			
			array = Arrays.copyOfRange(array, 0, ++position);
		}
		
		return array;
	}
	
	
	/**
	 * Structure for storing a person's full name
	 * 
	 * <ul>
	 * <li><b>first</b> - first name</li>
	 * <li><b>last</b> - last name</li>
	 * </ul>
	 * 
	 * @author Imran Mammadli
	 **/
	public static class Pair implements Comparable<Pair>
	{
		private String first;
		private String last;
		
		public Pair(String first, String last)
		{
			this.first = first;
			this.last = last;
		}
		
		@Override
		public String toString()
		{
			return "[ " + this.first + " - " + this.last + " ]";
		}

		@Override
		public int compareTo(Pair that)
		{
			// other pair is NULL
			if (that == null)
			{
				return 1;
			}
			
			String thisName = this.first;
			String thatName = that.first;
			
			return thisName.compareTo(thatName);
		}
	}	
}