Mercurial > repos > rhope

changeset 126:85f8012b6938

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Simplify and speed up List by removing support for sparse Lists
author Mike Pavone <pavone@retrodev.com>
date Thu, 28 Oct 2010 21:39:17 -0400
parents e556416e9c91
children
files list.rhope
diffstat 1 files changed, 37 insertions(+), 131 deletions(-) [+]
line wrap: on
line diff
--- 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]
 }
+