home *** CD-ROM | disk | FTP | other *** search
/ ActiveX Programming Unleashed CD / AXU.iso / jgl_1_1 / src / permuting.java < prev    next >
Encoding:
Java Source  |  1996-09-10  |  5.2 KB  |  151 lines
  1. // Copyright(c) 1996 ObjectSpace, Inc.
  2. // Portions Copyright(c) 1995, 1996 Hewlett-Packard Company.
  3.  
  4. package jgl;
  5.  
  6. /**
  7.  * The Permuting class contains generic permuting algorithms.
  8.  * <p>
  9.  * @see jgl.examples.PermutingExamples
  10.  * @version 1.1
  11.  * @author ObjectSpace, Inc.
  12.  */
  13.  
  14. public final class Permuting
  15.   {
  16.   private Permuting()
  17.     {
  18.     }
  19.  
  20.   /**
  21.    * Arrange a sequence to become its next permutation. If it was already the last 
  22.    * permutation, become the first permutation. Logically, the entire set of permutations 
  23.    * is lexicographically ordered using a comparator.
  24.    * @param first An iterator positioned at the first element of the sequence.
  25.    * @param last An iterator positioned immediately after the last element of the sequence.
  26.    * @param comparator A binary predicate that returns true if its first operand is "less" than its second operand.
  27.    * @return true unless the sequence was already the last permutation.
  28.    */
  29.   public static boolean nextPermutation( BidirectionalIterator first, BidirectionalIterator last, BinaryPredicate comparator )
  30.     {
  31.     if ( !(first.getContainer() instanceof Sequence) )
  32.       throw new IllegalArgumentException( "iterator containers must be a Sequence" );
  33.  
  34.     if( first.equals( last ) )
  35.       return false;
  36.  
  37.     BidirectionalIterator i = (BidirectionalIterator) first.clone();
  38.     i.advance();
  39.  
  40.     if( i.equals( last ) )
  41.       return false;
  42.  
  43.     i = (BidirectionalIterator) last.clone();
  44.     i.retreat();
  45.  
  46.     while( true )
  47.       {
  48.       BidirectionalIterator ii = (BidirectionalIterator) i.clone();
  49.       i.retreat();
  50.  
  51.       if( comparator.execute( i.get(), ii.get() ) )
  52.         {
  53.         BidirectionalIterator j = (BidirectionalIterator) last.clone();
  54.         j.retreat();
  55.  
  56.         while( !comparator.execute( i.get(), j.get() ) )
  57.           j.retreat();
  58.  
  59.         Swapping.iterSwap( i, j );
  60.         Reversing.reverse( ii, last );
  61.         return true;
  62.         }
  63.  
  64.       if( i.equals( first ) )
  65.         {
  66.         Reversing.reverse( first, last );
  67.         return false;
  68.         }
  69.       }
  70.     }
  71.  
  72.   /**
  73.    * Arrange a container to become its next permutation. If the container is already the 
  74.    * last permutation, become the first permutation. Logically, the entire set of 
  75.    * permutations is lexicographically ordered using a comparator.
  76.    * @param container The container.
  77.    * @param comparator A binary predicate that returns true if its first operand is "less" than its second operand.
  78.    * @return true unless the container was already the last permutation.
  79.    */
  80.   public static boolean nextPermutation( Container container, BinaryPredicate comparator )
  81.     {
  82.     return nextPermutation( (BidirectionalIterator) container.start(), (BidirectionalIterator) container.finish(), comparator );
  83.     }
  84.  
  85.   /**
  86.    * Arrange a sequence to become its previous permutation. If it was already the first 
  87.    * permutation, become the last permutation. Logically, the entire set of permutations 
  88.    * is lexicographically ordered using a comparator.
  89.    * @param first An iterator positioned at the first element of the sequence.
  90.    * @param last An iterator positioned immediately after the last element of the sequence.
  91.    * @param comparator A binary predicate that returns true if its first operand is "less" than its second operand.
  92.    * @return true unless the sequence was already the first permutation.
  93.    */
  94.   public static boolean prevPermutation( BidirectionalIterator first, BidirectionalIterator last, BinaryPredicate comparator )
  95.     {
  96.     if ( !(first.getContainer() instanceof Sequence) )
  97.       throw new IllegalArgumentException( "iterator containers must be a Sequence" );
  98.  
  99.     if( first.equals( last ) )
  100.       return false;
  101.  
  102.     BidirectionalIterator i = (BidirectionalIterator) first.clone();
  103.     i.advance();
  104.  
  105.     if( i.equals( last ) )
  106.       return false;
  107.  
  108.     i = (BidirectionalIterator) last.clone();
  109.     i.retreat();
  110.  
  111.     while( true )
  112.       {
  113.       BidirectionalIterator ii = (BidirectionalIterator) i.clone();
  114.       i.retreat();
  115.  
  116.       if( comparator.execute( ii.get(), i.get() ) )
  117.         {
  118.         BidirectionalIterator j = (BidirectionalIterator) last.clone();
  119.         j.retreat();
  120.  
  121.         while( !comparator.execute( j.get(), i.get() ) ) 
  122.           j.retreat();
  123.  
  124.         Swapping.iterSwap( i, j );
  125.         Reversing.reverse( ii, last );
  126.         return true;
  127.         }
  128.  
  129.       if( i.equals( first ) )
  130.         {
  131.         Reversing.reverse( first, last );
  132.         return false;
  133.         }
  134.       }
  135.     }
  136.  
  137.   /**
  138.    * Arrange a container to become its previous permutation. If it was already the first 
  139.    * permutation, become the last permutation. Logically, the entire set of permutations 
  140.    * is lexicographically ordered using a comparator.
  141.    * @param container The container.
  142.    * @param comparator A binary predicate that returns true if its first operand is "less" than its second operand.
  143.    * @return true unless the container was already the first permutation.
  144.    */
  145.   public static boolean prevPermutation( Container container, BinaryPredicate comparator )
  146.     {
  147.     return prevPermutation( (BidirectionalIterator) container.start(), (BidirectionalIterator) container.finish(), comparator );
  148.     }
  149.   }
  150.  
  151.