# Datatypes R2 Issue 85

## Contents

# Data Types Issue 85: QSET (GTS) Enhance Detail

## Introduction

Proposal Datatypes_R2_Issue_83 introduced the QSET interface:

QSET<T specializes QTY> specializes SET<T> { QSET<T> union(SET<T> otherset); QSET<T> except(T element); QSET<T> except(SET<T> otherset); QSET<T> intersection(SET<T> otherset); IVL<T> hull; IVL<T> nextTo(T element); IVL<T> nextAfter(T element); QSET<T> periodicHull(SET<T> otherset); BL interleaves(SET<T> otherset); };

With this we can assert:

- IVL<T> specializes QSET<T>
- PIVL<T> specializes QSET<T>
- EIVL<T specializes TS> specializes QSET<T>

And finally GTS is defined equivalent to SET<TS>.

This is all nice and fine. We also specify the literal form perfectly with all semantics, where the semantics of combinations of IVL and PIVL etc. is created using the union, intersection and other operations of SET. While this is all sufficient for the abstract data type definition, it leaves the reader without a clue just how to implement this. As I implemented this for Java SIG I came up with the obvious solution which could perhaps be mentioned somehow to clarify this question to other implementers.

## Issue

What is not obvious to many is that an implementation of QSET can not be done by enumeration of elements, nor even by enumeration of all consecutive intervals. Instead, a general QSET is a term which can be used to generate specific intervals when sufficient data is provided. In effect, the following 3 methods

IVL<T> hull(); IVL<T> nextTo(T element); IVL<T> nextAfter(T element);

are the once that reduce the complex QSET term to simpler intervals. They are a reflection of the QSET by a (partial) enumeration of the QSET's extension in terms of greatest consecutive subsets (intervals). But QSET itself is intensionally defined as a term:

QSET<T> union(SET<T> otherset); QSET<T> except(T element); QSET<T> except(SET<T> otherset); QSET<T> intersection(SET<T> otherset);

all return QSETs. A term algrbra is usually defined using data structures that represent the terms. Naturally therefore one would define:

- QSETUnion<T> specializes QSET<T>
- QSETDifference<T> specializes QSET<T>
- QSETIntersection<T> specializes QSET<T>

In addition we added QSETSingulatity<T> specializes QSET<T>, but that is really just a DSET<T> (discrete set), so we don't need to add this QSETSingularity in the abstract specification.

QSETUnion, QSETDifference, and QSETIntersection can all be considered specializations of a common QSETTerms super-class. A QSETTerm is an abstract class defined as follows:

abstract type QSETTerm<T specializes QTY> specializes QSET<ANY>, LIST<QSET<T>>;

Each specialization of the QSETTerm implements the contains operation according to the meaning of the set.

invariant(QSETUnion<T> u, T x) { u.contains(x).equals(u.head().contains(x).or(u.tail().contains(x)); }

I don't think more guidance than this needs to be provided short of just writhing down the entire implementation of this in invariant expression language.

## Discussion

This proposal does not change any semantics, it does not seem to be required for the semantic specification, but it might make the GTS less enigmatic. Perhaps this should be mentioned in an section under QSET which would be introduced as not necessary for semantic definition but useful to further understanding and implementation.

It certainly avoids the mistake to use the XML representation as the source for implementation advice, which would be a bad idea. The sequence of QSET + operator is not a useful specification of the term.

For any more advanced implementation it will be critical to optimize certain operations, or rewrite, canonicalize the terms. That is perfectly fine, because the exact term structure is not relevant for equality of qsets.

## Links

Back to Data Types R2 issues