ÿØÿà JFIF    ÿÛ „ !.%+&8&+/1555$;@;4?.451 4,$,44444444444414444444444444444444444444444444444444ÿÀ  á á" ÿÄ     ÿÄ ?    !1AQaq"2‘¡±ÁðBRbrÑá#‚’¢²3S CñÿÄ   ÿÄ !    !1QAa‘2ÿÚ   ? 5˜Z¯V¦cø)›t/? z¨±>Õ5€¶‹Á¤·¼z¼Ü¬+ñ®v¤¨_ˆR­BFn©—˜ý®ç̝P8gýt·ÉSTŦˆìät?þé¼íìN/Þa)ì–í6ô… Ï¿øÃj´¿KÇü]ÿ ªô¹-eKànëÕHTx}ýSÜ›ÿ ”7Ø×&µ<¦  ¥ÑO¶[Ù¯ä¨ÞÃÿ PZ-¬;#õ|•oaÿ ©CìÞz3˜öː/¤­ñTûIØ}š^ mÓ%ªxˆ¥ÉŸu=Z+ISe¿45™¼u;ú&WØ÷€æßQ™®{|íx*TC“#ZŠìZ§²‹ 6pv…³¿¡äª*áZÐ%ÒOáˆo"x«OHk w±æ+¬V(kMúŸ5Vö«$ ÁrÏbàb57/luR ¸ÑÛj Òµì`Ðœq­û žICÀÊ•©4€Âcà¨Ï€O´<èÐ:›ù(Ë^L8þ‘ÍÌ#¸Ð_Ì©ÙK(Öz 4¬û+¸;ü’V’84‘¬ÃŽ:[â‡ÔÌáõp¢~§ªlæ£ö{®G>J¼"°‡7¯ÆÉèßû ‹É‹§ÁòÃýâßî ^ƾÙõ‹×óH#«LP½ïX=xÑÍ$|W?•~• îëÔ©ª‹ {ÝT…Kÿ ”hûâá)J*ö˜–ÔU;iÇ€/ ÆþjóZ\ýwØ=Ìm ºèËL9 ýèÆð/¨’¥öo=nË.%Îì ŽÕ¯È|{Oj²ƒE6e/ßdÄõ²Ìâ1O®ò×TsəԸhOMýíMˆ¿¼H˜l²,7Â¥#MF/Úf°Ö½± ¸–dr‹NýÊ íjqx{œÉ ä-È ¦ øÄër¨q°ð †nцýÑÄÆ’mä…n<0È™;ÁÝá¯ÁZƒ7FÀmì­ É&9ˆîéi¶ùN§Y• ÃZãAâ?•‡©‰ , ó¾IŸŠc1 4â&y­&pŠ­6;M À 0¹qç»p.á …ŸÅáK@%6·y6ƒ‰3?”úºŽ‰éX5ªPT §µ!=Mž«Ú½‹ÅgÂSâÉaþÓoö–¯ÁÔìR>5éÿ üs¶ÆUcÌ kÇR ]ÿ ù¬¼«VŽ;Â|‡~¢¦”ÏÅ°æ {L™Õ°Óv¹ò¸írŽ¡×¢CÃ!íVÕ {¶»sŒNPg/ "uÕbkm²“$ďå¿é¹§°½æz¯6 †s¿!s–wÚÝ“™Œ °.ûj>·+™Òa…©Œ&rÝÎtÛë긪Ît’LAVp%c Úý[ÄzJ¾ÇàXXç@˜ó<êL]·T˜¾¥1Ó©V‡g´æ½¦Ý@¹óø!_@´ÞâSÁ —S3™•& ]@JHÚý©ZŽ €×æÔr»Áf!‡yÞ4Mv*èÓã_{‘åóUuљØ«Oïé*®EvÑ Œ÷‡U \"㪒ÍK+À 4“M¡ï:0¥5í!'<@î´”>Ç»&Z–ïCCV˜Ì5Šo&îhè.žû |ÓK©h$s6KìŒëã)¹hI¦GïOåóI;ììü#É$Š0…Ææ¥TØ.5­¾gn´ “ÂÖ\:hœ89G)J@„}œ:’Ò{/Š"¦_Æ×7Æ3VÇŠÊa]ÚŒÙ€Ä–=®uÁßâACZƒ§§£ Qnâ:«,×{tyø¬iÛcœÜÄ€H½ÄÍCk´÷šß .W'b¤Íåh]÷€=,Žv×cÚEÚHXJX¶îo¨FÒtèöŸ>ªª6[J®Fµ£sGÁeqõfe\íjÒÐïÄÐGˆe1Ø‹.Ø”‘Ëuø Y­ˆÜ ŽG|zùªüMpDnQWÄ”%JŠ™)â*p@Örš«ÕT2Ð%ˆG#ª„ ·¤!°ŸOTÂT¸aÚ%4&h™LµšØüÐ.F¿²ÐÞ_Ç‚¾ÅÃaÜ÷09Æ q€öy˜v‡85õN÷]¬äѼóS{°_MŽ¬úÔ#°Ç¸0åÞè2ëôPcvÆw9®ií1Ä8F™˜à‰´+‰Ik1òÝ7“Ñ×ÒsÝ\x‚h`ÞÑ`ó"|µEcý£n˜h`}GÞ !±ù²Ápü²ß6 0ïi󜵩SÈÇ7˜-ÕURO˜¦´f$ªž-Í6(œ}<„ éc øs]ŽŽ„*—¾ ìdŽ„)méª\¿êÎIg¾ØÞ~I#C/¼¼´EÁÈŽi8“©õådô·>euä ƒ'Ê×लR1ÉJE1ÐAát`t;ÇР%Ý<‡¥„ÍÆ`×Oyó)õiI€ñQaŸ4Ûù\áàaÃÔ¹HÃu¹*k€¦<„e S‡&õÏ B!ŽhüÞ`yj}mªf×\¿ Ç~æ­9‡û\՞Ǖg²1Žû5V7 !àöšm° c`ܬøÇìµÒ'P"?…´Ö,"§^•õŽ¨sÔ)6˜sæéÍR¼ ò|Sl”‹7 nPW Gòú÷½§O¯‡„l¡kSÞŒr½PÊ@æ¢pŽ-mÿ #Ÿ˜Àº¶Áä¦;ïÔæ$1££`“Õ>„—·ž)ßð³ñ#Ï Ô$¶œ‰ÊE‹À;÷º ¯«P:Ñ”8–IÊtpÞ3ª“>ê“þës4ò2OÏÕ­±zô†Õ§‰.÷ä¸;¿˜“'œ›žª}«Œ{ª±Ì 9ÔóÞÕ‡0 $íWV3Üì¬ —@kÝ4@¿r¼±½¬™›?øØæ´'Áé®CË3-g$˜ö‡×auÚi´Žp/êÛ æF›Ú2v‹ã¿¿,nB1̨ƃqÞa5͝@&Æû“él÷ \C²½UÍc ¯k×¢U ÖéQå™—-r wô ÞÏ<Ò=&=ÿ Ôê Òêˈt,i—;LîÜ á¸*ÚÃ1$êL•LÍ <É)ýÐà’ ;F™{ƒ™˜€&'}‚ãÄK`¡ÞT@I;®žZóè‚s’7®°›+§O­Åq©é»²9<Ô J ¼9O’HL»Ùïì¸rk¼Ž_ý‘TŸu[²ßÚŒ·ü÷B%¯E ŸÔX5êO´ Ç•€’I0 ÉJX` ñ¹õ%;µŸD‘«´€àwÒ™U ûئžÖö\×®×´8 ½‡ºÐÆÓ§?Àkmœ=;d5*@-ì0F Rªýš[Ü6âö̃ڸr*KA9· u*µæ£?U¸Âêí†8@¦X4 e-ò„0s{ HâUpU?¼mñRa°®a%Ð'tÉ×’\¾ÊÉ]t›h>·(Ë@R¼¡Ãt h}’O÷au<+nT…Ö…MӐ??Óe95 q>í/;&JSû °¯ÊéÞ øƒ*Ã2½Ài&:nôUl=¾¿5eˆ3”ñc|Ú2V”>„»&eE;«ÚäC p¢Û úy 9š[ŒÌx¼擼A&DåÒ¯ˆ¤ÀÌ;"˜ ÏQä¸åhÊ}Ûq«Û0WžÒ|»€ø®öCm5•\ÇÀ§Pe3£]0ÃàLDÉ‰1øªxjgwT‚÷¿LΨK‹›ùs—xˆÜ±µ kæ¸f‰‰ÜGk/LÛØ6d9ò¶ùA{ƒA3š/¬D¬khÓk‰`˜"㯒r¿±Óã jx‡°e}<Ñø\3y:'À•/h½Í€Ç4~g ?Û(¼]v‘ªlKÎâ~?O‚W%{Ì:“'©úNq¾›úo(X’¥¯ˆ nFê{Ç€ü?º'ë ø‹ì Þ09ŒÌç9Æ —ËC`j@ÓÄ(+a‹un¸#ÂꟋ{K`‘ÑÍÍ'à´»/Û,KW;Þ4²þð ï Nm|~fGÏ(…³Ã)«1ö­Õ ¥‡¨©ƒÃ™ü-s=à=U66Ï«Ýc蓦W¹íž®›nÔ%êÇìŒ<#Ü×84ån®Ð ÒåOC` ñânÑs‡¢ç 1õ%Îhì½Ã½® e:ݼUZo™`  ÅZŸŒÊ«ê1ÏÄo$q¹Þ€©ˆhÐÉä¯ñ[!…Ú˜àJ:x2$Íß&PåT£6ç— ‡Í*4Ýšçjÿ ‰É nófÐ ó(L5C•åÆ\rMÒ@ò }y-W}™üýVù—ú¢=Ù”c®‘< M ž ´Phr ¦©TD ‘ù.$´÷O‡‘V2Æò.=IUŒ=ž‡â¬i™aþÓåÙ?òUø'ØÖ•.~* šTŒ!•-×áºTâ®ä#õü'´ eýlYÅÓeÕKÂrT"CÚ@u!Óxƒ{š3€}1¿(r}%«nËamjÑ%ÑNEò v ˜à  σöK³,*º.àzù¨™Ó ÚçâU¦*¿ 9{%Ö¹ njûdaXöb) kÛƱûÓ\°M7ˆÂ=û›ç¿Ã‚­V»Cg–8ÙêE- j)k$º`Ã-ùEýeBÆÇ]c¡°ñty&Òd0nõ'¡W+ƒ*|–øµFa\GQªEAÔp5\Ǽ·¼Ç8·õ -â§Ú[ ‡ uZeÖ 3}×d'+¹:ð+K†Û®s!Ï$úe€<Û”x)1»a­¡LC]¸µík…ÚàA»AYº{†ªS[¦5HÒ7ù --,ísòDØ€èk ÞÀîÜ ò@â( ËNˆë›4ô½•/¦o‡€Û7 ê•ÆêòðÜy'Án½µ á˜ݦ ndeo…[ì¶Ê,¥R³Ä=À±—–ß;£™´ñSâ*g§”ïaið‘Jå~™ÓÞ ß³Õ¢»8x埒²52>AÊb&-÷\7´éÄù€T˜,w;3{ï˜k…à¹ÄqÀ«œ{€\ ˆ¾[´¨јr &Úé„Ívˆ±8†¿]|¬ņ4I×pÞS1ÈÖz‰#Ìv‡G!YNògñ:màTz¢Ý1ô©^O=~ë|5Bã™ç•¼µõ•bÆ@úÕS¬ÈŒ#¬zünrŸ û” Z²•ï›èðV"ÁHÚý©wÝ €7¼Ìu1hÑa3Éä û f$o¿É ™Ú›ÝçnpÒ3äÌ3†Í§,Äï]$‰/pê †«À¼¸e9­Æê_C]žƒ·ý·frÁN«, E=›Çq -‰öŒ:aÏ¿±í&£Í:-} 84‘ÿ eƒQÑeëSsuiA ³g㟥ú£?ÿ ʼn*”“÷aühe:ÊWa@ÒÞk±eØ] F Ô—r.åä˜ @ö¥ªZoÐýYL·¥S²G/‡ñ <~*ZÆ´è>JlòàÛƽÿ 窘ìGN¢:I®KšJp/`íIÁÀõ#Ä-€ö­šµŒoF4|ÆQØÆ@Ì|£Ô…¢À{9˜è½Üó›€ôYÒÎYsið;ís¤€à²ˆ‚4qÉVŒI$ ‰"° æµ8cXGjœˏ¡Aâý•ËÜ¢ûï e·çLx']á"oÅÎê3¯Ç—¹”ó0nå‚âg{Œñ> S´˜îè°g238‚ãköÝfÚd´6Ò€;ò÷±¢™¼›º ¢Æ'¥Ðx'e¬ç ]bÈÆV¢ó‹kýBO ðÊâ$Ÿ!×T 3Mýמ žìٍàÌü‘8÷€àæØ8æ©6‰©L´«…oãpð„~Çk‰!ñ;‹”ÛžÍ àž±z Ÿôû øŸÝužÏ;ÿ #|u6™Þ¬ÚˆÐõA4¶â|ôl|Ê2ŽÇ¤ÝÅÇY.<#Aí.k§hóF‚”Y; M½Ö4hŸ4&›­¿tès´%FìL¥£Ãk‰ÇT¤haÁ¤ÚxfÉ`ÑìË›>i 3t‚:,–+^÷´–{Û–Nxi"x‘Ûg î¨>¥Õ܁ùZH,2Û“:8xÊ¢Çí9.É-Ìâã-=çjwµS˜dütžçwýGòú®®ûº_ˆýx$–¡ãøO EÚÛÏ÷R„×w+3£Á£öUMyR²¹âŒ°š›¸Ñãò9§Ó_Dl+Ùßc›úšGÅÌc†Ž!Ko=¶.‘Îÿ c²(2®V mª.ÿ ¹B›¹å ù„öŸSV>™ü¯$y:G¢Z×àøúdî¹û­·ýÇ´:•c LÍõi_‹ö+ÎæGÊè>OŠ•äž´§Þ{X}¨1ÚTc›»Qþ•êô°t¿OP?eæ~É{5]•ÙR£r5†nZ\ã@ &îJõ ¾àC°þV>fé¥/ü5ñÊIº_é5 ;e­h<@ Ä&æÃëE%;X,ÒãÆÞ`Oò¦kŸm#˜!ÀyÄ¢| óLšò¥Ä` ¶R=|ÈCâh5ò3DˆïF†ðÒ#ÅìÛœ?¸yhBãœí ZxßÎÄhºRK„`Þödvײ™ÀÈÑÒgŒuY w³%†ƒÓzõ ÖÏp‚dH®¦A´ù§»ÓÇMæ~)ˆð‡û:ù&Ä •vGD´À n ݇¼Ö8Fö óáà£~Ë¥x`oK|Ä?fxiØü%pìR>éò+Û±éÎ>núlFŤ'tq8LZÏvÃ?„¡ß±È⽆¯³íü@x|PöUäèØã¡ð‚ŒAìÏ"vÍwóŸÍ{ ý0.z È•Ö{,N¡£¡ŸKÕÙž>Ýœþ ÍÀ°<×EA!Å‚D™IúOÍ¡>ôG}Â` ÍßkÜL™Ž Þð™ {IøF²¹òQ3&!ÃÂÞz.d&Ï-sH¸,Ôõ˜ŽP€ 77ˆÝ¼ÊëÜw =cÕ Ú,ØÐ5ÎYÐ)ì´öœgŒ[¤ßv㙑8心>h]§µháYš£²ºÑ.{Ï7Sð•?´~×SÃKýJÛ˜ ™Íäiúu<µX¶1õ^kâçIÑ£sZ4h>j*ÔšD:4­¿_ ÷¸ Õxæÿ ¸?Mù _•­ÊÐ ä ÷ý ÑwL œ­ïnTkÛUÍN©ë:¦fV ¶ÜÔÜMªÅâA½–¿R×TXš-%iTÊT•‡Ù‚JôϐZxWÑè‰f‰òG º ×Õû2aZ7OU3[“×AT–ÞŒ…-‘¤”Ì ì&(ˆ¿­•ƒkï’:ðY¦W‘ Å)“†‘˜³Åtcø˜ñTÂwÚÇ4|üLÇªí–v- qˆèU qPE.†â‘˜µ Æ,ÐÅs]8¾„oúÑ i>ÜxxÈó)ƒ ´æÁâØ$À‰vžŸf$Ž |ãw;ÀÁIJ»b` {¦Ó¤Ú$©YÀ‘n@Óïž«9J¼êG m¤ ܯ¹ÌW4€ÐÒÅÛ‡#褕Ÿn-?í|с¥÷Ú¹¬'´ÞÜ9ÓK `hê£SÄSà?7—Wí_´…óB›»:=Ãïq`<8ñÓŒÑlú2d¬ê³£hÖ[l|$vÝro~'R®‰§°ñmY ͧäP |PUª¹·:3Œ[Û{Xÿ ºâ@‚W–Äé u‚ ¯´*=íή.pûÒdt @G‰¬ s¸ ëÉücr ÞæѨÊ@>¤¢Ö±. Þ'¯°ÌME[YéïĵÂCå½ Ué©Áû'Ê9%eÔðNU”ë‘ÌsD3/®+UI˜9h.WC”빓$#:pz:YÓ ¿xž* ³$Í +$kñAŠ‹†¢ Uê>¸)_š¬÷©ßAÂÔb9ÇU ¯¾á•9¯ÏÏ÷O÷¼¼Fähal1‰3Ì[Ïr•´UCksNÐ] R‘¸¥H+§Šé†c©vÖÞ0iÓ76s†î!§=ß ¼~Ô'°Ãmäoäš³ªøi1úÉ)³yV8 CLÄØÁ‘WYïi€H6ÖÑiámø^ÈY´°Ñ7¥Û*—Ñ©L«Qƒï—Ùrÿ ›£Ð*š¸ˆL©ˆ$ˆ ÷¾D§9È®«qbqC)–ˆïv´çñsÑVT­Ø, <àïºÀO«Jý·õ àfPìð .wFšir´þ’2_Y *Æ€x\« ì€9š@ Ž|F⇥ˆkZ@hÖÄ0t¿-<“‹qµ¾*ZL¤Ú)&BJpÓF5=$„at*Zš$’ÑtdûÝRI1 2Ž‰$€$I$#‰SÞ’Hë¬ï;Á$¡t$’`<(ñÇt)$‡Ð.Êf¢X’Kt=Éé$‚ˆªè¢oÝëòI%Rgcª÷ŠyI%¡‰ÿ !ñ)´õ $¤ Ô’IIGÿÙfrom collections import deque import unittest from test import support, seq_tests import gc import weakref import copy import pickle import random import struct BIG = 100000 def fail(): raise SyntaxError yield 1 class BadCmp: def __eq__(self, other): raise RuntimeError class MutateCmp: def __init__(self, deque, result): self.deque = deque self.result = result def __eq__(self, other): self.deque.clear() return self.result class TestBasic(unittest.TestCase): def test_basics(self): d = deque(range(-5125, -5000)) d.__init__(range(200)) for i in range(200, 400): d.append(i) for i in reversed(range(-200, 0)): d.appendleft(i) self.assertEqual(list(d), list(range(-200, 400))) self.assertEqual(len(d), 600) left = [d.popleft() for i in range(250)] self.assertEqual(left, list(range(-200, 50))) self.assertEqual(list(d), list(range(50, 400))) right = [d.pop() for i in range(250)] right.reverse() self.assertEqual(right, list(range(150, 400))) self.assertEqual(list(d), list(range(50, 150))) def test_maxlen(self): self.assertRaises(ValueError, deque, 'abc', -1) self.assertRaises(ValueError, deque, 'abc', -2) it = iter(range(10)) d = deque(it, maxlen=3) self.assertEqual(list(it), []) self.assertEqual(repr(d), 'deque([7, 8, 9], maxlen=3)') self.assertEqual(list(d), [7, 8, 9]) self.assertEqual(d, deque(range(10), 3)) d.append(10) self.assertEqual(list(d), [8, 9, 10]) d.appendleft(7) self.assertEqual(list(d), [7, 8, 9]) d.extend([10, 11]) self.assertEqual(list(d), [9, 10, 11]) d.extendleft([8, 7]) self.assertEqual(list(d), [7, 8, 9]) d = deque(range(200), maxlen=10) d.append(d) support.unlink(support.TESTFN) fo = open(support.TESTFN, "w") try: fo.write(str(d)) fo.close() fo = open(support.TESTFN, "r") self.assertEqual(fo.read(), repr(d)) finally: fo.close() support.unlink(support.TESTFN) d = deque(range(10), maxlen=None) self.assertEqual(repr(d), 'deque([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])') fo = open(support.TESTFN, "w") try: fo.write(str(d)) fo.close() fo = open(support.TESTFN, "r") self.assertEqual(fo.read(), repr(d)) finally: fo.close() support.unlink(support.TESTFN) def test_maxlen_zero(self): it = iter(range(100)) deque(it, maxlen=0) self.assertEqual(list(it), []) it = iter(range(100)) d = deque(maxlen=0) d.extend(it) self.assertEqual(list(it), []) it = iter(range(100)) d = deque(maxlen=0) d.extendleft(it) self.assertEqual(list(it), []) def test_maxlen_attribute(self): self.assertEqual(deque().maxlen, None) self.assertEqual(deque('abc').maxlen, None) self.assertEqual(deque('abc', maxlen=4).maxlen, 4) self.assertEqual(deque('abc', maxlen=2).maxlen, 2) self.assertEqual(deque('abc', maxlen=0).maxlen, 0) with self.assertRaises(AttributeError): d = deque('abc') d.maxlen = 10 def test_count(self): for s in ('', 'abracadabra', 'simsalabim'*500+'abc'): s = list(s) d = deque(s) for letter in 'abcdefghijklmnopqrstuvwxyz': self.assertEqual(s.count(letter), d.count(letter), (s, d, letter)) self.assertRaises(TypeError, d.count) # too few args self.assertRaises(TypeError, d.count, 1, 2) # too many args class BadCompare: def __eq__(self, other): raise ArithmeticError d = deque([1, 2, BadCompare(), 3]) self.assertRaises(ArithmeticError, d.count, 2) d = deque([1, 2, 3]) self.assertRaises(ArithmeticError, d.count, BadCompare()) class MutatingCompare: def __eq__(self, other): self.d.pop() return True m = MutatingCompare() d = deque([1, 2, 3, m, 4, 5]) m.d = d self.assertRaises(RuntimeError, d.count, 3) # test issue11004 # block advance failed after rotation aligned elements on right side of block d = deque([None]*16) for i in range(len(d)): d.rotate(-1) d.rotate(1) self.assertEqual(d.count(1), 0) self.assertEqual(d.count(None), 16) def test_comparisons(self): d = deque('xabc') d.popleft() for e in [d, deque('abc'), deque('ab'), deque(), list(d)]: self.assertEqual(d==e, type(d)==type(e) and list(d)==list(e)) self.assertEqual(d!=e, not(type(d)==type(e) and list(d)==list(e))) args = map(deque, ('', 'a', 'b', 'ab', 'ba', 'abc', 'xba', 'xabc', 'cba')) for x in args: for y in args: self.assertEqual(x == y, list(x) == list(y), (x,y)) self.assertEqual(x != y, list(x) != list(y), (x,y)) self.assertEqual(x < y, list(x) < list(y), (x,y)) self.assertEqual(x <= y, list(x) <= list(y), (x,y)) self.assertEqual(x > y, list(x) > list(y), (x,y)) self.assertEqual(x >= y, list(x) >= list(y), (x,y)) def test_contains(self): n = 200 d = deque(range(n)) for i in range(n): self.assertTrue(i in d) self.assertTrue((n+1) not in d) # Test detection of mutation during iteration d = deque(range(n)) d[n//2] = MutateCmp(d, False) with self.assertRaises(RuntimeError): n in d # Test detection of comparison exceptions d = deque(range(n)) d[n//2] = BadCmp() with self.assertRaises(RuntimeError): n in d def test_contains_count_stop_crashes(self): class A: def __eq__(self, other): d.clear() return NotImplemented d = deque([A(), A()]) with self.assertRaises(RuntimeError): _ = 3 in d d = deque([A(), A()]) with self.assertRaises(RuntimeError): _ = d.count(3) def test_extend(self): d = deque('a') self.assertRaises(TypeError, d.extend, 1) d.extend('bcd') self.assertEqual(list(d), list('abcd')) d.extend(d) self.assertEqual(list(d), list('abcdabcd')) def test_add(self): d = deque() e = deque('abc') f = deque('def') self.assertEqual(d + d, deque()) self.assertEqual(e + f, deque('abcdef')) self.assertEqual(e + e, deque('abcabc')) self.assertEqual(e + d, deque('abc')) self.assertEqual(d + e, deque('abc')) self.assertIsNot(d + d, deque()) self.assertIsNot(e + d, deque('abc')) self.assertIsNot(d + e, deque('abc')) g = deque('abcdef', maxlen=4) h = deque('gh') self.assertEqual(g + h, deque('efgh')) with self.assertRaises(TypeError): deque('abc') + 'def' def test_iadd(self): d = deque('a') d += 'bcd' self.assertEqual(list(d), list('abcd')) d += d self.assertEqual(list(d), list('abcdabcd')) def test_extendleft(self): d = deque('a') self.assertRaises(TypeError, d.extendleft, 1) d.extendleft('bcd') self.assertEqual(list(d), list(reversed('abcd'))) d.extendleft(d) self.assertEqual(list(d), list('abcddcba')) d = deque() d.extendleft(range(1000)) self.assertEqual(list(d), list(reversed(range(1000)))) self.assertRaises(SyntaxError, d.extendleft, fail()) def test_getitem(self): n = 200 d = deque(range(n)) l = list(range(n)) for i in range(n): d.popleft() l.pop(0) if random.random() < 0.5: d.append(i) l.append(i) for j in range(1-len(l), len(l)): assert d[j] == l[j] d = deque('superman') self.assertEqual(d[0], 's') self.assertEqual(d[-1], 'n') d = deque() self.assertRaises(IndexError, d.__getitem__, 0) self.assertRaises(IndexError, d.__getitem__, -1) def test_index(self): for n in 1, 2, 30, 40, 200: d = deque(range(n)) for i in range(n): self.assertEqual(d.index(i), i) with self.assertRaises(ValueError): d.index(n+1) # Test detection of mutation during iteration d = deque(range(n)) d[n//2] = MutateCmp(d, False) with self.assertRaises(RuntimeError): d.index(n) # Test detection of comparison exceptions d = deque(range(n)) d[n//2] = BadCmp() with self.assertRaises(RuntimeError): d.index(n) # Test start and stop arguments behavior matches list.index() elements = 'ABCDEFGHI' nonelement = 'Z' d = deque(elements * 2) s = list(elements * 2) for start in range(-5 - len(s)*2, 5 + len(s) * 2): for stop in range(-5 - len(s)*2, 5 + len(s) * 2): for element in elements + 'Z': try: target = s.index(element, start, stop) except ValueError: with self.assertRaises(ValueError): d.index(element, start, stop) else: self.assertEqual(d.index(element, start, stop), target) # Test large start argument d = deque(range(0, 10000, 10)) for step in range(100): i = d.index(8500, 700) self.assertEqual(d[i], 8500) # Repeat test with a different internal offset d.rotate() def test_index_bug_24913(self): d = deque('A' * 3) with self.assertRaises(ValueError): i = d.index("Hello world", 0, 4) def test_insert(self): # Test to make sure insert behaves like lists elements = 'ABCDEFGHI' for i in range(-5 - len(elements)*2, 5 + len(elements) * 2): d = deque('ABCDEFGHI') s = list('ABCDEFGHI') d.insert(i, 'Z') s.insert(i, 'Z') self.assertEqual(list(d), s) def test_insert_bug_26194(self): data = 'ABC' d = deque(data, maxlen=len(data)) with self.assertRaises(IndexError): d.insert(2, None) elements = 'ABCDEFGHI' for i in range(-len(elements), len(elements)): d = deque(elements, maxlen=len(elements)+1) d.insert(i, 'Z') if i >= 0: self.assertEqual(d[i], 'Z') else: self.assertEqual(d[i-1], 'Z') def test_imul(self): for n in (-10, -1, 0, 1, 2, 10, 1000): d = deque() d *= n self.assertEqual(d, deque()) self.assertIsNone(d.maxlen) for n in (-10, -1, 0, 1, 2, 10, 1000): d = deque('a') d *= n self.assertEqual(d, deque('a' * n)) self.assertIsNone(d.maxlen) for n in (-10, -1, 0, 1, 2, 10, 499, 500, 501, 1000): d = deque('a', 500) d *= n self.assertEqual(d, deque('a' * min(n, 500))) self.assertEqual(d.maxlen, 500) for n in (-10, -1, 0, 1, 2, 10, 1000): d = deque('abcdef') d *= n self.assertEqual(d, deque('abcdef' * n)) self.assertIsNone(d.maxlen) for n in (-10, -1, 0, 1, 2, 10, 499, 500, 501, 1000): d = deque('abcdef', 500) d *= n self.assertEqual(d, deque(('abcdef' * n)[-500:])) self.assertEqual(d.maxlen, 500) def test_mul(self): d = deque('abc') self.assertEqual(d * -5, deque()) self.assertEqual(d * 0, deque()) self.assertEqual(d * 1, deque('abc')) self.assertEqual(d * 2, deque('abcabc')) self.assertEqual(d * 3, deque('abcabcabc')) self.assertIsNot(d * 1, d) self.assertEqual(deque() * 0, deque()) self.assertEqual(deque() * 1, deque()) self.assertEqual(deque() * 5, deque()) self.assertEqual(-5 * d, deque()) self.assertEqual(0 * d, deque()) self.assertEqual(1 * d, deque('abc')) self.assertEqual(2 * d, deque('abcabc')) self.assertEqual(3 * d, deque('abcabcabc')) d = deque('abc', maxlen=5) self.assertEqual(d * -5, deque()) self.assertEqual(d * 0, deque()) self.assertEqual(d * 1, deque('abc')) self.assertEqual(d * 2, deque('bcabc')) self.assertEqual(d * 30, deque('bcabc')) def test_setitem(self): n = 200 d = deque(range(n)) for i in range(n): d[i] = 10 * i self.assertEqual(list(d), [10*i for i in range(n)]) l = list(d) for i in range(1-n, 0, -1): d[i] = 7*i l[i] = 7*i self.assertEqual(list(d), l) def test_delitem(self): n = 500 # O(n**2) test, don't make this too big d = deque(range(n)) self.assertRaises(IndexError, d.__delitem__, -n-1) self.assertRaises(IndexError, d.__delitem__, n) for i in range(n): self.assertEqual(len(d), n-i) j = random.randrange(-len(d), len(d)) val = d[j] self.assertIn(val, d) del d[j] self.assertNotIn(val, d) self.assertEqual(len(d), 0) def test_reverse(self): n = 500 # O(n**2) test, don't make this too big data = [random.random() for i in range(n)] for i in range(n): d = deque(data[:i]) r = d.reverse() self.assertEqual(list(d), list(reversed(data[:i]))) self.assertIs(r, None) d.reverse() self.assertEqual(list(d), data[:i]) self.assertRaises(TypeError, d.reverse, 1) # Arity is zero def test_rotate(self): s = tuple('abcde') n = len(s) d = deque(s) d.rotate(1) # verify rot(1) self.assertEqual(''.join(d), 'eabcd') d = deque(s) d.rotate(-1) # verify rot(-1) self.assertEqual(''.join(d), 'bcdea') d.rotate() # check default to 1 self.assertEqual(tuple(d), s) for i in range(n*3): d = deque(s) e = deque(d) d.rotate(i) # check vs. rot(1) n times for j in range(i): e.rotate(1) self.assertEqual(tuple(d), tuple(e)) d.rotate(-i) # check that it works in reverse self.assertEqual(tuple(d), s) e.rotate(n-i) # check that it wraps forward self.assertEqual(tuple(e), s) for i in range(n*3): d = deque(s) e = deque(d) d.rotate(-i) for j in range(i): e.rotate(-1) # check vs. rot(-1) n times self.assertEqual(tuple(d), tuple(e)) d.rotate(i) # check that it works in reverse self.assertEqual(tuple(d), s) e.rotate(i-n) # check that it wraps backaround self.assertEqual(tuple(e), s) d = deque(s) e = deque(s) e.rotate(BIG+17) # verify on long series of rotates dr = d.rotate for i in range(BIG+17): dr() self.assertEqual(tuple(d), tuple(e)) self.assertRaises(TypeError, d.rotate, 'x') # Wrong arg type self.assertRaises(TypeError, d.rotate, 1, 10) # Too many args d = deque() d.rotate() # rotate an empty deque self.assertEqual(d, deque()) def test_len(self): d = deque('ab') self.assertEqual(len(d), 2) d.popleft() self.assertEqual(len(d), 1) d.pop() self.assertEqual(len(d), 0) self.assertRaises(IndexError, d.pop) self.assertEqual(len(d), 0) d.append('c') self.assertEqual(len(d), 1) d.appendleft('d') self.assertEqual(len(d), 2) d.clear() self.assertEqual(len(d), 0) def test_underflow(self): d = deque() self.assertRaises(IndexError, d.pop) self.assertRaises(IndexError, d.popleft) def test_clear(self): d = deque(range(100)) self.assertEqual(len(d), 100) d.clear() self.assertEqual(len(d), 0) self.assertEqual(list(d), []) d.clear() # clear an empty deque self.assertEqual(list(d), []) def test_remove(self): d = deque('abcdefghcij') d.remove('c') self.assertEqual(d, deque('abdefghcij')) d.remove('c') self.assertEqual(d, deque('abdefghij')) self.assertRaises(ValueError, d.remove, 'c') self.assertEqual(d, deque('abdefghij')) # Handle comparison errors d = deque(['a', 'b', BadCmp(), 'c']) e = deque(d) self.assertRaises(RuntimeError, d.remove, 'c') for x, y in zip(d, e): # verify that original order and values are retained. self.assertTrue(x is y) # Handle evil mutator for match in (True, False): d = deque(['ab']) d.extend([MutateCmp(d, match), 'c']) self.assertRaises(IndexError, d.remove, 'c') self.assertEqual(d, deque()) def test_repr(self): d = deque(range(200)) e = eval(repr(d)) self.assertEqual(list(d), list(e)) d.append(d) self.assertIn('...', repr(d)) def test_print(self): d = deque(range(200)) d.append(d) try: support.unlink(support.TESTFN) fo = open(support.TESTFN, "w") print(d, file=fo, end='') fo.close() fo = open(support.TESTFN, "r") self.assertEqual(fo.read(), repr(d)) finally: fo.close() support.unlink(support.TESTFN) def test_init(self): self.assertRaises(TypeError, deque, 'abc', 2, 3) self.assertRaises(TypeError, deque, 1) def test_hash(self): self.assertRaises(TypeError, hash, deque('abc')) def test_long_steadystate_queue_popleft(self): for size in (0, 1, 2, 100, 1000): d = deque(range(size)) append, pop = d.append, d.popleft for i in range(size, BIG): append(i) x = pop() if x != i - size: self.assertEqual(x, i-size) self.assertEqual(list(d), list(range(BIG-size, BIG))) def test_long_steadystate_queue_popright(self): for size in (0, 1, 2, 100, 1000): d = deque(reversed(range(size))) append, pop = d.appendleft, d.pop for i in range(size, BIG): append(i) x = pop() if x != i - size: self.assertEqual(x, i-size) self.assertEqual(list(reversed(list(d))), list(range(BIG-size, BIG))) def test_big_queue_popleft(self): pass d = deque() append, pop = d.append, d.popleft for i in range(BIG): append(i) for i in range(BIG): x = pop() if x != i: self.assertEqual(x, i) def test_big_queue_popright(self): d = deque() append, pop = d.appendleft, d.pop for i in range(BIG): append(i) for i in range(BIG): x = pop() if x != i: self.assertEqual(x, i) def test_big_stack_right(self): d = deque() append, pop = d.append, d.pop for i in range(BIG): append(i) for i in reversed(range(BIG)): x = pop() if x != i: self.assertEqual(x, i) self.assertEqual(len(d), 0) def test_big_stack_left(self): d = deque() append, pop = d.appendleft, d.popleft for i in range(BIG): append(i) for i in reversed(range(BIG)): x = pop() if x != i: self.assertEqual(x, i) self.assertEqual(len(d), 0) def test_roundtrip_iter_init(self): d = deque(range(200)) e = deque(d) self.assertNotEqual(id(d), id(e)) self.assertEqual(list(d), list(e)) def test_pickle(self): for d in deque(range(200)), deque(range(200), 100): for i in range(pickle.HIGHEST_PROTOCOL + 1): s = pickle.dumps(d, i) e = pickle.loads(s) self.assertNotEqual(id(e), id(d)) self.assertEqual(list(e), list(d)) self.assertEqual(e.maxlen, d.maxlen) def test_pickle_recursive(self): for d in deque('abc'), deque('abc', 3): d.append(d) for i in range(pickle.HIGHEST_PROTOCOL + 1): e = pickle.loads(pickle.dumps(d, i)) self.assertNotEqual(id(e), id(d)) self.assertEqual(id(e[-1]), id(e)) self.assertEqual(e.maxlen, d.maxlen) def test_iterator_pickle(self): orig = deque(range(200)) data = [i*1.01 for i in orig] for proto in range(pickle.HIGHEST_PROTOCOL + 1): # initial iterator itorg = iter(orig) dump = pickle.dumps((itorg, orig), proto) it, d = pickle.loads(dump) for i, x in enumerate(data): d[i] = x self.assertEqual(type(it), type(itorg)) self.assertEqual(list(it), data) # running iterator next(itorg) dump = pickle.dumps((itorg, orig), proto) it, d = pickle.loads(dump) for i, x in enumerate(data): d[i] = x self.assertEqual(type(it), type(itorg)) self.assertEqual(list(it), data[1:]) # empty iterator for i in range(1, len(data)): next(itorg) dump = pickle.dumps((itorg, orig), proto) it, d = pickle.loads(dump) for i, x in enumerate(data): d[i] = x self.assertEqual(type(it), type(itorg)) self.assertEqual(list(it), []) # exhausted iterator self.assertRaises(StopIteration, next, itorg) dump = pickle.dumps((itorg, orig), proto) it, d = pickle.loads(dump) for i, x in enumerate(data): d[i] = x self.assertEqual(type(it), type(itorg)) self.assertEqual(list(it), []) def test_deepcopy(self): mut = [10] d = deque([mut]) e = copy.deepcopy(d) self.assertEqual(list(d), list(e)) mut[0] = 11 self.assertNotEqual(id(d), id(e)) self.assertNotEqual(list(d), list(e)) def test_copy(self): mut = [10] d = deque([mut]) e = copy.copy(d) self.assertEqual(list(d), list(e)) mut[0] = 11 self.assertNotEqual(id(d), id(e)) self.assertEqual(list(d), list(e)) for i in range(5): for maxlen in range(-1, 6): s = [random.random() for j in range(i)] d = deque(s) if maxlen == -1 else deque(s, maxlen) e = d.copy() self.assertEqual(d, e) self.assertEqual(d.maxlen, e.maxlen) self.assertTrue(all(x is y for x, y in zip(d, e))) def test_copy_method(self): mut = [10] d = deque([mut]) e = d.copy() self.assertEqual(list(d), list(e)) mut[0] = 11 self.assertNotEqual(id(d), id(e)) self.assertEqual(list(d), list(e)) def test_reversed(self): for s in ('abcd', range(2000)): self.assertEqual(list(reversed(deque(s))), list(reversed(s))) def test_reversed_new(self): klass = type(reversed(deque())) for s in ('abcd', range(2000)): self.assertEqual(list(klass(deque(s))), list(reversed(s))) def test_gc_doesnt_blowup(self): import gc # This used to assert-fail in deque_traverse() under a debug # build, or run wild with a NULL pointer in a release build. d = deque() for i in range(100): d.append(1) gc.collect() def test_container_iterator(self): # Bug #3680: tp_traverse was not implemented for deque iterator objects class C(object): pass for i in range(2): obj = C() ref = weakref.ref(obj) if i == 0: container = deque([obj, 1]) else: container = reversed(deque([obj, 1])) obj.x = iter(container) del obj, container gc.collect() self.assertTrue(ref() is None, "Cycle was not collected") check_sizeof = support.check_sizeof @support.cpython_only def test_sizeof(self): BLOCKLEN = 64 basesize = support.calcvobjsize('2P4nP') blocksize = struct.calcsize('P%dPP' % BLOCKLEN) self.assertEqual(object.__sizeof__(deque()), basesize) check = self.check_sizeof check(deque(), basesize + blocksize) check(deque('a'), basesize + blocksize) check(deque('a' * (BLOCKLEN - 1)), basesize + blocksize) check(deque('a' * BLOCKLEN), basesize + 2 * blocksize) check(deque('a' * (42 * BLOCKLEN)), basesize + 43 * blocksize) class TestVariousIteratorArgs(unittest.TestCase): def test_constructor(self): for s in ("123", "", range(1000), ('do', 1.2), range(2000,2200,5)): for g in (seq_tests.Sequence, seq_tests.IterFunc, seq_tests.IterGen, seq_tests.IterFuncStop, seq_tests.itermulti, seq_tests.iterfunc): self.assertEqual(list(deque(g(s))), list(g(s))) self.assertRaises(TypeError, deque, seq_tests.IterNextOnly(s)) self.assertRaises(TypeError, deque, seq_tests.IterNoNext(s)) self.assertRaises(ZeroDivisionError, deque, seq_tests.IterGenExc(s)) def test_iter_with_altered_data(self): d = deque('abcdefg') it = iter(d) d.pop() self.assertRaises(RuntimeError, next, it) def test_runtime_error_on_empty_deque(self): d = deque() it = iter(d) d.append(10) self.assertRaises(RuntimeError, next, it) class Deque(deque): pass class DequeWithBadIter(deque): def __iter__(self): raise TypeError class TestSubclass(unittest.TestCase): def test_basics(self): d = Deque(range(25)) d.__init__(range(200)) for i in range(200, 400): d.append(i) for i in reversed(range(-200, 0)): d.appendleft(i) self.assertEqual(list(d), list(range(-200, 400))) self.assertEqual(len(d), 600) left = [d.popleft() for i in range(250)] self.assertEqual(left, list(range(-200, 50))) self.assertEqual(list(d), list(range(50, 400))) right = [d.pop() for i in range(250)] right.reverse() self.assertEqual(right, list(range(150, 400))) self.assertEqual(list(d), list(range(50, 150))) d.clear() self.assertEqual(len(d), 0) def test_copy_pickle(self): d = Deque('abc') e = d.__copy__() self.assertEqual(type(d), type(e)) self.assertEqual(list(d), list(e)) e = Deque(d) self.assertEqual(type(d), type(e)) self.assertEqual(list(d), list(e)) for proto in range(pickle.HIGHEST_PROTOCOL + 1): s = pickle.dumps(d, proto) e = pickle.loads(s) self.assertNotEqual(id(d), id(e)) self.assertEqual(type(d), type(e)) self.assertEqual(list(d), list(e)) d = Deque('abcde', maxlen=4) e = d.__copy__() self.assertEqual(type(d), type(e)) self.assertEqual(list(d), list(e)) e = Deque(d) self.assertEqual(type(d), type(e)) self.assertEqual(list(d), list(e)) for proto in range(pickle.HIGHEST_PROTOCOL + 1): s = pickle.dumps(d, proto) e = pickle.loads(s) self.assertNotEqual(id(d), id(e)) self.assertEqual(type(d), type(e)) self.assertEqual(list(d), list(e)) def test_pickle_recursive(self): for proto in range(pickle.HIGHEST_PROTOCOL + 1): for d in Deque('abc'), Deque('abc', 3): d.append(d) e = pickle.loads(pickle.dumps(d, proto)) self.assertNotEqual(id(e), id(d)) self.assertEqual(type(e), type(d)) self.assertEqual(e.maxlen, d.maxlen) dd = d.pop() ee = e.pop() self.assertEqual(id(ee), id(e)) self.assertEqual(e, d) d.x = d e = pickle.loads(pickle.dumps(d, proto)) self.assertEqual(id(e.x), id(e)) for d in DequeWithBadIter('abc'), DequeWithBadIter('abc', 2): self.assertRaises(TypeError, pickle.dumps, d, proto) def test_weakref(self): d = deque('gallahad') p = weakref.proxy(d) self.assertEqual(str(p), str(d)) d = None support.gc_collect() # For PyPy or other GCs. self.assertRaises(ReferenceError, str, p) def test_strange_subclass(self): class X(deque): def __iter__(self): return iter([]) d1 = X([1,2,3]) d2 = X([4,5,6]) d1 == d2 # not clear if this is supposed to be True or False, # but it used to give a SystemError @support.cpython_only def test_bug_31608(self): # The interpreter used to crash in specific cases where a deque # subclass returned a non-deque. class X(deque): pass d = X() def bad___new__(cls, *args, **kwargs): return [42] X.__new__ = bad___new__ with self.assertRaises(TypeError): d * 42 # shouldn't crash with self.assertRaises(TypeError): d + deque([1, 2, 3]) # shouldn't crash class SubclassWithKwargs(deque): def __init__(self, newarg=1): deque.__init__(self) class TestSubclassWithKwargs(unittest.TestCase): def test_subclass_with_kwargs(self): # SF bug #1486663 -- this used to erroneously raise a TypeError SubclassWithKwargs(newarg=1) class TestSequence(seq_tests.CommonTest): type2test = deque def test_getitem(self): # For now, bypass tests that require slicing pass def test_getslice(self): # For now, bypass tests that require slicing pass def test_subscript(self): # For now, bypass tests that require slicing pass def test_free_after_iterating(self): # For now, bypass tests that require slicing self.skipTest("Exhausted deque iterator doesn't free a deque") #============================================================================== libreftest = """ Example from the Library Reference: Doc/lib/libcollections.tex >>> from collections import deque >>> d = deque('ghi') # make a new deque with three items >>> for elem in d: # iterate over the deque's elements ... print(elem.upper()) G H I >>> d.append('j') # add a new entry to the right side >>> d.appendleft('f') # add a new entry to the left side >>> d # show the representation of the deque deque(['f', 'g', 'h', 'i', 'j']) >>> d.pop() # return and remove the rightmost item 'j' >>> d.popleft() # return and remove the leftmost item 'f' >>> list(d) # list the contents of the deque ['g', 'h', 'i'] >>> d[0] # peek at leftmost item 'g' >>> d[-1] # peek at rightmost item 'i' >>> list(reversed(d)) # list the contents of a deque in reverse ['i', 'h', 'g'] >>> 'h' in d # search the deque True >>> d.extend('jkl') # add multiple elements at once >>> d deque(['g', 'h', 'i', 'j', 'k', 'l']) >>> d.rotate(1) # right rotation >>> d deque(['l', 'g', 'h', 'i', 'j', 'k']) >>> d.rotate(-1) # left rotation >>> d deque(['g', 'h', 'i', 'j', 'k', 'l']) >>> deque(reversed(d)) # make a new deque in reverse order deque(['l', 'k', 'j', 'i', 'h', 'g']) >>> d.clear() # empty the deque >>> d.pop() # cannot pop from an empty deque Traceback (most recent call last): File "", line 1, in -toplevel- d.pop() IndexError: pop from an empty deque >>> d.extendleft('abc') # extendleft() reverses the input order >>> d deque(['c', 'b', 'a']) >>> def delete_nth(d, n): ... d.rotate(-n) ... d.popleft() ... d.rotate(n) ... >>> d = deque('abcdef') >>> delete_nth(d, 2) # remove the entry at d[2] >>> d deque(['a', 'b', 'd', 'e', 'f']) >>> def roundrobin(*iterables): ... pending = deque(iter(i) for i in iterables) ... while pending: ... task = pending.popleft() ... try: ... yield next(task) ... except StopIteration: ... continue ... pending.append(task) ... >>> for value in roundrobin('abc', 'd', 'efgh'): ... print(value) ... a d e b f c g h >>> def maketree(iterable): ... d = deque(iterable) ... while len(d) > 1: ... pair = [d.popleft(), d.popleft()] ... d.append(pair) ... return list(d) ... >>> print(maketree('abcdefgh')) [[[['a', 'b'], ['c', 'd']], [['e', 'f'], ['g', 'h']]]] """ #============================================================================== __test__ = {'libreftest' : libreftest} def test_main(verbose=None): import sys test_classes = ( TestBasic, TestVariousIteratorArgs, TestSubclass, TestSubclassWithKwargs, TestSequence, ) support.run_unittest(*test_classes) # verify reference counting if verbose and hasattr(sys, "gettotalrefcount"): import gc counts = [None] * 5 for i in range(len(counts)): support.run_unittest(*test_classes) gc.collect() counts[i] = sys.gettotalrefcount() print(counts) # doctests from test import test_deque support.run_doctest(test_deque, verbose) if __name__ == "__main__": test_main(verbose=True)