This is Info file pm.info, produced by Makeinfo version 1.68 from the input file bigpm.texi.  File: pm.info, Node: Set/Crontab, Next: Set/IntRange, Prev: Set/Bag, Up: Module List Expand crontab(5)-style integer lists ************************************* NAME ==== Set::Crontab - Expand crontab(5)-style integer lists SYNOPSIS ======== $s = Set::Crontab->new("1-9/3,>15,>30,!23", [0..30]); if ($s->contains(3)) { ... } DESCRIPTION =========== Set::Crontab parses crontab-style lists of integers and defines some utility functions to make it easier to deal with them. Syntax ------ Numbers, ranges, *, and step values all work exactly as described in `crontab(5)' in this node. A few extensions to the standard syntax are described below. < and > N does likewise for elements larger than N. ! !N excludes N from the set. It applies to the other specified range; otherwise it applies to the specified ranges (i.e. "!3" with a range of "1-10" corresponds to "1-2,4-10", but ">3,!7" in the same range means "4-6,8-10"). Functions --------- new($spec, [@range]) Creates a new Set::Crontab and returns a reference to it. contains($num) Returns true if $num exists in the set. list() Returns the expanded list corresponding to the set. The functions described above croak if they are called with incorrect arguments. SEE ALSO ======== `crontab(5)' in this node AUTHOR ====== Abhijit Menon-Sen Copyright 2001 Abhijit Menon-Sen. All Rights Reserved. This is free software; you may redistribute and/or modify it under the same terms as Perl itself.  File: pm.info, Node: Set/IntRange, Next: Set/IntSpan, Prev: Set/Crontab, Up: Module List Sets of Integers **************** NAME ==== Set::IntRange - Sets of Integers Easy manipulation of sets of integers (arbitrary intervals) SYNOPSIS ======== METHODS ------- Version $version = $Set::IntRange::VERSION; new $set = Set::IntRange->new($lower,$upper); $set = $any_set->new($lower,$upper); Resize $set->Resize($lower,$upper); Size ($lower,$upper) = $set->Size(); Empty $set->Empty(); Fill $set->Fill(); Flip $set->Flip(); Interval_Empty $set->Interval_Empty($lower,$upper); $set->Empty_Interval($lower,$upper); # (deprecated) Interval_Fill $set->Interval_Fill($lower,$upper); $set->Fill_Interval($lower,$upper); # (deprecated) Interval_Flip $set->Interval_Flip($lower,$upper); $set->Flip_Interval($lower,$upper); # (deprecated) Interval_Scan_inc while (($min,$max) = $set->Interval_Scan_inc($start)) Interval_Scan_dec while (($min,$max) = $set->Interval_Scan_dec($start)) Bit_Off $set->Bit_Off($index); $set->Delete($index); # (deprecated) Bit_On $set->Bit_On($index); $set->Insert($index); # (deprecated) bit_flip $bit = $set->bit_flip($index); if ($set->bit_flip($index)) $bit = $set->flip($index); # (deprecated) if ($set->flip($index)) # (deprecated) bit_test $bit = $set->bit_test($index); if ($set->bit_test($index)) $bit = $set->contains($index); if ($set->contains($index)) $bit = $set->in($index); # (deprecated) if ($set->in($index)) # (deprecated) Norm $norm = $set->Norm(); Min $min = $set->Min(); Max $max = $set->Max(); Union $set1->Union($set2,$set3); # in-place is possible! Intersection $set1->Intersection($set2,$set3); # in-place is possible! Difference $set1->Difference($set2,$set3); # in-place is possible! ExclusiveOr $set1->ExclusiveOr($set2,$set3); # in-place is possible! Complement $set1->Complement($set2); # in-place is possible! is_empty if ($set->is_empty()) is_full if ($set->is_full()) equal if ($set1->equal($set2)) subset if ($set1->subset($set2)) if ($set1->inclusion($set2)) # (deprecated) Lexicompare $cmp = $set1->Lexicompare($set2); # unsigned Compare $cmp = $set1->Compare($set2); # signed Copy $set1->Copy($set2); Shadow $other_set = $some_set->Shadow(); Clone $twin_set = $some_set->Clone(); to_Enum $string = $set->to_Enum(); # e.g., "-8..-5,-1..2,4,6..9" from_Enum eval { $set->from_Enum($string); }; to_Hex $string = $set->to_Hex(); # e.g., "0007AF1E" from_Hex eval { $set->from_Hex($string); }; BitVector $set->BitVector->any_Bit_Vector_method(); OVERLOADED OPERATORS -------------------- # "$index" is a number or a Perl scalar variable containing a # number which represents the set containing only that element: Emptyness if ($set) # if not empty if (! $set) # if empty unless ($set) # if empty Equality if ($set1 == $set2) if ($set1 != $set2) if ($set == $index) if ($set != $index) Lexical Comparison $cmp = $set1 cmp $set2; if ($set1 lt $set2) if ($set1 le $set2) if ($set1 gt $set2) if ($set1 ge $set2) if ($set1 eq $set2) if ($set1 ne $set2) $cmp = $set cmp $index; if ($set lt $index) if ($set le $index) if ($set gt $index) if ($set ge $index) if ($set eq $index) if ($set ne $index) String Conversion $string = "$set"; print "\$set = '$set'\n"; Union $set1 = $set2 + $set3; $set1 += $set2; $set1 = $set2 | $set3; $set1 |= $set2; $set1 = $set2 + $index; $set += $index; $set1 = $set2 | $index; $set |= $index; Intersection $set1 = $set2 * $set3; $set1 *= $set2; $set1 = $set2 & $set3; $set1 &= $set2; $set1 = $set2 * $index; $set *= $index; $set1 = $set2 & $index; $set &= $index; Difference $set1 = $set2 - $set3; $set1 -= $set2; $set1 = $set2 - $set1; $set1 = $set2 - $index; $set1 = $index - $set2; $set -= $index; ExclusiveOr $set1 = $set2 ^ $set3; $set1 ^= $set2; $set1 = $set2 ^ $index; $set ^= $index; Complement $set1 = -$set2; $set1 = ~$set2; $set = -$set; $set = ~$set; Subset Relationship if ($set1 <= $set2) True Subset Relationship if ($set1 < $set2) Superset Relationship if ($set1 >= $set2) True Superset Relationship if ($set1 > $set2) Norm $norm = abs($set); DESCRIPTION =========== This class lets you dynamically create sets of arbitrary intervals of integers and perform all the basic operations for sets on them (for a list of available methods and operators, see above). See `Bit::Vector(3)' in this node for more details! SEE ALSO ======== Bit::Vector(3), Set::IntegerFast(3), Math::MatrixBool(3), Math::MatrixReal(3), DFA::Kleene(3), Math::Kleene(3), Graph::Kruskal(3). VERSION ======= This man page documents "Set::IntRange" version 5.0. AUTHOR ====== Steffen Beyer . COPYRIGHT ========= Copyright (c) 1996, 1997 by Steffen Beyer. All rights reserved. LICENSE ======= This package is free software; you can redistribute it and/or modify it under the same terms as Perl itself.  File: pm.info, Node: Set/IntSpan, Next: Set/NestedGroups, Prev: Set/IntRange, Up: Module List Manages sets of integers ************************ NAME ==== Set::IntSpan - Manages sets of integers SYNOPSIS ======== use Set::IntSpan qw(grep_set map_set); $Set::IntSpan::Empty_String = $string; $set = new Set::IntSpan $set_spec; $valid = valid Set::IntSpan $run_list; $set = copy $set $set_spec; $run_list = run_list $set; @elements = elements $set; $u_set = union $set $set_spec; $i_set = intersect $set $set_spec; $x_set = xor $set $set_spec; $d_set = diff $set $set_spec; $c_set = complement $set; equal $set $set_spec; equivalent $set $set_spec; superset $set $set_spec; subset $set $set_spec; $n = cardinality $set; empty $set; finite $set; neg_inf $set; pos_inf $set; infinite $set; universal $set; member $set $n; insert $set $n; remove $set $n; $min = min $set; $max = max $set; $subset = grep_set { ... } $set; $mapset = map_set { ... } $set; for ($element=$set->first; defined $element; $element=$set->next) { ... } for ($element=$set->last ; defined $element; $element=$set->prev) { ... } $element = $set->start($n); $element = $set->current; REQUIRES ======== Perl 5.004, Exporter EXPORTS ======= `@EXPORT' --------- Nothing `@EXPORT_OK' ------------ `grep_set', `map_set' DESCRIPTION =========== `Set::IntSpan' manages sets of integers. It is optimized for sets that have long runs of consecutive integers. These arise, for example, in .newsrc files, which maintain lists of articles: alt.foo: 1-21,28,31 alt.bar: 1-14192,14194,14196-14221 Sets are stored internally in a run-length coded form. This provides for both compact storage and efficient computation. In particular, set operations can be performed directly on the encoded representation. `Set::IntSpan' is designed to manage finite sets. However, it can also represent some simple infinite sets, such as {x | x>n}. This allows operations involving complements to be carried out consistently, without having to worry about the actual value of INT_MAX on your machine. SET SPECIFICATIONS ================== Many of the methods take a *set specification*. There are four kinds of set specifications. Empty ----- If a set specification is omitted, then the empty set is assumed. Thus, $set = new Set::IntSpan; creates a new, empty set. Similarly, copy $set; removes all elements from $set. Object reference ---------------- If an object reference is given, it is taken to be a `Set::IntSpan' object. Array reference --------------- If an array reference is given, then the elements of the array are taken to be the elements of the set. The array may contain duplicate elements. The elements of the array may be in any order. Run list -------- If a string is given, it is taken to be a *run list*. A run list specifies a set using a syntax similar to that in newsrc files. A run list is a comma-separated list of *runs*. Each run specifies a set of consecutive integers. The set is the union of all the runs. Runs may be written in any of several forms. Finite forms ------------ n { n } a-b {x | a<=x && x<=b} Infinite forms -------------- (-n {x | x<=n} n-) {x | x>=n} (-) The set of all integers Empty forms ----------- The empty set is consistently written as " (the null string). It is also denoted by the special form '-' (a single dash). Restrictions ------------ The runs in a run list must be disjoint, and must be listed in increasing order. Valid characters in a run list are 0-9, '(', ')', '-' and ','. White space and underscore (_) are ignored. Other characters are not allowed. Examples -------- - { } 1 { 1 } 1-2 { 1, 2 } -5-1 { -5, -4, -3, -2, -1 } (-) the integers (-1 the negative integers 1-3, 4, 18-21 { 1, 2, 3, 4, 18, 19, 20, 21 } ITERATORS ========= Each set has a single *iterator*, which is shared by all calls to first, last, start, next, prev, and current. At all times, the iterator is either an element of the set, or undef. first, last, and start set the iterator; next, and prev move it; and current returns it. Calls to these methods may be freely intermixed. Using next and prev, a single loop can move both forwards and backwards through a set. Using start, a loop can iterate over portions of an infinite set. METHODS ======= Creation -------- $set = new `Set::IntSpan' *$set_spec* Creates and returns a `Set::IntSpan' object. The initial contents of the set are given by *$set_spec*. $ok = valid `Set::IntSpan' $run_list Returns true if $run_list is a valid run list. Otherwise, returns false and leaves an error message in $@. $set = copy $set *$set_spec* Copies *$set_spec* into $set. The previous contents of $set are lost. For convenience, copy returns $set. $run_list = `run_list' $set Returns a run list that represents $set. The run list will not contain white space. $set is not affected. By default, the empty set is formatted as '-'; a different string may be specified in `$Set::IntSpan::Empty_String'. *@elements* = elements $set Returns an array containing the elements of $set. The elements will be sorted in numerical order. In scalar context, returns an array reference. $set is not affected. Set operations -------------- $u_set = union $set *$set_spec* Returns the set of integers in either $set or *$set_spec*. $i_set = `intersect' $set *$set_spec* Returns the set of integers in both $set and *$set_spec*. $x_set = xor $set *$set_spec* Returns the set of integers in $set or *$set_spec*, but not both. $d_set = diff $set *$set_spec* Returns the set of integers in $set but not in *$set_spec*. $c_set = `complement' $set Returns the set of integers that are not in $set. For all set operations, a new `Set::IntSpan' object is created and returned. The operands are not affected. Comparison ---------- `equal' $set *$set_spec* Returns true iff $set and *$set_spec* contain the same elements. `equivalent' $set *$set_spec* Returns true iff $set and *$set_spec* contain the same number of elements. All infinite sets are equivalent. `superset' $set *$set_spec* Returns true iff $set is a superset of *$set_spec*. `subset' $set *$set_spec* Returns true iff $set is a subset of *$set_spec*. Cardinality ----------- $n = `cardinality' $set Returns the number of elements in $set. Returns -1 for infinite sets. empty $set Returns true iff $set is empty. `finite' $set Returns true iff $set is finite. `neg_inf' $set Returns true iff $set contains {x | xn} for some n. `infinite' $set Returns true iff $set is infinite. universal $set Returns true iff $set contains all integers. Membership ---------- member $set $n Returns true iff the integer $n is a member of $set. insert $set $n Inserts the integer $n into $set. Does nothing if $n is already a member of $set. remove $set $n Removes the integer $n from $set. Does nothing if $n is not a member of $set. Extrema ------- min $set Returns the smallest element of $set, or undef if there is none. max $set Returns the largest element of $set, or undef if there is none. Iterators --------- $set->first Sets the iterator for $set to the smallest element of $set. If there is no smallest element, sets the iterator to undef. Returns the iterator. $set->last Sets the iterator for $set to the largest element of $set. If there is no largest element, sets the iterator to undef. Returns the iterator. $set->start($n) Sets the iterator for $set to $n. If $n is not an element of $set, sets the iterator to undef. Returns the iterator. $set->next Sets the iterator for $set to the next element of $set. If there is no next element, sets the iterator to undef. Returns the iterator. next will return undef only once; the next call to next will reset the iterator to the smallest element of $set. $set->prev Sets the iterator for $set to the previous element of $set. If there is no previous element, sets the iterator to undef. Returns the iterator. prev will return undef only once; the next call to prev will reset the iterator to the largest element of $set. $set->current Returns the iterator for $set. FUNCTIONS ========= $sub_set = `grep_set' { ... } $set Evaluates the BLOCK for each integer in $set (locally setting $_ to each integer) and returns a `Set::IntSpan' object containing those integers for which the BLOCK returns TRUE. Returns undef if $set is infinite. $map_set = `map_set' { ... } $set Evaluates the BLOCK for each integer in $set (locally setting $_ to each integer) and returns a `Set::IntSpan' object containg all the integers returned as results of all those evaluations. Evaluates the BLOCK in list context, so each element of $set may produce zero, one, or more elements in the returned set. Returns undef if $set is infinite. CLASS VARIABLES =============== `$Set::IntSpan::Empty_String' `$Set::IntSpan::Empty_String' contains the string that is returned when `run_list' is called on the empty set. `$Empty_String' is initially '-'; alternatively, it may be set to ". Other values should be avoided, to ensure that `run_list' always returns a valid run list. `run_list' accesses `$Empty_String' through a reference stored in $set->{`empty_string'}. Subclasses that wish to override the value of `$Empty_String' can reassign this reference. DIAGNOSTICS =========== Any method (except valid) will die if it is passed an invalid run list. `Set::IntSpan::_copy_run_list: Bad syntax:' *$runList* (F) $run_list has bad syntax `Set::IntSpan::_copy_run_list: Bad order:' *$runList* (F) $run_list has overlapping runs or runs that are out of order. `Set::IntSpan::elements: infinite set' (F) An infinte set was passed to elements. Out of memory! (X) elements $set can generate an "Out of memory!" message on sufficiently large finite sets. NOTES ===== Traps ----- Beware of forms like union $set [1..5]; This passes an element of @set to union, which is probably not what you want. To force interpretation of $set and [1..5] as separate arguments, use forms like union $set +[1..5]; or $set->union([1..5]); Cardinality ----------- You cannot use the obvious comparison routine { $a->cardinality <=> $b->cardinality } to sort sets by size, because `cardinality' returns -1 for infinte sets. (All the non-negative integers were taken. Sorry.) Instead, you have to write something like { my $a_card = $a->cardinality; my $b_card = $b->cardinality; $a_card == $b_card and return 0; $a_card < 0 and return 1; $b_card < 0 and return -1; $a_card <=> $b_card } grep_set and map_set -------------------- `grep_set' and `map_set' make it easy to construct sets for which the internal representation used by `Set::IntSpan' is not small. Consider: $billion = new Set::IntSpan '0-1_000_000_000'; # OK $odd = grep_set { $_ & 1 } $billion; # trouble $even = map_set { $_ * 2 } $billion; # double trouble Error handling -------------- There are two common approaches to error handling: exceptions and return codes. There seems to be some religion on the topic, so `Set::IntSpan' provides support for both. To catch exceptions, protect method calls with an eval: $run_list = ; eval { $set = new Set::IntSpan $run_list }; $@ and print "$@: try again\n"; To check return codes, use an appropriate method call to validate arguments: $run_list = ; if (valid Set::IntSpan $run_list) { $set = new Set::IntSpan $run_list } else { print "$@ try again\n" } Similarly, use `finite' to protect calls to elements: finite $set and @elements = elements $set; Calling elements on a large, finite set can generate an "Out of memory!" message, which cannot (easily) be trapped. Applications that must retain control after an error can use `intersect' to protect calls to elements: @elements = elements { intersect $set "-1_000_000 - 1_000_000" }; or check the size of $set first: finite $set and cardinality $set < 2_000_000 and @elements = elements $set; Limitations ----------- Although `Set::IntSpan' can represent some infinite sets, it does not perform infinite-precision arithmetic. Therefore, finite elements are restricted to the range of integers on your machine. Roots ----- The sets implemented here are based on a Macintosh data structure called a region. See Inside Macintosh for more information. AUTHOR ====== Steven McDougall, swmcd@world.std.com COPYRIGHT ========= Copyright 1996-1998 by Steven McDougall. This module is free software; you can redistribute it and/or modify it under the same terms as Perl itself.  File: pm.info, Node: Set/NestedGroups, Next: Set/NestedGroups/Member, Prev: Set/IntSpan, Up: Module List grouped data eg ACL's, city/state/country etc ********************************************* NAME ==== Set::NestedGroups - grouped data eg ACL's, city/state/country etc SYNOPSIS ======== use Set::NestedGroups; $nested = new Set::NestedGroups; $nested->add('user','group'); $nested->add('group','parentgroup'); do_something() if($nested->member('user','parentgroup')); DESCRIPTION =========== Set::NestedGroups gives an implementation of nested groups, access control lists (ACLs) would be one example of nested groups. For example, if Joe is a Manager, and Managers have access to payroll, you can create an ACL which implements these rules, then ask the ACL if Joe has access to payroll. Another example, you may wish to track which city, state and country people are in, by adding people to cities, cities to states, and states to countries. CONSTRUTORS =========== new() creates a new Set::NestedGroups object. new( fh ) creates a new Set::NestedGroups object, the object will be initialized using data read from this handle. For details on the format, see the save() method new( $sth ) creates a new Set::NestedGroups object, the object will be initialized using data read using this this DBI statement handle. For details on the format, see the save() method METHODS ======= add ( $member, $group) adds a member to a group. The group will be created if it doesn't already exist. remove ( $member, $group ) removes a member from a group. If this was the last member in this group, then the group will be deleted. If the member was only in this group, then the member will be deleted. save(FILEHANDLE) Outputs the object to the given filehandle, which must be already open in write mode. The format is compatable with the format used by CGI, and can be used with new to initialize a new object; Returns true if successfully wrote the data, or false if something went wrong (usually that meant that the handle wasn't already open in write mode). save($sth) Saves the object to a DBI database. This can be used with new to initialize a new object. The $sth should be expecting 2 values, in this fashion: $sth = $dbh->prepare('insert into acl values (?,?)') $acl->save($dbh); $sth->finish(); $sth = $dbh->prepare('select * from acl'); $newacl=new ACL($sth); Returns true if successfully wrote the data, or false if something went wrong. member ( $member, $group ) Returns true if $member is a member of $group. member ( $member ) returns true if $member exists in any group. group ( $group ) returns true if $group exists groups ( $member, %options ) Returns the groups that $member belongs to. Options are explained below. members ( $group , %options ) Returns the members of $group. Keep on reading for the options list(%options) Returns a Set::NestedGroups::Member object that will output an list of the members & groups. This could be considered a calling of groups() on each member, except this is more efficent. The object can be used as follows. $list=$nested->list(); for(my $i=0;$i<$list->rows();$i++){ my ($member,$group)=$list->next(); print "$member=$group\n"; } options ------- By default, the above methods give every valid combination. However you might not always want that. Therefore there are options which can prevent return of certain values. All of these examples presume that 'joe' is a member of 'managers', and 'managers' is a member of payroll, and that you are using only one of these options. You can use all 3, but that gets complicated to explain. -norecurse=>1 No Recursion is performed, method would ignore payroll, and return only managers. -nomiddles=>1 Doesn't returns groups 'in the middle', method would ignore mangers, and return only payroll. -nogroups=>1 Doesn't return members that are groups. This only applies to the list() method, in which case it acts like nomiddles, except on the member instead of the group. list would ignore managers and return joe => managers , joe => payroll. This sounds a lot more confusing than it actually is, once you try it once or twice you'll get the idea. AUTHOR ====== Alan R. Barclay, gorilla@elaine.drink.com SEE ALSO ======== perl(1), CGI, DBI.  File: pm.info, Node: Set/NestedGroups/Member, Next: Set/Object, Prev: Set/NestedGroups, Up: Module List Set of nested groups ******************** NAME ==== Set::NestedGroup::Member - Set of nested groups SYNOPSIS ======== use Set::NestedGroup; $acl = new Set::NestedGroup; $acl->add('user','group'); $acl->add('group','parentgroup'); $list=$acl->list(); for(my $i=0;$i<$list->rows();$i++){ my ($member,$group)=$list->next(); print "$member=$group\n"; } DESCRIPTION =========== Set::NestedGroup::Member objects are returns from a Set::NestedGroup object's list() method. METHODS ======= rows () Returns the number of rows this has. May be used to construct a loop to extract all the data. next () Returns a list comprising of the next member & group. Returns undef when the list is exhausted. AUTHOR ====== Alan R. Barclay, gorilla@elaine.drink.com SEE ALSO ======== perl(1), Set::NestedGroup  File: pm.info, Node: Set/Object, Next: Set/Scalar, Prev: Set/NestedGroups/Member, Up: Module List set of objects ************** NAME ==== Set::Object - set of objects SYNOPSIS ======== use Set::Object; $set = Set::Object->new(); DESCRIPTION =========== This modules implements a set of objects, that is, an unordered collection of objects without duplication. CLASS METHODS ============= new( [list] ) ------------- Return a new `Set::Object' containing the elements passed in list. The elements must be objects. INSTANCE METHODS ================ insert( [list] ) ---------------- Add objects to the `Set::Object'. Adding the same object several times is not an error, but any `Set::Object' will contain at most one occurence of the same object. Returns the number of elements that were actually added. includes( [list] ) ------------------ Return `true' if all the objects in list are members of the `Set::Object'. list may be empty, in which case `true' is returned. members ------- Return the objects contained in the `Set::Object'. size ---- Return the number of elements in the `Set::Object'. remove( [list] ) ---------------- Remove objects from a `Set::Object'. Removing the same object more than once, or removing an object absent from the `Set::Object' is not an error. Returns the number of elements that were actually removed. clear ----- Empty this `Set::Object'. as_string --------- Return a textual Smalltalk-ish representation of the `Set::Object'. Also available as overloaded operator "". intersection( [list] ) ---------------------- Return a new `Set::Object' containing the intersection of the `Set::Object's passed as arguments. Also available as overloaded operator *. union( [list] ) --------------- Return a new `Set::Object' containing the union of the `Set::Object's passed as arguments. Also available as overloaded operator +. subset( set ) ------------- Return `true' if this `Set::Object' is a subset of set. Also available as operator <=. proper_subset( set ) -------------------- Return `true' if this `Set::Object' is a proper subset of set Also available as operator <. superset( set ) --------------- Return `true' if this `Set::Object' is a superset of set. Also available as operator >=. proper_superset( set ) ---------------------- Return `true' if this `Set::Object' is a proper superset of set Also available as operator >. INSTALLATION ============ This module is partly written in C, so you'll need a C compiler to install it. Use the familiar sequence: perl Makefile.PL make make test make install This module was developed on Windows NT 4.0, using the Visual C++ compiler with Service Pack 2. It was also tested on AIX using IBM's xlc compiler. PERFORMANCE =========== The following benchmark compares `Set::Object' with using a hash to emulate a set-like collection: use Set::Object; package Obj; sub new { bless { } } @els = map { Obj->new() } 1..1000; require Benchmark; Benchmark::timethese(100, { 'Control' => sub { }, 'H insert' => sub { my %h = (); @h{@els} = @els; }, 'S insert' => sub { my $s = Set::Object->new(); $s->insert(@els) }, } ); %gh = (); @gh{@els} = @els; $gs = Set::Object->new(@els); $el = $els[33]; Benchmark::timethese(100_000, { 'H lookup' => sub { exists $gh{33} }, 'S lookup' => sub { $gs->includes($el) } } ); On my computer the results are: Benchmark: timing 100 iterations of Control, H insert, S insert... Control: 0 secs ( 0.01 usr 0.00 sys = 0.01 cpu) (warning: too few iterations for a reliable count) H insert: 68 secs (67.81 usr 0.00 sys = 67.81 cpu) S insert: 9 secs ( 8.81 usr 0.00 sys = 8.81 cpu) Benchmark: timing 100000 iterations of H lookup, S lookup... H lookup: 7 secs ( 7.14 usr 0.00 sys = 7.14 cpu) S lookup: 6 secs ( 5.94 usr 0.00 sys = 5.94 cpu) AUTHOR ====== Jean-Louis Leroy, jll@skynet.be LICENCE ======= Copyright (c) 1998-1999, Jean-Louis Leroy. All Rights Reserved. This module is free software. It may be used, redistributed and/or modified under the terms of the Perl Artistic License SEE ALSO ======== perl(1). overload.pm  File: pm.info, Node: Set/Scalar, Next: Set/Scalar/Base, Prev: Set/Object, Up: Module List basic set operations ******************** NAME ==== Set::Scalar - basic set operations SYNOPSIS ======== use Set::Scalar; $s = Set::Scalar->new; $s->insert('a', 'b'); $s->delete('b'); $t = Set::Scalar->new('x', 'y', $z); DESCRIPTION =========== Creating -------- $s = Set::Scalar->new; $s = Set::Scalar->new(@members); $t = $s->clone; Modifying --------- $s->insert(@members); $s->delete(@members); $s->invert(@members); # insert if hasn't, delete if has Displaying ---------- print $s, "\n"; The display format of a set is the members of the set separated by spaces and enclosed in parentheses (). You can even display recursive sets. Querying -------- @members = $s->members; @elements = $s->elements; # alias for members $size = $s->size; if ($s->member($member)) { ... $s->element # alias for member $s->has # alias for member $s->contains # alias for member $s->is_null $s->is_universal $s->null # the null set $s->universe # the universe of the set Deriving -------- $u = $s->union($t); $i = $s->intersection($t); $d = $s->difference($t); $e = $s->symmetric_difference($t); $v = $s->unique($t); $c = $s->complement; These methods have operator overloads: $u = $s + $t; # union $i = $s * $t; # intersection $d = $s - $t; # difference $e = $s % $t; # symmetric_difference $v = $s / $t; # unique $c = -$s; # complement Both the `symmetric_difference' and unique are symmetric on all their arguments. For two sets they are identical but for more than two sets beware: `symmetric_difference' returns true for elements that are in an odd number (1, 3, 5, ...) of sets, unique returns true for elements that are in one set. Some examples of the various set differences: set or difference value $a (a b c d e) $b (c d e f g) $c (e f g h i) $a->difference($b) (a b) $a->symmetric_difference($b) (a b f g) $a->unique($b) (a b f g) $b->difference($a) (f g) $b->symmetric_difference($a) (a b f g) $b->unique($a) (a b f g) $a->difference($b, $c) (a b) $a->symmetric_difference($b, $c) (a b e h i) $a->unique($b, $c) (a b h i) Comparing --------- $eq = $s->is_equal($t); $dj = $s->is_disjoint($t); $pi = $s->is_properly_intersecting($t); $ps = $s->is_proper_subset($t); $pS = $s->is_proper_superset($t); $is = $s->is_subset($t); $iS = $s->is_superset($t); $cmp = $s->compare($t); The compare method returns a string from the following list: "equal", "disjoint", "proper subset", "proper superset", "proper intersect", and in future (once I get around implementing it), "disjoint universes". These methods have operator overloads: $eq = $s == $t; # is_equal $dj = $s != $t; # is_disjoint # No operator overload for is_properly_intersecting. $ps = $s < $t; # is_proper_subset $pS = $s > $t; # is_proper_superset $is = $s <= $t; # is_subset $iS = $s >= $t; # is_superset $cmp = $s <=> $t; AUTHOR ====== Jarkko Hietaniemi  File: pm.info, Node: Set/Scalar/Base, Next: Set/Scalar/Null, Prev: Set/Scalar, Up: Module List base class for Set::Scalar ************************** NAME ==== Set::Scalar::Base - base class for Set::Scalar SYNOPSIS ======== *Internal use only*. DESCRIPTION =========== See the Set::Scalar documentation. AUTHOR ====== Jarkko Hietaniemi  File: pm.info, Node: Set/Scalar/Null, Next: Set/Scalar/Real, Prev: Set/Scalar/Base, Up: Module List internal class for Set::Scalar ****************************** NAME ==== Set::Scalar::Null - internal class for Set::Scalar SYNOPSIS ======== *Internal use only*. DESCRIPTION =========== *This is not the module you are looking for.* If you want documentation see *Note Set/Scalar: Set/Scalar,. AUTHOR ====== Jarkko Hietaniemi  File: pm.info, Node: Set/Scalar/Real, Next: Set/Scalar/Universe, Prev: Set/Scalar/Null, Up: Module List internal class for Set::Scalar ****************************** NAME ==== Set::Scalar::Real - internal class for Set::Scalar SYNOPSIS ======== *Internal use only*. DESCRIPTION =========== *This is not the module you are looking for.* If you want documentation see *Note Set/Scalar: Set/Scalar,. AUTHOR ====== Jarkko Hietaniemi  File: pm.info, Node: Set/Scalar/Universe, Next: Set/Scalar/Valued, Prev: Set/Scalar/Real, Up: Module List universes for set members ************************* NAME ==== Set::Scalar::Universe - universes for set members SYNOPSIS ======== *Do not use directly.* DESCRIPTION =========== There are only two guaranteed interfaces, both sort of indirect. The first one is accessing the universe of a set: $set->universe This contains the members of the universe $set->universe->members of the $set. The second supported interface is displaying set universes. print $set->universe, "\n"; This will display the members of the set inside square brackets: [], as opposed to sets, which have their members shown inside parentheses: (). AUTHOR ====== Jarkko Hietaniemi  File: pm.info, Node: Set/Scalar/Valued, Next: Set/Scalar/ValuedUniverse, Prev: Set/Scalar/Universe, Up: Module List valued sets *********** NAME ==== Set::Scalar::Valued - valued sets SYNOPSIS ======== use Set::Scalar::Valued; $s = Set::Scalar::Valued->new; $s->insert(a => 12, 'b c' => $d); $s->delete('b c' => $d); $t = Set::Scalar->new(x => $y, y => $z); DESCRIPTION =========== Valued sets are an extension of the traditional set concept. In addition to a member just existing in the set, the member also has a distinct value. You can think of this a combination of a traditional set and a Perl hash. The used methods are as for the traditional of Set::Scalar, with the difference that when creating (new()) or modifying (insert(), delete(), invert()), you must supply twice the number of arguments: the member-value pairs, instead of just the members. Note, though, that in the current implementation of delete() the value half is unused, the deletion is by the member. In future implementation this behavior may change so that also the value matters. There are a couple of additional methods: %ve = $s->valued_members; which returns the member-value pairs, and @v = $s->values; which returns just the values (in the same order as the members() method would return the members), and $v = $s->value($member); which returns the value of the member. The display format of a valued set is the member-value pairs separated by " => ", the pairs separated by ", " and enclosed in curly brackets {}. AUTHOR ====== Jarkko Hietaniemi  File: pm.info, Node: Set/Scalar/ValuedUniverse, Next: Set/Scalar/Virtual, Prev: Set/Scalar/Valued, Up: Module List universes for valued set members ******************************** NAME ==== Set::Scalar::ValuedUniverse - universes for valued set members SYNOPSIS ======== *Do not use directly.* DESCRIPTION =========== There are only two guaranteed interfaces, both sort of indirect. The first one is accessing the universe of a valued set: $valued_set->universe This contains the members of the universe $valued_set->universe->members of the `$valued_set'. The second supported interface is displaying universes of valued sets. print $valued_set->universe, "\n"; This will display the members of the valued set inside square brackets: [], as opposed to valued sets, which have their members shown inside parentheses: (). AUTHOR ====== Jarkko Hietaniemi  File: pm.info, Node: Set/Scalar/Virtual, Next: Set/Window, Prev: Set/Scalar/ValuedUniverse, Up: Module List internal class for Set::Scalar ****************************** NAME ==== Set::Scalar::Virtual - internal class for Set::Scalar SYNOPSIS ======== *Internal use only*. DESCRIPTION =========== *This is not the module you are looking for.* If you want documentation see *Note Set/Scalar: Set/Scalar,. AUTHOR ====== Jarkko Hietaniemi  File: pm.info, Node: Set/Window, Next: Sex, Prev: Set/Scalar/Virtual, Up: Module List Manages an interval on the integer line *************************************** NAME ==== Set::Window - Manages an interval on the integer line SYNOPSIS ======== use Set::Window; $window = new_lr Set::Window $left, $right; $window = new_ll Set::Window $left, $length; $window = empty Set::Window; $left = $window->left; $right = $window->right; $size = $window->size; @bounds = $window->bounds; @elements = $window->elements; empty $window; eqivalent $window1 $window2; equal $window1 $window2; $window = copy $window $window = offset $window $offset $window = inset $window $inset $window = cover $window @windows $window = intersect $window @windows @windows = $window->series($length); REQUIRES ======== Perl 5.003, Exporter EXPORTS ======= Nothing DESCRIPTION =========== A `Set::Window' object represents a window on the integer line; that is, a finite set of consecutive integers. Methods are provided for creating and modifying windows, for obtaining information about windows, and for performing some simple set operations on windows. The empty window ---------------- The empty window represents the empty set. Like the empty set, the empty window is unique. METHODS ======= Creation -------- `new_lr Set::Window' $left`,' $right Creates and returns a new `Set::Window' object. $left and $right specify the first and last integers in the window. If $right is less than $left, returns the empty window. `new_ll Set::Window' $left`,' $length Creates and returns a new Set::Window object. $left is the first integer in the interval, and $length is the number of integers in the interval If $length is less than one, returns the empty window. `empty Set::Window' Creates and returns an empty `Set::Window' object. Access ------ *$window*`->left' Returns the first integer in the window, or undef if *$window* is empty. *$window*`->right' Returns the last integer in the window, or undef if *$window* is empty. *$window*`->size' Returns the number of integers in the window. The identity *$window*`->size == '*$window*`->right - '*$window*`->left + 1' holds for all non-empty windows. *$window*`->bounds' Returns a list of the first and last integers in *$window*, or undef if *$window* is empty. In scalar context, returns an array reference. *$window*`->elements' Returns a list of the integers in *$window*, in order. In scalar context, returns an array reference. Predicates ---------- empty *$window* Returns true iff *$window* is empty. `equal' *$window1* *$window2* Returns true iff *$window1* and *$window2* are the same. All empty windows are `equal'. `equivalent' *$window1* *$window2* Returns true iff *$window1* and *$window2* are the same size. Modification ------------ These methods implement copy semantics: modifications are made to a copy of the original window. The original window is unaltered, and the new window is returned. copy *$window* Creates and returns a (deep) copy of *$window*. offset *$window* $offset Makes a copy of *$window*, and then shifts it by $offset. Positive values of $offset move the window to the right; negative values move it to the left. Returns the new window. If offset is called on the empty window, it returns the empty window. `inset' *$window* *$inset* Makes a copy of *$window*, and then shrinks it by *$inset* at each end. If *$inset* is negative, the window expands. Returns the new window. If `inset' is called on the empty window, it returns the empty window. `cover' *$window* *@windows* Creates and returns the smallest window that covers (i.e. contains) *$window* and all the *@windows*. `intersect' *$window* *@windows* Creates and returns the largest window that is contained by *$window* and all the *@windows*. This may be the empty window. Utility ------- *$window*`->series('$length) Returns a list of all the windows of $length that are contained in *$window*, ordered from left to right. In scalar context, returns an array reference. If $length is greater than *$window*`->length', the list will be empty. If $length is less than 1, returns undef. DIAGNOSTICS =========== None. NOTES ===== Why? ---- Belive it or not, I actually needed this structure in a program. Maybe someone else will need it, too. Weight ------ `Set::Window' objects are designed to be lightweight. If you need more functionality, consider using `Set::IntSpan'. Error handling -------------- `Set::Window' does not issue any diganostics; in particular, none of the methods can die. Calling elements on a large window can lead to an `out of memory!' message, which cannot be trapped (as of perl 5.003). Applications that must retain control can protect calls to elements with an `intersect' $limit = new_lr Set::Window -1_000_000, 1_000_000; @elements = $window->intersect($limit)->elements; or check the size of *$window* first: length $window < 2_000_000 and @elements = elements $window; Operations involving the empty window are handled consistently. They return valid results if they make sense, and undef otherwise. Thus: Set::Window->empty->elements returns an empty list, because the empty window has no elements, while Set::Windows->empty->bounds returns undef, because the empty window has no first or last element. SEE ALSO ======== perl(1), `Set::IntSpan' AUTHOR ====== Steven McDougall, swmcd@world.std.com COPYRIGHT ========= Copyright (c) 1996, 1997 Steven McDougall. All rights reserved. This module is free software; you can redistribute it and/or modify it under the same terms as Perl itself.  File: pm.info, Node: Sex, Next: Shell, Prev: Set/Window, Up: Module List Perl teaches the birds and the bees. ************************************ NAME ==== Sex - Perl teaches the birds and the bees. SYNOPSIS ======== package Catholicism; use Sex qw(strict Religion); package Mormonism; use Sex qw(Catholicism Sex); DESCRIPTION =========== Heterogeneous recombination of Perl packages. Given two (or more, I'm a liberal guy) packages, Sex.pm will recombine their symbols at random recombining them into the new module thus providing a cross-section of its functions and global variables. It will also push the parent classes onto the child's @ISA array. So you could do: package Net::SFTP; use Sex qw(Net::FTP Net::SSLeay); And get a secure FTP client! The recombination occurs in such a way to ensure that the child will contain -all- the symbols of both parents. Should two (or more) parents wish to bestow the same symbol on its child one will be chosen at random. For example: package DejaNews; use Sex qw(LWP::Simple Net::NNTP); LWP::Simple and Net::NNTP both have a head() function and thus they try to give head() to their child. Sex.pm will suck the head() off either LWP::Simple or Net::NNTP and stick it to DejaNews. Afterwards, DejaNews can procede to finally use its head(). Here's another timely example for Sex in the 21st century: package URI::Bot9000; use Sex qw(URI LWP::RobotUA protected); Because of the dire consequences of having sex with URI, one should make sure you're well protected. BUGS ==== There are many bugs you can get from having Sex used too often on your computer. Please be sure your programs are Safe before they have Sex. package Trojan; use Sex qw(Safe Sex); AUTHOR ====== Michael 'The Porn King of CMU' Schwern SEE ALSO ======== 'Disco Dolls in Hot Skin' 'Exhausted: The John Holmes Story' 'Deep Recursion' starring Ada Lovelace. 'The Fly' (1953)  File: pm.info, Node: Shell, Next: Silly/StringMaths, Prev: Sex, Up: Module List run shell commands transparently within perl ******************************************** NAME ==== Shell - run shell commands transparently within perl SYNOPSIS ======== See below. DESCRIPTION =========== Date: Thu, 22 Sep 94 16:18:16 -0700 Message-Id: <9409222318.AA17072@scalpel.netlabs.com> To: perl5-porters@isu.edu From: Larry Wall Subject: a new module I just wrote Here's one that'll whack your mind a little out. #!/usr/bin/perl use Shell; $foo = echo("howdy", "", "world"); print $foo; $passwd = cat("  File: pm.info, Node: Silly/StringMaths, Next: Silly/Werder, Prev: Shell, Up: Module List Perl extension for doing maths with strings ******************************************* NAME ==== Silly::StringMaths - Perl extension for doing maths with strings SYNOPSIS ======== use Silly::StringMaths qw(add subtract multiply divide exponentiate); # Add two positive numbers - returns ABFOOR print add("FOO", "BAR"); # Add a generally positive number and a negative number # - returns ot print add("FNoRD", "yncft"); # Subtract several numbers from a rather large one # - returns accdeiiiiloopssu print subtract("Supercalifragilisticepsialidocious", "stupid", "made", "up", "word"); # Multiply two negative numbers - returns AAACCCCCCEEELLLNNN print multiply("cancel", "out"); # Divide two numbers - returns AAA print divide("EuropeanCommission", "France"); # Confirm Pythagorus' theorum - returns nothing print subtract(exponentiate("FETLA", "PI"), exponentiate("TLA", "PI"), exponentiate("ETLA", "PI")); DESCRIPTION =========== Silly::StringMaths provides support for basic integer mathematics, using strings rather than numbers. Upper-case letters are positive, lower-case letters are negative, so ABCDEF would be 6 (but WOMBAT would also be 6), whereas positive would actually be -8. Mixed-case is also possible, so Compaq is actually -5. Most methods return a canonicalised version of the string - e.g. `ampq' rather than `Compaq' (mixed case removed, the result sorted alphabetically). The behaviour of other characters is as yet undefined, but be warned that non-alphabetical characters may be reserved for floating point or imaginary numbers. Actual numbers (i.e. the characters 0 to 9) will never be used by this module. BASIC METHODS ============= add --- Takes an array of strings, returns the sum. subtract -------- Takes a string, subtracts all other supplied strings from it and returns the result. multiply -------- Takes a string and multiplies it by all the other strings, returning the resulting product. divide ------ Takes a string, and divides it by all the other strings, returning the result. Results are rounded down. exponentiate ------------ Takes a number, raises it to the appropriate power, as specified by the other arguments. Returns the result. (Note that some textual information is lost here - the result will be either As or as). USEFUL TOOLBOX METHODS ====================== normalise --------- Takes a string with, potentially, a mix of upper-case and lower-case letters, and returns a sorted string that is unmistakeably either positive or negative. sign ---- Returns the sign of a number as either 1, 0 or -1 (as a string, obviously). negative -------- Returns whether the supplied string is negative or not invert ------ Takes a reference to a number, inverts it. AUTHOR ====== Sam Kington, sam@illuminated.co.uk SEE ALSO ======== perl(1).