#!/usr/bin/env python

GAP_CHUNK = 16

def Buffer(buffer, gapBeginning, gapEnd, size):
	def memmove(dest, src, n):
		nonlocal buffer
		assert(dest >= 0)
		assert(src >= 0)
		assert(n >= 0)
		assert(dest + n <= len(buffer))
		assert(src + n <= len(buffer))
		#print("move", dest, src, n)
		if dest < src:
			for i in range(n):
				buffer[dest + i] = buffer[src + i]
		elif dest > src:
			for i in range(n - 1, -1, -1):
				buffer[dest + i] = buffer[src + i]
		else:
			pass
	def moveGapTo(position):
		nonlocal buffer
		nonlocal gapBeginning
		nonlocal gapEnd
		gapSize = gapEnd - gapBeginning
		newGapBeginning = position
		newGapEnd = newGapBeginning + gapSize
		leftBeginning = min(gapBeginning, newGapBeginning)
		rightEnd = max(gapEnd, newGapEnd)
		# leftBeginning and rightEnd are on the gap boundaries.
		if leftBeginning < gapBeginning:
			memmove(leftBeginning + gapSize, leftBeginning, gapBeginning - leftBeginning)
		elif rightEnd > gapEnd:
			memmove(gapBeginning, gapEnd, rightEnd - gapEnd)
		else:
			pass
		for i in range(newGapBeginning, newGapEnd):
			buffer[i] = "#"
		gapBeginning = newGapBeginning
		gapEnd = newGapEnd
	def growGapTo(newGapSize): # grows to at least newGapSize!
		nonlocal gapBeginning
		nonlocal gapEnd
		gapSize = gapEnd - gapBeginning
		if newGapSize > gapSize:
			newGapSize = int((newGapSize + GAP_CHUNK - 1) / GAP_CHUNK)*GAP_CHUNK
			growSize = newGapSize - gapSize
			bufferCapacity = len(buffer)
			for i in range(growSize):
				buffer.append("!")
			memmove(gapEnd + growSize, gapEnd, bufferCapacity - gapEnd)
			gapEnd = gapBeginning + newGapSize
	def insert(position, text):
		nonlocal buffer
		nonlocal size
		nonlocal gapBeginning
		growGapTo(len(text))
		moveGapTo(position)
		buffer[position : position + len(text)] = text
		gapBeginning += len(text)
		size += len(text)
		assert(gapBeginning <= gapEnd)
	def getText():
		return "".join(buffer[:gapBeginning] + buffer[gapEnd:])
	def getSize():
		return size
	def clone():
		return Buffer(buffer[:], gapBeginning, gapEnd, size)
	def dump():
		print("".join(buffer))
		print(gapBeginning)
		print(gapEnd)
		print(size)
	return lambda name: {
		"insert": insert,
		"getText": getText,
		"getSize": getSize,
		"clone": clone,
		"dump": dump,
	}[name]
def newBuffer():
	buffer = []
	gapBeginning = 0
	gapEnd = 0
	size = 0
	return Buffer(buffer, gapBeginning, gapEnd, size)

def test1(expectedBuffer, buffer, position, text):
	def insertExpected(position, text):
		nonlocal expectedBuffer
		expectedBuffer[position:position] = [c for c in text]
	def insert(position, text):
		buffer("insert")(position, text)
	def getExpectedText():
		return("".join(expectedBuffer))
	def getText():
		return(buffer("getText")())
	def getSize():
		return(buffer("getSize")())
	def insertAndCheck(position, text):
		insert(position, text)
		insertExpected(position, text)
		return(getText() == getExpectedText())
	def clone():
		return(buffer("clone")())
	backup = clone()
	if not insertAndCheck(position, text):
		backup("dump")()
		print("tried to insert at position", position, text, file=sys.stderr)
		assert(False)
def test2(expectedBuffer, buffer):
	import random
	for z in range(10000):
		print("try ", z)
		#print("size", buffer("getSize")())
		position = random.randint(0, buffer("getSize")())
		count = random.randint(0, 100)
		text = "".join([chr(random.randint(48, 90)) for c in range(count)])
		test1(expectedBuffer, buffer, position, text)
def test3():
	expectedBuffer = []
	buffer = newBuffer()
	test1(expectedBuffer, buffer, 0, "A")
def loadBufferIns(text, gapBeginning, gapEnd, size, insertPosition, insertText):
	assert(gapBeginning <= gapEnd)
	assert(gapEnd <= len(text))
	assert(size == len(text) - (gapEnd - gapBeginning))
	v = [c for c in text]
	buffer = Buffer(v, gapBeginning, gapEnd, size)
	expectedBuffer = (v[:gapBeginning] + v[gapEnd:])[:]
	test1(expectedBuffer, buffer, insertPosition, insertText)
def main2():
	#loadBuffer("R;128WAECZK8TJUO=QK0F3YG43J5DB2UPG3YTAK>V:0H57GZ>HC70K04?R<<C@N22TF37BJNT8GKUIGOU3J5P9RYTFIKZLBI@S6FU@;QJM8MYNP00T178@QXAJ;EL5:Q?6V3J4VJHZFP8Z6F=R02GL0HWPMM=8WT1UEB>OSJW:;NTSRNM7L5ER2:T9O<TPL=>DMAGX1E86AICYFHK?Q;<C;S3X;L5;R9TU@MQOPH<;CAJRT<5Y7;UZL@73F=;604LH35F5LDZKYU5N@D5BK8S<9=A0YA4L<:1B41=9S31DHR89EMMD5@7ZGAN<DRYXTEHKD=ETFIR6HH;PYK8<M7R:Y>KQRY3C1?7D<U;WXL8;;D@F?R68U0GQ@538EEI;LCSA=<0RHQA2GKBMRUY?@8RTOOMY47@;67>:O?T1JVKGEDJ=OEL>E0I?@JK5EXQVNQJKW>MDA:3?EJ37ZO7Q=?QU;AOXQ@:3KTO37?0ZPYYU7HZZDNUAPSN2BT1G3BTI2M@XD9J;UMQIDX2YPO<RAG1ISYX3W<?6EN=@J886JN@GFMCWZVILL6HZKYG8OTY@TY:1MJEL;A?TZ174VCU73CVJ6ZU:JN8NPGCWGBF;ETY:QJL0KI?5CR51UW<@JU5=?Q@M731Q>ZSO6XL4OTYD4DSVCV8JR7X0DSOJ>33OWQ;M<83LEC0M7EX;6D8>S5GJY7:6FDG:=4RSE5XV5P3YMGDPB@K6LDIKAQ6A5UTIYNG2U;3R3R0ZZOPZ6CBCXZPOW;?HVH>D@O6ATNW4V2NG4@LS=HHE41Y289A>ECY3RNOQ<@G2MKGKZOO;U4GTI=F2LCHU", 98, 98, 834)
	buffer = loadBufferIns("KFQYPJ29LRQ5>ZRD@YVX?0R2=Z9<FJ0XXI>JGO1<K9Z7PKI4?4=Y94:3BOA=2;CKIEKT6@EP5PBIPGJDR>Y5R8MJR3VM@IW8N3X3XVHIC0I5NIDMSMI3?1ORN:8?807DN6>>:IQMF:3WCY?W7F4DZSE2ZTM07?H:=ROK6:0M>D10IDF9JNBD=L:3KH16=CS6VT;TI3L3V15@T5Z1WTB6=9<Z1MXNSB1I8CLUR0KQRW>HP?VTYL<U:625W>T7:C?08ZJ87J6;J8K5U4THQELTL7NPDYRRC>GLO79<V7S15AWMCGANTBIP8>3DW<MVWWZLHVGZ@>O1TLI59Q<HVJ5KKPQ6H;ZCA4556MT7A0?K:5><6ZOOHEWE3I?85389Q03SPQEBT::RUZXMTID:7A91@ERZ>4E3VM?XNI<ZF4HDZ206=0:6TP0IKS77CAP4TKDP;N=QYN>>3<E>0WQUI4L8JR2EPMOI3S>OJBBB?M5S6?LJ2IC3I;RTN5WW:T3BL7<CN;RVQGACXRRXZDAZMZI30MV3MCHPYZOYP50KENPDJ5UXIL0@XOVV8L>3I6X3=J=458G>@O0ZBPYXPT2VAR>26E;U04Q:9@D2M4@;9Z;HWUM?ZO=2F6:OZ5>L46C8TIE>GAMKY4CW6VNQX2@3VYA<ZMWQSC;<C7XH0QWE>ALK4=8<YRJ<87ZI><2<8PU<D:II3>BKMJQ40X2RH@PZ:G>YRECWWN>FBLJY1U=OAX7A?KWDM:N07NM:BTU6DWPT;6QO1J7IUSAWCYNJ@@ZWHRKN6QW@IUQ:ZIPMOL?PERS91W8W5DZHXSUI3CK2>>FGRJH3MMYYWWD>B20QJZJIXEPT0EI3ZJ7CVUPFSUI70RSO3VZRFJML4BTY@YZJS?S:X0X0=OX?SX:4ES9E8@TNAQQQ5Z4GHT4R788N582S<ZTUEG4<U0EX9;SA2", 482, 482, 949, 932, "CGR7;>2BX=QWHAZO=DBXI82H91KK")
	#tried to insert at position 932 CGR7;>2BX=QWHAZO=DBXI82H91KK
	pass
def main3():
	buffer = loadBufferIns("1X>@GPLX8G7?R:<R;=GMUF9;02A7>7BO1>NO3PELE;M2TXXZH@R6U52ZE8OXEVJ9Z3VHISWBMGRHU=DYMN?J5GP4WP<KXP4>115QQJIU8YP@SL=6S;E8=HMAIVJ?SD;8LPSW820W6@Y0APE9>LG9JI0H8<LG8F;CGZ7?S<<AU?MG>;SM6?WIBXRK;F?G48@88J02:E84OZR6E=QFLDR201DUQ5:S;1R<9ZG3IMWK6YSAV97SSWL6C4LS73H61P<YOVKC8P;ASB4L6GR8<5ZIU>QS01O?8S9RX@HM21;VK4:@YX37EM4HQ4EBX4Z8BX?K=WVZD9?8O=78S:HIBQ@97X>PSJ;@4:GLN<YT;MH0Q?YMLZ07K2DDWBMVO2TDSKQ=60<Q@VA6:Y@DSD@;0NIWI3DK?3EU6J66>RUSOW7ECK:NP>:995;T<:B<<W<KV>T=XJ2TA7OJB<>6K9J>JBLFSM2J7T1K@?;HR7AZ8AEHWN8<0CCJ;MM516GW8UAL?ZJG9ADOZTKREC@3M97:4Y16L4ECF26YT8EF@F9<8M=?NXPDCD8768AQJJG>85SU<41####>5>UK:@85@K6<;33S>PU8JYHX4AY@?>YCV57;XVL1?IM73H:LR>TBM=X>YNLVQE6R95BR1=<==75<?19PFKGZF5VHUHYM@X4QDVO3N1X4MEWP11OUKMG57A>Y47B<SLSZIFYWP=1JT@6NVRD0>=LWABNTBKFWASZP8IWKNOT57OXXL@:MZJICZFXK4J1SMDP9HQ7UVFYN?IHPK0Q8F;O44GNCF?S6MG>3LDNOXX4><9=9<;7D6SPX5H=1CYW;R7068U27UXZA01HA>6WTJ@D;G6BW?993@I9=ZXV=KBS:RO@2Y?:DDS?JI@<I10N5D46:QCAZOCVZL", 575, 579, 905, 498, "A")
if __name__ == "__main__":
	main3()
	test3()
	expectedBuffer = []
	buffer = newBuffer()
	#main2()
	test2(expectedBuffer, buffer)