from __future__ import annotations
from typing import TypeVar, Generic, List
from tudelft.utilities.immutablelist.AbstractImmutableList import AbstractImmutableList
from tudelft.utilities.immutablelist.ImmutableList import ImmutableList
from typing import Set

E = TypeVar('E')

class ListWithRemove(Generic[E], AbstractImmutableList[E]):
	'''
 	Creates new list with some elements removed from the list. Immutable	
	@param list	an ImmutableList
	@param removed the removed items. Set to empty set initially.	
	'''

	def __init__(self,  list: ImmutableList[E], removed: Set[int]):
		self._list = list
		self._removedIndices=sorted(frozenset(removed))


	#Override
	def get(self , index:int) ->E :
		return self._list.get(self._realIndex(index))

	def _realIndex(self, index:int) -> int:
		'''
		 @param index
		 @return the real index of an item in the original list. This can be
		         larger than given index because {@link #remvedIndices} are
		         invisible. This operation can become expensive if many items have
		          been removed
		'''
		realIndex:int = index;
		
		# invariant: realIndex has correct value if only removedIndices up to
		# current iteration were in the list.
		for removed in self._removedIndices:
			if removed > realIndex: 
				break
			realIndex += 1

		return realIndex;


	#Override
	def size(self) ->int:
		return self._list.size() - len(self._removedIndices)

	def remove(self, index:int) -> ListWithRemove[E]:
		'''	
		 Remove item at index n
		 
		 @param index index of the element to return
		 @return the element at the specified position in this list before it was
		         removed.
		'''
		removed:Set[int] = set(self._removedIndices)
		removed.add(self._realIndex(index));
		return ListWithRemove(self._list, removed);