home *** CD-ROM | disk | FTP | other *** search
/ ActiveX Programming Unleashed CD / AXU.iso / jgl_1_1 / jgl_1_1.exe / src / SetOperations.java < prev    next >
Encoding:
Java Source  |  1996-09-10  |  21.9 KB  |  409 lines
  1. // Copyright(c) 1996 ObjectSpace, Inc.
  2. // Portions Copyright(c) 1995, 1996 Hewlett-Packard Company.
  3.  
  4. package jgl;
  5.  
  6. /**
  7.  * The SetOperations class contains generic set operation algorithms.
  8.  * <p>
  9.  * @see jgl.examples.SetOperationsExamples
  10.  * @version 1.1
  11.  * @author ObjectSpace, Inc.
  12.  */
  13.  
  14. public final class SetOperations
  15.   {
  16.   /**
  17.    * Return true if every element in the first sequence is also in the second.
  18.    * It assumed that both sequences were sorted prior to this operation according
  19.    * to their hash code. The time complexity is linear and the space complexity 
  20.    * is constant.
  21.    * @param first1 An iterator positioned at the first element of the first sequence.
  22.    * @param last1 An iterator positioned immediately after the last element of the first sequence.
  23.    * @param first2 An iterator positioned at the first element of the second sequence.
  24.    * @param last2 An iterator positioned immediately after the last element of the second sequence.
  25.    * @return True if every element in the first sequence is also in the second.
  26.    */
  27.   public static boolean includes( InputIterator first1, InputIterator last1, InputIterator first2, InputIterator last2 )
  28.     {
  29.     return includes( first1, last1, first2, last2, new HashComparator() ); 
  30.     }
  31.  
  32.   /**
  33.    * Return true if every element in the second sequence is also in the first.
  34.    * It assumed that both sequences were sorted prior to this operation according
  35.    * to the specified comparator. The time complexity is linear and the space complexity 
  36.    * is constant.
  37.    * @param first1 An iterator positioned at the first element of the first sequence.
  38.    * @param last1 An iterator positioned immediately after the last element of the first sequence.
  39.    * @param first2 An iterator positioned at the first element of the second sequence.
  40.    * @param last2 An iterator positioned immediately after the last element of the second sequence.
  41.    * @param comparator A BinaryPredicate that returns true if its first operand is "less" than its second operand.
  42.    * @return True if every element in the second sequence is also in the first.
  43.    */
  44.   public static boolean includes( InputIterator first1, InputIterator last1, InputIterator first2, InputIterator last2, BinaryPredicate comparator )
  45.     {
  46.     InputIterator first1x = (InputIterator) first1.clone();
  47.     InputIterator first2x = (InputIterator) first2.clone();
  48.  
  49.     while( !first1x.equals( last1 ) && !first2x.equals( last2 ) )
  50.       if( comparator.execute( first2x.get(), first1x.get() ) )
  51.         {
  52.         return false;
  53.         }
  54.       else if( comparator.execute( first1x.get(), first2x.get() ) )
  55.         {
  56.         first1x.advance();
  57.         }
  58.       else
  59.         {
  60.         first1x.advance();
  61.         first2x.advance();
  62.         }
  63.  
  64.     return first2x.equals( last2 );
  65.   }
  66.  
  67.   /**
  68.    * Return true if every element in the second container is also in the first.
  69.    * It assumed that both containers were sorted prior to this operation according
  70.    * to the specified comparator. The time complexity is linear and the space complexity 
  71.    * is constant.
  72.    * @param container1 The first container.
  73.    * @param container2 The second container.
  74.    * @param comparator A BinaryPredicate that returns true if its first operand is "less" than its second operand.
  75.    * @return True if every element in the second container is also in the first.
  76.    */
  77.   public static boolean includes( Container container1, Container container2, BinaryPredicate comparator )
  78.     {
  79.     return includes( container1.start(), container1.finish(), container2.start(), container2.finish(), comparator );
  80.     }
  81.  
  82.   /**
  83.    * Place the sorted union of two sequences into another sequence. 
  84.    * It assumed that both sequences were sorted prior to this operation according
  85.    * to their hash code. The result is undefined if the two input sequences overlap. 
  86.    * If an element occurs in both sequences, the element from the first sequence is
  87.    * copied into the result sequence. The time complexity is linear and the space 
  88.    * complexity is constant.
  89.    * @param first1 An iterator positioned at the first element of the first input sequence.
  90.    * @param last1 An iterator positioned immediately after the last element of the first input sequence.
  91.    * @param first2 An iterator positioned at the first element of the second input sequence.
  92.    * @param last2 An iterator positioned immediately after the last element of the second input sequence.
  93.    * @param result An iterator positioned at the first element of the output sequence.
  94.    * @return An iterator positioned immediately after the last element of the output sequence.
  95.    */
  96.   public static OutputIterator setUnion( InputIterator first1, InputIterator last1, InputIterator first2, InputIterator last2, OutputIterator result )
  97.     {
  98.     return setUnion( first1, last1, first2, last2, result, new HashComparator() );
  99.     }
  100.  
  101.   /**
  102.    * Place the sorted union of two sequences into another sequence. 
  103.    * It assumed that both sequences were sorted prior to this operation according
  104.    * to the specified comparator. The result is undefined if the two input sequences 
  105.    * overlap. If an element occurs in both sequences, the element from the first sequence 
  106.    * is copied into the result sequence. The time complexity is linear and the space 
  107.    * complexity is constant.
  108.    * @param first1 An iterator positioned at the first element of the first input sequence.
  109.    * @param last1 An iterator positioned immediately after the last element of the first input sequence.
  110.    * @param first2 An iterator positioned at the first element of the second input sequence.
  111.    * @param last2 An iterator positioned immediately after the last element of the second input sequence.
  112.    * @param result An iterator positioned at the first element of the output sequence.
  113.    * @param comparator A BinaryPredicate that returns true if its first operand is "less" than its second operand.
  114.    * @return An iterator positioned immediately after the last element of the output sequence.
  115.    */
  116.   public static OutputIterator setUnion( InputIterator first1, InputIterator last1, InputIterator first2, InputIterator last2, OutputIterator result, BinaryPredicate comparator )
  117.     {
  118.     InputIterator first1x = (InputIterator) first1.clone();
  119.     InputIterator first2x = (InputIterator) first2.clone();
  120.     OutputIterator resultx = (OutputIterator) result.clone();
  121.  
  122.     while( !first1x.equals( last1 ) && !first2x.equals( last2 ) )
  123.       if( comparator.execute( first1x.get(), first2x.get() ) )
  124.         {
  125.         resultx.put( first1x.get() );
  126.         resultx.advance();
  127.         first1x.advance();
  128.         }
  129.       else if( comparator.execute( first2x.get(), first1x.get() ) )
  130.         {
  131.         resultx.put( first2x.get() );
  132.         resultx.advance();
  133.         first2x.advance();
  134.         }
  135.       else
  136.         {
  137.         resultx.put( first1x.get() );
  138.         resultx.advance();
  139.         first1x.advance();
  140.         first2x.advance();
  141.         }
  142.  
  143.       return Copying.copy( first2x, last2, Copying.copy( first1x, last1, resultx ) );
  144.     }
  145.  
  146.   /**
  147.    * Place the sorted union of two containers into a sequence. 
  148.    * It assumed that both containers were sorted prior to this operation according
  149.    * to the specified comparator. If an element occurs in both containers, the element 
  150.    * from the first container is copied into the result sequence. The time complexity is 
  151.    * linear and the space complexity is constant.
  152.    * @param container1 The first container.
  153.    * @param container2 The second container.
  154.    * @param result An iterator positioned at the first element of the output sequence.
  155.    * @param comparator A BinaryPredicate that returns true if its first operand is "less" than its second operand.
  156.    * @return An iterator positioned immediately after the last element of the output sequence.
  157.    */
  158.   public static OutputIterator setUnion( Container container1, Container container2, OutputIterator result, BinaryPredicate comparator )
  159.     {
  160.     return setUnion( container1.start(), container1.finish(), container2.start(), container2.finish(), result, comparator );
  161.     }
  162.  
  163.   /**
  164.    * Place the sorted intersection of two sequences into another sequence. 
  165.    * It assumed that both sequences were sorted prior to this operation according
  166.    * to their hash code. The result is undefined if the two input sequences overlap. 
  167.    * If an element occurs in both sequences, the element from the first sequence is
  168.    * copied into the result sequence. The time complexity is linear and the space 
  169.    * complexity is constant.
  170.    * @param first1 An iterator positioned at the first element of the first input sequence.
  171.    * @param last1 An iterator positioned immediately after the last element of the first input sequence.
  172.    * @param first2 An iterator positioned at the first element of the second input sequence.
  173.    * @param last2 An iterator positioned immediately after the last element of the second input sequence.
  174.    * @param result An iterator positioned at the first element of the output sequence.
  175.    * @return An iterator positioned immediately after the last element of the output sequence.
  176.    */
  177.   public static OutputIterator setIntersection( InputIterator first1, InputIterator last1, InputIterator first2, InputIterator last2, OutputIterator result )
  178.     {
  179.     return setIntersection( first1, last1, first2, last2, result, new HashComparator() );
  180.     }
  181.  
  182.   /**
  183.    * Place the sorted intersection of two sequences into another sequence. 
  184.    * It assumed that both sequences were sorted prior to this operation according
  185.    * to the specified comparator. The result is undefined if the two input sequences 
  186.    * overlap. If an element occurs in both sequences, the element from the first sequence 
  187.    * is copied into the result sequence. The time complexity is linear and the space 
  188.    * complexity is constant.
  189.    * @param first1 An iterator positioned at the first element of the first input sequence.
  190.    * @param last1 An iterator positioned immediately after the last element of the first input sequence.
  191.    * @param first2 An iterator positioned at the first element of the second input sequence.
  192.    * @param last2 An iterator positioned immediately after the last element of the second input sequence.
  193.    * @param result An iterator positioned at the first element of the output sequence.
  194.    * @param comparator A BinaryPredicate that returns true if its first operand is "less" than its second operand.
  195.    * @return An iterator positioned immediately after the last element of the output sequence.
  196.    */
  197.   public static OutputIterator setIntersection( InputIterator first1, InputIterator last1, InputIterator first2, InputIterator last2, OutputIterator result, BinaryPredicate comparator )
  198.     {
  199.     InputIterator first1x = (InputIterator) first1.clone();
  200.     InputIterator first2x = (InputIterator) first2.clone();
  201.     OutputIterator resultx = (OutputIterator) result.clone();
  202.  
  203.     while( !first1x.equals( last1 ) && !first2x.equals( last2 ) )
  204.       if( comparator.execute( first1x.get(), first2x.get() ) )
  205.         {
  206.         first1x.advance();
  207.         }
  208.       else if( comparator.execute( first2x.get(), first1x.get() ) )
  209.         {
  210.         first2x.advance();
  211.         }
  212.       else
  213.         {
  214.         resultx.put( first1x.get() );
  215.         resultx.advance();
  216.         first1x.advance();
  217.         first2x.advance();
  218.         }
  219.  
  220.       return resultx;
  221.     }
  222.  
  223.   /**
  224.    * Place the sorted intersection of two containers into a sequence. 
  225.    * It assumed that both containers were sorted prior to this operation according
  226.    * to the specified comparator. If an element occurs in both containers, the element 
  227.    * from the first container is copied into the result sequence. The time complexity is 
  228.    * linear and the space complexity is constant.
  229.    * @param container1 The first container.
  230.    * @param container2 The second container.
  231.    * @param result An iterator positioned at the first element of the output sequence.
  232.    * @param comparator A BinaryPredicate that returns true if its first operand is "less" than its second operand.
  233.    * @return An iterator positioned immediately after the last element of the output sequence.
  234.    */
  235.   public static OutputIterator setIntersection( Container container1, Container container2, OutputIterator result, BinaryPredicate comparator )
  236.     {
  237.     return setIntersection( container1.start(), container1.finish(), container2.start(), container2.finish(), result, comparator );
  238.     }
  239.  
  240.   /**
  241.    * Place the sorted difference of two sequences into another sequence. 
  242.    * The output sequence will contain all elements that are in the first sequence 
  243.    * but not in the second sequence.
  244.    * It assumed that both sequences were sorted prior to this operation according
  245.    * to their hash code. The result is undefined if the two input sequences overlap. 
  246.    * If an element occurs in both sequences, the element from the first sequence is
  247.    * copied into the result sequence. The time complexity is linear and the space 
  248.    * complexity is constant.
  249.    * @param first1 An iterator positioned at the first element of the first input sequence.
  250.    * @param last1 An iterator positioned immediately after the last element of the first input sequence.
  251.    * @param first2 An iterator positioned at the first element of the second input sequence.
  252.    * @param last2 An iterator positioned immediately after the last element of the second input sequence.
  253.    * @param result An iterator positioned at the first element of the output sequence.
  254.    * @return An iterator positioned immediately after the last element of the output sequence.
  255.    */
  256.   public static OutputIterator setDifference( InputIterator first1, InputIterator last1, InputIterator first2, InputIterator last2, OutputIterator result )
  257.     {
  258.     return setDifference( first1, last1, first2, last2, result, new HashComparator() );
  259.     }
  260.  
  261.   /**
  262.    * Place the sorted difference of two sequences into another sequence. 
  263.    * The output sequence will contain all elements that are in the first sequence 
  264.    * but not in the second sequence.
  265.    * It assumed that both sequences were sorted prior to this operation according
  266.    * to the specified comparator. The result is undefined if the two input sequences 
  267.    * overlap. If an element occurs in both sequences, the element from the first sequence 
  268.    * is copied into the result sequence. The time complexity is linear and the space 
  269.    * complexity is constant.
  270.    * @param first1 An iterator positioned at the first element of the first input sequence.
  271.    * @param last1 An iterator positioned immediately after the last element of the first input sequence.
  272.    * @param first2 An iterator positioned at the first element of the second input sequence.
  273.    * @param last2 An iterator positioned immediately after the last element of the second input sequence.
  274.    * @param result An iterator positioned at the first element of the output sequence.
  275.    * @param comparator A BinaryPredicate that returns true if its first operand is "less" than its second operand.
  276.    * @return An iterator positioned immediately after the last element of the output sequence.
  277.    */
  278.   public static OutputIterator setDifference( InputIterator first1, InputIterator last1, InputIterator first2, InputIterator last2, OutputIterator result, BinaryPredicate comparator )
  279.     {
  280.     InputIterator first1x = (InputIterator) first1.clone();
  281.     InputIterator first2x = (InputIterator) first2.clone();
  282.     OutputIterator resultx = (OutputIterator) result.clone();
  283.  
  284.     while( !first1x.equals( last1 ) && !first2x.equals( last2 ) )
  285.       if( comparator.execute( first1x.get(), first2x.get() ) )
  286.         {
  287.         resultx.put( first1x.get() );
  288.         resultx.advance();
  289.         first1x.advance();
  290.         }
  291.       else if( comparator.execute( first2x.get(), first1x.get() ) )
  292.         {
  293.         first2x.advance();
  294.         }
  295.       else
  296.         {
  297.         first1x.advance();
  298.         first2x.advance();
  299.         }
  300.  
  301.       return Copying.copy( first1x, last1, resultx );
  302.     }
  303.  
  304.   /**
  305.    * Place the sorted difference of two containers into a sequence. 
  306.    * The output sequence will contain all elements that are in the first container
  307.    * but not in the second container.
  308.    * It assumed that both containers were sorted prior to this operation according
  309.    * to the specified comparator. If an element occurs in both containers, the element 
  310.    * from the first container is copied into the result sequence. The time complexity is 
  311.    * linear and the space complexity is constant.
  312.    * @param container1 The first container.
  313.    * @param container2 The second container.
  314.    * @param result An iterator positioned at the first element of the output sequence.
  315.    * @param comparator A BinaryPredicate that returns true if its first operand is "less" than its second operand.
  316.    * @return An iterator positioned immediately after the last element of the output sequence.
  317.    */
  318.   public static OutputIterator setDifference( Container container1, Container container2, OutputIterator result, BinaryPredicate comparator )
  319.     {
  320.     return setDifference( container1.start(), container1.finish(), container2.start(), container2.finish(), result, comparator );
  321.     }
  322.  
  323.   /**
  324.    * Place the sorted symmetric difference of two sequences into another sequence. 
  325.    * The output sequence will contain all elements that are in one sequence 
  326.    * but not in the other.
  327.    * It assumed that both sequences were sorted prior to this operation according
  328.    * to their hash code. The result is undefined if the two input sequences overlap. 
  329.    * If an element occurs in both sequences, the element from the first sequence is
  330.    * copied into the result sequence. The time complexity is linear and the space 
  331.    * complexity is constant.
  332.    * @param first1 An iterator positioned at the first element of the first input sequence.
  333.    * @param last1 An iterator positioned immediately after the last element of the first input sequence.
  334.    * @param first2 An iterator positioned at the first element of the second input sequence.
  335.    * @param last2 An iterator positioned immediately after the last element of the second input sequence.
  336.    * @param result An iterator positioned at the first element of the output sequence.
  337.    * @return An iterator positioned immediately after the last element of the output sequence.
  338.    */
  339.   public static OutputIterator setSymmetricDifference( InputIterator first1, InputIterator last1, InputIterator first2, InputIterator last2, OutputIterator result )
  340.     {
  341.     return setSymmetricDifference( first1, last1, first2, last2, result, new HashComparator() );
  342.     }
  343.  
  344.   /**
  345.    * Place the sorted symmetric difference of two sequences into another sequence. 
  346.    * The output sequence will contain all elements that are in one sequence 
  347.    * but not in the other.
  348.    * It assumed that both sequences were sorted prior to this operation according
  349.    * to the specified comparator. The result is undefined if the two input sequences 
  350.    * overlap. If an element occurs in both sequences, the element from the first sequence 
  351.    * is copied into the result sequence. The time complexity is linear and the space 
  352.    * complexity is constant.
  353.    * @param first1 An iterator positioned at the first element of the first input sequence.
  354.    * @param last1 An iterator positioned immediately after the last element of the first input sequence.
  355.    * @param first2 An iterator positioned at the first element of the second input sequence.
  356.    * @param last2 An iterator positioned immediately after the last element of the second input sequence.
  357.    * @param result An iterator positioned at the first element of the output sequence.
  358.    * @param comparator A BinaryPredicate that returns true if its first operand is "less" than its second operand.
  359.    * @return An iterator positioned immediately after the last element of the output sequence.
  360.    */
  361.   public static OutputIterator setSymmetricDifference( InputIterator first1, InputIterator last1, InputIterator first2, InputIterator last2, OutputIterator result, BinaryPredicate comparator )
  362.     {
  363.     InputIterator first1x = (InputIterator) first1.clone();
  364.     InputIterator first2x = (InputIterator) first2.clone();
  365.     OutputIterator resultx = (OutputIterator) result.clone();
  366.  
  367.     while( !first1x.equals( last1 ) && !first2x.equals( last2 ) )
  368.       if( comparator.execute( first1x.get(), first2x.get() ) )
  369.         {
  370.         resultx.put( first1x.get() );
  371.         resultx.advance();
  372.         first1x.advance();
  373.         }
  374.       else if( comparator.execute( first2x.get(), first1x.get() ) )
  375.         {
  376.         resultx.put( first2x.get() );
  377.         resultx.advance();
  378.         first2x.advance();
  379.         }
  380.       else
  381.         {
  382.         first1x.advance();
  383.         first2x.advance();
  384.         }
  385.  
  386.       return Copying.copy( first2x, last2, Copying.copy( first1x, last1, resultx ) );
  387.     }
  388.  
  389.   /**
  390.    * Place the sorted symmetric difference of two containers into a sequence. 
  391.    * The output sequence will contain all elements that are in one container
  392.    * but not in the other.
  393.    * It assumed that both containers were sorted prior to this operation according
  394.    * to the specified comparator. If an element occurs in both containers, the element 
  395.    * from the first container is copied into the result sequence. The time complexity is 
  396.    * linear and the space complexity is constant.
  397.    * @param container1 The first container.
  398.    * @param container2 The second container.
  399.    * @param result An iterator positioned at the first element of the output sequence.
  400.    * @param comparator A BinaryPredicate that returns true if its first operand is "less" than its second operand.
  401.    * @return An iterator positioned immediately after the last element of the output sequence.
  402.    */
  403.   public static OutputIterator setSymmetricDifference( Container container1, Container container2, OutputIterator result, BinaryPredicate comparator )
  404.     {
  405.     return setSymmetricDifference( container1.start(), container1.finish(), container2.start(), container2.finish(), result, comparator );
  406.     }
  407.   }
  408.  
  409.