Dequeue Ranged Operations

[Nestharus]

This tutorial will cover ranged operations for dequeues.

Because a dequeue is a doubly linked list, collections of nodes can be moved around with the same amount of operations as single nodes.

Looking back at destruction-

if (last != 0) then
	set last.next = thistype(0).next
	set thistype(0).next = first
endif

This will actually recycle all of the nodes in the entire list.

The end of the list is pushed right behind the first node on the recycle stack. The first node of the recycle stack is set to the beginning of the list. As long as the beginning and end of a given range are known, the entire range can be treated as a single node.

node.next could be lastOfRange.next
node.previous could be firstOfRange.previous

All of the nodes in between the beginning and the end don't matter because their pointers don't change (previous/next values). All that matters is updating the beginning and end of the list. In this way, a single node can be regarded as a ranged operation from the node to the node.

call move(node, node)
call move(startNode, endNode)

When overwriting nodes, the previous nodes don't have to be removed. The reason for this is because nothing in the list will point to the previous nodes after the operation is complete.

Simple code

method move takes thistype start, thistype end, thistype toList, thistype toStart, thistype toEnd returns nothing
	if (start.previous == 0) then
		set toList.first = end.next
	endif
	if (end.next == 0) then
		set toList.last = start.previous
	endif
	set start.previous.next = end.next
	set end.next.previous = start.previous

	set toStart.previous.next = start
	set toEnd.next.previous = end
	set start.previous = toStart.previous
	set end.next = toEnd.next
endmethod

//where start is the first node of nodes to move
//where end is the last node of nodes to move
//where toStart is the start.previous
//where toEnd is the end.next
method move takes thistype start, thistype end, thistype toList, thistype toStart, thistype toEnd returns nothing
	if (first != 0) then
		if (start == 0) then
			set start = first
		endif
		if (end == 0) then
			set end = last
		endif

		//handle starts/ends
		if (start == first) then
			set first = end.next
		endif
		if (end == last) then
			set last = start.previous
		endif

		//relink previous list, not necessary for a swap
		set start.previous.next = end.next
		set end.next.previous = start.previous
	endif

	if (start == 0 or end == 0) then
		set start = 0
		set end = 0
	endif

	if (toList.first == 0) then
		set toList.first = start
		set toList.last = end
		set start.previous = 0
		set end.next = 0
	else
		if (toStart == 0 or toStart.previous == 0) then
			set toStart = 0
		else
			set toStart = toStart.previous
		endif
		if (toEnd == 0 or toEnd.previous == 0) then
			set toEnd = 0
		else
			set toEnd = toEnd.next
		endif

		if (toStart == 0) then
			set toList.first = start
			set start.previous = 0
		else
			if (start == 0) then
				set toStart.next = toEnd
			else
				set toStart.next = start
				set start.previous = toStart
			endif
		endif
		if (toEnd == 0) then
			set toList.last = end
			set end.next = 0
		else
			if (end == 0) then
				set toEnd.previous = toStart
			else
				set toEnd.previous = end
				set end.next = toEnd
			endif
		endif
	endif
endmethod

With that method, the overwritten nodes are just floating in space. They could possibly be cleared out or moved into another list.

The swap method wouldn't have set first.previous = end.next, but would rather relink those to the toStart and toEnd

Simple Code

static method swap takes thistype list1, thistype start1, thistype end1, thistype list2, thistype start2, thistype end2 returns nothing
	local thistype cStart = start1.previous
	local thistype cEnd = end1.next
	if (start.previous == 0) then
		set list1.first = start2
	endif
	if (end.next == 0) then
		set list1.last = end2
	endif
	if (start2.previous == 0) then
		set list2.first = start1
	endif
	if (end2.next == 0) then
		set list2.last = end1
	endif

	set start2.previous.next = start1
	set end2.next.previous = end1
	set start1.previous = start2.previous
	set end1.next = end2.next

	set cStart.next = start2
	set cEnd.previous = end2
	set start2.previous = cStart
	set end2.next = cEnd
endmethod

static method swap takes thistype list1, thistype start1, thistype end1, thistype list2, thistype start2, thistype end2 returns nothing
	if (list1.first != 0) then
		if (start1 == 0) then
			set start1 = list1.first
		endif
		if (end1 == 0) then
			set end1 = list1.last
		endif

		//handle starts/ends
		if (start1 == list1.first) then
			set list1.first = end2
		endif
		if (end1 == list1.last) then
			set list1.last = start2
		endif
	endif
	if (list2.first != 0) then
		if (start2 == 0) then
			set start2 = list2.first
		endif
		if (end2 == 0) then
			set end2 = list2.last
		endif

		//handle starts/ends
		if (start2 == list2.first) then
			set list2.first = end1
		endif
		if (end2 == list1.last) then
			set list2.last = start1
		endif
	endif
	
	if (start1 == 0 or end1 == 0) then
		set start1 = 0
		set end1 = 0
	endif
	if (start2 == 0 or end2 == 0) then
		set start2 = 0
		set end2 = 0
	endif

	if (start1.previous != 0) then
		if (start2 == 0) then
			set start1.previous.next = end1
		else
			set start1.previous.next = start2
		endif
	endif
	if (end1.next != 0) then
		if (end2 == 0) then
			set end1.next.previous = start1
		else
			set end1.next.previous = end2
		endif
	endif

	if (start2.previous != 0) then
		if (start1 == 0) then
			set start2.previous.next = end2
		else
			set start2.previous.next = start1
		endif
	endif
	if (end2.next != 0) then
		if (end1 == 0) then
			set end2.next.previous = start2
		else
			set end2.next.previous = end1
		endif
	endif
endmethod

Complex code handles all possible errors (preventing messed up links and what not.

 

[PurgeandFire]

I suggest adding more comments to explain what is going on in the code, but it is okay at the moment. It is useful for certain data management, and nice general knowledge, so ~Approved.

EDIT: gy'd by request