Tk Source Code

Check-in [232ed197]
Login
Bounty program for improvements to Tcl and certain Tcl packages.
Tcl 2019 Conference, Houston/TX, US, Nov 4-8
Send your abstracts to tclconference@googlegroups.com
or submit via the online form by Sep 9.

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:Better comments explaining the algorithm in ::tk::TextUndoRedoProcessMarks
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | tip-449
Files: files | file ages | folders
SHA1:232ed197fe60795af8931a7abe38a3d46d8053d4
User & Date: fvogel 2016-07-05 20:02:59
Context
2016-07-05
20:03
Removed unintended whitespace change check-in: 33ccff8f user: fvogel tags: tip-449
20:02
Better comments explaining the algorithm in ::tk::TextUndoRedoProcessMarks check-in: 232ed197 user: fvogel tags: tip-449
2016-07-04
21:26
Return indices making sense at undo/redo return time. The returned ranges are optimized (no duplicates, no overlapping ranges). Works but needs polishing. check-in: 6c03c35d user: fvogel tags: tip-449
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to library/text.tcl.

1213
1214
1215
1216
1217
1218
1219

1220
1221
1222
1223
1224
1225


1226

1227
1228
1229
1230
1231
1232
1233
1234
1235
1236
1237
1238
1239
1240
1241

1242
1243
1244
1245
1246
1247
1248
1249
1250

1251
1252


1253

1254
1255
1256

1257
1258

1259
1260

1261



1262
1263
1264
1265
1266
1267
1268
1269




1270
1271
#
# Arguments:
# w -	The text widget

proc ::tk::TextUndoRedoProcessMarks {w} {
    set indices {}
    set undoMarks {}

    # only consider the temporary marks set by an undo/redo action
    foreach mark [$w mark names] {
        if {[string range $mark 0 11] eq "tk::undoMark"} {
            lappend undoMarks $mark
        }
    }


    # the number of undo/redo marks is always even

    set nUndoMarks [llength $undoMarks]
    set n [expr {$nUndoMarks / 2}]
    set undoMarks [lsort -dictionary $undoMarks]
    set Lmarks [lrange $undoMarks 0 [expr {$n - 1}]]
    set Rmarks [lrange $undoMarks $n [llength $undoMarks]]
    foreach Lmark $Lmarks Rmark $Rmarks {
        lappend indices [$w index $Lmark] [$w index $Rmark]
        $w mark unset $Lmark $Rmark
    }
#puts "Unoptimized indices: $indices"
    # process ranges to:
    #   - remove those already fully included in another range
    #   - merge overlapping ranges
    set ind [lsort -dictionary -stride 2 $indices]
    set indices {}

    for {set i 0} {$i < $nUndoMarks} {incr i 2} {
        set il1 [lindex $ind $i]
        set ir1 [lindex $ind [expr {$i + 1}]]
        lappend indices $il1 $ir1
#puts "  range1: $il1 $ir1"
        for {set j [expr {$i + 2}]} {$j < $nUndoMarks} {incr j 2} {
            set il2 [lindex $ind $j]
            set ir2 [lindex $ind [expr {$j + 1}]]
#puts "  range2: $il2 $ir2"

            if {[$w compare $il2 > $ir1]} {
                # second range starts after the end of first range


                set j $nUndoMarks

            } else {
                if {[$w compare $ir2 > $ir1]} {
                    # second range overlaps with first range

                    set indices [lreplace $indices end-1 end]
                    lappend indices $il1 $ir2

                } else {
                    # second range is fully included in first range

                }



                set ind [lreplace $ind $j [expr {$j + 1}]]
                incr j -2
                incr nUndoMarks -2
            }
#puts "    indices: $indices"
        }
    }
#puts "OPTIMIZED indices: $indices"




    return $indices
}







>






>
>
|
>









|





>




|



<
>


>
>

>


|
>


>


>
|
>
>
>



|
<
|
|
<
>
>
>
>


1213
1214
1215
1216
1217
1218
1219
1220
1221
1222
1223
1224
1225
1226
1227
1228
1229
1230
1231
1232
1233
1234
1235
1236
1237
1238
1239
1240
1241
1242
1243
1244
1245
1246
1247
1248
1249
1250
1251
1252
1253
1254

1255
1256
1257
1258
1259
1260
1261
1262
1263
1264
1265
1266
1267
1268
1269
1270
1271
1272
1273
1274
1275
1276
1277
1278
1279

1280
1281

1282
1283
1284
1285
1286
1287
#
# Arguments:
# w -	The text widget

proc ::tk::TextUndoRedoProcessMarks {w} {
    set indices {}
    set undoMarks {}

    # only consider the temporary marks set by an undo/redo action
    foreach mark [$w mark names] {
        if {[string range $mark 0 11] eq "tk::undoMark"} {
            lappend undoMarks $mark
        }
    }

    # transform marks into indices
    # the number of undo/redo marks is always even, each right mark
    # completes a left mark to give a range
    set nUndoMarks [llength $undoMarks]
    set n [expr {$nUndoMarks / 2}]
    set undoMarks [lsort -dictionary $undoMarks]
    set Lmarks [lrange $undoMarks 0 [expr {$n - 1}]]
    set Rmarks [lrange $undoMarks $n [llength $undoMarks]]
    foreach Lmark $Lmarks Rmark $Rmarks {
        lappend indices [$w index $Lmark] [$w index $Rmark]
        $w mark unset $Lmark $Rmark
    }

    # process ranges to:
    #   - remove those already fully included in another range
    #   - merge overlapping ranges
    set ind [lsort -dictionary -stride 2 $indices]
    set indices {}

    for {set i 0} {$i < $nUndoMarks} {incr i 2} {
        set il1 [lindex $ind $i]
        set ir1 [lindex $ind [expr {$i + 1}]]
        lappend indices $il1 $ir1
 
        for {set j [expr {$i + 2}]} {$j < $nUndoMarks} {incr j 2} {
            set il2 [lindex $ind $j]
            set ir2 [lindex $ind [expr {$j + 1}]]

 
            if {[$w compare $il2 > $ir1]} {
                # second range starts after the end of first range
                # -> further second ranges do not need to be considered
                #    because ranges were sorted by increasing first index
                set j $nUndoMarks
 
            } else {
                if {[$w compare $ir2 > $ir1]} {
                    # second range overlaps first range
                    # -> merge them into a single range
                    set indices [lreplace $indices end-1 end]
                    lappend indices $il1 $ir2

                } else {
                    # second range is fully included in first range
                    # -> ignore it

                }
                # in both cases above, the second range shall be
                # trimmed out from the list of ranges
                set ind [lreplace $ind $j [expr {$j + 1}]]
                incr j -2
                incr nUndoMarks -2
 

            }


        }

    }

    return $indices
}