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]
}