cursors.cpp

namespace cursor_linked_list {
	typedef int position;

	struct person //элемент списка
	{
		object obj;
		position next;

		person()
				:obj("-", "-"), next(-1) { }
		person(position p)
				:next(p) { };
		person(const object& x, position n = 0)
				:obj(x), next(n) { };

	};

	class list {
	public:
		list() { head = -1; }
		~list() { RESET(); }
		void INSERT(object& x, position pos); //вставка
		position LOCATE(const object& x) const; //возвращает позицию объекта Х в списке
		object& RETRIEVE(position pos) const; //возвращает объект, расположенный в позиции p
		position REMOVE(position pos); //удаление объекта Х по позиции
		void RESET();
		void PRINT() const;
		position ENDL() const; //возвращает позицию за последним эл-том
		position NEXT(position pos) const;
		position PREVIOUS(position pos) const; //возвращает позицию предыдущую р
		position FIRST() const; //возвращает первую позицию в списке
		static void init(); //инициализация массива
		static person fictive;
		static const position position_fictive = -2;

		/*TEST FUNCTIONS*/
		void print_nexts() const
		{
			position temp = -2;
			cout << "[(CURRENT),(NEXT) (NAME ADDRESS)]" << endl;
			for (int i = 0; i < size; i++)
			{
				cout << "[" << i << "," << array[i].next << " (" << array[i].obj.name << " " << array[i].obj.address << ")]\n";
			}
			cout << endl;
		}
	private:
		position head;
		position search_pos(position pos) const; //существование позиции
		position pos_last() const; //возвращает последний элемент списка
		void move_position(position& pos1, position& pos2);
		static const int size = 10;
		static person array[size];
		static position SPACE; //голова списка свободных
	};

	person   list::fictive(object("NULL", "NULL"), -2);
	person   list::array[size];
	position list::SPACE = 0;

	void list::INSERT(object& x, position pos)
	{
		if (pos == -1) //если вставляем в конец
		{
			if (head != -1) //если список не пуст
			{
				position tail = pos_last(); //ищем последний элемент списка
				move_position(SPACE, array[tail].next); //перемещаем из свободных в позицию после последнего
				array[array[tail].next].obj = x; //записываем объект в новый эл-т списка
			}
			else //если список пуст
			{
				move_position(SPACE, head); //перемещаем из свободных в голову
				array[head].obj = x; //записываем объект в новый эл-т списка
			}
			return;
		}
		if (pos == head)
		{
			move_position(SPACE, array[head].next); //перемещаем из свободных в позицию за головой
			array[array[head].next].obj = array[head].obj;
			array[head].obj = x;
			return;
		}
		if (search_pos(pos)) //если позиция сущ-т
		{
			move_position(SPACE, array[pos].next); //перемещаем из свободных в позицию за p
			array[array[pos].next].obj = array[pos].obj; //перезаписываем объекты
			array[pos].obj = x;
			return;
		}

	}

	position list::REMOVE(position pos)
	{
		if (head == -1)
			return pos;

		if (pos == -1)
			return pos;

		if (pos == head)
		{
			move_position(head, SPACE); //удаление из головы списка
			return head;
		}

		position prev = search_pos(pos);
		if (prev != -1)
		{
			move_position(array[prev].next, SPACE);
			return array[prev].next;
		}
	}

	/*Возвращает первую свободную позицию*/
	position list::ENDL() const
	{
		return -1;
	}

	/* Инициализируем каждый элемент массива (ссылаем next на каждый последующий элемент) */
	void list::init()
	{
		int i;
		for (i = 0; i < size - 1; i++)
		{
			array[i].next = i + 1;
		}
		array[i].next = -1;
	}

	/* Возвращает предыдущую позицию (позицию перед искомой позицией)*/
	position list::search_pos(position pos) const
	{
		position temp = array[head].next;
		position prev = head;
		while (temp != -1)   //для всех остальных элементов списка
		{
			if (temp == pos)  //позиция следующего элемента совпадает c искомым (pos) ?
			{
				return prev; //возвращаем текущий
			}
			prev = temp;
			temp = array[temp].next; //переходим к следующему
		}
		return -1;
	}

	position list::pos_last() const
	{
		position temp = array[head].next;
		position prev = head;
		while (temp != -1) //за текущим элементом есть следующий?
		{
			prev = temp;
			temp = array[temp].next; //переходим ко следующему
		}
		return prev; //возвращаем последний элемент
	}

	position list::LOCATE(const object& x) const
	{
		position temp = head;
		while (temp != -1) //пока текущий элемент существует
		{
			if (array[temp].obj == x) //если текущий объект совпадает с x
				return temp;                                            //возвращаем его позицию
			temp = array[temp].next;                                                           //иначе переходим к следующему
		}
		return -1; //если объект не найден, возвращаем END()
	}

	object& list::RETRIEVE(position pos) const //Возвращение объекта по позиции
	{
		if (search_pos(pos))     //если позиция есть в списке
			return array[pos].obj;     //вернуть объект по позиции
		return fictive.obj; //вернуть фиктивный объект, если позиции в списке нет
	}

	position list::NEXT(position pos) const
	{
		position find = search_pos(pos);
		if (find != position_fictive)
		{
			if (array[pos].next != -1)    //если следующий за pos элемент существует, то вернем
			{
				return array[pos].next;
			}
			else
			{
				return -1;
			} //иначе вернем ENDL()
		}
		return position_fictive; //если позиции в списке нет, возвращаем фиктивный
	}

	position list::PREVIOUS(position pos) const
	{
		if (pos != -1) //если берем предыдущий не от конца
		{
			position find = search_pos(pos); //находим позицию перед pоs (если она есть в списке)
			if (find == -1) //если искомая позиция отсуствует или является головой, то вернем фиктивную позицию
				return position_fictive;
			return find;  //иначе вернем, что искали
		}
		else return pos_last(); //если же предыдущий от (endl), то вернем последний
	}

	/*Возвращение позиции первого элемента или ENDL(), если список пуст*/
	position list::FIRST() const
	{
		if (head != -1)
		{
			return head;
		}
		return -1;
	}

	void list::RESET()
	{
		if (head != -1) //если в списке что-то есть
		{
			position temp = pos_last(); //находим последний элемент в tail
			array[temp].next = SPACE; //цепляем к списку список свободных
			SPACE = head;
			head = -1;
		}
	}

	void list::PRINT() const
	{
		position temp = head;
		while (temp != -1)
		{
			array[temp].obj.print();
			temp = array[temp].next;
		}
		cout << endl;
	}

	void list::move_position(position& pos1, position& pos2)
	{
		position temp = pos1; //запоминаем ссылку на перемещаемый эл-т
		pos1 = array[temp].next; //переставляем ссылку в то место, куда хотим переместить
		array[temp].next = pos2; //ссылаем на первый эл-т из списка свободных (тут происходит либо добаление из списка своб., либо исключение из обычного)
		pos2 = temp; //переписываем голову списка свободных
	}
}