1# This file is a Tcl script to test out the B-tree facilities of
2# Tk's text widget (the contents of the file "tkTextBTree.c".  There are
3# several file with additional tests for other features of text widgets.
4# This file is organized in the standard fashion for Tcl tests.
5#
6# Copyright (c) 1992-1994 The Regents of the University of California.
7# Copyright (c) 1994 Sun Microsystems, Inc.
8# Copyright (c) 1998-1999 by Scriptics Corporation.
9# All rights reserved.
10#
11# RCS: @(#) $Id: textBTree.test,v 1.5 2002/07/13 20:28:35 dgp Exp $
12
13package require tcltest 2.1
14namespace import -force tcltest::configure
15namespace import -force tcltest::testsDirectory
16configure -testdir [file join [pwd] [file dirname [info script]]]
17configure -loadfile [file join [testsDirectory] constraints.tcl]
18tcltest::loadTestedCommands
19
20catch {destroy .t}
21text .t
22.t debug on
23
24test btree-1.1 {basic insertions} {
25    .t delete 1.0 100000.0
26    .t insert 1.0 "Line 1\nLine 2\nLine 3"
27    .t get 1.0 1000000.0
28} "Line 1\nLine 2\nLine 3\n"
29test btree-1.2 {basic insertions} {
30    .t delete 1.0 100000.0
31    .t insert 1.0 "Line 1\nLine 2\nLine 3"
32    .t insert 1.3 XXX
33    .t get 1.0 1000000.0
34} "LinXXXe 1\nLine 2\nLine 3\n"
35test btree-1.3 {basic insertions} {
36    .t delete 1.0 100000.0
37    .t insert 1.0 "Line 1\nLine 2\nLine 3"
38    .t insert 3.0 YYY
39    .t get 1.0 1000000.0
40} "Line 1\nLine 2\nYYYLine 3\n"
41test btree-1.4 {basic insertions} {
42    .t delete 1.0 100000.0
43    .t insert 1.0 "Line 1\nLine 2\nLine 3"
44    .t insert 2.1 X\nYY
45    .t get 1.0 1000000.0
46} "Line 1\nLX\nYYine 2\nLine 3\n"
47test btree-1.5 {basic insertions} {
48    .t delete 1.0 100000.0
49    .t insert 1.0 "Line 1\nLine 2\nLine 3"
50    .t insert 2.0 X\n\n\n
51    .t get 1.0 1000000.0
52} "Line 1\nX\n\n\nLine 2\nLine 3\n"
53test btree-1.6 {basic insertions} {
54    .t delete 1.0 100000.0
55    .t insert 1.0 "Line 1\nLine 2\nLine 3"
56    .t insert 2.6 X\n
57    .t get 1.0 1000000.0
58} "Line 1\nLine 2X\n\nLine 3\n"
59test btree-1.7 {insertion before start of text} {
60    .t delete 1.0 100000.0
61    .t insert 1.0 "Line 1\nLine 2\nLine 3"
62    .t insert 0.4 XXX
63    .t get 1.0 1000000.0
64} "XXXLine 1\nLine 2\nLine 3\n"
65test btree-1.8 {insertion past end of text} {
66    .t delete 1.0 100000.0
67    .t insert 1.0 "Line 1\nLine 2\nLine 3"
68    .t insert 100.0 ZZ
69    .t get 1.0 1000000.0
70} "Line 1\nLine 2\nLine 3ZZ\n"
71test btree-1.9 {insertion before start of line} {
72    .t delete 1.0 100000.0
73    .t insert 1.0 "Line 1\nLine 2\nLine 3"
74    .t insert 2.-3 Q
75    .t get 1.0 1000000.0
76} "Line 1\nQLine 2\nLine 3\n"
77test btree-1.10 {insertion past end of line} {
78    .t delete 1.0 100000.0
79    .t insert 1.0 "Line 1\nLine 2\nLine 3"
80    .t insert 2.40 XYZZY
81    .t get 1.0 1000000.0
82} "Line 1\nLine 2XYZZY\nLine 3\n"
83test btree-1.11 {insertion past end of last line} {
84    .t delete 1.0 100000.0
85    .t insert 1.0 "Line 1\nLine 2\nLine 3"
86    .t insert 3.40 ABC
87    .t get 1.0 1000000.0
88} "Line 1\nLine 2\nLine 3ABC\n"
89
90test btree-2.1 {basic deletions} {
91    .t delete 1.0 100000.0
92    .t insert 1.0 "Line 1\nLine 2\nLine 3"
93    .t delete 1.0 1.3
94    .t get 1.0 1000000.0
95} "e 1\nLine 2\nLine 3\n"
96test btree-2.2 {basic deletions} {
97    .t delete 1.0 100000.0
98    .t insert 1.0 "Line 1\nLine 2\nLine 3"
99    .t delete 2.2
100    .t get 1.0 1000000.0
101} "Line 1\nLie 2\nLine 3\n"
102test btree-2.3 {basic deletions} {
103    .t delete 1.0 100000.0
104    .t insert 1.0 "Line 1\nLine 2\nLine 3"
105    .t delete 2.0 2.3
106    .t get 1.0 1000000.0
107} "Line 1\ne 2\nLine 3\n"
108test btree-2.4 {deleting whole lines} {
109    .t delete 1.0 100000.0
110    .t insert 1.0 "Line 1\nLine 2\nLine 3"
111    .t delete 1.2 3.0
112    .t get 1.0 1000000.0
113} "LiLine 3\n"
114test btree-2.5 {deleting whole lines} {
115    .t delete 1.0 100000.0
116    .t insert 1.0 "Line 1\nLine 2\n\n\nLine 5"
117    .t delete 1.0 5.2
118    .t get 1.0 1000000.0
119} "ne 5\n"
120test btree-2.6 {deleting before start of file} {
121    .t delete 1.0 100000.0
122    .t insert 1.0 "Line 1\nLine 2\nLine 3"
123    .t delete 0.3 1.2
124    .t get 1.0 1000000.0
125} "ne 1\nLine 2\nLine 3\n"
126test btree-2.7 {deleting after end of file} {
127    .t delete 1.0 100000.0
128    .t insert 1.0 "Line 1\nLine 2\nLine 3"
129    .t delete 10.3
130    .t get 1.0 1000000.0
131} "Line 1\nLine 2\nLine 3\n"
132test btree-2.8 {deleting before start of line} {
133    .t delete 1.0 100000.0
134    .t insert 1.0 "Line 1\nLine 2\nLine 3"
135    .t delete 3.-1 3.3
136    .t get 1.0 1000000.0
137} "Line 1\nLine 2\ne 3\n"
138test btree-2.9 {deleting before start of line} {
139    .t delete 1.0 100000.0
140    .t insert 1.0 "Line 1\nLine 2\nLine 3"
141    .t delete 1.-1 1.0
142    .t get 1.0 1000000.0
143} "Line 1\nLine 2\nLine 3\n"
144test btree-2.10 {deleting after end of line} {
145    .t delete 1.0 100000.0
146    .t insert 1.0 "Line 1\nLine 2\nLine 3"
147    .t delete 1.8 2.1
148    .t get 1.0 1000000.0
149} "Line 1ine 2\nLine 3\n"
150test btree-2.11 {deleting after end of last line} {
151    .t delete 1.0 100000.0
152    .t insert 1.0 "Line 1\nLine 2\nLine 3"
153    .t delete 3.8 4.1
154    .t get 1.0 1000000.0
155} "Line 1\nLine 2\nLine 3\n"
156test btree-2.12 {deleting before start of file} {
157    .t delete 1.0 100000.0
158    .t insert 1.0 "Line 1\nLine 2\nLine 3"
159    .t delete 1.8 0.0
160    .t get 1.0 1000000.0
161} "Line 1\nLine 2\nLine 3\n"
162test btree-2.13 {deleting past end of file} {
163    .t delete 1.0 100000.0
164    .t insert 1.0 "Line 1\nLine 2\nLine 3"
165    .t delete 1.8 4.0
166    .t get 1.0 1000000.0
167} "Line 1\n"
168test btree-2.14 {deleting with end before start of line} {
169    .t delete 1.0 100000.0
170    .t insert 1.0 "Line 1\nLine 2\nLine 3"
171    .t delete 1.3 2.-3
172    .t get 1.0 1000000.0
173} "LinLine 2\nLine 3\n"
174test btree-2.15 {deleting past end of line} {
175    .t delete 1.0 100000.0
176    .t insert 1.0 "Line 1\nLine 2\nLine 3"
177    .t delete 1.3 1.9
178    .t get 1.0 1000000.0
179} "Lin\nLine 2\nLine 3\n"
180test btree-2.16 {deleting past end of line} {
181    .t delete 1.0 100000.0
182    .t insert 1.0 "Line 1\nLine 2\nLine 3"
183    .t delete 3.2 3.15
184    .t get 1.0 1000000.0
185} "Line 1\nLine 2\nLi\n"
186test btree-2.17 {deleting past end of line} {
187    .t delete 1.0 100000.0
188    .t insert 1.0 "Line 1\nLine 2\nLine 3"
189    .t delete 3.0 3.15
190    .t get 1.0 1000000.0
191} "Line 1\nLine 2\n\n"
192test btree-2.18 {deleting past end of line} {
193    .t delete 1.0 100000.0
194    .t insert 1.0 "Line 1\nLine 2\nLine 3"
195    .t delete 1.0 3.15
196    .t get 1.0 1000000.0
197} "\n"
198test btree-2.19 {deleting with negative range} {
199    .t delete 1.0 100000.0
200    .t insert 1.0 "Line 1\nLine 2\nLine 3"
201    .t delete 3.2 2.4
202    .t get 1.0 1000000.0
203} "Line 1\nLine 2\nLine 3\n"
204test btree-2.20 {deleting with negative range} {
205    .t delete 1.0 100000.0
206    .t insert 1.0 "Line 1\nLine 2\nLine 3"
207    .t delete 3.2 3.1
208    .t get 1.0 1000000.0
209} "Line 1\nLine 2\nLine 3\n"
210test btree-2.21 {deleting with negative range} {
211    .t delete 1.0 100000.0
212    .t insert 1.0 "Line 1\nLine 2\nLine 3"
213    .t delete 3.2 3.2
214    .t get 1.0 1000000.0
215} "Line 1\nLine 2\nLine 3\n"
216
217proc setup {} {
218    .t delete 1.0 100000.0
219    .t tag delete x y
220    .t insert 1.0 "Text for first line\nSecond line\n\nLast line of info"
221    .t tag add x 1.1
222    .t tag add x 1.5 1.13
223    .t tag add x 2.2 2.6
224    .t tag add y 1.5
225}
226
227test btree-3.1 {inserting with tags} {
228    setup
229    .t insert 1.0 XXX
230    list [.t tag ranges x] [.t tag ranges y]
231} {{1.4 1.5 1.8 1.16 2.2 2.6} {1.8 1.9}}
232test btree-3.2 {inserting with tags} {
233    setup
234    .t insert 1.15 YYY
235    list [.t tag ranges x] [.t tag ranges y]
236} {{1.1 1.2 1.5 1.13 2.2 2.6} {1.5 1.6}}
237test btree-3.3 {inserting with tags} {
238    setup
239    .t insert 1.7 ZZZZ
240    list [.t tag ranges x] [.t tag ranges y]
241} {{1.1 1.2 1.5 1.17 2.2 2.6} {1.5 1.6}}
242test btree-3.4 {inserting with tags} {
243    setup
244    .t insert 1.7 \n\n
245    list [.t tag ranges x] [.t tag ranges y]
246} {{1.1 1.2 1.5 3.6 4.2 4.6} {1.5 1.6}}
247test btree-3.5 {inserting with tags} {
248    setup
249    .t insert 1.5 A\n
250    list [.t tag ranges x] [.t tag ranges y]
251} {{1.1 1.2 2.0 2.8 3.2 3.6} {2.0 2.1}}
252test btree-3.6 {inserting with tags} {
253    setup
254    .t insert 1.13 A\n
255    list [.t tag ranges x] [.t tag ranges y]
256} {{1.1 1.2 1.5 1.13 3.2 3.6} {1.5 1.6}}
257
258test btree-4.1 {deleting with tags} {
259    setup
260    .t delete 1.6 1.9
261    list [.t tag ranges x] [.t tag ranges y]
262} {{1.1 1.2 1.5 1.10 2.2 2.6} {1.5 1.6}}
263test btree-4.2 {deleting with tags} {
264    setup
265    .t delete 1.1 2.3
266    list [.t tag ranges x] [.t tag ranges y]
267} {{1.1 1.4} {}}
268test btree-4.3 {deleting with tags} {
269    setup
270    .t delete 1.4 2.1
271    list [.t tag ranges x] [.t tag ranges y]
272} {{1.1 1.2 1.5 1.9} {}}
273test btree-4.4 {deleting with tags} {
274    setup
275    .t delete 1.14 2.1
276    list [.t tag ranges x] [.t tag ranges y]
277} {{1.1 1.2 1.5 1.13 1.15 1.19} {1.5 1.6}}
278test btree-4.5 {deleting with tags} {
279    setup
280    .t delete 1.0 2.10
281    list [.t tag ranges x] [.t tag ranges y]
282} {{} {}}
283test btree-4.6 {deleting with tags} {
284    setup
285    .t delete 1.0 1.5
286    list [.t tag ranges x] [.t tag ranges y]
287} {{1.0 1.8 2.2 2.6} {1.0 1.1}}
288test btree-4.7 {deleting with tags} {
289    setup
290    .t delete 1.6 1.9
291    list [.t tag ranges x] [.t tag ranges y]
292} {{1.1 1.2 1.5 1.10 2.2 2.6} {1.5 1.6}}
293test btree-4.8 {deleting with tags} {
294    setup
295    .t delete 1.5 1.13
296    list [.t tag ranges x] [.t tag ranges y]
297} {{1.1 1.2 2.2 2.6} {}}
298
299set bigText1 {}
300for {set i 0} {$i < 10} {incr i} {
301    append bigText1 "Line $i\n"
302}
303set bigText2 {}
304for {set i 0} {$i < 200} {incr i} {
305    append bigText2 "Line $i\n"
306}
307test btree-5.1 {very large inserts, with tags} {
308    setup
309    .t insert 1.0 $bigText1
310    list [.t tag ranges x] [.t tag ranges y]
311} {{11.1 11.2 11.5 11.13 12.2 12.6} {11.5 11.6}}
312test btree-5.2 {very large inserts, with tags} {
313    setup
314    .t insert 1.2 $bigText2
315    list [.t tag ranges x] [.t tag ranges y]
316} {{1.1 1.2 201.3 201.11 202.2 202.6} {201.3 201.4}}
317test btree-5.3 {very large inserts, with tags} {
318    setup
319    for {set i 0} {$i < 200} {incr i} {
320	.t insert 1.8 "longer line $i\n"
321    }
322    list [.t tag ranges x] [.t tag ranges y] [.t get 1.0 1.100] [.t get 198.0 198.100]
323} {{1.1 1.2 1.5 201.5 202.2 202.6} {1.5 1.6} {Text forlonger line 199} {longer line 2}}
324
325test btree-6.1 {very large deletes, with tags} {
326    setup
327    .t insert 1.1 $bigText2
328    .t delete 1.2 201.2
329    list [.t tag ranges x] [.t tag ranges y]
330} {{1.4 1.12 2.2 2.6} {1.4 1.5}}
331test btree-6.2 {very large deletes, with tags} {
332    setup
333    .t insert 1.1 $bigText2
334    for {set i 0} {$i < 200} {incr i} {
335	.t delete 1.2 2.2
336    }
337    list [.t tag ranges x] [.t tag ranges y]
338} {{1.4 1.12 2.2 2.6} {1.4 1.5}}
339test btree-6.3 {very large deletes, with tags} {
340    setup
341    .t insert 1.1 $bigText2
342    .t delete 2.3 10000.0
343    .t get 1.0 1000.0
344} {TLine 0
345Lin
346}
347test btree-6.4 {very large deletes, with tags} {
348    setup
349    .t insert 1.1 $bigText2
350    for {set i 0} {$i < 100} {incr i} {
351	.t delete 30.0 31.0
352    }
353    list [.t tag ranges x] [.t tag ranges y]
354} {{101.0 101.1 101.4 101.12 102.2 102.6} {101.4 101.5}}
355test btree-6.5 {very large deletes, with tags} {
356    setup
357    .t insert 1.1 $bigText2
358    for {set i 0} {$i < 100} {incr i} {
359	set j [expr $i+2]
360	set k [expr 1+2*$i]
361	.t tag add x $j.1 $j.3
362	.t tag add y $k.1 $k.6
363    }
364    .t delete 2.0 200.0
365    list [.t tag ranges x] [.t tag ranges y]
366} {{3.0 3.1 3.4 3.12 4.2 4.6} {1.1 1.6 3.4 3.5}}
367test btree-6.6 {very large deletes, with tags} {
368    setup
369    .t insert 1.1 $bigText2
370    for {set i 0} {$i < 100} {incr i} {
371	set j [expr $i+2]
372	set k [expr 1+2*$i]
373	.t tag add x $j.1 $j.3
374	.t tag add y $k.1 $k.6
375    }
376    for {set i 199} {$i >= 2} {incr i -1} {
377	.t delete $i.0 [expr $i+1].0
378    }
379    list [.t tag ranges x] [.t tag ranges y]
380} {{3.0 3.1 3.4 3.12 4.2 4.6} {1.1 1.6 3.4 3.5}}
381
382.t delete 1.0 end
383.t insert 1.0 "Text for first line\nSecond line\n\nLast line of info"
384set i 1
385foreach check {
386    {1.3 1.6 1.7 2.0 {1.3 1.6 1.7 2.0}}
387    {1.3 1.6 1.6 2.0 {1.3 2.0}}
388    {1.3 1.6 1.4 2.0 {1.3 2.0}}
389    {2.0 4.3 1.4 1.10 {1.4 1.10 2.0 4.3}}
390    {2.0 4.3 1.4 1.end {1.4 1.19 2.0 4.3}}
391    {2.0 4.3 1.4 2.0 {1.4 4.3}}
392    {2.0 4.3 1.4 3.0 {1.4 4.3}}
393    {1.2 1.3 1.6 1.7 1.end 2.0 2.4 2.7 3.0 4.0 1.1 4.2 {1.1 4.2}}
394    {1.2 1.3 1.6 1.7 1.end 2.0 2.4 2.7 3.0 4.0 1.3 4.2 {1.2 4.2}}
395    {1.2 1.3 1.6 1.7 1.end 2.0 2.4 2.7 3.0 4.0 1.1 3.0 {1.1 4.0}}
396    {1.2 1.3 1.6 1.7 1.end 2.0 2.4 2.7 3.0 4.0 1.2 3.0 {1.2 4.0}}
397} {
398    test btree-7.$i {tag addition and removal} {
399	.t tag remove x 1.0 end
400	while {[llength $check] > 2} {
401	    .t tag add x [lindex $check 0] [lindex $check 1]
402	    set check [lrange $check 2 end]
403	}
404	.t tag ranges x
405    } [lindex $check [expr [llength $check]-1]]
406    incr i
407}
408
409test btree-8.1 {tag addition and removal, weird ranges} {
410    .t delete 1.0 100000.0
411    .t tag delete x
412    .t insert 1.0 "Text for first line\nSecond line\n\nLast line of info"
413    .t tag add x 0.0 1.3
414    .t tag ranges x
415} {1.0 1.3}
416test btree-8.2 {tag addition and removal, weird ranges} {
417    .t delete 1.0 100000.0
418    .t tag delete x
419    .t insert 1.0 "Text for first line\nSecond line\n\nLast line of info"
420    .t tag add x 1.40 2.4
421    .t tag ranges x
422} {1.19 2.4}
423test btree-8.3 {tag addition and removal, weird ranges} {
424    .t delete 1.0 100000.0
425    .t tag delete x
426    .t insert 1.0 "Text for first line\nSecond line\n\nLast line of info"
427    .t tag add x 4.40 4.41
428    .t tag ranges x
429} {}
430test btree-8.4 {tag addition and removal, weird ranges} {
431    .t delete 1.0 100000.0
432    .t tag delete x
433    .t insert 1.0 "Text for first line\nSecond line\n\nLast line of info"
434    .t tag add x 5.1 5.2
435    .t tag ranges x
436} {}
437test btree-8.5 {tag addition and removal, weird ranges} {
438    .t delete 1.0 100000.0
439    .t tag delete x
440    .t insert 1.0 "Text for first line\nSecond line\n\nLast line of info"
441    .t tag add x 1.1 9.0
442    .t tag ranges x
443} {1.1 5.0}
444test btree-8.6 {tag addition and removal, weird ranges} {
445    .t delete 1.0 100000.0
446    .t tag delete x
447    .t insert 1.0 "Text for first line\nSecond line\n\nLast line of info"
448    .t tag add x 1.1 1.90
449    .t tag ranges x
450} {1.1 1.19}
451test btree-8.7 {tag addition and removal, weird ranges} {
452    .t delete 1.0 100000.0
453    .t tag delete x
454    .t insert 1.0 "Text for first line\nSecond line\n\nLast line of info"
455    .t tag add x 1.1 4.90
456    .t tag ranges x
457} {1.1 4.17}
458test btree-8.8 {tag addition and removal, weird ranges} {
459    .t delete 1.0 100000.0
460    .t tag delete x
461    .t insert 1.0 "Text for first line\nSecond line\n\nLast line of info"
462    .t tag add x 3.0 3.0
463    .t tag ranges x
464} {}
465
466test btree-9.1 {tag names} {
467    setup
468    .t tag names
469} {sel x y}
470test btree-9.2 {tag names} {
471    setup
472    .t tag add tag1 1.8
473    .t tag add tag2 1.8
474    .t tag add tag3 1.7 1.9
475    .t tag names 1.8
476} {x tag1 tag2 tag3}
477test btree-9.3 {lots of tag names} {
478    setup
479    .t insert 1.2 $bigText2
480    foreach i {tag1 foo ThisOne {x space} q r s t} {
481	.t tag add $i 150.2
482    }
483    foreach i {u tagA tagB tagC and more {$} \{} {
484	.t tag add $i 150.1 150.3
485    }
486    .t tag names 150.2
487} {tag1 foo ThisOne {x space} q r s t u tagA tagB tagC and more {$} \{}
488test btree-9.4 {lots of tag names} {
489    setup
490    .t insert 1.2 $bigText2
491    .t tag delete tag1 foo ThisOne more {x space} q r s t u
492    .t tag delete tagA tagB tagC and {$} \{ more
493    foreach i {tag1 foo ThisOne more {x space} q r s t} {
494	.t tag add $i 150.2
495    }
496    foreach i {foo ThisOne u tagA tagB tagC and more {$} \{} {
497	.t tag add $i 150.4
498    }
499    .t tag delete tag1 more q r tagA
500    .t tag names 150.2
501} {foo ThisOne {x space} s t}
502
503proc msetup {} {
504    .t delete 1.0 100000.0
505    .t insert 1.0 "Text for first line\nSecond line\n\nLast line of info"
506    .t mark set m1 1.2
507    .t mark set l1 1.2
508    .t mark gravity l1 left
509    .t mark set next 1.6
510    .t mark set x 1.6
511    .t mark set m2 2.0
512    .t mark set m3 2.100
513    .t tag add x 1.3 1.8
514}
515test btree-10.1 {basic mark facilities} {
516    msetup
517    list [lsort [.t mark names]] [.t index m1] [.t index m2] [.t index m3]
518} {{current insert l1 m1 m2 m3 next x} 1.2 2.0 2.11}
519test btree-10.2 {basic mark facilities} {
520    msetup
521    .t mark unset m2
522    lsort [.t mark names]
523} {current insert l1 m1 m3 next x}
524test btree-10.3 {basic mark facilities} {
525    msetup
526    .t mark set m2 1.8
527    list [lsort [.t mark names]] [.t index m1] [.t index m2] [.t index m3]
528} {{current insert l1 m1 m2 m3 next x} 1.2 1.8 2.11}
529
530test btree-11.1 {marks and inserts} {
531    msetup
532    .t insert 1.1 abcde
533    list [.t index l1] [.t index m1] [.t index next] [.t index x] [.t index m2] [.t index m3]
534} {1.7 1.7 1.11 1.11 2.0 2.11}
535test btree-11.2 {marks and inserts} {
536    msetup
537    .t insert 1.2 abcde
538    list [.t index l1] [.t index m1] [.t index next] [.t index x] [.t index m2] [.t index m3]
539} {1.2 1.7 1.11 1.11 2.0 2.11}
540test btree-11.3 {marks and inserts} {
541    msetup
542    .t insert 1.3 abcde
543    list [.t index l1] [.t index m1] [.t index next] [.t index x] [.t index m2] [.t index m3]
544} {1.2 1.2 1.11 1.11 2.0 2.11}
545test btree-11.4 {marks and inserts} {
546    msetup
547    .t insert 1.1 ab\n\ncde
548    list [.t index l1] [.t index m1] [.t index next] [.t index x] [.t index m2] [.t index m3]
549} {3.4 3.4 3.8 3.8 4.0 4.11}
550test btree-11.5 {marks and inserts} {
551    msetup
552    .t insert 1.4 ab\n\ncde
553    list [.t index l1] [.t index m1] [.t index next] [.t index x] [.t index m2] [.t index m3]
554} {1.2 1.2 3.5 3.5 4.0 4.11}
555test btree-11.6 {marks and inserts} {
556    msetup
557    .t insert 1.7 ab\n\ncde
558    list [.t index l1] [.t index m1] [.t index next] [.t index x] [.t index m2] [.t index m3]
559} {1.2 1.2 1.6 1.6 4.0 4.11}
560
561test btree-12.1 {marks and deletes} {
562    msetup
563    .t delete 1.3 1.5
564    list [.t index l1] [.t index m1] [.t index next] [.t index x] [.t index m2] [.t index m3]
565} {1.2 1.2 1.4 1.4 2.0 2.11}
566test btree-12.2 {marks and deletes} {
567    msetup
568    .t delete 1.3 1.8
569    list [.t index l1] [.t index m1] [.t index next] [.t index x] [.t index m2] [.t index m3]
570} {1.2 1.2 1.3 1.3 2.0 2.11}
571test btree-12.3 {marks and deletes} {
572    msetup
573    .t delete 1.2 1.8
574    list [.t index l1] [.t index m1] [.t index next] [.t index x] [.t index m2] [.t index m3]
575} {1.2 1.2 1.2 1.2 2.0 2.11}
576test btree-12.4 {marks and deletes} {
577    msetup
578    .t delete 1.1 1.8
579    list [.t index l1] [.t index m1] [.t index next] [.t index x] [.t index m2] [.t index m3]
580} {1.1 1.1 1.1 1.1 2.0 2.11}
581test btree-12.5 {marks and deletes} {
582    msetup
583    .t delete 1.5 3.1
584    list [.t index l1] [.t index m1] [.t index next] [.t index x] [.t index m2] [.t index m3]
585} {1.2 1.2 1.5 1.5 1.5 1.5}
586test btree-12.6 {marks and deletes} {
587    msetup
588    .t mark set m2 4.5
589    .t delete 1.5 4.1
590    list [.t index l1] [.t index m1] [.t index next] [.t index x] [.t index m2] [.t index m3]
591} {1.2 1.2 1.5 1.5 1.9 1.5}
592test btree-12.7 {marks and deletes} {
593    msetup
594    .t mark set m2 4.5
595    .t mark set m3 4.5
596    .t mark set m1 4.7
597    .t delete 1.5 4.1
598    list [.t index l1] [.t index m1] [.t index next] [.t index x] [.t index m2] [.t index m3]
599} {1.2 1.11 1.5 1.5 1.9 1.9}
600
601destroy .t
602text .t
603test btree-13.1 {tag searching} {
604    .t delete 1.0 100000.0
605    .t insert 1.0 "Text for first line\nSecond line\n\nLast line of info"
606    .t tag next x 2.2 2.1
607} {}
608test btree-13.2 {tag searching} {
609    .t delete 1.0 100000.0
610    .t insert 1.0 "Text for first line\nSecond line\n\nLast line of info"
611    .t tag add x 2.2 2.4
612    .t tag next x 2.2 2.3
613} {2.2 2.4}
614test btree-13.3 {tag searching} {
615    .t delete 1.0 100000.0
616    .t insert 1.0 "Text for first line\nSecond line\n\nLast line of info"
617    .t tag add x 2.2 2.4
618    .t tag next x 2.3 2.6
619} {}
620test btree-13.4 {tag searching} {
621    .t delete 1.0 100000.0
622    .t insert 1.0 "Text for first line\nSecond line\n\nLast line of info"
623    .t tag add x 2.5 2.8
624    .t tag next x 2.1 2.6
625} {2.5 2.8}
626test btree-13.5 {tag searching} {
627    .t delete 1.0 100000.0
628    .t insert 1.0 "Text for first line\nSecond line\n\nLast line of info"
629    .t tag add x 2.5 2.8
630    .t tag next x 2.1 2.5
631} {}
632test btree-13.6 {tag searching} {
633    .t delete 1.0 100000.0
634    .t insert 1.0 "Text for first line\nSecond line\n\nLast line of info"
635    .t tag add x 2.1 2.4
636    .t tag next x 2.5 2.8
637} {}
638test btree-13.7 {tag searching} {
639    .t delete 1.0 100000.0
640    .t insert 1.0 "Text for first line\nSecond line\n\nLast line of info"
641    .t tag add x 2.5 2.8
642    .t tag next x 2.1 2.4
643} {}
644test btree-13.8 {tag searching} {
645    setup
646    .t insert 1.2 $bigText2
647    .t tag add x 190.3 191.2
648    .t tag next x 3.5
649} {190.3 191.2}
650
651test btree-14.1 {check tag presence} {
652    setup
653    .t insert 1.2 $bigText2
654    .t tag add x 3.5 3.7
655    .t tag add y 133.9 141.5
656    .t tag add z 1.5 180.2
657    .t tag add q 141.4 142.3
658    .t tag add x 130.2 145.1
659    .t tag add a 141.0
660    .t tag add b 4.3
661    .t tag add b 7.5
662    .t tag add b 140.3
663    for {set i 120} {$i < 160} {incr i} {
664	.t tag add c $i.4
665    }
666    foreach i {a1 a2 a3 a4 a5 a6 a7 a8 a9 10 a11 a12 a13} {
667	.t tag add $i 122.2
668    }
669    .t tag add x 141.3
670    .t tag names 141.1
671} {x y z}
672
673test btree-15.1 {rebalance with empty node} {
674    catch {destroy .t}
675    text .t
676    .t debug 1
677    .t insert end "1\n2\n3\n4\n5\n6\n7\n8\n9\n10\n11\n12\n13\n14\n15\n16\n17\n18\n19\n20\n21\n22\n23"
678    .t delete 6.0 12.0
679    .t get 1.0 end
680} "1\n2\n3\n4\n5\n12\n13\n14\n15\n16\n17\n18\n19\n20\n21\n22\n23\n"
681
682proc setupBig {} {
683    .t delete 1.0 end
684    .t tag delete x y
685    .t tag configure x -foreground blue
686    .t tag configure y -underline true
687    # Create a Btree with 2002 lines (2000 + already existing + phantom at end)
688    # This generates a level 3 node with 9 children
689    # Most level 2 nodes cover 216 lines and have 6 children, except the last
690    # level 2 node covers 274 lines and has 7 children.
691    # Most level 1 nodes cover 36 lines and have 6 children, except the
692    # rightmost node has 58 lines and 9 children.
693    # Level 2: 2002 = 8*216 + 274
694    # Level 1: 2002 = 54*36 + 58
695    # Level 0: 2002 = 332*6 + 10
696    for {set i 0} {$i < 2000} {incr i} {
697	append x "Line $i abcd efgh ijkl\n"
698    }
699    .t insert insert $x
700    .t debug 1
701}
702
703test btree-16.1 {add tag does not push root above level 0} {
704    catch {destroy .t}
705    text .t
706    setupBig
707    .t tag add x 1.1 1.10
708    .t tag add x 5.1 5.10
709    .t tag ranges x
710} {1.1 1.10 5.1 5.10}
711test btree-16.2 {add tag pushes root up to level 1 node} {
712    catch {destroy .t}
713    text .t
714    .t debug 1
715    setupBig
716    .t tag add x 1.1 1.10
717    .t tag add x 8.1 8.10
718    .t tag ranges x
719} {1.1 1.10 8.1 8.10}
720test btree-16.3 {add tag pushes root up to level 2 node} {
721    .t tag remove x 1.0 end
722    .t tag add x 8.1 9.10
723    .t tag add x 180.1 180.end
724    .t tag ranges x
725} {8.1 9.10 180.1 180.23}
726test btree-16.4 {add tag pushes root up to level 3 node} {
727    .t tag remove x 1.0 end
728    .t tag add y 1.1 2000.0
729    .t tag add x 1.1 8.10
730    .t tag add x 180.end 217.0
731    list [.t tag ranges x] [.t tag ranges y]
732} {{1.1 8.10 180.23 217.0} {1.1 2000.0}}
733test btree-16.5 {add tag doesn't push root up} {
734    .t tag remove x 1.0 end
735    .t tag add x 1.1 8.10
736    .t tag add x 2000.0 2000.3
737    .t tag add x 180.end 217.0
738    .t tag ranges x
739} {1.1 8.10 180.23 217.0 2000.0 2000.3}
740test btree-16.6 {two node splits at once pushes root up} {
741    .t delete 1.0 end
742    for {set i 1} {$i < 10} {incr i} {
743	.t insert end "Line $i\n"
744    }
745    .t tag add x 8.0 8.end
746    .t tag add y 9.0 end
747    set x {}
748    for {} {$i < 50} {incr i} {
749	append x "Line $i\n"
750    }
751    .t insert end $x y
752    list [.t tag ranges x] [.t tag ranges y]
753} {{8.0 8.6} {9.0 51.0}}
754# The following find bugs in the SearchStart procedures
755test btree-16.7 {Partial tag remove from before first range} {
756    .t tag remove x 1.0 end
757    .t tag add x 2.0 2.6
758    .t tag remove x 1.0 2.0
759    .t tag ranges x
760} {2.0 2.6}
761test btree-16.8 {Partial tag remove from before first range} {
762    .t tag remove x 1.0 end
763    .t tag add x 2.0 2.6
764    .t tag remove x 1.0 2.1
765    .t tag ranges x
766} {2.1 2.6}
767test btree-16.9 {Partial tag remove from before first range} {
768    .t tag remove x 1.0 end
769    .t tag add x 2.0 2.6
770    .t tag remove x 1.0 2.3
771    .t tag ranges x
772} {2.3 2.6}
773test btree-16.10 {Partial tag remove from before first range} {
774    .t tag remove x 1.0 end
775    .t tag add x 1.0 2.6
776    .t tag remove x 1.0 2.5
777    .t tag ranges x
778} {2.5 2.6}
779test btree-16.11 {StartSearchBack boundary case} {
780    .t tag remove x 1.0 end
781    .t tag add x 1.3 1.4
782    .t tag prevr x 2.0 1.4
783} {}
784test btree-16.12 {StartSearchBack boundary case} {
785    .t tag remove x 1.0 end
786    .t tag add x 1.3 1.4
787    .t tag prevr x 2.0 1.3
788} {1.3 1.4}
789test btree-16.13 {StartSearchBack boundary case} {
790    .t tag remove x 1.0 end
791    .t tag add x 1.0 1.4
792    .t tag prevr x 1.3
793} {1.0 1.4}
794
795
796test btree-17.1 {remove tag does not push root down} {
797    catch {destroy .t}
798    text .t
799    .t debug 0
800    setupBig
801    .t tag add x 1.1 5.10
802    .t tag remove x 3.1 5.end
803    .t tag ranges x
804} {1.1 3.1}
805test btree-17.2 {remove tag pushes root from level 1 to level 0} {
806    .t tag remove x 1.0 end
807    .t tag add x 1.1 8.10
808    .t tag remove x 3.1 end
809    .t tag ranges x
810} {1.1 3.1}
811test btree-17.3 {remove tag pushes root from level 2 to level 1} {
812    .t tag remove x 1.0 end
813    .t tag add x 1.1 180.10
814    .t tag remove x 35.1 end
815    .t tag ranges x
816} {1.1 35.1}
817test btree-17.4 {remove tag doesn't change level 2} {
818    .t tag remove x 1.0 end
819    .t tag add x 1.1 180.10
820    .t tag remove x 35.1 180.0
821    .t tag ranges x
822} {1.1 35.1 180.0 180.10}
823test btree-17.5 {remove tag pushes root from level 3 to level 0} {
824    .t tag remove x 1.0 end
825    .t tag add x 1.1 1.10
826    .t tag add x 2000.1 2000.10
827    .t tag remove x 1.0 2000.0
828    .t tag ranges x
829} {2000.1 2000.10}
830test btree-17.6 {text deletion pushes root from level 3 to level 0} {
831    .t tag remove x 1.0 end
832    .t tag add x 1.1 1.10
833    .t tag add x 2000.1 2000.10
834    .t delete 1.0 "1000.0 lineend +1 char"
835    .t tag ranges x
836} {1000.1 1000.10}
837
838catch {destroy .t}
839text .t
840test btree-18.1 {tag search back, no tag} {
841    .t insert 1.0 "Line 1 abcd efgh ijkl\n"
842    .t tag prev x 1.1 1.1
843} {}
844test btree-18.2 {tag search back, start at existing range} {
845    .t tag remove x 1.0 end
846    .t tag add x 1.1 1.4
847    .t tag add x 1.8 1.11
848    .t tag add x 1.16
849    .t tag prev x 1.1
850} {}
851test btree-18.3 {tag search back, end at existing range} {
852    .t tag remove x 1.0 end
853    .t tag add x 1.1 1.4
854    .t tag add x 1.8 1.11
855    .t tag add x 1.16
856    .t tag prev x 1.3 1.1
857} {1.1 1.4}
858test btree-18.4 {tag search back, start within range} {
859    .t tag remove x 1.0 end
860    .t tag add x 1.1 1.4
861    .t tag add x 1.8 1.11
862    .t tag add x 1.16
863    .t tag prev x 1.10 1.0
864} {1.8 1.11}
865test btree-18.5 {tag search back, start at end of range} {
866    .t tag remove x 1.0 end
867    .t tag add x 1.1 1.4
868    .t tag add x 1.8 1.11
869    .t tag add x 1.16
870    list [.t tag prev x 1.4 1.0] [.t tag prev x 1.11 1.0]
871} {{1.1 1.4} {1.8 1.11}}
872test btree-18.6 {tag search back, start beyond range, same level 0 node} {
873    .t tag remove x 1.0 end
874    .t tag add x 1.1 1.4
875    .t tag add x 1.8 1.11
876    .t tag add x 1.16
877    .t tag prev x 3.0
878} {1.16 1.17}
879test btree-18.7 {tag search back, outside any range} {
880    .t tag remove x 1.0 end
881    .t tag add x 1.1 1.4
882    .t tag add x 1.16
883    .t tag prev x 1.8 1.5
884} {}
885test btree-18.8 {tag search back, start at start of node boundary} {
886    setupBig
887    .t tag remove x 1.0 end
888    .t tag add x 2.5 2.8
889    .t tag prev x 19.0
890} {2.5 2.8}
891test btree-18.9 {tag search back, large complex btree spans} {
892    .t tag remove x 1.0 end
893    .t tag add x 1.3 1.end
894    .t tag add x 200.0 220.0
895    .t tag add x 500.0 520.0
896    list [.t tag prev x end] [.t tag prev x 433.0]
897} {{500.0 520.0} {200.0 220.0}}
898
899destroy .t
900
901# cleanup
902::tcltest::cleanupTests
903return
904
905
906
907
908
909
910
911
912
913
914
915
916
917