# -*- tcl -*-

proc unionA {args} {
    switch [llength $args] {
        0 {
            return {}
        }
        1 {
            return [lindex $args 0]
        }
        default {
            foreach set $args {
                foreach e $set {
                    set tmp($e) .
                }
            }
            return [array names tmp]
        }
    }
}



proc unionB {args} {
    switch [llength $args] {
        0 {
            return {}
        }
        1 {
            return [lindex $args 0]
        }
        default {
            set tmp {}
            foreach set $args {
                foreach e $set {
                    lappend tmp $e
                }
            }
            # remove duplicates --
            # sort and scan. shortcut in case of empty or
            # single-element result.

            if {[llength $tmp] < 2} {
                return $tmp
            }

            set tmp  [lsort tmp]
            set last [lindex $tmp 0]
            set tmp  [lrange $tmp 1 end]
            set res  $last

            foreach e $tmp {
                if {[string compare $e $last] != 0} {
                    lappend res $e
                    set last    $e
                }
            }

            return $res
        }
    }
}



proc unionC {args} {
    switch [llength $args] {
        0 {
            return {}
        }
        1 {
            return [lindex $args 0]
        }
        default {
            set tmp {}
            foreach set $args {
                foreach e $set {
                    lappend tmp $e
                }
            }
            # -W- remove duplicates --
            # hash out. shortcut in case of empty or
            # single-element result.

            if {[llength $tmp] < 2} {
                return $tmp
            }

            foreach e $tmp {
                set tmpa($e) .
            }

            return [array names tmpa]
        }
    }
}

# A O(nm)

# B O(nm+nmlognm)

# C O(nm)

foreach {i text a b} {
    01 {10/10/0} {1 2 3 4 5 6 7 8 9 0} {a b c d e f g h i j}
    02 {05/10/0} {1 2 3 4 5}           {a b c d e f g h i j}
    03 {10/05/0} {1 2 3 4 5 6 7 8 9 0} {a b c d e}
    04 {05/05/0} {1 2 3 4 5}           {a b c d e}

    05 {15/15/0} {1 2 3 4 5 6 7 8 9 0 p q r s t} {a b c d e f g h i j k l m n o}
    06 {15/10/0} {1 2 3 4 5 6 7 8 9 0 p q r s t} {a b c d e f g h i j}
    07 {10/15/0} {1 2 3 4 5 6 7 8 9 0}           {a b c d e f g h i j k l m n o}

    08 {10/10/5} {1 2 3 4 5 6 7 8 9 0} {1 2 3 4 5 f g h i j}
    09 {05/10/5} {a b c d e}           {a b c d e f g h i j}
    10 {10/05/5} {a b c d 5 e 7 8 9 0} {a b c d e}
    11 {05/05/5} {1 2 3 4 5}           {1 2 3 4 5}

    12 {15/15/5} {1 2 3 4 5 6 7 8 9 0 a b c d e} {a b c d e f g h i j k l m n o}
    13 {15/10/5} {1 2 3 4 5 6 7 8 9 0 p q r s t} {1 2 3 4 5 f g h i j}
    14 {10/15/5} {k l m n o 6 7 8 9 0}           {a b c d e f g h i j k l m n o}
} {
    puts stderr "-- $i --" ; flush stderr
    puts stdout "--------------------------------------"
    puts stdout "$i A $text [time {unionA $a $b} 2000]"
    puts stdout "$i B $text [time {unionB $a $b} 2000]"
    puts stdout "$i C $text [time {unionC $a $b} 2000]"
}

puts stdout "--------------------------------------"

<<categories>>Performance