Mercurial > repos > rhope
view list.rhope @ 126:85f8012b6938
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 | f4fc0a98088a |
children |
line wrap: on
line source
Blueprint List Leaf { Buffer } Index@List Leaf[list,index:out,not found] { out, not found <- [[list]Buffer >>]Index[index] } Set@List Leaf[list,index,value:out,invalid index] { len <- [[list]Buffer >>]Length If[[[index] > [7]] And [[index] >= [len]]] { out <- [[[[[[Build[List()] ]Buffer << [Array[]] ]Left << [list] ]Right << [List[]] ]Offset << [8i32] ]Length << [[list]Length] ]Set[index, value] }{ out <- [list]Buffer <<[ [[list]Buffer >>]Set[index, value] ] } } Length@List Leaf[list:out] { out <- [[list]Buffer >>]Length } Last@List Leaf[list:out,none] { len <- [[list]Buffer >>]Length ,none <-If[len] { out <- [len]-[1] } } Append@List Leaf[list,val:out] { [list]Last { index <- [~]+[1] } { index <- 0 } out <- [list]Set[index, val] } First@List Leaf[list:out,none] { [[list]Buffer >>]Index[0] { out <- 0 } { none <- Yes } } Next@List Leaf[list,index:next,none] { pos next <- [index]+[1] ,none <- If[[pos next] < [[list]Length]] { next <- Val[pos next] } } Blueprint List { Buffer Left Right Offset(Int32,Naked) Length(Int32,Naked) } List[:out(List)] { out <- [Build[List Leaf()]]Buffer <<[Array[]] } Index@List[list,index:out,not found] { offset <- [list]Offset >> If[[index]<[offset]] { out, not found <- [[list]Left >>]Index[index] }{ right offset <- [offset]+[8i32] If[[index] < [right offset]] { out, not found <- [[list]Buffer >>]Index[[index]-[[list]Offset >>]] }{ out, not found <- [[list]Right >>]Index[[index]-[right offset]] } } } Length@List[list:out] { out <- [list]Length >> } Set@List[list,index,val:out,invalid index] { If[[index]>[[list]Length]] { out <- [[list]Set[[index]-[1], val] ]Set[index, val] }{ offset <- [list]Offset >> If[[index]<[offset]] { lsize <- [[list]Left >>]Length ,invalid <- [[list]Left >>]Set[index, val] { out <- [[list]Left <<[~] ]Length <<[ [[list]Length >>]+[[[~]Length]-[lsize]] ] } }{ right offset <- [offset]+[8] If[[index]<[right offset]] { off index <- [index]-[[list]Offset >>] bsize <- [[list]Buffer >>]Length [[list]Buffer >>]Set[off index, val] { out <- [[list]Buffer <<[~] ]Length <<[ [[list]Length >>]+[[[~]Length >>]-[bsize]] ] } }{ rsize <- [[list]Right>>]Length adj ind <- [index]-[right offset] If[[[[list]Left>>]Length] > [rsize]] { [[list]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] ]Length << [ [[list]Length]+[1] ] } } } } } Last@List[list:out,none] { out <- [[list]Length]-[1] } Append@List[list,val:out] { [list]Last { index <- [~]+[1] } { index <- 0 } out <- [list]Set[index, val] } First@List[list:out,none] { If[[[list]Left >>]Length] { out <- [[list]Left >>]First }{ out <- [list]Offset >> } } Next@List[list,index:next,none] { pos next <- [index]+[1] ,none <- If[[pos next] < [[list]Length]] { next <- Val[pos next] } } New Like@List[in:out] { out <- List[] } New Like@List Leaf[in:out] { out <- List[] } //TODO: Implement a more efficent version of this _Tail[list, cur, dest:out] { ndest <- [dest]Append[[list]Index[cur]] [list]Next[cur] { out <- _Tail[list, ~, ndest] }{ out <- Val[ndest] } } Tail[list,start:out] { newlist <- New Like[list] [list]Index[start] { out <- _Tail[list, start, newlist] }{ out <- Val[newlist] } } Concatenate[left,right:out] { out <- Fold[Append[?], left, right] } Print@List Leaf[list:out] { If[[[list]Buffer >>]Length] { Print["List"] { out <- _Print Seq[list, [list]First] } }{ out <- Print["List\n\t{Empty}"] } } Print@List[list:out] { Print["List"] { out <- _Print Seq[list, [list]First] } } Peek@List[list:out,empty] { [list]Last { out <- [list]Index[~] }{ empty <- list } } Peek@List Leaf[list:out,empty] { [list]Last { out <- [list]Index[~] }{ empty <- list } } _Check Present[check in,val,index:out] { [check in]Index[index] { If[[~]=[val]] { out <- No } { out <- Yes } }{ out <- Yes } } _=List[a,b:out] { ,out <- If[[[a]Length]=[[b]Length]] { [a]Find[_Check Present[b,?]] { out <- No }{ out <- Yes } } } =@List Leaf[a,b:out] { out <- _=List[a,b] } =@List[a,b:out] { out <- _=List[a,b] }