module namespace set-impl = "http://fxsl.sf.net/data/set/implementation";
import module namespace tree = "http://fxsl.sf.net/data/bintree"
at "../../BinaryTree/bintreeModule.xquery";
(:
Create an empty set -- ∅ (0x2205)
:)
declare function set-impl:set()
as function() as item()*
{
function() {tree:tree()} (: underlying bintree :)
};
declare function set-impl:empty($pSet as function() as item()*)
as xs:boolean
{
tree:empty($pSet[1]())
};
declare function set-impl:size($pSet as function() as item()*)
as xs:integer
{
tree:size($pSet[1]())
};
declare function set-impl:equals
($pSet1 as function() as item()*,
$pSet2 as function() as item()*
)
as xs:boolean
{
set-impl:size($pSet1) eq set-impl:size($pSet1)
and
deep-equal(set-impl:data($pSet1), set-impl:data($pSet2))
};
declare function set-impl:add
($pSet as function() as item()*,
$pItem as item()
)
as function() as item()*
{
function() {tree:insert($pSet[1](), $pItem)}
};
declare function set-impl:data($pSet as function() as item()*)
as item()*
{
tree:data($pSet[1]())
};
(:
The Set Theory belongs to (member of) ∈ (0x22F2)
operation
:)
declare function set-impl:member
($pItem as item()?,
$pSet as function() as item()*
)
as xs:boolean
{
tree:contains($pSet[1](), $pItem)
};
(:
The Set Theory does not belong to (not member of)∉ (0x2209)
operation
:)
declare function set-impl:not-member
($pItem as item()?,
$pSet as function() as item()*
)
as xs:boolean
{
not(set-impl:member($pItem, $pSet))
};
declare function set-impl:remove
($pSet as function() as item()*,
$pItem as item()
)
as function() as item()*
{
function() {tree:deleteNode($pSet[1](), $pItem)}
};
(:
The classic set-theory U operation -- union of two sets
:)
declare function set-impl:U
($pSet1 as function() as item()*,
$pSet2 as function() as item()*
)
as function() as item()*
{
let $vBiggerSet :=
if(set-impl:size($pSet1) ge set-impl:size($pSet2))
then $pSet1
else $pSet2,
$vSmallerSet :=
if(not(set-impl:size($pSet1) ge set-impl:size($pSet2)))
then $pSet1
else $pSet2
return
fold-left(set-impl:add#2, $vBiggerSet, set-impl:data($vSmallerSet))
};
(:
The classic set-theory set-difference operation \
:)
declare function set-impl:diff
($pSet1 as function() as item()*,
$pSet2 as function() as item()*
)
as function() as item()*
{
fold-left(set-impl:remove#2, $pSet1, set-impl:data($pSet2))
};
(:
The classic set-theory ∩ (∩) /\
set-intersection operation
:)
declare function set-impl:intersect
($pSet1 as function() as item()*,
$pSet2 as function() as item()*
)
as function() as item()*
{
let $vBiggerSet :=
if(set-impl:size($pSet1) ge set-impl:size($pSet2))
then $pSet1
else $pSet2,
$vSmallerSet :=
if(not(set-impl:size($pSet1) ge set-impl:size($pSet2)))
then $pSet1
else $pSet2,
$to-be-removed :=
filter(set-impl:not-member(?, $vBiggerSet),
set-impl:data($vSmallerSet)
)
return
fold-left(set-impl:remove#2, $vSmallerSet, $to-be-removed)
};
(:
(:
The classic set-theory ∩ (∩) /\
set-intersection operation
:)
declare function set-impl:intersect
($pSet1 as function() as item()*,
$pSet2 as function() as item()*
)
as function() as item()*
{
set-impl:diff($pSet1,set-impl:diff($pSet1, $pSet2))
};
:)
(:
The classic set-theory symmetric-difference operation
:)
declare function set-impl:sym-diff
($pSet1 as function() as item()*,
$pSet2 as function() as item()*
)
as function() as item()*
{
set-impl:U(set-impl:diff($pSet1, $pSet2), set-impl:diff($pSet2, $pSet1))
};
(:
The classic set-theory set ⊇ ('⊇') operation
:)
declare function set-impl:includes
($pSet1 as function() as item()*,
$pSet2 as function() as item()*
)
as xs:boolean
{
empty(set-impl:data($pSet2)[set-impl:not-member(.,$pSet1)])
};
declare function set-impl:print
($pSet as function() as item()*)
as element()?
{
tree:print($pSet[1]())
};
declare function set-impl:serialize
($pSet as function() as item()*)
as element()?
{
set-impl:print($pSet)
};
declare function set-impl:deserialize
($pSerialization as element()?)
as function() as item()*
{
function() {tree:deserialize($pSerialization)}
};