Can't find the bug

[wallace]

I've been looking at this code for 3 days. I've chased it through manually dozens of times and all my research says that it should work flawlessly, but it doesn't.

Code:

TYPE two3node
    leftbranch as two3node ptr
    midbranch as two3node ptr
    rightbranch as two3node ptr
    leftvalue as integer
    rightvalue as integer
    
    tempbranch as two3node ptr   'for adding and promoting
    tempvalue as integer
    
    parent as two3node ptr
END TYPE

TYPE two3tree
    Root as two3node ptr
    depth as integer
    size as integer
END TYPE

Declare Function Newtwo3node Overload (Value as integer) as two3node ptr
Declare Function Newtwo3node (lvalue as integer, rvalue as integer) as two3node ptr
Declare Function Newtwo3node () as two3node ptr
Declare Function Newtwo3tree () as two3tree ptr
Declare Sub DisplayAll(tree as Two3Tree ptr)
Declare Sub displaynode (p as two3node ptr, x as integer, y as integer, level as integer)
Declare Sub AddValue(tree as two3tree ptr, value as integer)
Declare Sub AddNode (pp as two3node ptr, tree as two3tree ptr, pnode as two3node ptr)
Declare Sub Deletesubtree(node as two3node ptr)
Declare Sub DeleteTwo3Tree(tree as two3tree ptr)
Declare Sub cprint (x as integer, y as integer, text as string, colour as integer)
Declare Sub display2node(x as integer, y as integer, node as two3node ptr)
Declare Sub display3node(x as integer, y as integer, node as two3node ptr)
Declare Function findrightleaf (tree as two3tree ptr, value as integer) as two3node ptr
Declare Sub sort(p as two3node ptr)
Declare Sub Inserttotemp (src as two3node ptr, dest as two3node ptr)
Declare Function greatestvalue (p as two3node ptr)

Dim shared twonodedisplay as integer ptr
dim shared threenodedisplay as integer ptr
dim shared fontarray(95, 5) as integer  

dim shared diag


'load the font
      OPEN "roman.fnt" FOR BINARY AS #1
      st = 1
      FOR l = 0 TO 95
         FOR x = 0 TO 5
            GET #1, st, fontarray(l, x)
            st = st + 2
         NEXT
      NEXT
      CLOSE
'*********
screenres 800, 600, 32  '800x600x32 bit window
'load the node bitmaps
    BLOAD "23node2.bmp"
    twonodedisplay = imagecreate(31, 18)
    GET (0, 0) - (30, 17), twonodedisplay
    threenodedisplay = imagecreate(58, 18)
    GET (31, 0) - (88, 17), threenodedisplay
'*********
dim tre as two3tree ptr
tre = newTwo3Tree
Open "number.txt" for input as #1
While not eof(1)
   If a then Addvalue tre, a
   displayall tre
   input #1, a
   cprint 0,0,"Press Any Key to add " + STR$(a), rgb(0,25,50)
   sleep
Wend
sleep
deletesubtree tre -> root
deallocate tre 'return mem to osx
close


Function Newtwo3node () as two3node ptr
    return Newtwo3node(0,0)
End Function
    
Function Newtwo3node(value as integer) as two3node ptr
    return Newtwo3node(value, 0)
End Function

Function Newtwo3node(lvalue as integer, rvalue as integer) as two3node ptr
    dim temp as two3node ptr
    temp = allocate(len(two3node))
    temp -> leftvalue = lvalue
    temp -> rightvalue = rvalue
    temp -> leftbranch = 0
    temp -> midbranch = 0
    temp -> rightbranch = 0
    temp -> parent = 0
    return temp
End Function

Sub DisplayAll(tree as Two3Tree ptr)
   BLOAD "aqua.bmp"
   If tree = 0 or tree -> root = 0 then exit sub
   displaynode tree -> root, 400, 100, 1
end sub
  
Sub displaynode (p as two3node ptr, xx as integer, xy as integer, level as integer)
   IF not p -> rightvalue then
      IF p -> leftbranch then 'it has children
         LINE (xx, xy + 9) - (xx - 800 \ (3 ^ level), xy + 59), rgb(0,25,150)
         LINE (xx, xy + 9) - (xx + 800 \ (3 ^ level), xy + 59), rgb(0,75,100)
         displaynode p -> leftbranch, xx - 800 \ (3 ^ level), xy + 50, level + 1
         displaynode p -> midbranch, xx + 800 \ (3 ^ level), xy + 50, level + 1  'no need to check if it has one branch is has 2
      end if
      display2node xx, xy, p
   Else
      IF p -> leftbranch then 'it has children
         LINE (xx, xy + 9) - (xx - 800 \ (3 ^ level), xy + 59), rgb(0,25,150)
         LINE (xx, xy + 9) - (xx, xy + 59), rgb(0,50,125)
         LINE (xx, xy + 9) - (xx + 800 \ (3 ^ level), xy + 59), rgb(0,75,100)
         displaynode p -> leftbranch, xx - 800 \ (3 ^ level), xy + 50, level + 1
         displaynode p -> midbranch, xx, xy + 50, level + 1
         displaynode p -> rightbranch, xx + 800 \ (3 ^ level), xy + 50, level + 1  'no need to check if it has one branch is has 3
      end if
      display3node xx, xy, p
   End if
end sub

Sub AddValue(tree as two3tree ptr, value as integer)
   dim temp as two3node ptr
   temp = NewTwo3Node(value)
   IF tree -> root = 0 then 'new root node
      tree -> root = temp
      tree -> size = 1
      tree -> depth = 1
      exit sub
   end if
   dim p as two3node ptr
   p = findrightleaf(tree, value)
   AddNode(p, tree, temp)
End Sub

Sub AddNode (pp as two3node ptr, tree as two3tree ptr, pnode as two3node ptr)
   dim p as two3node ptr, node as two3node ptr
   p = pp
   node = pnode
   If not p -> rightvalue then
      p -> rightvalue = node -> leftvalue
      IF p -> leftbranch = node then
         p -> leftbranch = node -> leftbranch
      else p -> midbranch = node -> leftbranch
      end if
      p -> rightbranch = node -> midbranch
      deallocate node
      sort p
   else  'i have to promote
         'first insert all the values
         p -> tempvalue = node -> leftvalue
         IF p -> leftbranch = node then
            p -> leftbranch = node -> leftbranch
         elseif p -> midbranch = node then p -> midbranch = node -> leftbranch
         else p -> rightbranch = node -> leftbranch
         end if
         p -> tempbranch = node -> midbranch
         sort p
         'now split it up
         dim node2 as two3node ptr
         node2 = NewTwo3Node(p -> leftvalue)
         node2 -> leftbranch = p -> leftbranch
         node2 -> midbranch = p -> midbranch
         node2 -> parent = p
         IF node2 -> leftbranch then node2 -> leftbranch -> parent = node2
         IF node2 -> midbranch then node2 -> midbranch -> parent = node2
         deallocate node
         node = NewTwo3Node(p -> rightvalue)
         node -> leftbranch = p -> rightbranch
         node -> midbranch = p -> tempbranch
         node -> parent = p
         IF node -> leftbranch then node -> leftbranch -> parent = node
         IF node -> midbranch then node -> midbranch -> parent = node
         p -> rightbranch = 0
         p -> tempbranch = 0
         p -> leftbranch = node2
         p -> midbranch = node
         p -> leftvalue = p -> tempvalue
         p -> rightvalue = 0
         p -> tempvalue = 0
         tree -> size = tree -> size + 1
         IF p -> parent then
            Addnode p -> parent, tree, p
         ELSE
            tree -> root = p
            tree -> depth = tree -> depth + 1
         end if
   end if
End Sub

Sub DeleteTwo3Tree(tree as Two3Tree ptr)
   DeleteSubTree (tree -> root)
   Deallocate tree
   tree = 0
End Sub

Sub Deletesubtree(node as two3node ptr)
   IF node -> rightbranch then Deletesubtree node -> rightbranch
   If node -> midbranch then Deletesubtree node -> midbranch
   If node -> leftbranch then DeleteSubtree node -> leftbranch
   deallocate node
   node = 0
end sub

sub display2node(x as integer, y as integer, node as two3node ptr)
    put (x - 16, y), twonodedisplay, ALPHA, 196
    dim strin as string
    strin = STR$(node -> leftvalue) + ",_" + STR$(node -> rightvalue)
    xx = x + 15 - len(strin) * 3
    cprint xx - 5, y + 4, STR$(node -> leftvalue), 0
end sub

sub display3node(x as integer, y as integer, node as two3node ptr)
    put (x - 29, y), threenodedisplay, ALPHA, 196
    dim strin as string
    strin = STR$(node -> leftvalue) + ",_" + STR$(node -> rightvalue)
    xx = x + 29 - len(strin) * 3
    cprint xx - 26, y + 4, STR$(node -> leftvalue) + ",_" + STR$(node -> rightvalue), 0
end sub

SUB cprint (x as integer, y as integer, text as string, colour as integer)
   FOR ll = 1 TO LEN(text)
      l = ASC(MID$(text, ll, 1)) - 33
      IF l <> 62 AND l > -1 THEN
         FOR a = x TO x + 5
            LINE (a, y)-(a, y + 15), colour, , fontarray(l, a - x)
         NEXT
      END IF
      x = x + 6
   NEXT
END SUB

Function Newtwo3tree () as two3tree ptr
    dim temp as two3tree ptr
    temp = allocate(len(two3tree))
    temp -> root = 0
    temp -> depth = 0
    temp -> size = 0
    return temp
End Function

Function findrightleaf (tree as two3tree ptr, value as integer) as two3node ptr
   dim p as two3node ptr
   p = tree -> root
   while p -> leftbranch  'traverse to the leaf level
      IF value < p -> leftvalue then
         p = p -> leftbranch
      ELSEIF p -> rightvalue > 0 and value > p -> rightvalue then p = p -> rightbranch
      ELSE p = p -> midbranch
      end if
   wend
   return p
End Function

Sub Sort (p as two3node ptr)
   If p -> tempvalue then
      'get the tempvalue in the middle
      If p -> tempvalue > p -> rightvalue then SWAP p -> tempvalue, p -> rightvalue
      If p -> tempvalue < p -> leftvalue then SWAP p -> tempvalue, p -> leftvalue
   END IF
   IF p -> rightvalue then
      IF p -> rightvalue < p -> leftvalue then SWAP p -> rightvalue, p -> leftvalue
   END IF
  
   'now lets order the branches
  
   'lowest = left, highest = temp
   FOR i = 0 TO 2  '3 times through to set right if in reverse order
      IF p -> leftbranch then
         If greatestvalue(p -> leftbranch) > p -> midbranch -> leftvalue then SWAP p -> leftbranch, p -> midbranch
      END IF
      IF p -> rightbranch then
         IF greatestvalue (p -> midbranch) > p -> rightbranch -> leftvalue then swap p -> midbranch, p -> rightbranch
      End if
      IF p -> tempbranch then
         IF greatestvalue (p -> rightbranch) > p -> tempbranch -> leftvalue then swap p -> rightbranch, p -> tempbranch
      END IF
   NEXT
END SUB

Sub Inserttotemp (src as two3node ptr, dest as two3node ptr)
   dest -> tempvalue = src -> leftvalue
   IF dest -> leftbranch = src then
      dest -> leftbranch = src -> leftbranch
      dest -> tempbranch = src -> rightbranch
   ELSEIF dest -> midbranch = src then
      dest -> midbranch = src -> leftbranch
      dest -> tempbranch = src -> rightbranch
   ELSE
      dest -> rightbranch = src -> rightbranch
      dest -> tempbranch = src -> leftbranch
   END IF
   sort dest
   Deallocate src  'return memory to OS X
End Sub

Function greatestvalue (p as two3node ptr)
   IF p -> rightvalue then return p -> rightvalue
   return p -> leftvalue
End Function

number.txt:

13
65607

2
4
6
7
3
5
18
1
14
6
200
100
123
143
164

It displayed the tree correctly until it has to triple promote. Here is the tree before hand:

. 4,7
. 2 6 18,200
1 3 5 6 14 100,123 65607

Then when i try to insert 143, nothing happens except I loose 100 from the three node that its in. leaving me with:

. 4,7
. 2 6 18,200
1 3 5 6 14 123 65607
[/code]