Re: Set operations

[Phil Pennock <zsh-workers+phil.pennock@xxxxxxxxxxxx>]

On 2008-09-27 at 21:48 +0100, Peter Stephenson wrote:
> I appreciate there's a problem here, but I'm a little bit lost as to
> what exactly you're after.  Do you mean you'd like the "|" in the (j,|,)
> to be treated as a pattern character, but the characters substituted
> from the paramater named by b not to be expanded?

What I was after wasn't anywhere near as good as what you provided.

I was thinking that just as we have (q) to apply shell quoting, we
should have a flag to escape pattern characters, which would have
laboriously allowed me to do what you've just done much more easily by
avoiding the whole problem.  :)

Escape+join+parse_that vs only-parse-the-join

> If I'm not following, you may want white chococlate mousse followed by a
> cappuccino.

No, but my wife would love that.

> Anyway, I'm not sure why I didn't do this ages ago, it makes testing
> lists of alternatives vastly easier.

Oh good, that's two different uses for it which means it's definitely
more broadly helpful and it's not just me.  *phew*  Thanks.

Okay, the two attachments provide the resulting clean set operations,
with a stupid bug fixed and the intersection operations cleaned up, and
the Test file for these.

I'm not attached to any names, but I put the first file in
Functions/Misc/load_dataset and the test file depends upon that.  I just
named load_dataset "load_dataset-post-20080927.zsh" to remind anyone
using this that it uses your new (~) parameter expansion option.

I'm also not attached to this code, since messing with 'let' to have zsh
understand sets in arithmetic context is more appealing to me, every
time I think about it.  But the two approaches should be mutually
compatible and this is the one I opted for.

And I *just* realised that I needed set_equal, which sets $?, to provide
a clean way to test for equality, since not only are the sets not
maintained in sorted order, but the need to deal with arbitrary data
would lead to bugginess.  *sigh*  Arithmetic with no equality tests.
What was I thinking?  Done.

Do people think superset/subset/strict_superset/strict_subset would be
useful too?

-Phil

# provide functions for manipulating unique lists as sets.

function newset {
	setopt local_options no_ksh_arrays
	local name="$1"; shift
	typeset -gUa $name
	set -A $name "$@"
}

function copyset_tofrom {
	setopt local_options no_ksh_arrays
	local new="$1" old="$2"
	typeset -gUa $new
	set -A $new "${(P@)old}"
}
function copyset_fromto { copyset_tofrom "$2" "$1" }

function set_add_new {
	setopt local_options no_ksh_arrays
	local new="$1" a="$2" b="$3"
	typeset -gUa $new
	set -A $new "${(P@)a}" "${(P@)b}"
}

function set_add_in {
	setopt local_options no_ksh_arrays
	local name="$1" b="$2"
	set -A $name "${(P@)name}" "${(P@)b}"
}

function set_add_print {
	setopt local_options no_ksh_arrays
	local a="$1" b="$2"
	typeset -Ua tmp
	tmp=("${(P@)a}" "${(P@)b}")
	print -r -- ${(q)tmp}
}

function set_subtract_new {
	setopt local_options no_ksh_arrays
	local new="$1" a="$2" b="$3"
	typeset -gUa $new
	set -A $new "${(P@)a:#${(P~j,|,)b}}"
}

function set_subtract_in {
	setopt local_options no_ksh_arrays
	local name="$1" b="$2"
	set -A $name "${(P@)name:#${(P~j,|,)b}}"
}

function set_subtract_print {
	setopt local_options no_ksh_arrays
	local a="$1" b="$2"
	typeset -Ua tmp
	tmp=("${(P@)a:#${(P~j,|,)b}}")
	print -r -- ${(q)tmp}
}

function set_intersection_new {
	setopt local_options no_ksh_arrays
	local new="$1" a="$2" b="$3"
	typeset -gUa $new
	set -A $new "${(@PM)a:#${(P~j,|,)b}}"
}

function set_intersection_in {
	setopt local_options no_ksh_arrays
	local name="$1" b="$2"
	set -A $name "${(@PM)name:#${(P~j,|,)b}}"
}

function set_intersection_print {
	setopt local_options no_ksh_arrays
	local a="$1" b="$2"
	typeset -Ua tmp
	tmp=("${(@PM)a:#${(P~j,|,)b}}")
	print -r -- ${(q)tmp}
}

function set_union_new { set_add_new "$@" }
function set_union_in { set_add_in "$@" }
function set_union_print { set_add_print "$@" }

function set_difference_new { set_subtract_new "$@" }
function set_difference_in { set_subtract_in "$@" }
function set_difference_print { set_subtract_print "$@" }

function set_symmetric_difference_new {
	setopt local_options no_ksh_arrays
	local new="$1" a="$2" b="$3"
	typeset -gUa $new
	set -A $new "${(P@)a:#${(P~j,|,)b}}" "${(P@)b:#${(P~j,|,)a}}"
}

function set_symmetric_difference_in {
	setopt local_options no_ksh_arrays
	local name="$1" b="$2"
	set -A $name "${(P@)name:#${(P~j,|,)b}}" "${(P@)b:#${(P~j,|,)name}}"
}

function set_symmetric_difference_print {
	setopt local_options no_ksh_arrays
	local a="$1" b="$2"
	typeset -Ua tmp
	tmp=("${(P@)a:#${(P~j,|,)b}}" "${(P@)b:#${(P~j,|,)a}}")
	print -r -- ${(q)tmp}
}

function set_insert_list {
	setopt local_options no_ksh_arrays
	local name="$1"; shift
	set -A $name "${(P@)name}" "$@"
}

function set_remove_list {
	setopt local_options no_ksh_arrays
	local name="$1"; shift
	set -A $name "${(P@)name:#${(~j,|,)@}}"
}

function set_equal {
	setopt local_options no_ksh_arrays
	local a="$1" b="$2"
	[[ "${${(P@oq)a}}" == "${${(P@oq)b}}" ]]
}

# Is there a way to print the variable, in the style of "typeset -p",
# but showing the -U unique-flag?

%prep
 fpath=(../Functions/Misc)
 autoload load_dataset
 load_dataset

%test
 newset x a b c d
 newset y c d e f
 copyset_tofrom z x
 print -l "$x" "$y" "$z"
0:Testing basic set creation
>a b c d
>c d e f
>a b c d

 set_add_print x y
 set_add_in z y
 print $z
 set_add_new z x y
 print $z
0:Testing set addition (union)
>a b c d e f
>a b c d e f
>a b c d e f

 set_subtract_new z x y
 print $z
 copyset_fromto x z
 set_subtract_in z y
 print $z
 set_subtract_print x y
 set_subtract_print y x
0:Testing set subtraction (asymmetric difference)
>a b
>a b
>a b
>e f

 set_intersection_new z x y
 print $z
 copyset_tofrom z x
 set_intersection_in z y
 print $z
 set_intersection_print x y
0:Testing set intersection
>c d
>c d
>c d

 set_symmetric_difference_new z x y
 print $z
 copyset_tofrom z x
 set_symmetric_difference_in z y
 print $z
 set_symmetric_difference_print x y
 set_symmetric_difference_print y x
0:Testing set symmetric difference
>a b e f
>a b e f
>a b e f
>e f a b

 set_insert_list y 'a|b' '*'
 set_remove_list x d
 print -l "$x" "$y"
0:Testing basic set item addition and removal
>a b c
>c d e f a|b *

 set_intersection_print x y
 set_symmetric_difference_print x y
 set_union_print x y
 set_difference_print x y
 set_difference_print y x
0:Testing set resilience to meta characters
>c
>a b d e f a\|b \*
>a b c d e f a\|b \*
>a b
>d e f a\|b \*

 newset z b c a
 set_equal x z
0:Testing set equality

 newset z a 'b c'
 set_equal x z
1:Testing set inequality