# HG changeset patch
# User Mike Pavone <pavone@retrodev.com>
# Date 1288316357 14400
# Node ID 85f8012b6938e7227291f9309a7e746db8520101
# Parent  e556416e9c91ecb03d84fc887b8ebd8e17e8dbae
Simplify and speed up List by removing support for sparse Lists

diff -r e556416e9c91 -r 85f8012b6938 list.rhope
--- a/list.rhope	Thu Oct 28 21:07:03 2010 -0400
+++ b/list.rhope	Thu Oct 28 21:39:17 2010 -0400
@@ -11,54 +11,20 @@
 
 Set@List Leaf[list,index,value:out,invalid index]
 {
-	If[[index] < [0]]
-	{
-		rev index <- [[[list]Buffer >>]Length]+[index]
-		invalid index <- If[[rev index] < [0]] {}
-		{
-			out,invalid index <- [list]Set[rev index, value]
-		}
-			
-	}{
-		len <- [[list]Buffer >>]Length
-		If[[index] > [len]]
-		{
-			makeleft <- Yes
-		}{
-			If[[[index] > [7]] And [[index] >= [len]]]
-			{
-				makeleft <- Yes
-			}{
-				out <- [list]Buffer <<[ [[list]Buffer >>]Set[index, value] ]
-			}
-		}
-	}
 
-	Val[makeleft]
+	len <- [[list]Buffer >>]Length
+	
+	If[[[index] > [7]] And [[index] >= [len]]]
 	{
 		out <- [[[[[[Build[List()]
-			]Buffer << [[Array[]]Append[value]]
+			]Buffer << [Array[]]
 			]Left << [list]
 			]Right << [List[]]
-			]Offset << [index]
-			]Right Offset <<[[index]+[8i32]]
-			]Length << [ [[list]Length]+[1] ]
-	}
-}
-
-_Right Set@List Leaf[list,index,val:out,didn't set]
-{
-	len <- [[list]Buffer >>]Length
-	do it <- If[[index] < [len]] {}
-	{
-		,didn't set <- If[[index]=[len]]
-		{
-			didn't set,do it <- If[[index]>[7]]
-		}
-	}
-	Val[do it]
-	{
-		out <- [list]Set[index,val]
+			]Offset << [8i32]
+			]Length << [[list]Length]
+			]Set[index, value]
+	}{
+		out <- [list]Buffer <<[ [[list]Buffer >>]Set[index, value] ]
 	}
 }
 
@@ -106,7 +72,6 @@
 	Left
 	Right
 	Offset(Int32,Naked)
-	Right Offset(Int32,Naked)
 	Length(Int32,Naked)
 }
 
@@ -117,15 +82,17 @@
 
 Index@List[list,index:out,not found]
 {
-	If[[index]<[[list]Offset >>]]
+	offset <- [list]Offset >>
+	If[[index]<[offset]]
 	{
 		out, not found <- [[list]Left >>]Index[index]
 	}{
-		If[[index] < [[list]Right Offset >>]]
+		right offset <- [offset]+[8i32]
+		If[[index] < [right offset]]
 		{
 			out, not found <- [[list]Buffer >>]Index[[index]-[[list]Offset >>]]
 		}{
-			out, not found <- [[list]Right >>]Index[[index]-[[list]Right Offset >>]]
+			out, not found <- [[list]Right >>]Index[[index]-[right offset]]
 		}
 	}
 }
@@ -137,60 +104,34 @@
 
 Set@List[list,index,val:out,invalid index]
 {
-	If[[index] < [0]]
+	If[[index]>[[list]Length]]
 	{
-		, invalid index <- [list]Last
-		{ rev index <- [[~]+[1]]+[index] }
-		invalid index <- If[[rev index] < [0]] {}
-		{ out,invalid index <- [list]Set[rev index, val] }
-		
+		out <- [[list]Set[[index]-[1], val]
+			]Set[index, val]
 	}{
-		If[[index]<[[list]Offset >>]]
+		offset <- [list]Offset >>
+		If[[index]<[offset]]
 		{
 			lsize <- [[list]Left >>]Length
-			[[list]Left >>]Set[index, val]
+			,invalid <- [[list]Left >>]Set[index, val]
 			{
 				out <- [[list]Left <<[~]
 					]Length <<[ [[list]Length >>]+[[[~]Length]-[lsize]] ]
 			}
 		}{	
-			
-			If[[index]<[[list]Right Offset >>]]
+			right offset <- [offset]+[8]
+			If[[index]<[right offset]]
 			{
 				off index <- [index]-[[list]Offset >>]
 				bsize <- [[list]Buffer >>]Length
-				If[[off index]>[bsize]]
+				[[list]Buffer >>]Set[off index, val]
 				{
-					If[[[list]Right >>]Length]
-					{
-						my end <- [[list]Offset >>]+[[[list]Buffer >>]Length]
-						nroffset <- [[[index]-[my end]]/[2]]+[my end]
-						nright <- out <- [[[[[[Build[List()]
-							]Buffer << [[Array[]]Append[val]]
-							]Left << [List[]]
-							]Right << [[list]Right >>]
-							]Offset << [[index]-[nroffset]]
-							]Right Offset <<[ [[list]Right Offset>>]-[nroffset] ]
-							]Length << [ [[[list]Right >>]Length]+[1] ]
-
-						out <- [[[list]Right <<[nright]
-							]Length <<[ [[list]Length >>]+[1] ]
-							]Right Offset <<[nroffset]
-					}{
-						out <- [[[list]Right <<[ [[list]Right >>]Set[0, val] ]
-							]Right Offset <<[index]
-							]Length <<[ [[list]Length >>]+[1] ]
-					}
-				}{
-					[[list]Buffer >>]Set[off index, val]
-					{
-						out <- [[list]Buffer <<[~]
-							]Length <<[ [[list]Length >>]+[[[~]Length >>]-[bsize]] ]
-					}
+					out <- [[list]Buffer <<[~]
+						]Length <<[ [[list]Length >>]+[[[~]Length >>]-[bsize]] ]
 				}
 			}{
 				rsize <- [[list]Right>>]Length
-				adj ind <- [index]-[[list]Right Offset>>]
+				adj ind <- [index]-[right offset]
 				If[[[[list]Left>>]Length] > [rsize]]
 				{
 					[[list]Right >>]Set[adj ind, val]
@@ -199,41 +140,21 @@
 							]Length <<[ [[list]Length >>]+[[[~]Length]-[rsize]] ]
 					}
 				}{
-					[[list]Right >>]_Right Set[adj ind, val]
-					{
-						out <- [[list]Right <<[~]
-							]Length <<[ [[list]Length >>]+[[[~]Length]-[rsize]] ]
-					}{
-						out <- [[[[[[Build[List()]
-							]Buffer << [[Array[]]Append[val]]
-							]Left << [list]
-							]Right << [List[]]
-							]Offset << [index]
-							]Right Offset <<[[index]+[8i32]]
-							]Length << [ [[list]Length]+[1] ]
-					}
+					out <- [[[[[Build[List()]
+						]Buffer << [[Array[]]Append[val]]
+						]Left << [list]
+						]Right << [List[]]
+						]Offset << [index]
+						]Length << [ [[list]Length]+[1] ]
 				}
 			}
 		}
 	}
 }
 
-_Right Set@List[list,index,val:out,didn't set]
-{
-	If[[[list]Right Offset >>]>[index]]
-	{
-		out <- [list]Set[index, val]
-	}{
-		,didn't set <- [[list]Right >>]_Right Set[[index]-[[list]Right Offset >>], val]
-		{ out <- [list]Right <<[~] }
-	}
-}
-
 Last@List[list:out,none]
 {
-	[[list]Right >>]Last 
-	{ out <- [~]+[[list]Right Offset >>] }
-	{ out <- [[[[list]Buffer >>]Length]-[1]]+[[list]Offset >>] }
+	out <- [[list]Length]-[1]
 }
 
 Append@List[list,val:out]
@@ -256,25 +177,10 @@
 
 Next@List[list,index:next,none]
 {
-	If[[index] < [[[list]Offset >>]-[1]]]
+	pos next <- [index]+[1]
+	,none <- If[[pos next] < [[list]Length]]
 	{
-		next <- [[list]Left >>]Next[index] {}
-		{ next <- Offset >>[list] }
-	}{
-		If[[index] < [[list]Right Offset >>]]
-		{
-			pos next <- [index]+[1]
-			If[[pos next] < [[[[list]Buffer >>]Length]+[[list]Offset >>]]]
-			{
-				next <- Val[pos next]
-			}{
-				,none <- [[list]Right >>]First
-				{ next <- [~]+[[list]Right Offset >>] }
-			}
-		}{
-			,none <- [[list]Right >>]Next[[index]-[[list]Right Offset >>]]
-			{ next <- [~]+[[list]Right Offset >>] }
-		}
+		next <- Val[pos next]
 	}
 }
 
@@ -332,7 +238,6 @@
 	{ out <- _Print Seq[list, [list]First] }
 }
 
-
 Peek@List[list:out,empty]
 {
 	[list]Last
@@ -387,3 +292,4 @@
 {
 	out <- _=List[a,b]
 }
+