1package Set::Tiny; 2 3use 5.004; 4use strict; 5 6require Exporter; 7@Set::Tiny::ISA = qw(Exporter); 8@Set::Tiny::EXPORT_OK = qw(set); 9 10$Set::Tiny::VERSION = '0.04'; 11 12sub new { 13 my $class = shift; 14 my %self; 15 @self{@_} = (); 16 return bless \%self, $class; 17} 18 19sub set { 20 if (ref($_[0]) eq "Set::Tiny") { 21 return $_[0]->clone(); 22 } 23 elsif (ref($_[0]) eq 'ARRAY') { 24 return Set::Tiny->new(@{$_[0]}); 25 } 26 else { 27 return Set::Tiny->new(@_); 28 } 29} 30 31sub as_string { "(" . join(" ", sort keys %{$_[0]}) . ")" } 32 33sub size { scalar keys %{$_[0]} } 34 35sub element { exists $_[0]->{$_[1]} ? $_[1] : () } 36 37sub elements { keys %{$_[0]} } 38 39sub contains { 40 my $self = shift; 41 exists $self->{$_} or return for @_; 42 return 1; 43} 44 45sub clone { 46 my $class = ref $_[0]; 47 return $class->new( keys %{$_[0]} ); 48} 49 50sub clear { 51 %{$_[0]} = (); 52 return $_[0]; 53} 54 55sub insert { 56 my $self = shift; 57 @{$self}{@_} = (); 58 return $self; 59} 60 61sub remove { 62 my $self = shift; 63 delete @{$self}{@_}; 64 return $self; 65} 66 67sub invert { 68 my $self = shift; 69 exists $self->{$_} ? delete $self->{$_} : ($self->{$_} = undef) for @_; 70 return $self; 71} 72 73sub is_null { ! %{$_[0]} } 74 75sub is_subset { $_[1]->contains( keys %{$_[0]} ) } 76 77sub is_proper_subset { $_[0]->size < $_[1]->size && $_[0]->is_subset($_[1]) } 78 79sub is_superset { $_[1]->is_subset($_[0]) } 80 81sub is_proper_superset { $_[0]->size > $_[1]->size && $_[1]->is_subset($_[0]) } 82 83sub is_equal { $_[1]->is_subset($_[0]) && $_[0]->is_subset($_[1]) } 84 85sub is_disjoint { ! $_[0]->intersection($_[1])->size } 86 87sub is_properly_intersecting { 88 ! $_[0]->is_disjoint($_[1]) 89 && $_[0]->difference($_[1])->size 90 && $_[1]->difference($_[0])->size 91} 92 93sub difference { $_[0]->clone->remove(keys %{$_[1]}) } 94 95sub union { 96 my $class = ref $_[0]; 97 return $class->new( keys %{$_[0]}, keys %{$_[1]} ); 98} 99 100sub intersection { 101 my $class = ref $_[0]; 102 return $class->new( grep { exists($_[0]->{$_}) } keys %{$_[1]} ); 103} 104 105sub intersection2 { 106 my $class = ref $_[0]; 107 my ($a, $b) = $_[0]->size > $_[1]->size ? ($_[0], $_[1]) : ($_[1], $_[0]); 108 return $class->new( grep { exists($a->{$_}) } keys %{$b} ); 109} 110 111sub symmetric_difference { $_[0]->clone->invert(keys %{$_[1]}) } 112 113{ 114 *copy = \&clone; 115 *has = \&contains; 116 *member = \&element; 117 *members = \&elements; 118 *delete = \&remove; 119 *is_empty = \&is_null; 120 *unique = \&symmetric_difference; 121} 122 1231; 124 125__END__ 126 127=head1 NAME 128 129Set::Tiny - Simple sets of strings 130 131=head1 VERSION 132 133Version 0.04 134 135=head1 SYNOPSIS 136 137 use Set::Tiny; 138 139 my $s1 = Set::Tiny->new(qw( a b c )); 140 my $s2 = Set::Tiny->new(qw( b c d )); 141 142 my $u = $s1->union($s2); 143 my $i = $s1->intersection($s2); 144 my $s = $s1->symmetric_difference($s2); 145 146 print $u->as_string; # (a b c d) 147 print $i->as_string; # (b c) 148 print $s->as_string; # (a d) 149 150 print "i is a subset of s1" if $i->is_subset($s1); 151 print "u is a superset of s1" if $u->is_superset($s1); 152 153 # or using the shorter initializer: 154 155 use Set::Tiny qw( set ); 156 157 my $s1 = set(qw( a b c )); 158 my $s2 = set([1, 2, 3]); 159 160=head1 DESCRIPTION 161 162Set::Tiny is a thin wrapper around regular Perl hashes to perform often needed 163set operations, such as testing two sets of strings for equality, or checking 164whether one is contained within the other. 165 166For a more complete implementation of mathematical set theory, see 167L<Set::Scalar>. For sets of arbitrary objects, see L<Set::Object>. 168 169=head2 Why Set::Tiny? 170 171=over 172 173=item Convenience 174 175Set::Tiny aims to provide a convenient interface to commonly used set 176operations, which you would usually implement using regular hashes and a couple 177of C<for> loops (in fact, that's exactly what Set::Tiny does). 178 179=item Speed 180 181The price in performance you pay for this convenience when using a 182full-featured set implementation like L<Set::Scalar> is way too high if you 183don't actually need the advanced functionality it offers. 184Run F<examples/benchmark.pl> for a (non-representative) comparison 185between different C<Set::> modules. 186 187=item Ease of use 188 189L<Set::Object> offers better performance than L<Set::Scalar>, but needs a C 190compiler to install. Set::Tiny has no dependencies and contains no C code. 191 192=back 193 194=head1 EXPORTABLE FUNCTIONS 195 196=head2 set( [I<list or arrayref>] ) 197 198If you request it, Set::Tiny can export a function C<set()>, which lets you 199create a Set::Tiny instance in a more compact form. 200 201Unlike the constructor, this function also accepts the set elements as an array 202reference. 203 204If you pass an existing Set::Tiny to the initializer, it creates a clone of the set 205and returns that. 206 207=head1 METHODS 208 209Note that all methods that expect a I<list> of set elements stringify 210their arguments before inserting them into the set. 211 212=head2 new( [I<list>] ) 213 214Class method. Returns a new Set::Tiny object, initialized with the strings in 215I<list>, or the empty set if I<list> is empty. 216 217=head2 clone 218 219=head2 copy 220 221Returns a new set with the same elements as this one. 222 223=head2 insert( [I<list>] ) 224 225Inserts the elements in I<list> into the set. 226 227=head2 delete( [I<list>] ) 228 229=head2 remove( [I<list>] ) 230 231Removes the elements in I<list> from the set. Elements that are not 232members of the set are ignored. 233 234=head2 invert( [I<list>] ) 235 236For each element in I<list>, if it is already a member of the set, 237deletes it from the set, else insert it into the set. 238 239=head2 clear 240 241Removes all elements from the set. 242 243=head2 as_string 244 245Returns a string representation of the set. 246 247=head2 elements 248 249=head2 members 250 251Returns the (unordered) list of elements. 252 253=head2 size 254 255Returns the number of elements. 256 257=head2 has( [I<list>] ) 258 259=head2 contains( [I<list>] ) 260 261Returns true if B<all> of the elements in I<list> are members of the set. If 262I<list> is empty, returns true. 263 264=head2 element( [I<string>] ) 265 266=head2 member( [I<string>] ) 267 268Returns the string if it is contained in the set. 269 270=head2 is_null 271 272=head2 is_empty 273 274Returns true if the set is the empty set. 275 276=head2 union( I<set> ) 277 278Returns a new set containing both the elements of this set and I<set>. 279 280=head2 intersection( I<set> ) 281 282Returns a new set containing the elements that are present in both this 283set and I<set>. 284 285=head2 intersection2( I<set> ) 286 287Like C<intersection()>, but orders the sets by size before comparing their 288elements. This results in a small overhead for small, evenly sized sets, but 289a large speedup when comparing bigger (~ 100 elements) and very unevenly 290sized sets. 291 292=head2 difference( I<set> ) 293 294Returns a new set containing the elements of this set with the elements 295of I<set> removed. 296 297=head2 unique( I<set> ) 298 299=head2 symmetric_difference( I<set> ) 300 301Returns a new set containing the elements that are present in either this set 302or I<set>, but not in both. 303 304=head2 is_equal( I<set> ) 305 306Returns true if this set contains the same elements as I<set>. 307 308=head2 is_disjoint( I<set> ) 309 310Returns true if this set has no elements in common with I<set>. Note that the 311empty set is disjoint to any other set. 312 313=head2 is_properly_intersecting( I<set> ) 314 315Returns true if this set has elements in common with I<set>, but both 316also contain elements that they have not in common with each other. 317 318=head2 is_proper_subset( I<set> ) 319 320Returns true if this set is a proper subset of I<set>. 321 322=head2 is_proper_superset( I<set> ) 323 324Returns true if this set is a proper superset of I<set>. 325 326=head2 is_subset( I<set> ) 327 328Returns true if this set is a subset of I<set>. 329 330=head2 is_superset( I<set> ) 331 332Returns true if this set is a superset of I<set>. 333 334=head1 AUTHOR 335 336Stanis Trendelenburg, C<< <trendels at cpan.org> >> 337 338=head1 CREDITS 339 340Thanks to Adam Kennedy for advice on how to make this module C<Tiny>. 341 342=head1 BUGS 343 344Please report any bugs or feature requests to C<bug-set-tiny at rt.cpan.org>, or through 345the web interface at L<http://rt.cpan.org/NoAuth/ReportBug.html?Queue=Set-Tiny>. I will be notified, and then you'll 346automatically be notified of progress on your bug as I make changes. 347 348=head1 COPYRIGHT & LICENSE 349 350Copyright 2009 Stanis Trendelenburg, all rights reserved. 351 352This program is free software; you can redistribute it and/or modify it 353under the same terms as Perl itself. 354 355=head1 SEE ALSO 356 357L<Set::Scalar>, L<Set::Object> 358