home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 2 / Apprentice-Release2.iso / Tools / Languages / Python 1.1 / Demo / lutz / sets.py < prev    next >
Encoding:
Text File  |  1994-10-08  |  42.5 KB  |  1,460 lines  |  [TEXT/R*ch]
  1. #
  2. # RelDB
  3. #
  4. # set processing in python
  5. #
  6. # defines 3 items:
  7. #   class Set  -- basic, generic set processing
  8. #   class RSet -- a Set, with relational algebra
  9. #   test_sets  -- a testing function
  10. #
  11. # a set object (Set): 
  12. # (1) is an unordered collection
  13. # (2) allows heterogeneous collections  
  14. # (3) can grow and shrink arbitrarily
  15. #
  16. # a relational set object (RSet):
  17. # (1) is a Set object
  18. # (2) supports relational algebra operations
  19. #
  20. # users can initialize and concatenate
  21. # sets with normal lists, character strings, 
  22. # tuples (in python), other sets, and other 
  23. # user-defined sequence objects;  users  
  24. # can also use any sequence type (built-in
  25. # or user-defined) on the left-hand side
  26. # of most binary set operations;
  27. #
  28. # sets are unordered collections of arbitrary 
  29. # data items: items can be a mixture of any 
  30. # data type (but some operations assume a
  31. # particular node format);  supports most 
  32. # common set operations, as well as some 
  33. # relational algebra operators (via the Rset
  34. # subclass);
  35. #
  36. # sets are implemented using Python lists (but
  37. # we could use other forms), and encapsulated in 
  38. # a class;  there is a conversion to strings; 
  39. #
  40. # there are many ways to represent relational 
  41. # database tuples and tables in Python:
  42. #   --character strings (and split fields apart)
  43. #   --simple lists ([[name,value], [name,value],...])
  44. #   --Pythin tuples ( (value,value,..) or ((name,value), (name,value),..)
  45. #   --lists with seperate name lists (['f1','f2'..], [a,b,..], [c,d,..])
  46. #   --empty classes (class T:  x = T(); x.f1=a, x.f2=b; ...)
  47. #   --dictionaries ( {'name':value, 'name':value,....}, {...}, .. )
  48. #
  49. # we use dictionaries here for clarity, but they're 
  50. # probably not the most efficient alternative (hashing 
  51. # versus indexing);  each tuple is a dictionary, and
  52. # a table is just a list of dictionaries;  we also don't 
  53. # load tables from an external file-- they are assumed to 
  54. # be already present in the program (dictionary constants 
  55. # in python);  dictionaries are slow to copy and compare
  56. # in python, so they're probably a poor representation
  57. # for tuples/records;
  58. #
  59. # notes:
  60. # 1) Uses python's OOP class facility for sets.  We only
  61. # use inheritance to define the RSet() relational set
  62. # subclass of Set(). Since there's little over-riding of 
  63. # methids in Rset, OOP isn't strictly necessary (we could 
  64. # a module of library functions that operate on simple 
  65. # lists instead).
  66. #
  67. # We could, in priciple, also sub-classes to define 
  68. # different internal formats (list sets, string sets, 
  69. # etc) this would require making the concatenation 
  70. # operation virtual, since '+' needs the same type on 
  71. # each side (different singleton syntax).  Since we 
  72. # use lists internally, we can use the faster '.append'
  73. # list method to concatenate onto a set (versus '+').
  74. #
  75. # 2) Python's 'in' and subscripting are generic, but '+'
  76. # requires the same types on left and right.
  77. # Python's '==' (and therefore 'in') handles lists,
  78. # tuples, dictionaries and strings right (its not
  79. # just address comparison ('is' does that): strings
  80. # compare lexically, lists/tuples are traversed 
  81. # recursively, and dictionaries are compared 
  82. # recursively after their fields are sorted.
  83. #
  84. # 3) We do minimal error checking here: you'll get 
  85. # a normal subscripting or dictionary exception if 
  86. # you do something weird with a set;
  87. #
  88. # 4) example usage:
  89. #    python
  90. #    >>> import sets
  91. #    >>> sets.test_sets()
  92. #
  93. #    >>> from sets import *
  94. #    >>> test_sets()
  95. #    >>> import pbd
  96. #    >>> pdb.run('test_sets()')
  97. #
  98. #    >>> x = Set().init('abd')          (interactive)
  99. #    >>> y = Set().init('db')
  100. #    >>> x.intersect(y)
  101. #
  102. #    >>> from sets import *
  103. #    >>> test_sets()
  104. #    >>> from sets import *
  105. #    >>> table1.join(table2).list([])   (tables exported)
  106. ##############################################################  
  107. ##############################################################
  108.  
  109.  
  110.  
  111.  
  112.  
  113. class Set:
  114.  
  115.  
  116.  
  117. #######################################################
  118. # init() takes an optional argument, and allows the
  119. # init value to be a list, character string, tuple,
  120. # another existing set, or any sequence class object;
  121. #######################################################
  122.  
  123.  
  124.  
  125.  
  126.     def init(self, *value):
  127.         self.data = []
  128.         if value: 
  129.             self.concat(value[0])
  130.         return self
  131.  
  132.  
  133.     def display(self):
  134.         print
  135.         print '<',
  136.         for x in self.data: print x,
  137.         print '>'
  138.  
  139.  
  140.     def list(self):
  141.         print
  142.         for x in self.data: print x
  143.  
  144.  
  145.     def to_string(self):
  146.         result = ''
  147.         for x in self.data: result = result + x
  148.         return result
  149.  
  150.  
  151.     def to_list(self):
  152.         return self.data[:]               # copy list
  153.  
  154.  
  155.     def to_RSet(self): 
  156.         return RSet().init(self.data)     # see notes at RSet class
  157.  
  158.  
  159.  
  160.  
  161. #################################################
  162. # note that self.data can be accessed directly;
  163. # we need copy() since assignment just binds a 
  164. # variable to an existing object: changing one
  165. # variable may effect another variable's value;
  166. #################################################
  167.  
  168.  
  169.  
  170.  
  171.     def get(self):        
  172.         return self.data    
  173.     
  174.  
  175.     def set(self, value): 
  176.         self.data = []
  177.         self.concat(value)             # allow any seqence object
  178.  
  179.  
  180.     def copy(self):
  181.         return Set().init(self)        # or copy via self.data[:]
  182.  
  183.  
  184.  
  185.  
  186.  ############################################################
  187.  # insertion, deletion, duplication (in place);
  188.  # concat() allows adding lists, strings, tuples, other 
  189.  # sets, and any other user-defined sequence class object, 
  190.  # to a given set object;
  191.  #
  192.  # concat() uses 'in' to generically iterate over any 
  193.  # sequence type: lists, strings, tuples, and any user-
  194.  # defined sequence class;  any user-defined class
  195.  # which overloads '__len__' and '__getitem__' methods
  196.  # will work with 'in' generation;  our Set class does
  197.  # this too, so 'value' can be another set, and we don't  
  198.  # really need a special type test of the form:
  199.  #      if type(value) == type(self): 
  200.  #           value = value.data
  201.  #
  202.  # notes: 
  203.  # 1) 'x.concat(y.get())' = 'x.concat(y)' = 'x = x + y'
  204.  # 2) 'list.append(x)' is faster than 'list = list + [x]'
  205.  # 3) 'type(self)==type(value)': all class instances 
  206.  #    have the same type, so this only tells us it's an
  207.  #    instance-- we assume its a Set() instance as well;
  208.  #    we need type() since classes can;t over-ride 'in';
  209.  #
  210.  # 4) deletion can be coded many ways in python:
  211.  #     try:
  212.  #         self.data.remove(value)
  213.  #     except: 
  214.  #         pass                      
  215.  #
  216.  #     del self.data[self.data.index(value)]
  217.  #
  218.  #     for i in range(len(self.data)):
  219.  #         if self.data[i] == value
  220.  #             sef.data = self.data[:i] + self.data[i+1:]
  221.  ###########################################################
  222.  
  223.  
  224.  
  225.  
  226.     def concat(self, value):             
  227.         for x in value:                       # generic iterator   
  228.             self.data.append(x)           
  229.                                               
  230.  
  231.     def delete(self, value):
  232.         if value in self.data:
  233.             self.data.remove(value)
  234.  
  235.  
  236.     def delete_all(self, value):
  237.         while value in self.data:
  238.             self.delete(value)                # Set delete, not list 
  239.  
  240.  
  241.     def delete_set(self, sequence):
  242.         for x in sequence:
  243.             self.delete(x)                    # in-place 'difference'
  244.  
  245.                                       
  246.     def repeat(self, copies):
  247.         self.data = self.data * copies
  248.         
  249.  
  250.  
  251.  
  252. ########################################################
  253. # searching (index), function apply and mapping, etc.;
  254. # Pyton has an apply(func,args), but it doesn't 
  255. # apply the funtion to a list;
  256. ########################################################
  257.  
  258.  
  259.  
  260.  
  261.     def search(self, value):              
  262.         for i in range(len(self.data)):     # if value in self.data:  
  263.             if self.data[i] == value:       #    return self.data.index(value)
  264.                 return i              
  265.         return -1                     
  266.  
  267.  
  268.     def apply(self, func):
  269.         for x in self.data: func(x)
  270.  
  271.  
  272.     def map(self, func):
  273.         result = []
  274.         for x in self.data: result.append(func(x))
  275.         return Set().init(result)
  276.  
  277.  
  278.     def accum(self, func, start):
  279.         result = start
  280.         for x in self.data: result = func(result, x)
  281.         return result
  282.  
  283.  
  284.     def accum_op(self, optr, start):
  285.         result = start
  286.         for x in self.data: result = eval(`result` + optr + `x`)
  287.         return result
  288.  
  289.  
  290.     def sum(self):    return self.accum_op('+', 0)
  291.  
  292.     def prod(self):   return self.accum_op('*', 1)
  293.         
  294.     def abs(self):    return self.map(abs)
  295.  
  296.     def neg(self):    return self.map(negate)
  297.     
  298.     def square(self): return self.map(square)
  299.  
  300.  
  301.  
  302.  
  303. ##########################################################
  304. # a set member generator;
  305. #
  306. # these routines are mostly superfluous, since we
  307. # can generate set nodes using 'in' in for loops:
  308. #       for x in set:
  309. #           process(x)
  310. #
  311. # we can do this because we've overloaded len() and
  312. # x[i] to work with set instances (see below);  this
  313. # allows 'in' to generate items in a sequence class;
  314. # 
  315. # makes a copy of the set's list (using [:] slices),
  316. # so that generation ignores set changes between next()
  317. # calls (an index/counter can become wrong);
  318. ##########################################################
  319.  
  320.  
  321.  
  322.  
  323.     def first(self):
  324.         self.tail = self.data[:]            
  325.         return self.next()                  
  326.     
  327.  
  328.     def next(self):
  329.         if self.tail == []:  
  330.             return []
  331.         else:
  332.             head, self.tail = self.tail[0], self.tail[1:]
  333.             return head
  334.  
  335.  
  336.  
  337.  
  338. ############################################
  339. # basic set operations;
  340. # uses very simplistic algorithms;
  341. # also available with operators &, |, ^ ;
  342. #
  343. # note: the right-hand operand to these
  344. # methods ('other') can be another Set,
  345. # or any built-in or user-defined sequence
  346. # type (lists, character strings, tuples.
  347. # other class objects): 'in' generates Set 
  348. # items too;
  349. #
  350. # since 'in' also iterates over the left
  351. # operand ('self'), we don't really need
  352. # to use 'self.data' in the 'if' and 'for'
  353. # statements in the code below (we could
  354. # just use 'self');  but the left must
  355. # be a Set object to call the methods, 
  356. # and using '.data' avoids 1 method call;
  357. ############################################
  358.  
  359.  
  360.  
  361.  
  362.     def intersect(self, other):
  363.         result = []
  364.         for x in self.data:
  365.             if x in other:                     # not 'other.data'
  366.                 result.append(x)
  367.         return Set().init(result)
  368.  
  369.  
  370.     def union(self, other):
  371.         result = self.data[:]                  # copy list 
  372.         for x in other:
  373.             if not x in self.data:
  374.                 result.append(x)
  375.         return Set().init(result)
  376.  
  377.  
  378.     def difference(self, other):
  379.         result = []
  380.         for x in self.data:
  381.             if not x in other:
  382.                 result.append(x)
  383.         return Set().init(result)
  384.     
  385.  
  386.  
  387.  
  388. ################################################################
  389. # set membership, occurrence counts, equivalence, subsumption;
  390. #
  391. # member() and occurs() are not strictly needed:
  392. #
  393. # member -> 
  394. #    'in' works with Set objects, since Set overloads the
  395. #    '__len__' and '__getitem__' methods ('in' works on all
  396. #    sequences generically);  so we can directly code:
  397. #          if value in set:
  398. #               process..
  399. # occurs ->
  400. #    we can simply use the built-in count() list method:  
  401. #          self.data.count(value)
  402. #
  403. # notes:
  404. # 1) 2 sets are 'equivalent' if they have exactly the same 
  405. # elements, but in possibly different orders;
  406. #
  407. # 2) a set 'subsumes' another, if all it contains (at 
  408. # least) all elements in the other set, in any order,
  409. # plus arbitrarily many other items (it must be at least 
  410. # as long as the subsumed set);  this is the same as
  411. # saying the operand is a _subset_ of the object;
  412. ###############################################################
  413.  
  414.  
  415.  
  416.  
  417.     def member(self, value): 
  418.         return (value in self.data)                # boolean 1|0
  419.  
  420.  
  421.     def occurs(self, value):
  422.         i = 0
  423.         for x in self.data: 
  424.             if x == value: i = i+1                 # .count     
  425.         return i
  426.  
  427.  
  428.     def equiv(self, other):
  429.         copy = other.data[:]                       # dont change other
  430.         for x in self.data:
  431.             if not x in copy:                      # other must be a set
  432.                 return 0
  433.             copy.remove(x)
  434.         return (copy == [])
  435.  
  436.  
  437.     def subsume(self, other):
  438.         copy = self.data[:]
  439.         for x in other.data:
  440.             if not x in copy:
  441.                 return 0
  442.             copy.remove(x)
  443.         return 1
  444.  
  445.  
  446.  
  447.  
  448. ############################################################
  449. # bagof() variants: 
  450. #
  451. # create a new set of items composed of items in the 
  452. # set that satisfy/succeed a given testing function;
  453. #
  454. # bagof() is a generic dispatcher; it selects one  
  455. # of 4 bagof methods based on the datatype of the 
  456. # argument and/or the numberof arguments passed
  457. #
  458. # bagof1() takes a function which must take exactly one
  459. # argument (set item), and return a 0/1 boolean result;
  460. #
  461. # bagof2() takes an arbitrary expression (a string),
  462. # which should evaluate to 0/1 boolean result;  in
  463. # the expression string, the variable name 'x' will
  464. # reference the generated set item (eval() evaluates
  465. # an expression in the context of the eval() call);
  466. #
  467. # bagof3() is bagof2(), except that it creates a
  468. # function enclosing the expression, and passes it
  469. # to bagof() (rather than calling eval() repeatedly)
  470. # (exec() is like eval(), but allows full statements)
  471. #
  472. # bagof4() takes a generation variable, a function,
  473. # and a list of arguments to send the function in the 
  474. # form of a tuple;  it binds the generation variable 
  475. # to successive set items, and calls the function 
  476. # with an argument list composed of members of the
  477. # tuple;  the set item can be referenced by using
  478. # the generation variable in the argument list tuple;
  479. #
  480. # bagof5() is like bagof4(), except that is always 
  481. # places the generated item in argument 1, in the 
  482. # call to the testing funtion; this simplifies the
  483. # interface;
  484. #
  485. # notes:
  486. # 1) 'apply' in bagof4() refers to the built-in apply,
  487. # not the Set method (need self.apply to get to method)
  488. #
  489. # 2) The string expression variants must be used with
  490. # care: you must concatenate the string representation 
  491. # of values into the expr;  this requires backquotes
  492. # for lists and tuple;  since Set overloads __repr__, 
  493. # sets can be printed with backquotes, without having
  494. # to call the '.get()' method to get the set's value list
  495. #
  496. # 3) bagof3() must do eval('_f') to get the function it  
  497. # just created;  using 'global _f' does not seem to avoid
  498. # this: '_f' is likely always stored in the local scope
  499. # when 'def' runs, and the '_f'' refence maps to the global
  500. # scope statically (since its not assigned) ???
  501. #
  502. # 4) bagof4() is a bit tricky...
  503. # Python passes parameters by value (copy)-- this
  504. # really means passing by object reference: the formal
  505. # parameter initially 'shares' the object the actual
  506. # parameter is bound to, but the 2 diverge as soon as
  507. # the formal parameter is reassigned in the function.
  508. #
  509. # But, when the formal/actual share a 'mutable' object,
  510. # changes made to it through the formal will be
  511. # reflected in the actual.  In other words, pass by
  512. # reference can be simulated by using a list object
  513. # enclosing the item, and changing the value of
  514. # the list node.
  515. #
  516. # Also, python has no delayed evaluation, except
  517. # for strings: arguments are fully evaluated in a
  518. # call before the call is made, so use a variable
  519. # in a call that we hope will become successively
  520. # bound insode the function [bagof4(x, member, (x,y))]
  521. #
  522. # For both these reasons, bagof4() requires that  
  523. # the generation variable be passed in as a 1-item
  524. # list, and that the test function expect the 1-item
  525. # list to be passed in;  it rebinds list[0], and
  526. # so changes the value of the generation variable;
  527. ############################################################
  528.  
  529.  
  530.  
  531.  
  532.     def bagof(self, *args):
  533.         if len(args) == 1:
  534.             if type(args[0]) == type(''):
  535.                 return self.bagof3(args[0])                # string expr
  536.             else:
  537.                 return self.bagof1(args[0])                # 1-arg function
  538.         
  539.         elif len(args) == 2:
  540.             return self.bagof5(args[0], args[1])           # func+extra-args
  541.         elif len(args) == 3:
  542.             return self.bagof4(args[0], args[1]. args[2])  # gen+func+args
  543.         else:
  544.             raise set_error
  545.  
  546.  
  547.  
  548.  
  549.     def bagof1(self, func):
  550.         res = []
  551.         for x in self.data:
  552.             if func(x): res.append(x)
  553.         return Set().init(res)
  554.  
  555.  
  556.     def bagof2(self, expr):
  557.         res = []
  558.         for x in self.data:
  559.             if eval(expr): res.append(x)
  560.         return Set().init(res)
  561.  
  562.  
  563.     def bagof3(self, expr):
  564.         exec('def _f(x): return ' + expr + '\n')
  565.         return self.bagof1(eval('_f'))
  566.  
  567.  
  568.     def bagof4(self, gen, func, args):
  569.         res = []
  570.         for gen[0] in self.data:
  571.             if apply(func, args): res.append(gen[0])
  572.         return Set().init(res)
  573.  
  574.  
  575.     def bagof5(self, func, args):
  576.         res = []
  577.         for x in self.data:
  578.             if apply(func, (x,) + args): res.append(x)
  579.         return Set().init(res)
  580.  
  581.  
  582.  
  583.  
  584. #
  585. # usage examples
  586. #
  587.  
  588.  
  589.     def intersect1(self, other):
  590.         global global_list
  591.         global_list = other
  592.         return self.bagof(in_global_list)
  593.     
  594.     # def in_global_list(x): return x in global_list
  595.  
  596.  
  597.     def intersect2(self, other):
  598.         return self.bagof2('(x in ' + `other` + ')')
  599.  
  600.  
  601.     def intersect3(self, other):
  602.         return self.bagof3('(x in ' + `other` + ')')
  603.     
  604.  
  605.     def intersect4(self, other):
  606.         gen = [[]]
  607.         return self.bagof4(gen, member2, (gen, other))
  608.  
  609.     # def member2(x,y): return (x[0] in y)
  610.  
  611.  
  612.     def intersect5(self, other):
  613.         return self.bagof5(member, (other,))
  614.  
  615.     # def member(x,y): return (x in y)
  616.  
  617.  
  618.  
  619.  
  620. ###################################################################
  621. # sorting;
  622. #
  623. # 3 sorts: 
  624. # sort() does a simple list sort, and uses the builtin method;
  625. # sort_keyed() sorts a list of tuples on a given field's value; 
  626. # sort_keyed2() is like sort_keyed(), but it builds a comparison
  627. # function so it can use the built-in sort() method 
  628. #
  629. # notes: 
  630. # 1) sort_keyed() uses a simple insertion sort (others are better)
  631. # 2) sort_keyed2() must construct a function, since it must 
  632. #    select field values before calling cmp() (and .sort only
  633. #    alows for the 2 operands as parameters)
  634. # 3) Python has a built-in '.reverse()' method for lists;  we
  635. #    write our own for illustration only
  636. # 4) sort() must make an explicit copy of self's list: we can't
  637. #    just code 'copy = self.data', or else we'd wind up sorting
  638. #    'self's list too (.sort is in-place, and '=' just binds)
  639. # 5) sort_keyed2() must backquote the field name (so it gets
  640. #    quoted), and calleval() to fetch the created function (see
  641. #    the bagof() stuff for more setails)
  642. ###################################################################
  643.  
  644.  
  645.  
  646.  
  647.     def sort(self):
  648.         copy = self.copy()             
  649.         copy.data.sort()                            # list sort, not set sort
  650.         return copy
  651.  
  652.  
  653.     def sort_keyed(self, field):                    # simple insertion sort
  654.         result = []
  655.         for x in self.data:
  656.             i = 0
  657.             for y in result:
  658.                 if x[field] <= y[field]: break
  659.                 i = i+1
  660.             result[i:i] = [x]                       # or, result.insert(i,x)
  661.         return Set().init(result)
  662.  
  663.  
  664.     def sort_keyed2(self, field):
  665.         func = 'def _cmp(x,y): return cmp(x['+`field`+'], y['+`field`+'])\n'
  666.         exec(func)
  667.         copy = self.copy()
  668.         copy.data.sort(eval('_cmp'))       
  669.         return copy                            # cmp() is builtin: -1,0,+1
  670.  
  671.  
  672.  
  673.  
  674. #########################################################
  675. # permutations(): generate all permutations of the set
  676. # reversed(): reverse a list manually (not in place)
  677. # subsets(): geneate all subsets of length n
  678. # combos(): generate all combinations of length n
  679. #
  680. # notes: 
  681. # 1) these methods use recursive functions outside
  682. # the class;  the outside functions avoid creating
  683. # new Set objects at each level of the recursion;
  684. #
  685. # 2) subsets() treats '[a,b]' as equivalent to 
  686. # '[b,a]' (and only generates 1 instance); combos()
  687. # treats the 2 cases as different (and gens both--
  688. # order matters); combos() is really just a length
  689. # (size) limited permutations();
  690. #########################################################
  691.  
  692.  
  693.  
  694.  
  695.     def permutations(self):
  696.         return Set().init(permute(self.data))
  697.  
  698.  
  699.     def reversed(self):
  700.         return Set().init(reverse(self.data))
  701.  
  702.  
  703.     def subsets(self, n):
  704.         return Set().init(subset(self.data, n))
  705.  
  706.  
  707.     def combos(self, n):
  708.         if n > len(self.data):
  709.             return Set().init()
  710.         else:
  711.             return Set().init(combo(self.data, n))
  712.  
  713.  
  714.  
  715.  
  716. ##################################################################
  717. # overload some operators to work with Set instances;
  718. # Python uses special method names to overload operators,
  719. # instead of special syntax (as in C++);
  720. #
  721. # '+' and '*' works for sets as for normal lists, but '+'
  722. # allows appending any sequence type to the set ('+' is not
  723. # generic for built-in types);
  724. #
  725. # notes: 
  726. # 0) it look like difference() and delete_set() are really
  727. # the same (but delete_set( )is done in-place), so '-' and
  728. # '^' are functionally equivalent (oops..);
  729. #
  730. # 1) '+' (and '-' and '*) isn't quite right: 'x = y + value' 
  731. # will also change y;  to be correct, it should make a copy:
  732. #   def __add_(self, value):
  733. #       copy = self.copy()
  734. #       copy.concat(value)
  735. #       return copy
  736. # --> this has now been corrected <-- 
  737. #
  738. # 2) it's critical that we overload __len__ and __getitem__
  739. # (which correspond to len(), and x[i] indexing): this allows 
  740. #
  741. #   (1) 'in' to generate items in the set in 'for' loops, and 
  742. #   (2) 'in' to test membership in conditional expressions
  743. #
  744. # in 'for' loops, 'in' lets us generically iterate over sets 
  745. # just like any other sequence type (lists, strings, tuples,
  746. # other user-defined sequence classes);  this allows us to 
  747. # use just about any sequence type to init or concat onto a
  748. # set, and allows the right-hand-side of a binary set operation
  749. # to be any sequence type;  for example, we can intersect
  750. # a set and a character string:
  751. #
  752. #       x = Set().init(['abcdefg'])
  753. #       x.intersect('aceg')
  754. #
  755. # most binary operations allow non-Set sequence types on the 
  756. # right side, but the left side must be a Set object (or else
  757. # we can't invoke a Set method);
  758. #
  759. # since 'in' also iterates over and test membership in sets, 
  760. # we don't really need to use 'self.data' in the 'if' and 'for'
  761. # statements in most of the code above: we could just use 'self';  
  762. # but, since we know 'self' is a Set (or else we can't call the 
  763. # methods, we can avoid 1 or more method calls by explicitly using 
  764. # the '.data' field name (we avoid calling the __len__ and 
  765. # __getitem__ methods, and instead use the built-in list
  766. # data type's mechanisms (which are presumably faster));
  767. ##################################################################
  768.  
  769.  
  770.  
  771.  
  772.     def __cmp__(self, other): return self.equiv(other)          # ==, <, >
  773.     def __repr__(self):       return `self.data`                # print set
  774.     def __len__(self):        return len(self.data)             # len()
  775.     
  776.     def __getitem__(self, key):    return self.data[key]        # set[i]
  777.     def __setitem__(self, key, x): self.data[key] = x           # set[i]=x
  778.     def __delitem__(self, key):    del self.data[key]           # del set[i]   
  779.     def __getslice__(self, i, j):  return self.data[i:j]        # set[i:j]
  780.     
  781.     def __add__(self, value): 
  782.         res = self.copy(); res.concat(value); return res        #  set + x
  783.     def __sub__(self, value): 
  784.         res = self.copy(); res.delete_set(value); return res    # set - x
  785.     def __mul__(self, value):                 
  786.         res = self.copy(); res.repeat(value); return res        # set * n
  787.  
  788.     def __or__(self, other):  return self.union(other)          # set | set
  789.     def __and__(self, other): return self.intersect(other)      # set & set
  790.     def __xor__(self, other): return self.difference(other)     # set ^ set
  791.  
  792.     def __neg__(self): return self.reversed()                   # -set
  793.     def __pos__(self): return self.sort()                       # +set
  794.  
  795.  
  796.  
  797.  
  798.  
  799.  
  800. ##################################################
  801. # some utility functions called by the methods
  802. # see descriptions at calling methods;
  803. #
  804. # notes:
  805. # 1) 'member' here is global in the module; it
  806. # does not clash with the 'member' Set method,
  807. # since that function can only be reached via
  808. # qualification (instance.member(), Set.member())
  809. ##################################################
  810.  
  811.  
  812.  
  813.  
  814. set_error = 'Set class error'
  815.  
  816. def negate(n): return -n
  817. def square(n): return n * n
  818.  
  819. def member(x,y):  return (x in y)
  820. def member2(x,y): return (x[0] in y)               # for intersect4()
  821. def in_global_list(x): return x in global_list     # for intersect1()
  822.  
  823.  
  824.  
  825.  
  826. def permute(list):
  827.     if list == []:                                  
  828.         return [[]]
  829.     else:
  830.         result = []
  831.         for i in range(len(list)):
  832.             pick = list[i]
  833.             rest = list[:i] + list[i+1:]
  834.             for x in permute(rest):
  835.                 result.append([pick] + x)
  836.         return result
  837.  
  838.  
  839.  
  840.  
  841. def reverse(list): 
  842.     result = []
  843.     for x in list:
  844.         result = [x] + result
  845.     return result                  # or: copy = list; copy.reverse()
  846.  
  847.  
  848.  
  849.  
  850.  
  851. # [help], 4 -> [help]
  852. # [help], 3 -> [hel], [hep], [hlp], [elp]
  853. # [help], 2 -> [he], [hl], [hp], [el], [ep] [lp]
  854. # [help], 1 -> [h], [e], [l], [p]
  855.  
  856.  
  857.  
  858. def subset(list, size):
  859.     if size == 0 or list == []:
  860.         return [[]]
  861.     else:
  862.         result = []
  863.         for i in range(0, (len(list) - size) + 1):
  864.             pick = list[i]
  865.             rest = list[i+1:]                            # drop [:i]
  866.             for x in subset(rest, size - 1):
  867.                 result.append([pick] + x)
  868.         return result
  869.            
  870.  
  871.  
  872.  
  873. # [help], 4 -> [help], [hepl], [hlep], [hlpe], [hpel], ...
  874. # [help], 3 -> [hel], [hep], [hle], [hlp], [hpe], [hpl], [ehl], ...
  875. # [help], 2 -> [he], [hl], [hp], [eh], [el], [ep], [lh], [le], ...
  876. # [help], 1 -> [h], [e], [l], [p]
  877.  
  878.  
  879.  
  880. def combo(list, size):
  881.     if size == 0 or list == []:                                  
  882.         return [[]]
  883.     else:
  884.         result = []
  885.         for i in range(len(list)):
  886.             pick = list[i]
  887.             rest = list[:i] + list[i+1:]
  888.             for x in combo(rest, size-1):
  889.                 result.append([pick] + x)
  890.         return result
  891.  
  892.  
  893.  
  894.  
  895.  
  896.  
  897.  
  898. ##########################################################
  899. ##########################################################
  900. # RSet() subclass: basic relational algebra operations;
  901. # assumes items in the set are 'tuples', which 
  902. # are implemented as Python dictionaries (name:value)
  903. #
  904. # implemented as a subclass instance of the general
  905. # class Set(), since these operations require a 
  906. # specific set item format;  note that RSet 
  907. # inherits all Set methods, including its operator
  908. # overloadings;
  909. #
  910. # adds the following methods:
  911. #    select: returns a new set = old where field = value
  912. #    find: like select, but allow general comparison tests
  913. #    match: a generalized select (keys in another set)
  914. #    join: implements normal 'natural' join on a field
  915. #    product: a simple cartesian product operation
  916. #    unique: removes duplicate tuples from a copied set
  917. #    project: normal 'projection' operation
  918. #    copy_tuple: copies a tuple from a table
  919. #    input_tuple: enters tuple fields, and adds to the table
  920. #    input_list: like input, but field names in a list
  921. #    add_tuple: pass in a list/tuple/string of values
  922. #
  923. # over-rides these methods:
  924. #    init
  925. #    list
  926. #    to_string
  927. #
  928. # notes:
  929. # 1) list() allows an optional argument giving the
  930. # names of the fields to be displayed first (any other
  931. # fields of a tuple are given in any order after 
  932. # the fields in the list() argument).  Passing in an
  933. # empty list forces the [name]=value format.
  934. #
  935. # 2) find() could be more general: use bagof()
  936. # directly for arbitrary selection expressions.
  937. # 'or' can sometimes be simulated by using optr
  938. # 'in' with a list of values, but full-blown
  939. # boolean selection exprs must use bagof();
  940. # find() needs backquotes around the field name
  941. # so it's quoted in the resulting expr, as well
  942. # as around the value;
  943. #
  944. # 3) join() and product() must eplicitly copy each
  945. # tuple dictionary: 'copy = dict' just makes copy
  946. # _share_ the object that dict references, and any
  947. # changes in copy change dict too
  948. #
  949. # 4) we compare tuples and test for tuple membership
  950. # in a table using dictionary equality; 'in' works for 
  951. # lists of dictionaries in python: it uses dictionary 
  952. # equality, which sorts the fields, and compares them 
  953. # leixcographically (and compares their values); this 
  954. # is slow, but works (the 'is' operator tests whether
  955. # 2 variables reference the _same_ object);
  956. #
  957. # 5) product() simply concatenates the 2 tuples,
  958. # renaming same-named fields, by appending '_N' to
  959. # duplicae field names (N uniquely identifies the
  960. # field in the resulting tuple);  join() atually
  961. # deletes same-named fields (in the right operand);
  962. #
  963. # 6) input_tuple() and add_tuple() get the field 
  964. # list from an existing tuple in the table, so the
  965. # table can't be empty (and all tuples should have 
  966. # the same fields in any given table (relational));
  967. # input_tuple() and input_list() allow any type 
  968. # value to be entered for a field: it calls eval()
  969. # with the input string, to force the python parser 
  970. # to determine its type by syntax-- users should type
  971. # values using normal pyth syntax ('abd', 123, [..])
  972. #
  973. # 7) These methods return a RSet object, not a Set
  974. # object, so their results can have further rel ops
  975. # applied to them.  In general, Set and RSet objects
  976. # can be mixed: the left operaand must be an RSet to
  977. # invoke the methods, but the left ('other') can be
  978. # a RSet, a normal Set, or any built-in or user-def'd
  979. # sequence object (list, tuple, other class).  Since
  980. # Python is dynamically typed, Sets and RSets can
  981. # be passed to generic routines;  However, we provide 
  982. # a conversion from Set's to RSet's with a simple Set 
  983. # method:
  984. #
  985. #    def to_RSet(self): return RSet().init(self.data)
  986. #
  987. # This is needed if you use a simple Set() method
  988. # which returns a Set, and want to perform RSet
  989. # operations on the result.  There is no good reason
  990. # for a RSet -> Set conversion (RSet's _are_ Set's)
  991. ##########################################################
  992. ##########################################################
  993.  
  994.  
  995.  
  996.  
  997.  
  998. class RSet(Set):
  999.  
  1000.  
  1001.     def init(self, *value):
  1002.         if value:
  1003.             return Set.init(self, value[0])
  1004.         else:
  1005.             return Set.init(self)
  1006.  
  1007.  
  1008.  
  1009.     def list(self, *first): 
  1010.         print 
  1011.         print 'table =>'
  1012.         for x in self.data:
  1013.             if not first:
  1014.                 print '   tuple =>', x
  1015.             else:
  1016.                 print '   tuple =>',
  1017.                 for f in first[0]:
  1018.                     print '['+f+']=' + `x[f]`,             # backquotes
  1019.                 for f in x.keys():
  1020.                     if not f in first[0]:
  1021.                         print '['+f+']=' + `x[f]`,
  1022.                 print
  1023.  
  1024.  
  1025.  
  1026.     def to_string(self):
  1027.         raise rset_error, 'cannot convert to a string'
  1028.  
  1029.  
  1030.  
  1031.     def select(self, field, value):
  1032.         result = []
  1033.         for x in self.data:
  1034.             if x[field] == value:
  1035.                 result.append(x)
  1036.         return RSet().init(result)                  # return RSet, not Set
  1037.  
  1038.  
  1039.  
  1040.     def find(self, field, cmp, value):
  1041.         return \
  1042.             self.bagof('x['+ `field` +'] ' + cmp + ' ' + `value`).to_RSet()
  1043.  
  1044.  
  1045.  
  1046.     def match(self, other, field):
  1047.         result = []
  1048.         for x in self.data:
  1049.             for y in other:
  1050.                 if y[field] == x[field]:
  1051.                     result.append(x)
  1052.         return RSet().init(result)
  1053.  
  1054.  
  1055.  
  1056.     def join(self, other, field):
  1057.         result = []
  1058.         for x in self.data:
  1059.             for y in other:
  1060.                 if y[field] == x[field]:
  1061.                     compos = self.copy_tuple(x)
  1062.                     for k in y.keys(): 
  1063.                         if not x.has_key(k): 
  1064.                             compos[k] = y[k]
  1065.                     result.append(compos)
  1066.         return RSet().init(result)
  1067.  
  1068.  
  1069.  
  1070.     def product(self, other):
  1071.         result = []
  1072.         for x in self.data:
  1073.             for y in other:
  1074.                 compos = self.copy_tuple(x)
  1075.                 for k in y.keys(): 
  1076.                     if not x.has_key(k): 
  1077.                         compos[k] = y[k]
  1078.                     else:
  1079.                         i = 1
  1080.                         while x.has_key(k + '_' + `i`): 
  1081.                             i = i+1
  1082.                         compos[k + '_' + `i`] = y[k]
  1083.                 result.append(compos)
  1084.         return RSet().init(result)
  1085.  
  1086.  
  1087.  
  1088.     def unique(self):
  1089.         result = []
  1090.         for x in self.data:
  1091.             if not x in result:
  1092.                 result.append(x)
  1093.         return RSet().init(result)
  1094.  
  1095.  
  1096.  
  1097.     def project(self, fields):
  1098.         result = []
  1099.         for x in self.data:
  1100.             tuple = {}
  1101.             for y in fields:
  1102.                 if x.has_key(y):
  1103.                     tuple[y] = x[y]
  1104.             if tuple and not tuple in result:
  1105.                 result.append(tuple)
  1106.         return RSet().init(result)
  1107.  
  1108.  
  1109.  
  1110.     def copy_tuple(self, tup):
  1111.         res = {}
  1112.         for field in tup.keys():
  1113.             res[field] = tup[field]
  1114.         return res
  1115.  
  1116.  
  1117.  
  1118.     def input_tuple(self):
  1119.         self.input_list(self.data[0].keys())         # use tuple's fields
  1120.  
  1121.  
  1122.  
  1123.     def input_list(self, fields):
  1124.         tup = {}
  1125.         for x in fields:
  1126.             valstr = raw_input(x + ' => ')
  1127.             tup[x] = eval(valstr)                    # any type: parse it
  1128.         self.data.append(tup)
  1129.  
  1130.  
  1131.  
  1132.     def add_tuple(self, values):                     # types already known
  1133.         tup, i = {}, 0
  1134.         if len(values) != len(self.data[0]):
  1135.             raise rset_error, 'add_tuple length'
  1136.         for x in self.data[0].keys():
  1137.             tup[x], i = values[i], i+1
  1138.         self.data.append(tup)
  1139.  
  1140.  
  1141.  
  1142.  
  1143. rset_error = 'relational set error'
  1144.  
  1145.  
  1146.  
  1147.  
  1148.  
  1149.  
  1150.  
  1151. ##############################################################
  1152. ##############################################################
  1153. #
  1154. # the test driver
  1155. #
  1156. # notes:
  1157. # 1) `['a', 'b']` (backquotes) == '[\'a\', \'b\']'; 
  1158. # since find() already backquotes the search value, 
  1159. # we don't always need o do it below;
  1160. #
  1161. # 2) the 'complete', 'available', and 'object' tables
  1162. # are computed with relational operators statically;
  1163. # we could make these into something like 'schemas'
  1164. # if we store them as a string and eval() them to
  1165. # get their values on demand;  RSet has no real 
  1166. # 'schema' (delayed evaluation) facility as is;
  1167. #
  1168. # 3) test_sets() exports 6 tables to the global
  1169. # scope of the module on exit, so they can be used
  1170. # at the interactive propmt.  The user must do 
  1171. # another 'from sets import *' _after_ test_sets()
  1172. # runs, to get these symbols-- 'import *' statements
  1173. # in python get symbols in the module at the time 
  1174. # the 'import' executes (it does not get symbols
  1175. # added to the module's global scope later on).
  1176. # This complexity could be avoided by coding the
  1177. # tables global (assign them outside test_sets()).
  1178. ##############################################################
  1179. ##############################################################
  1180.  
  1181.  
  1182.  
  1183.  
  1184.  
  1185. def test_sets():
  1186.  
  1187.     x = Set().init('abcdefg')
  1188.     item = x.first()
  1189.     while item:                           # generator
  1190.         print item,
  1191.         item = x.next()
  1192.     print
  1193.  
  1194.     for item in x: print item,            # 'in' overload
  1195.     print
  1196.  
  1197.     print ('d' in x ), ('z' in x )        # 'in' overload
  1198.     
  1199.     x = RSet().init([{'name':'x', 'age':0, 'stats':[1,2,3]}])
  1200.     x.list([])
  1201.     x.add_tuple(('y', 1, [4,5,6]))
  1202.     x.add_tuple(('z', 2, [7,8]))
  1203.     x.list([])
  1204.  
  1205.  
  1206.  
  1207.     #############################
  1208.     # a simple employee database
  1209.     #############################
  1210.  
  1211.  
  1212.     a = RSet().init( \
  1213.             [{'name':'mark',  'job':'engineer'},     \
  1214.              {'name':'amrit', 'job':'engineer'},     \
  1215.              {'name':'sunil', 'job':'manager'},      \
  1216.              {'name':'marc',  'job':'prez'},         \
  1217.              {'name':'martin','job':'architect'},    \
  1218.              {'name':'jeff',  'job':'engineer'},     \
  1219.              {'name':'eve',   'job':'administrator'} \
  1220.             ])
  1221.     
  1222.  
  1223.     b = RSet().init( \
  1224.             [{'job':'engineer', 'pay':(25000,60000)},  \
  1225.              {'job':'manager',  'pay':(50000,'XXX')},  \
  1226.              {'job':'architect','pay':None},           \
  1227.              {'job':'prez',     'pay':'see figure 1'}  \
  1228.             ])
  1229.  
  1230.  
  1231.     c = RSet().init( \
  1232.             [{'name':'mark',  'job':'engineer'},     \
  1233.              {'name':'amrit', 'job':'engineer'},     \
  1234.              {'name':'sunil', 'job':'manager'},      \
  1235.              {'name':'john',  'job':'engineer'},     \
  1236.              {'name':'steve', 'job':'manager'}       \
  1237.             ])
  1238.  
  1239.  
  1240.     a.list()
  1241.     a.select('job', 'engineer').list()
  1242.     a.join(b, 'job').list()
  1243.     a.join(b, 'job').list(['name','pay'])
  1244.  
  1245.     a.project(['job']).list()      
  1246.     a.select('job', 'engineer').project(['name']).list()
  1247.  
  1248.     a.find('job', '>', 'engineer').list(['job'])
  1249.     c.find('job', '!=', 'engineer').list(['job'])
  1250.     a.bagof('x[\'name\'][0] == \'m\'').to_RSet().list(['name'])   
  1251.     a.bagof('x[\'job\'] > \'engineer\'').to_RSet().list([])
  1252.     a.bagof('x[\'job\'] > \'engineer\' or x[\'name\'] == \'eve\'').\
  1253.                                                     to_RSet().list([])
  1254.  
  1255.     a.project(['job']).difference(b.project(['job'])).list()
  1256.     a.join(b, 'job').project(['name', 'pay']).list()
  1257.     a.select('name','sunil').join(b,'job').project(['name', 'pay']).list()
  1258.     
  1259.     b.product(c).list([])
  1260.     a.product(c).list([])
  1261.     a.product(c).unique().list([])
  1262.     a.product(c).project(['name']).list([])
  1263.     a.product(c).project(['name', 'name_1']).list([])
  1264.  
  1265.     a.sort_keyed('name').to_RSet().list(['name'])
  1266.     a.sort_keyed2('name').to_RSet().list(['name'])
  1267.     c.sort_keyed('name').to_RSet().list(['name'])
  1268.  
  1269.     a.difference(c).list()
  1270.     a.intersect(c).list()
  1271.     a.union(c).list()
  1272.  
  1273.     print cmp( ((a ^ c) + (a & c)), a) 
  1274.     print cmp( ((a ^ c) | (a & c)), a)
  1275.     print cmp( ((a ^ c) | c), a)
  1276.  
  1277.     print ((a ^ c) + (a & c)).equiv(a) 
  1278.     print ((a ^ c) | c).equiv(a)
  1279.     print a.difference(c).union(a.intersect(c)).equiv(a)
  1280.     
  1281.  
  1282.  
  1283.     #########################
  1284.     # a languages database
  1285.     #########################
  1286.  
  1287.  
  1288.     langs = RSet().init([ \
  1289.         {'name':'prolog',   'type':'logic',   'rank':5, 'use':'aliens'},  \
  1290.         {'name':'alpha',    'type':'proced',  'rank':3, 'use':'glue'},    \
  1291.         {'name':'python',   'type':'proced',  'rank':1, 'use':'rad'},     \
  1292.         {'name':'icon',     'type':'proced',  'rank':1, 'use':'rad'},     \
  1293.         {'name':'scheme',   'type':'funct',   'rank':2, 'use':'aliens'},  \
  1294.         {'name':'smalltalk','type':'object',  'rank':4, 'use':'oop'},     \
  1295.         {'name':'dylan',    'type':'object',  'rank':7, 'use':'glue'},    \
  1296.         {'name':'self',     'type':'object',  'rank':7, 'use':'oop'},     \
  1297.         {'name':'rexx',     'type':'proced',  'rank':7, 'use':'shell'},   \
  1298.         {'name':'tcl',      'type':'proced',  'rank':6, 'use':'shell'},   \
  1299.         {'name':'d',        'type':'unknown', 'rank':7, 'use':'glue'},    \
  1300.         {'name':'lisp',     'type':'funct',   'rank':3, 'use':'aliens'},  \
  1301.         {'name':'perl',     'type':'proced',  'rank':7, 'use':'shell'}    \
  1302.       ])
  1303.  
  1304.  
  1305.     course = RSet().init([ \
  1306.         {'type':'logic',  'class':'ai'},        \
  1307.         {'type':'funct',  'class':'ai'},        \
  1308.         {'type':'proced', 'class':'compilers'}, \
  1309.         {'type':'logic',  'class':'compilers'}, \
  1310.         {'type':'object', 'class':'simulation'} \
  1311.       ])
  1312.  
  1313.  
  1314.     prof = RSet().init([ \
  1315.         {'class': 'ai',       'prof':'travis'}, \
  1316.         {'class':'compilers', 'prof':'horwitz'} \
  1317.       ])
  1318.  
  1319.  
  1320.     dbase     = langs.find('use', 'in', ['glue', 'rad', 'oop'])
  1321.  
  1322.     complete  = langs.find('name', 'not in', \
  1323.                  ['alpha', 'dylan'])                         # no backquotes
  1324.     
  1325.     objects   = langs.find('name', 'in', \
  1326.                  ['python', 'icon', 'smalltalk', 'self', 'dylan'])
  1327.     
  1328.     available = langs.find('name', 'not in', \
  1329.                  ['dylan', 'self', 'd', 'rexx'])
  1330.  
  1331.  
  1332.     dbase.list(['name'])
  1333.     langs.join(course,'type').project(['name','class']).list([])
  1334.     langs.join(course,'type').join(prof,'class').project(['name','prof']).list()    
  1335.     
  1336.     langs.select('use','aliens').join(course,'type').project(['class']).list()
  1337.     
  1338.     for x in ['<', '==', '>']:
  1339.         set = langs.find('rank', x, 3)
  1340.         set.project(['name', 'rank']).sort_keyed('rank').to_RSet().list([])
  1341.  
  1342.     worst = langs.find('rank', '>=', 5)
  1343.     worst.sort_keyed('rank').to_RSet().list(['name', 'rank'])
  1344.  
  1345.     langs.select('name', 'rad').list([]) 
  1346.     langs.select('use',  'rad').list([])
  1347.     available.list([])
  1348.     objects.list([])
  1349.  
  1350.     x = langs.find('use', 'in', ['rad', 'glue'])
  1351.     (x & complete & objects & available).to_RSet().project(['name']).list([])
  1352.     
  1353.     
  1354.  
  1355.     #######################
  1356.     # miscellaneous tests
  1357.     #######################
  1358.  
  1359.  
  1360.     print
  1361.     x = Set().init('abcdefg')
  1362.     print x.intersect('aczeg')
  1363.     y = Set().init('aceg')
  1364.     print x.intersect(y)
  1365.  
  1366.     z1 = Set().init('gcae')
  1367.     z2 = z1 + 'x'
  1368.     print x.subsume(y), x.subsume(z1), x.subsume(z2)
  1369.     print y.equiv(z1),  y.equiv(z2)
  1370.  
  1371.     x = Set().init(['h', 'e', 'l', 'p'])
  1372.     x.permutations().list()
  1373.  
  1374.     for i in range(0, len(x) + 2):                 # 0..5
  1375.         x.subsets(i).display()
  1376.     for i in range(0, len(x) + 2):
  1377.         x.combos(i).display()
  1378.  
  1379.     x = Set().init()
  1380.     x.set([1,2,3])
  1381.     x.permutations().display()
  1382.  
  1383.     x = Set().init()
  1384.     x.concat('alp')
  1385.     print permute(x.get())
  1386.  
  1387.     x.concat('po')
  1388.     x.display()
  1389.     x.reversed().display()
  1390.     x.sort().display()
  1391.     print x
  1392.     print x.to_string()
  1393.  
  1394.     print
  1395.     x = Set().init([1,2,3,4,5,6])
  1396.     y = Set().init([0,2,4,9,6,8,2])
  1397.     print x.intersect1(y)
  1398.     print x.intersect2(y)
  1399.     print x.intersect3(y)          # test bagof generators
  1400.     print x.intersect4(y)
  1401.     print x.intersect5(y)
  1402.  
  1403.     print x.bagof('x in '+`y`)         # dont need y.get()
  1404.     print x.bagof(member, (y,))        # dont need y.get()
  1405.  
  1406.  
  1407.  
  1408.     ###########################
  1409.     # test operator overloads
  1410.     ###########################
  1411.  
  1412.  
  1413.     print
  1414.     x = Set().init('abcd')
  1415.     y = Set().init('db')
  1416.     print len(x), x + 'efg', x - y, x * 3     # 'x - [..]' uses coerce()
  1417.     
  1418.     print x[0], x[0:2]
  1419.     x[1] = 'z'
  1420.     del x[0]
  1421.     print x
  1422.  
  1423.     print (x == 'abcde'), (x == x)
  1424.     print x.equiv(Set().init('abcde')), x.equiv(x)
  1425.     
  1426.     x.set('abcde')
  1427.     y = Set().init('azce')
  1428.     z = Set().init('axedy')
  1429.     print x | z
  1430.     print x & y
  1431.     print x ^ z
  1432.     print -x + z
  1433.     print x & y & z
  1434.     print x | y | z
  1435.     print x ^ y ^ z     
  1436.     print x + y + z
  1437.     print x - y - z
  1438.     print (x | y - z).display()
  1439.  
  1440.  
  1441.  
  1442.     ######################################
  1443.     # export tables for interactive tests
  1444.     ######################################
  1445.  
  1446.  
  1447.     global table1, table2, table2
  1448.     table1, table2, table3 = a, b, c
  1449.  
  1450.     global langs1, course1, prof1
  1451.     langs1, course1, prof1 = langs, course, prof 
  1452.  
  1453.  
  1454.  
  1455.  
  1456.  
  1457. #  
  1458. # sets.test_sets()
  1459. #  
  1460.