Remove and return last (default) or first (last=False) pair (key, value).

		Raises KeyError if the dictionary is empty.

		Runs in O(1) for last item, O(N) for first one.

def popitem(self, last=True):
		"""Remove and return last (default) or first (last=False) pair (key, value).

		Raises KeyError if the dictionary is empty.

		Runs in O(1) for last item, O(N) for first one.
		"""
		try:
			if last:
				key, value = self._list.pop()
				index = len(self._list)
			else:
				key, value = self._list.pop(0)
				index = 0
		except IndexError:
			raise KeyError("IndexedDict is empty")

		index2, value2 = self._dict.pop(key)
		assert index == index2
		assert value is value2

		if not last:
			self._fix_indices_after_delete()

		return key, value