ðŸŽ‰ Exercism Research is now launched. Help Exercism, help science and have some fun at research.exercism.io ðŸŽ‰

Published at Apr 09 2020
·
0 comments

Instructions

Test suite

Solution

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.

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

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.
```

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!

```
#!/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
}
}
```

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?

Level up your programming skills with 3,450 exercises across 52 languages, and insightful discussion with our volunteer team of welcoming mentors.
Exercism is
**100% free forever**.

## Community comments