Complex multi-linked list problem

Tyr_God_Of_War · **Posted:** Thu Jun 18, 2009 6:09 pm

I am trying to make a linked list that repersents many boxes that can keep up with a scrolling screen.

It can skip over a box if it is wider the the screen or if it's positioned just right, ect.

I've got a linked list with links to the next and previous box, sorted by left side and right side.
nextLeft, prevLeft step forward and backward through the list as if it were a doubly linked list sorted by the left side of each box. Same thing of nextRight and prevRight, but on a list sorted by the x values of the right side.
I have two variables, leftMost, and rightMost, which are (should be) pointers to the boxes on the edge of the viewing area.
leftMost is be found by looking through the list by right side until a box has a right side greater than the left side of the screen. In most cases, that will be the leftmost visible box, but it seems like this dosn't hold true for some exeptional cases.

I can insert into the list correctly.

I can, for simple arrangments where the order for left sides and right sides is the same, correctly find the boxes that are in the viewing area.

Turing:

import var Boxes % You don't really need to look at this, it just has a type :aBox with left,right,top and bot integer feilds and some stuff for working with them. I've attached it to the post.

var pervasive font := Font.New ("times:12")
assert font > 0

module Platforms
import var Boxes, Font
export ~.pform, root,
draw, drawOnScreen, drawLeftMost, drawRightMost,
insert, create, add,
fitWhere, fitWhereRight, initScreenbox

var pform : collection of
record
box : Boxes.aBox
nextLeft, prevLeft : pointer to pform % sorted by left side
nextRight, prevRight : pointer to pform %sorted by right side
end record

var root : ^pform
new pform, root

var leftMost, rightMost : ^pform := root

%var ref : ^pform
proc insertBeforeL (b, i : ^pform)
/* a, i
* a->right = i
* i -> left = a
***************
* a, b, i
* b->right =i
* b->left := i->left(a)
* i->left :=b
* a ->right =b
*/
b -> nextLeft := i
b -> prevLeft := i -> prevLeft /*a*/
i -> prevLeft /*a*/ -> nextLeft := b
i -> prevLeft := b
end insertBeforeL

proc insertAfterL (b, i : ^pform)
% i,b,c
b -> prevLeft := i
b -> nextLeft := i -> nextLeft
b -> nextLeft /*c*/ -> prevLeft := b
i -> nextLeft := b
end insertAfterL

proc insertBeforeR (b, i : ^pform)
/* a, i
* a->right = i
* i -> left = a
***************
* a, b, i
* b->right =i
* b->left := i->left(a)
* i->left :=b
* a ->right =b
*/
b -> nextRight := i
b -> prevRight := i -> prevRight /*a*/
i -> prevRight /*a*/ -> nextRight := b
i -> prevRight := b
end insertBeforeR

proc insertAfterR (b, i : ^pform)
% i,b,c
b -> prevRight := i
b -> nextRight := i -> nextRight
b -> nextRight /*c*/ -> prevRight := b
i -> nextRight := b
end insertAfterR

proc insert (b : ^pform)
if root -> nextLeft = root then % empty list
root -> nextLeft := b
root -> prevLeft := b
root -> nextRight := b
root -> prevRight := b

b -> nextLeft := root
b -> prevLeft := root
b -> nextRight := root
b -> prevRight := root
return
end if
var i : ^pform := root

loop
% if i -> nextLeft = root then
% put "at end of list"
% b -> nextLeft := i
% b -> prevLeft := i -> prevLeft /*a*/
% i -> prevLeft /*a*/ -> nextLeft := b
% i -> prevLeft := b
% return
% end if

% when c is more left than b
exit when i -> nextLeft = root or (i -> nextLeft -> box.left) > (b -> box.left)
i := i -> nextLeft
end loop
insertAfterL (b, i)

i := root
loop
exit when i -> nextRight = root or (i -> nextRight -> box.right) > (b -> box.right)
i := i -> nextRight
end loop
insertAfterR (b, i)
end insert

proc create (var b : ^pform, left, bot, right, top : int)
assert b = nil
new pform, b
b -> box := Boxes.create (left, bot, right, top)
insert (b)
end create

proc add (left, bot, right, top : int)
var b : ^pform
new pform, b
b -> box := Boxes.create (left, bot, right, top)
insert (b)
end add

proc draw (col : int)
var i := root -> nextLeft
var count := 0
loop
Boxes.draw (i -> box, col)
if true then
Font.Draw (intstr (count), i -> box.left + 2, i -> box.bot + 2, font, black)
end if
exit when i -> nextLeft = root
i := i -> nextLeft
count += 1
end loop

if true then
i := root -> nextRight
count := 0
loop
%Boxes.draw (i -> box, col)
if true then
Font.Draw (intstr (count), i -> box.right - 20, i -> box.bot + 2, font, black)
end if
exit when i -> nextRight = root
i := i -> nextRight
count += 1
end loop
end if
end draw

%Abandoned, at least for now.

% proc drawWithOnScreen (col : int)
% var i := root
% var count := 0
% loop
% Boxes.draw (i -> box, col)
% if true then
% Font.Draw (intstr (count), i -> box.left + 2, i -> box.bot + 2, font, black)
% end if
% exit when i -> nextLeft = leftMost
% i := i -> nextLeft
% count += 1
% end loop
% i := i -> nextLeft
% count += 1
% loop
% Boxes.drawFill (i -> box, col)
% if true then
% Font.Draw (intstr (count), i -> box.left + 2, i -> box.bot + 2, font, black)
% end if
% exit when i -> nextLeft = rightMost
% i := i -> nextLeft
% count += 1
% end loop
% i := i -> nextLeft
% count += 1
% loop
% Boxes.draw (i -> box, col)
% if true then
% Font.Draw (intstr (count), i -> box.left + 2, i -> box.bot + 2, font, black)
% end if
% exit when i -> nextLeft = root
% i := i -> nextLeft
% count += 1
% end loop
%
%
% if true then
% i := root
% count := 0
% loop
% %Boxes.draw (i -> box, col)
% if true then
% Font.Draw (intstr (count), i -> box.right - 20, i -> box.bot + 2, font, black)
% end if
% exit when i -> nextRight = root
% i := i -> nextRight
% count += 1
% end loop
% end if
% end drawWithOnScreen

proc drawOnScreen (col : int) %still not really working

% this
% if leftMost = rightMost then % only one box on screen
% Boxes.draw (leftMost -> box, col)
% return
% end if
var i := leftMost
Boxes.draw (leftMost -> box, col)
loop % skips over any ones that are right of LM's left, but still not on screen
i := i -> nextLeft
exit when i -> box.right >= leftMost -> box.right
end loop
loop
Boxes.draw (i -> box, col)
exit when i = rightMost
i := i -> nextLeft
end loop

end drawOnScreen

proc drawLeftMost (col : int)
Boxes.drawFill (leftMost -> box, col)
end drawLeftMost
proc drawRightMost (col : int)
Boxes.drawFill (rightMost -> box, col)
end drawRightMost

fcn fitWhere (left : int) : int % by left value. It counts how many boxes you're right of
var i := root
var count := 0
% if i -> nextLeft = root then
% result - 1
% end if
if i -> box.left > left then
result - 1
end if
loop
if i -> nextLeft = root then
result count
elsif left < i -> nextLeft -> box.left then
%put left, " < ", i -> nextLeft -> box.left
result count
end if
i := i -> nextLeft
count += 1
end loop

end fitWhere

fcn fitWhereRight (right : int) : int %Same thing, but going by right values
var i := root
var count := 0
% if i -> nextLeft = root then
% result - 1
% end if
if i -> box.right > right then
result - 1
end if
loop
if i -> nextRight = root then
result count
elsif right < i -> nextRight -> box.right then
%put right, " < ", i -> nextLeft -> box.right
result count
end if
i := i -> nextRight
count += 1
end loop

end fitWhereRight

proc initScreenbox (left, right : int) % this sets up leftMost and rightMost. I'm currently also using it for correction in the middle, but I hpoe to replace that later with ones that just look for new ones in the direction of motion and let go of ones in in other direction
var temp : ^pform
var lastGood : ^pform
leftMost := root
rightMost := root
if root -> nextRight = root then % the list is empty
return
end if

/* |left
* /-----|-\
* |lMost| |Right edge
* \-----|-/
*/
%leftMost := leftMost -> nextRight % skip root
loop
if leftMost -> nextRight = root then % it's the last one to the right
exit
end if
if leftMost -> box.right >= left then % it's the last one that is greater than left
exit
% lastGood := leftMost
% temp := leftMost
% loop
% temp := temp -> nextRight
% if temp -> box.left < leftMost -> box.left and temp -> box.right >= left then
% lastGood :=temp
% end if
%
% end loop
end if

leftMost := leftMost -> nextRight
end loop

/*|left |right
*|-\ /-|-----\
*| | left edge-> | |rMost|
*|-/ \-|-----/
*lMost
*
* -> is next
* <- is prev
* I want to go right from the leftedge until the left edge of the next box is greater than right, OR
* I want to go left from root untill the left edge is < right
% I pick the seccond one for now
*/
rightMost := root -> prevLeft % start at the right of the list. a,b,c,d,E
loop
exit when rightMost -> prevLeft = root or % it's back to the start. Might change it to mostLeft->something
rightMost -> box.left < right % it's the first one that is smaller than right

rightMost := rightMost -> prevLeft
end loop
end initScreenbox

root -> box := Boxes.create (-maxint, 0, -maxint, 0)
root -> nextLeft := root
root -> prevLeft := root
root -> nextRight := root
root -> prevRight := root

end Platforms

View.Set ("offscreenonly")
var mx, my, mb : int := 0
%Mouse.Where (mx, my, mb)
%var screenBox : Boxes.aBox := init (20, 50, 30, 70)
%var temp : ^Platforms.pform
Platforms.add (50, 30, 95, 60) % This is where the boxes are added. Feel free to change these around.
Platforms.add (90, 170, 210, 190)
Platforms.add (100, 300, 130, 330)
Platforms.add (150, 70, 250, 90)
Platforms.add (175, 175, 280, 195)

%Platforms.add (10, 10, 300, 50) % really wide boxes break it.

loop
Mouse.Where (mx, my, mb)
Platforms.initScreenbox (mx, mx + 100) % I'm pretending that maxx is 100 right here so I can look at them.
Draw.FillBox (mx, 0, mx + 100, maxy, blue)
Platforms.draw (black)

Platforms.drawLeftMost (green)
Platforms.drawRightMost (red)
Platforms.drawOnScreen (gray)
locate (1, 1)
put "Left spot: ", Platforms.fitWhere (mx)
put "Right spot: ", Platforms.fitWhereRight (mx)
View.Update
cls
end loop

Please specify what version of Turing you are using
4.1

DtY · **Posted:** Mon Jun 22, 2009 2:20 pm

Is this something you could replace with a flexible array?

DemonWasp · **Posted:** Mon Jun 22, 2009 2:56 pm

I think I'm missing something here: what problem are you running into?

Also, as DtY mentions, can you replace this with a flexible array or a (real) collection?

	Computer Science Canada Programming C, C++, Java, PHP, Ruby, Turing, VB Username: Password: Register
Wiki Blog Search Turing Chat Room Members