ch6ex1

README

= Exercise 6.1
// Refs:
:url-base: https://github.com/fenegroni/TGPL-exercise-solutions
:workflow: workflows/Exercise 6.1
:action: actions/workflows/ch6ex1.yml
:url-workflow: {url-base}/{workflow}
:url-action: {url-base}/{action}
:badge-exercise: image:{url-workflow}/badge.svg?branch=main[link={url-action}]

{badge-exercise}

Implement these additional methods:

[source]
----
func (*IntSet) Len() int      // return the number of elements
func (*IntSet) Remove(x int)  // remove x from the set
func (*IntSet) Clear()        // remove all elements from the set
func (*IntSet) Copy() *IntSet // return a copy of the set
----

== Tests

We implement unit tests at the single method level and at the type level.

Individual method tests cover a number of cases, some separated out.

The type level `TestIntSet` integrates all the set operations
and uses the string representation of a set to validate results.

== Clear and Trim

We implement the method `Trim` to allow efficient memory usage
since `Clear` and `Remove` clear bits but do not remove empty words
from the tail of the set.

If we add a big number to the set and then remove it,
we could be left with lots of unused memory
if adding big numbers to the set rarely happens.

== Compare

Comparing two sets needs some thinking because
if we want to make sets comparable we might need to do it in such a way
other packages can pick up on it.

== Negative numbers

Negative numbers are not handled and the interface allows them to be passed in.
What we do as a result is currently undefined behaviour.

== Benchmark `Len`

The `Len` method has two implementations: the first one uses the property of bitwise operators
to speedily count the bits set to 1 in an `int`.
The speed of this algorithm is variable and depends on the size of the set and the number of bits set to 1.

A second algorithm produces results in near-constant time, but requires the implementation to precalculate
the lookup table at the start, which means both start up time and memory size.
This might be a consideration in embedded real-time systems.

NOTE: We can write benchmarks to determine which algorithm is more appropriate for the specific programme,
and whether there's a way for us to pre-determine which one will be most advantageous.
We could keep track of the set population every time Len is called and fire up a goroutine to populate
the lookup table

Documentation

Index

• type IntSet
  • func (s *IntSet) Add(x int)
  • func (s *IntSet) Clear()
  • func (s *IntSet) Copy() *IntSet
  • func (s *IntSet) Has(x int) bool
  • func (s *IntSet) Len() int
  • func (s *IntSet) Remove(x int)
  • func (s *IntSet) String() string
  • func (s *IntSet) Trim()
  • func (s *IntSet) UnionWith(t *IntSet)

Types

type IntSet

type IntSet struct {
	// contains filtered or unexported fields
}

An IntSet is a set of small non-negative integers. Its zero value represents the empty set.

func (*IntSet) Add

func (s *IntSet) Add(x int)

Add the non-negative value x to the set

func (*IntSet) Clear

func (s *IntSet) Clear()

Clear removes all elements from the set

func (*IntSet) Copy

func (s *IntSet) Copy() *IntSet

Copy returns a copy of the set

func (*IntSet) Has

func (s *IntSet) Has(x int) bool

Has reports whether the set contains the non-negative value x

func (*IntSet) Len

func (s *IntSet) Len() int

Len returns the number of elements in the set

func (*IntSet) Remove

func (s *IntSet) Remove(x int)

Remove the non-negative value x from the set.

func (*IntSet) String

func (s *IntSet) String() string

String returns the set as a string of the form "{1 2 3}"

func (*IntSet) Trim

func (s *IntSet) Trim()

Trim removes unusued memory

func (*IntSet) UnionWith

func (s *IntSet) UnionWith(t *IntSet)

UnionWith sets s to the union of s and t