🎉 Exercism Research is now launched. Help Exercism, help science and have some fun at research.exercism.io 🎉
Avatar of glennj

glennj's solution

to Custom Set in the Tcl Track

Published at Apr 09 2020 · 0 comments
Instructions
Test suite
Solution

Note:

This exercise has changed since this solution was written.

Create a custom set type.

Sometimes it is necessary to define a custom data structure of some type, like a set. In this exercise you will define your own set. How it works internally doesn't matter, as long as it behaves like a set of unique elements.

Submitting Incomplete Solutions

It's possible to submit an incomplete solution so you can see how others have completed the exercise.

Running the tests

To run the test suite, execute one of the following commands:

tclsh custom-set.test            # Will stop testing after the first failure.
RUN_ALL=1 tclsh custom-set.test  # Will run all tests and report all failures.

Feedback, Issues, Pull Requests

The exercism/tcl repository on GitHub is the home for all of the Tcl exercises on Exercism.

If you have feedback about an exercise, or want to help implementing a new one, head over there and create an issue. We'll do our best to help you!

Source

custom-set.test

#!/usr/bin/env tclsh
set version 1.3.0
package require tcltest
namespace import ::tcltest::*
source "custom-set.tcl"

proc fail_fast {} {
    return [expr {
        ![info exists ::env(RUN_ALL)]
        || [string is boolean -strict $::env(RUN_ALL)]
        && !$::env(RUN_ALL)
    }]
}

proc failed {} {
    return [expr {$::tcltest::numTests(Failed) > 0}]
}

if {[fail_fast]} {
    proc test args {
        if {[failed]} {::tcltest::configure -skip *}
        uplevel [list ::tcltest::test {*}$args]
    }
}

proc cleanupTests {} {
    set failed [failed]
    uplevel 1 ::tcltest::cleanupTests
    if {$failed} {exit 1}
}

proc booleanMatch {expected actual} {
    return [expr {
        [string is boolean -strict $expected] &&
        [string is boolean -strict $actual] &&
        !!$expected == !!$actual
    }]
}
customMatch boolean booleanMatch

proc unorderedListsMatch {expected actual} {
    if {[llength $expected] != [llength $actual]} {
        return false
    }
    foreach elem $actual {
        if {[lsearch -exact $expected $elem] == -1} {
            return false
        }
    }
    return true
}
customMatch unorderedLists unorderedListsMatch


if {$::argv0 eq [info script]} {

    # Returns the elements of the set as a list
    # Sets are unordered.
    set cases {
        set-11.1 "sets with no elements" {} {}
        set-11.2 "sets with elements" {1 2 3 4} {4 3 1 2}
    }
    foreach {name description data result} $cases {
        test $name $description -body {
            set s [Set new $data]
            $s toList
        } -returnCodes ok -match unorderedLists -result $result
    }

    # Size of a set
    set cases {
        set-12.1 "size of sets with no elements" {} 0
        set-12.2 "size of sets with elements" {3 2 1} 3
    }
    foreach {name description data result} $cases {
        test $name $description -body {
            set s [Set new $data]
            $s size
        } -returnCodes ok -result $result
    }

    # Returns true if the set contains no elements
    set cases {
        set-1.1 "sets with no elements are empty" {} true
        set-1.2 "sets with elements are not empty" {1} false
    }
    foreach {name description data result} $cases {
        test $name $description -body {
            set s [Set new $data]
            $s isEmpty
        } -returnCodes ok -match boolean -result $result
    }

    # Sets can report if they contain an element
    set cases {
        set-2.1 "nothing is contained in an empty set" {} 1 false
        set-2.2 "when the element is in the set" {1 2 3} 1 true
        set-2.3 "when the element is not in the set" {1 2 3} 4 false
    }
    foreach {name description data element result} $cases {
        test $name $description -body {
            set s [Set new $data]
            $s contains $element
        } -returnCodes ok -match boolean -result $result
    }

    # A set is a subset if all of its elements are contained in the other set
    set cases {
        set-3.1 "empty set is a subset of another empty set" {} {} true
        set-3.2 "empty set is a subset of non-empty set" {} {1} true
        set-3.3 "non-empty set is not a subset of empty set" {1} {} false
        set-3.4 "set is a subset of set with exact same elements" {1 2 3} {1 2 3} true
        set-3.5 "set is a subset of larger set with same elements" {1 2 3} {4 1 2 3} true
        set-3.6 "set is not a subset of set that does not contain its elements" {1 2 3} {4 1 3} false
    }
    foreach {name description data1 data2 result} $cases {
        test $name $description -body {
            set s1 [Set new $data1]
            set s2 [Set new $data2]
            $s1 subsetOf $s2
        } -returnCodes ok -match boolean -result $result
    }

    # Sets are disjoint if they share no elements
    set cases {
        set-4.1 "the empty set is disjoint with itself" {} {} true
        set-4.2 "empty set is disjoint with non-empty set" {} {1} true
        set-4.3 "non-empty set is disjoint with empty set" {1} {} true
        set-4.4 "sets are not disjoint if they share an element" {1 2} {2 3} false
        set-4.5 "sets are disjoint if they share no elements" {1 2} {3 4} true
    }
    foreach {name description data1 data2 result} $cases {
        test $name $description -body {
            set s1 [Set new $data1]
            set s2 [Set new $data2]
            $s1 disjoint $s2
        } -returnCodes ok -match boolean -result $result
    }

    # Sets with the same elements are equal
    set cases {
        set-5.1 "empty sets are equal" {} {} true
        set-5.2 "empty set is not equal to non-empty set" {} {1 2 3} false
        set-5.3 "non-empty set is not equal to empty set" {1 2 3} {} false
        set-5.4 "sets with the same elements are equal" {1 2} {2 1} true
        set-5.5 "sets with different elements are not equal" {1 2 3} {1 2 4} false
        set-5.6 "set is not equal to larger set with same elements" {1 2 3} {1 2 3 4} false
    }
    foreach {name description data1 data2 result} $cases {
        test $name $description -body {
            set s1 [Set new $data1]
            set s2 [Set new $data2]
            $s1 equals $s2
        } -returnCodes ok -match boolean -result $result
    }

    # Unique elements can be added to a set
    set cases {
        set-6.1 "add to empty set" {} 3 {3}
        set-6.2 "add to non-empty set" {1 2 4} 3 {1 2 3 4}
        set-6.3 "adding an existing element does not change the set" {1 2 3} 3 {1 2 3}
    }
    foreach {name description data element result} $cases {
        test $name $description -body {
            set s [Set new $data]
            $s add $element
            $s toList
        } -returnCodes ok -match unorderedLists -result $result
    }

    # Intersection returns a set of all shared elements
    set cases {
        set-7.1 "intersection of two empty sets is an empty set" {} {} {}
        set-7.2 "intersection of an empty set and non-empty set is an empty set" {} {3 2 5} {}
        set-7.3 "intersection of a non-empty set and an empty set is an empty set" {1 2 3 4} {} {}
        set-7.4 "intersection of two sets with no shared elements is an empty set" {1 2 3} {4 5 6} {}
        set-7.5 "intersection of two sets with shared elements is a set of the shared elements" {1 2 3 4} {3 2 5} {2 3}
    }
    foreach {name description data1 data2 result} $cases {
        test $name $description -body {
            set s1 [Set new $data1]
            set s2 [Set new $data2]
            set s3 [$s1 intersection $s2]
            $s3 toList
        } -returnCodes ok -match unorderedLists -result $result
    }

    # Difference (or Complement) of a set is a set of all elements that are only in the first set
    set cases {
        set-8.1 "difference of two empty sets is an empty set" {} {} {}
        set-8.2 "difference of empty set and non-empty set is an empty set" {} {3 2 5} {}
        set-8.3 "difference of a non-empty set and an empty set is the non-empty set" {1 2 3 4} {} {1 2 3 4}
        set-8.4 "difference of two non-empty sets is a set of elements that are only in the first set" {3 2 1} {2 4} {1 3}
    }
    foreach {name description data1 data2 result} $cases {
        test $name $description -body {
            set s1 [Set new $data1]
            set s2 [Set new $data2]
            set s3 [$s1 difference $s2]
            $s3 toList
        } -returnCodes ok -match unorderedLists -result $result
    }

    # Union returns a set of all elements in either set
    set cases {
        set-9.1 "union of empty sets is an empty set" {} {} {}
        set-9.2 "union of an empty set and non-empty set is the non-empty set" {} {2} {2}
        set-9.3 "union of a non-empty set and empty set is the non-empty set" {1 3} {} {1 3}
        set-9.4 "union of non-empty sets contains all unique elements" {1 3} {2 3} {3 2 1}
    }
    foreach {name description data1 data2 result} $cases {
        test $name $description -body {
            set s1 [Set new $data1]
            set s2 [Set new $data2]
            set s3 [$s1 union $s2]
            $s3 toList
        } -returnCodes ok -match unorderedLists -result $result
    }

    cleanupTests
}
oo::class create Set {
    variable data

    constructor {{elements {}}} {
        set data [dict create]
        my addAll $elements
    }

    method toList   {}  {dict keys $data}
    method size     {}  {dict size $data}
    method isEmpty  {}  {expr {[my size] == 0}}
    method contains {e} {dict exists $data $e}

    method add {elem} {
        dict set data $elem ""
        return [self]
    }

    method addAll {elements} {
        foreach elem $elements {
            my add $elem
        }
        return [self]
    }

    method equals {other} {
        expr {[my size] == [$other size] && [my subsetOf $other]}
    }

    method foreach {varName body} {
        upvar 1 $varName var
        dict for {var _} $data {uplevel 1 $body}
    }

    method subsetOf {other} {
        # This can be implemented with
        #    expr {[my size] == [[my intersection $other] size]}
        # but that must examine every element in the set.
        # This short-circuits:

        set result true
        my foreach elem {
            if {![$other contains $elem]} {
                set result false
                break
            }
        }
        return $result
    }

    method disjoint {other} {
        # Similar to above
        #    [my intersection $other] isEmpty

        set result true
        my foreach elem {
            if {[$other contains $elem]} {
                set result false
                break
            }
        }
        return $result

    }

    method partition {other} {
        set intersection [[self class] new]
        set difference   [[self class] new]
        my foreach elem {
            if {[$other contains $elem]} {
                $intersection add $elem
            } else {
                $difference add $elem
            }
        }
        return [list $intersection $difference]
    }

    method intersection {other} {
        lindex [my partition $other] 0
    }

    method difference {other} {
        lindex [my partition $other] 1
    }

    method union {other} {
        set result [[self class] new]
        my     foreach elem {$result add $elem}
        $other foreach elem {$result add $elem}
        return $result
    }
}

Community comments

Find this solution interesting? Ask the author a question to learn more.

What can you learn from this solution?

A huge amount can be learned from reading other people’s code. This is why we wanted to give exercism users the option of making their solutions public.

Here are some questions to help you reflect on this solution and learn the most from it.

  • What compromises have been made?
  • Are there new concepts here that you could read more about to improve your understanding?