Subject: Re: interval origami
To: pgsql-sql@lists.postgresql.org
References: <20181130175719.l7izv65wjwgkls35@alvherre.pgsql>
 <d05565aa-551d-fac3-ba88-8215c8cbe0d4@riseup.net>
 <6d32b24f-2d3e-df79-81d2-3b1abb8cc4b4@riseup.net>
From: Adam Jensen <hanzer@riseup.net>
Openpgp: preference=signencrypt
Autocrypt: addr=hanzer@riseup.net; keydata=
 xsFNBFITbtMBEADj0R/kXShGc0soC29c5WkR56N/nsQ/VgXExduZ3Agyu/5AintZDbcJ9pLO
 PsaYKJfchIa9Fv1lcLhaaGPyPBYTklU8axSDpDa2Y6Kc2Ezyjq6dDEdk3La2eWER8BDQHNP+
 MYZ8Qin+tllQwX/uufC4UBvZxxIOhp05gAryvFPcXoq1MXrj5PdeNvFKtAVRNSwPDg1sIm6A
 ijZRcB6NfeMb/Yc543Yf450ewZTuebnJTQu55ywK5mpZExWiAZEr6z1cnbTfqG3Do82CWhak
 w16F5r0Vx25ckz0St8N5igdZOi57hS+dQLpxkVW2a6KqTQ+vbIjwEp4Kxj88PjI6CgZ9y6el
 mY4vmkDKXbGSDUjswUDQYuO2IXPT9GcE7H2grh2E5tvxH2DpL3lw5YFg5FPw6Ku8m1xYeh41
 xZ+tLGoYs9Qg/PA2a7pDeWn8p227jJ9Q9MxAcA2KfXRA6qfMTc/gvYF3bsVYorV8XwNcoQWv
 WoYFz7gAhXvmkbad40c8fUr8cKP0aFnqlIvC0QBkhhRMocG/1PcahwIMepv+F2nNBOFeFmxr
 YvcYXzNWnG5S/QNJvc5jAvgNZMfYz7R7KJGLinjq7ED/5Ly/EaDFkDSwNAAxKkPabxfryhb3
 6w7b509xa8EXRAi7reG04jFI+54PKMT5/FNrw9dhGnlJGU0KBQARAQABzR9BZGFtIEplbnNl
 biA8aGFuemVyQHJpc2V1cC5uZXQ+wsF3BBMBCgAhBQJSE27TAhsDBQsJCAcDBRUKCQgLBRYC
 AwEAAh4BAheAAAoJEGUApdpiqr3gNiAQAJ+lnXCQZZSsOYTxwXBlrVN5pepI8V+fd4ZZ3gn/
 wt7dpP2Ak4FQNDch8XvahhS/guKvosZjSayqynPF2eXcR8sXNV2uMwKpqas139PM/956FqYv
 XdN/GOGVHxR9KanafzJwMJj5f6+BrhPp1GVRwQYyUhdlmnZJhHMt+lRLu1h27m7E/IAngYia
 RJ6a3m6XJQFkRMz8mjSNV0AZBlNNvpycEJoS8RbMoynR5LIjdWlJye25ufox1pjY/XVhw3hF
 2HxRKAakO+q6Zc6v0MVmjDiIq+QxCqGdCoj0SACEmgOmI+SZl6rmenrSX0M/cktpNX9wyBYN
 CtxIdA6Zex+mOMmgo9g7T2n4xcqX83aIQKkuBJFfUj5yPBEWkjFvuYvtXbHogY3maFNYe+pm
 ZE6EZpBRZ8PCN17NLgxyh58yeJEx3oS1LDfqRz5SrFxfdN7bgExN3HKJJg7Jt32Oaml/8jSI
 BuxcEYimaP6MBkhrBHmd+TW3TUVGyQosqHGllQttXD92dm7wcaZnH0MNmroGG3+Czus2EgUS
 igFP4BwgNB8TaD17S6NQN83FVahAgjyhtadLtTzya/YSPrrvSHsKc88gasqNzvpsa+ggQZFX
 KALI/dozac61D6+UuTcUOvZCo5V4mIgeBMcw7PY6Ccycz9fHKghiPTuFdO1QI4KtujcXzsFN
 BFITbtMBEACnKEB3eI8FFIU4c9oDEkSPrZCwOOIjkaz9HfPOcLslFLVijqhPt4CCk5HM05KR
 yIYrYTyWytZfX+j2vW4TqJzntPBC+7oNjAIZ1l4UH6q8UxDya9+OLCx6awJNLo+5xmZ3pU7K
 vaTkvMguQfO7VWUK+f5nKYr/+lnZkxH0wuuLWomceEOk8Kt6g9+pQOC6w8FX4tYrtSFoSLHB
 bU7U1U4eJ3Hhp2b6PzHtJPtGORZ9i7CRRlZHONDNMw0EPcBkb5N0zgdLveVEUTfZfulR0TRN
 2dBktBXArfoO3qZN4aKseLXU8XRQUG5xJNwf8vY+8fzKvgeh3BUgz2USYofRcTKEmkurvoA+
 rKBMmGnW9s9pn8jlDLIB+V651YiJ+ip5HZL17pVI0zNDjKvqLw9EWGDaFh6WnIT+GTGKQBtu
 yzEZCKrPUkDxuqhZBRDw2ODdP37ccF9TippHW1e55oK3Wjgwon8DH7cJixzTXKIegTio459Y
 YE763IEXHjozhjZVYknaoysz4NRYJdYZKLjxsb4Xjc2BWLciumnEltaWGRl7MUblPH4jkMpD
 4dOmYNpuhtUau8/UPpeHn8uaIHGlPGq4G+z5Wlaf6WVwLFOZRG8LuFMqhQ/8AeYjqDy3dB10
 ruMDNpkiou/qDIIE2dHgvySMYntgPuEmCALHZMhIDvYCUwARAQABwsFfBBgBCgAJBQJSE27T
 AhsMAAoJEGUApdpiqr3gSxgP/jQJ34l85dNgrLqKOEOS7dfZzQRLjk0KkCIeCY/LmRDzyxD2
 Gre5jtxFBuGNvcdaG5puC8rVpM0KW+MATqf8OjUhks71nz9aT+aKIga7oA/USl6QtErsdx7s
 g0BSz3kId481W3SUsvk7sXUcdRdri5SXZvfXhC9cL7UUKiPaL6zet/SMtIv0lSNGWHo44h3i
 IJVggPcwTW0p5eQGn8+dLTtJFBNfdpHv+pwgtBCBtMnYckfxkq+Mfk1vDhjVYQjtc03N6LbU
 zSALmELQeKdmjqhDZGniq651CveqMSaS6UKKbf2iIAMvBiyjl+jWGgUy9EMcNUJIxkAM8EWV
 Lv8MNu72oJhaAJpjSybiCeK2prK4ZTJF0h7ll81ftGVr1Cp/jRkw1Pof2bVQmlILHXkJLZJs
 unFsEcHpwnw52gZXc/zYjMGfyZy/ihP4Pyp+E7qlUKuLpkpEB43Ix5u8jmcOkMKhBnNo9OO1
 p6Uwbl5GBIL/LXDKynYB98oXaxCzYkaxOrUWIu1ySJqRNnzAFMSwMqrR6fVumascjtAlBTMM
 sC/nN9VGG1VY0onGGJ80Vt+Fbhmj+zDpn0J3DfL2xD91+RxJaLCn8Iy/C4TikwsipXjnSmzA
 d6y+BJO5+lPxTTlg0UomOGv4ChmcVUEfXxk2GsvHZzsTA4qhLaZDuy9vR4eZ
Message-ID: <80ea3708-11be-e7e3-9f49-011a682e3bf4@riseup.net>
Date: Fri, 30 Nov 2018 19:04:10 -0500
MIME-Version: 1.0
In-Reply-To: <6d32b24f-2d3e-df79-81d2-3b1abb8cc4b4@riseup.net>
Content-Type: text/plain; charset=utf-8
Content-Language: en-US
Content-Transfer-Encoding: 8bit
Precedence: bulk

On 11/30/18 4:02 PM, Adam Jensen wrote:
> On 11/30/18 3:19 PM, Adam Jensen wrote:
>> The 'numrange' type with the 'overlaps' and 'intersection' operators
>> seem to cover the fundamental computations in a very natural way.
> 
> Actually, those operators might not be entirely sufficient. Given two
> ranges like this:
> 
> 10.0|39.0|interesting
> 15.0|21.0|fail
> 
> Something like the negative or inverse of the intersection is needed:
> 
> 10.0|15.0|interesting
> 21.0|39.0|interesting

I've mapped out nine time segment overlap scenarios:

1. good(10, 40) | bad(05, 15) -> good(15, 40)
2. good(10, 40) | bad(10, 15) -> good(15, 40)
3. good(10, 40) | bad(20, 30) -> good(10, 20), good(30, 40)
4. good(10, 40) | bad(20, 40) -> good(10, 20)
5. good(10, 40) | bad(20, 45) -> good(10, 20)
6. good(10, 40) | bad(05, 40) -> good()
7. good(10, 40) | bad(05, 45) -> good()
8. good(10, 40) | bad(10, 40) -> good()
9. good(10, 40) | bad(10, 45) -> good()

Letting gs/gf and bs/bf represent "good start-time"/"good finish-time"
and so on, pseudo-code to remove the bad segments looks like this:

find overlap: good(gs, gf) | bad(bs, bf)

CASE
	WHEN ((bs <= gs) AND (bf <  gf)) THEN  # 1 & 2
		-> (bf, gf)
	WHEN ((bs >  gs) AND (bf <  gf)) THEN  # 3
		-> (gs, bs), (bf, gf)
	WHEN ((bs >  gs) AND (bf >= gf)) THEN  # 4 &
		-> (gs, bs)
	WHEN ((bs <= gs) AND (bf >= gf)) THEN  # 6 & 7 & 8 & 9
		-> ()
END CASE;

And my first attempt at writing a PostgreSQL function looks like this:

CREATE FUNCTION find_overlap(gs REAL, gf REAL, bs REAL, bf REAL)
	RETURNS TABLE (start REAL, stop REAL) AS $$
	BEGIN
		CASE
			WHEN ((bs <= gs) AND (bf <  gf)) THEN
				RETURN NEXT (bf, gf);
				RETURN;
			WHEN ((bs >  gs) AND (bf <  gf)) THEN
				RETURN NEXT (gs, bs);
				RETURN NEXT (bf, gf);
				RETURN;
			WHEN ((bs >  gs) AND (bf >= gf)) THEN
				RETURN NEXT (gs, bs);
				RETURN;
			WHEN ((bs <= gs) AND (bf >= gf)) THEN
				RETURN;
		END CASE;
	END; $$
LANGUAGE plpgsql;

It results in:

ERROR:  RETURN NEXT cannot have a parameter in function with OUT parameters
LINE 6: RETURN NEXT (bf, gf);

Page 83 of the book "PostgreSQL Server Programming" mentions this
situation but doesn't actually describe or explain anything; nor does it
present a working example...

Any ideas?