Помогите с алгоритмом. Цепочка объектов...

[john.brown]

Помогите с алгоритмом. Цепочка объектов...

Творю, значит, класс ObjectsChain. Каждый обект имеет ссылку на предыдущий и следующий обект, а также порядковый номер ($prev, $next, $order). Все, вроде, хорошо, цепочка делается, можно вставить новый обект в нужное место... Но ни как не могу сделать перемещение обекта по цепочке. Т. е. был он 2ым, переместить 4ым... Уже замучился, плз, помогите кто хоть ссылкой на похожее.

Вот так оно должно бы работать:

$this->testAdd(); // create chain
 $obj = $this->chain->getByOrder(2);
 $obj->setValue('Moved');
 $obj->moveTo(3);
 		
 $obj2 = $this->chain->getByOrder(3);
 $this->assertEquals('Moved',$obj2->getValue());

Примерно такова одна из попыток реализации. Явно корявая, ибо один елемент из цепочки пропадает

public function moveTo($order) {		
	if($this->order == $order) {
		return true;
	}
	if($order > $this->order) {			
		$this->next->moveDown($this,$order);	
	}
	if($order < $this->order) {
		$this->moveUp($this,$order);
	}
}
private function moveDown($obj,$order) {	
		
	$this->prev = $obj->getPrev();				
	$obj->addNext($this->next);		
	$this->next = $obj;
	$obj->addPrev($this);		
	$this->order = $this->order-1;		
	$obj->setOrder($obj->getOrder()+1);
	$obj->moveTo($order);
}

 

[svetasmirnova]

Дубовое неэкономичное сонное решение в лоб, основанное на утверждении, что "можно вставить новый обект в нужное место":

class Chain {
//flags to roll back our transaction
private $movingNow = false;
private $phantom = null;

public function moveTo($order) {
$this->movingNow = true;
$this->phantom=($order < $this->curOrder) ? $this->curOrder + 1 : $this->curOrder - 1;
//insert into $order
//delete from $this->phantom
$this->phantom=null;
$this->movingNow = false;
}

 

[john.brown]

svetasmirnova

Не понял тебя. Наверно, и в правду сонный
Проблема имхо заключается именно в "вставить в нужное место". Обекты реально ссылается друг на друга, и если бы не нужда их иногда перемещать, $order наф не нужен был бы...

Если можно, подробнее, плз.

 

[partizan]

Если в каждом елементе хранится порядковый номер, то при вставке нужно изменить порядковые номера всех елементов, которые идут после вставленного. Тоесть получится O(n) операций.

Какой тогда смысл в такой структуре? Почему не запихнуть в массив?

 

[john.brown]

На счет порядкового номера я погорячился, не нужен он А интерес в структуре в некотором удобстве - с такой цепочкой можно обращатся как с одним обектом. ИМХо, оч удобно. Я как то на подобной штуке корзину делал, понравилось. Но там не надо было их перемещать.
С массивом, если класический Chain of responsibility, я не могу наследовать непосредственно от класса Chain, и с методами объектов получается работать через __call(), что не очень удобно...

 

[svetasmirnova]

john.brown
>Проблема имхо заключается именно в "вставить в нужное место".
Сначала вставляешь копию перемещаемого элемента на нужное место, потом удаляешь сам элемант: ты же сказал, что эти функции у тебя уже реализованы. Флаги добавлены, чтобы можно было отличить момент, когда копия уже вставлена, а оригинал ещё не удалён.

 

[HraKK]

хм зачем такой изврат ведь это обычный связанный список.
Прочитай любой мануал на эту тему там все научно-популярно обьяснено.