Set: Difference between revisions

Line 5,400:

=={{header|Phix}}==

First, a simple implementaion using native sequences:

<lang Phix>~~sequence set1 = {1,2,3},~~

with javascript_semantics

set2 = {3,4,5}

function is_element(object x, sequence set)

return find(x,set)!=0

function element(object x, sequence set)

end function

return find(x,set)!=0

end function

function set_union(sequence set1, set2)

for i=1 to length(set2) do

function union(sequence set1, sequence set2)

if not is_element(set2[i],set1) then

for i=1 to length(set2) do

set1 = append(set1,set2[i])

if not element(set2[i],set1) then

end if

set1 = append(set1,set2[i])

end for

end if

return set1

end for

end function

return set1

end function

function set_intersection(sequence set1, set2)

sequence res = {}

function intersection(sequence set1, sequence set2)

for i=1 to length(set1) do

sequence res = {}

if is_element(set1[i],set2) then

for i=1 to length(set1) do

res = append(res,set1[i])

if element(set1[i],set2) then

end if

res = append(res,set1[i])

end for

end if

return res

end for

end function

return res

end function

function set_difference(sequence set1, set2)

sequence res = {}

function difference(sequence set1, sequence set2)

for i=1 to length(set1) do

sequence res = {}

if not is_element(set1[i],set2) then

for i=1 to length(set1) do

res = append(res,set1[i])

if not element(set1[i],set2) then

end if

res = append(res,set1[i])

end for

end if

return res

end for

end function

return res

end function

function set_subset(sequence set1, set2)

for i=1 to length(set1) do

function subset(sequence set1, sequence set2)

if not is_element(set1[i],set2) then

for i=1 to length(set1) do

return false

if not element(set1[i],set2) then

end if

return false

end for

end if

return true

end for

end function

return true

end function

function set_equality(sequence set1, set2)

if length(set1)!=length(set2) then

function equality(sequence set1, sequence set2)

return false

if length(set1)!=length(set2) then

end if

return false

return set_subset(set1,set2)

end if

end function

return subset(set1,set2)

end function

--test code:

?is_element(3,{1,2,3}) -- 1

--test code:

?is_element(4,{1,2,3}) -- 0

?element(3,set1) -- 1

?set_union({1,2,3},{3,4,5}) -- {1,2,3,4,5}

?element(4,set1) -- 0

?set_intersection({1,2,3},{3,4,5}) -- {3}

?union(set1,set2) -- {1,2,3,4,5}

?set_difference({1,2,3},{3,4,5}) -- {1,2}

?intersection(set1,set2) -- {3}

?set_subset({1,2,3},{3,4,5}) -- 0

?difference(set1,set2) -- {1,2}

?set_subset({1,2},{1,2,3}) -- 1

?subset(set1,set2) -- 0

?set_equality({1,2,3},{3,4,5}) -- 0

?subset({1,2},set1) -- 1

?set_equality({1,2,3},{3,1,2}) -- 1

?equality(set1,set2) -- 0

~~?equality(set1,{3,1,2})~~ -- 1</lang>

Note that you get true/false instead of 1/0 under pwa/p2js - use printf(1,"%t\n",...) in place of ? to get an exact match.

<pre>

1

Line 5,476:

Line 5,477:

Alternative using dictionaries, which needs several additional visitor routines (at a pinch they could be merged),

but performance is better on larger sets:

<lang Phix>~~integer set1 = new_dict~~(),

with javascript_semantics

set2 = new_dict()

function create_set(sequence s={})

setd(3,0,set1)

integer res = new_dict()

setd(1,0,set1)

for i=1 to length(s) do

setd(2,0,set1)

setd(s[i],0,res)

setd(5,0,set2)

end for

setd(3,0,set2)

return res

setd(4,0,set2)

end function

function element(object x, integer set)

function element(object x, integer set)

return getd_index(x,set)!=0

return getd_index(x,set)!=0

end function

end function

function u_visitor(object key, object data, object user_data)

function u_visitor(object key, object data, object user_data)

integer {union_set,set2} = user_data

integer {union_set,set2} = user_data

if set2=0

if set2=0

or not element(key,union_set) then

or not element(key,union_set) then

setd(key,data,union_set)

setd(key,data,union_set)

end if

end if

return 1

return 1

end function

end function

function union(integer set1, integer set2)

function set_union(integer set1, integer set2)

integer union_set = new_dict()

integer union_set = new_dict()

traverse_dict(routine_id("u_visitor"),{union_set,0},set1)

traverse_dict(u_visitor,{union_set,0},set1)

traverse_dict(routine_id("u_visitor"),{union_set,set2},set2)

traverse_dict(u_visitor,{union_set,set2},set2)

return union_set

return union_set

end function

end function

function i_visitor(object key, object data, object user_data)

function i_visitor(object key, object data, object user_data)

integer {union_set,set2} = user_data

integer {inter_sect,set2} = user_data

if element(key,set2) then

if element(key,set2) then

setd(key,data,union_set)

setd(key,data,inter_sect)

end if

end if

return 1

return 1

end function

end function

function intersection(integer set1, integer set2)

function set_intersection(integer set1, integer set2)

integer union_set = new_dict()

integer inter_sect = new_dict()

traverse_dict(routine_id("i_visitor"),{union_set,set2},set1)

traverse_dict(i_visitor,{inter_sect,set2},set1)

return union_set

return inter_sect

end function

end function

function d_visitor(object key, object data, object user_data)

function d_visitor(object key, object data, object user_data)

integer {union_set,set2} = user_data

integer {diff_set,set2} = user_data

if not element(key,set2) then

if not element(key,set2) then

setd(key,data,union_set)

setd(key,data,diff_set)

end if

end if

return 1

return 1

end function

end function

function difference(integer set1, integer set2)

function set_difference(integer set1, integer set2)

integer union_set = new_dict()

integer diff_set = new_dict()

traverse_dict(routine_id("d_visitor"),{union_set,set2},set1)

traverse_dict(d_visitor,{diff_set,set2},set1)

return union_set

return diff_set

end function

end function

integer res

bool subset_res

function s_visitor(object key, object data, object user_data)

function s_visitor(object key, object data, object user_data)

integer set2 = user_data

integer set2 = user_data

if not element(key,set2) then

if not element(key,set2) then

res = 0

subset_res = false

return 0 -- cease traversal

return 0 -- cease traversal

end if

end if

return 1

return 1

end function

end function

function subset(integer set1, integer set2)

function subset(integer set1, integer set2)

res = 1

subset_res = true

traverse_dict(routine_id("s_visitor"),set2,set1)

traverse_dict(s_visitor,set2,set1)

return res

return subset_res

end function

end function

function equality(integer set1, integer set2)

function equality(integer set1, integer set2)

if dict_size(set1)!=dict_size(set2) then

if dict_size(set1)!=dict_size(set2) then

return false

return false

end if

end if

return subset(set1,set2)

return subset(set1,set2)

end function

end function

include builtins/map.e -- for keys()

include builtins/map.e -- for keys()

-- matching test code:

-- matching test code:

?element(3,set1) -- 1

integer set1 = create_set({3,1,2}),

?element(4,set1) -- 0

set2 = create_set({5,3,4}),

?keys(union(set1,set2)) -- {1,2,3,4,5}

set3 = create_set({2,1})

?keys(intersection(set1,set2)) -- {3}

?keys(difference(set1,set2)) -- {1,2}

?element(3,set1) -- 1

?subset(set1,set2) -- 0

?element(4,set1) -- 0

integer set3 = new_dict()

?keys(set_union(set1,set2)) -- {1,2,3,4,5}

setd(2,0,set3)

?keys(set_intersection(set1,set2)) -- {3}

setd(1,0,set3)

?keys(set_difference(set1,set2)) -- {1,2}

?subset(set3,set1) -- 1

?subset(set1,set2) -- 0

?equality(set1,set2) -- 0

?subset(set3,set1) -- 1

setd(3,0,set3)

?equality(set1,set2) -- 0

?equality(set1,set3) -- 1</lang>

setd(3,0,set3)

same output as above

?equality(set1,set3) -- 1

Same output as above. I have written a builtins/sets.e, and tried another approach with builtins/sets2.e, but neither really hit the spot.

=={{header|PicoLisp}}==