40 баллов

Спроектировать библиотеку коллекций для языка C++. Под коллекцией, в данном контексте, понимается "программный объект, содержащий в себе, тем или иным образом, набор значений одного или различных типов, и позволяющий обращаться к этим значениям." (см. http://ru.wikipedia.org/wiki/Коллекция_данных)

Создаваемая вами библиотека должна состоять из трех "слоев":

При проектировании и описании библиотеки следует обратить внимание на различие между интерфейсом коллекции, задающим ее назначение и способ использования, и конкретной реализацией (разница между "множеством вообще" и различными реализациями множества - на основе деревьев, хэш-таблиц и т.д.). Множество, фактически, является интерфейсом, поддерживающим набор стандартных операций (добавление элемента, проверка на наличие, удаление элемента, сложение с другим множеством и т.д.), реализовываться эти операции могут различным образом в зависимости от структур данных, лежащих в основе.

Должна быть предусмотрена возможность получения итератора, с помощью которого можно обойти всю коллекцию (см. STL и паттерн проектирования Итератор).

Необходимо разработать интерфейсы следующих коллекций: множество, ассоциированный массив, очередь и стек. Предложить реализацию ассоциированного массива на основе хеша, множества - на основе сбалансированного дерева поиска (АВЛ, красно-черное или любое другое, но обязательно с операциями балансировки), а всех остальных коллекций - на основе массива переменной длины. Массив переменной длины реализовать самостоятельно (не использовать std::vector и т.д.).

	Внимание
	Коллекции должны быть реализованы БЕЗ ПРИМЕНЕНИЯ МЕХАНИЗМА ШАБЛОНОВ (TEMPLATES) C++. То есть, коллекции должны быть ориентированы на хранение объектов, являющихся наследниками одного (базового) класса. Необходимо также определить интерфейс этого базового класса.

Для защиты лабораторной работы необходимо представить:

Разработанная библиотека должна допускать, например, такое использование:

/*...*/

int main() {

	/* Создается экземпляр множества, основанного на массиве.
	   Указатель на множество сохраняется в переменной абстрактного типа
	   Set (если мы в будущем захотим изменить реализацию множества, то
	   достаточно будет изменить лишь HashSet в этой строке на новый).
	 */	
	Set *s = new HashSet();

	/* Класс IntObject - наследник абстрактного класса Object, предназначенный
	   для хранения чисел типа int. Параметром конструктора является 
	   само число.
	 */
	Object *o = new IntObject(5);
	/* Добавляем созданный экземпляр в множество */
	s->add(o);

	Object *o = new IntObject(6);
	s->add(o);

	Object *o = new IntObject(5);

	/* Операция contains возвращает истину, если множество содержит
	   объект 
	 */
	if (s->contains(o)) cout << "As expected\n"; else cout << "Something wrong\n";

	Iterator *i = s->getIterator();
	for (; i->is(); i->next()) {
		cout << ((IntObject *)i)->intValue() << "\n";
	}
	delete i;

	/* Удаляем объект
	 */
	s->remove(o);

	if (s->contains(o)) cout << "Something wrong\n"; else cout << "As expected\n";

	delete s;

	return 0;
}