home *** CD-ROM | disk | FTP | other *** search
/ ActiveX Programming Unleashed CD / AXU.iso / jgl_1_1 / src / finding.java < prev    next >
Encoding:
Java Source  |  1996-09-11  |  10.8 KB  |  271 lines
  1. // Copyright(c) 1996 ObjectSpace, Inc.
  2. // Portions Copyright(c) 1995, 1996 Hewlett-Packard Company.
  3.  
  4. package jgl;
  5.  
  6. /**
  7.  * The Finding class contains generic Finding algorithms.
  8.  * <p>
  9.  * @see jgl.examples.FindingExamples
  10.  * @version 1.1
  11.  * @author ObjectSpace, Inc.
  12.  */
  13.  
  14. public final class Finding
  15.   {
  16.   private Finding()
  17.     {
  18.     }
  19.  
  20.   /**
  21.    * Find the first element in a sequence that matches a particular object using equals().
  22.    * The time complexity is linear and the space complexity is constant.
  23.    * @param first An iterator positioned at the first element of the sequence.
  24.    * @param last An iterator positioned immediately after the last element of the sequence.
  25.    * @param object The object to find.
  26.    * @return An iterator positioned at the first element that matches. If no match is 
  27.    * found, return an iterator positioned immediately after the last element of 
  28.    * the sequence. 
  29.    */
  30.   public static InputIterator find( InputIterator first, InputIterator last, Object object )
  31.     {
  32.     InputIterator firstx = (InputIterator) first.clone();
  33.  
  34.     while( !firstx.equals( last ) && !( firstx.get().equals( object ) ) )
  35.       firstx.advance();
  36.  
  37.     return firstx;
  38.     }
  39.  
  40.   /**
  41.    * Find the first element in a container that matches a particular object using equals().
  42.    * The time complexity is linear and the space complexity is constant.
  43.    * @param container The container.
  44.    * @param object The object to find.
  45.    * @return An iterator positioned at the first element that matches. If no match is 
  46.    * found, return an iterator positioned immediately after the last element of 
  47.    * the container. 
  48.    */
  49.   public static InputIterator find( Container container, Object object )
  50.     {
  51.     return find( container.start(), container.finish(), object );
  52.     }
  53.  
  54.   /**
  55.    * Find the first element in a sequence that satisfies a predicate.
  56.    * The time complexity is linear and the space complexity is constant.
  57.    * @param first An iterator positioned at the first element of the sequence.
  58.    * @param last An iterator positioned immediately after the last element of the sequence.
  59.    * @param predicate A unary predicate.
  60.    * @return An iterator positioned at the first element that matches. If no match is 
  61.    * found, return an iterator positioned immediately after the last element of 
  62.    * the sequence. 
  63.    */
  64.   public static InputIterator findIf( InputIterator first, InputIterator last, UnaryPredicate predicate )
  65.     {
  66.     InputIterator firstx = (InputIterator) first.clone();
  67.  
  68.     while( !firstx.equals( last ) && !predicate.execute( firstx.get() ) )
  69.       firstx.advance();
  70.  
  71.     return firstx;
  72.     }
  73.  
  74.   /**
  75.    * Find the first element in a container that satisfies a predicate.
  76.    * The time complexity is linear and the space complexity is constant.
  77.    * @param container The container.
  78.    * @param predicate A unary predicate.
  79.    * @return An iterator positioned at the first element that matches. If no match is 
  80.    * found, return an iterator positioned immediately after the last element of 
  81.    * the sequence. 
  82.    */
  83.   public static InputIterator findIf( Container container, UnaryPredicate predicate )
  84.     {
  85.     return findIf( container.start(), container.finish(), predicate );
  86.     }
  87.  
  88.   /**
  89.    * Find the first consecutive sequence of elements that match using equals().
  90.    * The time complexity is linear and the space complexity is constant.
  91.    * @param first An iterator positioned at the first element of the sequence.
  92.    * @param last An iterator positioned immediately after the last element of the sequence.
  93.    * @return An iterator positioned at the first element in the consecutive sequence. If
  94.    * no consecutive sequence is found, return an iterator positioned immediately after 
  95.    * the last element of the input sequence.
  96.    */
  97.   public static InputIterator adjacentFind( InputIterator first, InputIterator last )
  98.     {
  99.     return adjacentFind( first, last, new EqualTo() );
  100.     }
  101.  
  102.   /**
  103.    * Find the first consecutive sequence of elements that match using equals().
  104.    * The time complexity is linear and the space complexity is constant.
  105.    * @param container The container to search.
  106.    * @return An iterator positioned at the first element in the consecutive sequence. If
  107.    * no consecutive sequence is found, return an iterator positioned immediately after 
  108.    * the last element of the container.
  109.    */
  110.   public static InputIterator adjacentFind( Container container )
  111.     {
  112.     return adjacentFind( container.start(), container.finish() );
  113.     }
  114.  
  115.   /**
  116.    * Find the first consecutive sequence of elements that match using a predicate.
  117.    * The time complexity is linear and the space complexity is constant.
  118.    * @param first An iterator positioned at the first element of the sequence.
  119.    * @param last An iterator positioned immediately after the last element of the sequence.
  120.    * @param predicate A binary predicate.
  121.    * @return An iterator positioned at the first element in the consecutive sequence. If
  122.    * no consecutive sequence is found, return an iterator positioned immediately after 
  123.    * the last element of the input sequence.
  124.    */
  125.   public static InputIterator adjacentFind( InputIterator first, InputIterator last, BinaryPredicate predicate )
  126.     {
  127.     if( first.equals( last ) )
  128.       return last;
  129.  
  130.     InputIterator firstx = (InputIterator) first.clone();
  131.     InputIterator next = (InputIterator) first.clone();
  132.     next.advance();
  133.  
  134.     while( !next.equals( last ) )
  135.       {
  136.       if( predicate.execute( firstx.get(), next.get() ) )
  137.         return firstx;
  138.  
  139.       firstx.advance();
  140.       next.advance();
  141.       }
  142.  
  143.     return next;
  144.     }
  145.  
  146.   /**
  147.    * Find the first consecutive sequence of elements that match using a predicate.
  148.    * The time complexity is linear and the space complexity is constant.
  149.    * @param container The container to search.
  150.    * @param predicate A binary predicate.
  151.    * @return An iterator positioned at the first element in the consecutive sequence. If
  152.    * no consecutive sequence is found, return an iterator positioned immediately after 
  153.    * the last element of the container.
  154.    */
  155.   public static InputIterator adjacentFind( Container container, BinaryPredicate predicate )
  156.     {
  157.     return adjacentFind( container.start(), container.finish(), predicate );
  158.     }
  159.  
  160.   /**
  161.    * Return the first object in a range that satisfies a specified predicate, or null
  162.    * if no such object exists.
  163.    * The time complexity is linear and the space complexity is constant.
  164.    * @param first An iterator positioned at the first element in the range.
  165.    * @param last An iterator positioned immediately after the last element in the range.
  166.    * @param predicate A unary predicate.
  167.    * @return The first object that causes the predicate to return true.
  168.    * @exception IllegalArgumentException If the iterator containers are different.
  169.    */
  170.   public static Object detect( ForwardIterator first, ForwardIterator last, UnaryPredicate predicate )
  171.     {
  172.     Class firstClass = first.getContainer().getClass();
  173.     Class lastClass = last.getContainer().getClass();
  174.  
  175.     if( firstClass != lastClass )
  176.       throw new IllegalArgumentException( "iterator containers must be the same" );
  177.  
  178.     ForwardIterator firstx = (ForwardIterator) first.clone();
  179.     
  180.     while( !firstx.equals( last ) )
  181.       {
  182.       Object object = firstx.nextElement();
  183.  
  184.       if( predicate.execute( object ) )
  185.         return object;
  186.       }
  187.  
  188.     return null;
  189.     }
  190.   
  191.   /**
  192.    * Return the first object in a container that satisfies a specified predicate, or null
  193.    * if no such object exists.
  194.    * The time complexity is linear and the space complexity is constant.
  195.    * @param container The container to search.
  196.    * @param predicate A unary predicate.
  197.    * @return The first object that causes the predicate to return true.
  198.    * @exception IllegalArgumentException If the iterator containers are different.
  199.    */
  200.   public static Object detect( Container container, UnaryPredicate predicate )
  201.     {
  202.     return detect( container.start(), container.finish(), predicate );
  203.     }
  204.  
  205.   /**
  206.    * Return true if at least one object in the given range satisfies the specified 
  207.    * unary predicate. The time complexity is linear and the space complexity is constant.
  208.    * @param first An iterator positioned at the first element in the range.
  209.    * @param last An iterator positioned immediately after the last element in the range.
  210.    * @param predicate A unary predicate.
  211.    * @return true if at least one object satisfies the predicate.
  212.    * @exception IllegalArgumentException If the iterator containers are different.
  213.    */
  214.   public static boolean some( ForwardIterator first, ForwardIterator last, UnaryPredicate predicate )
  215.     {
  216.     return detect( first, last, predicate ) != null;
  217.     }
  218.   
  219.   /**
  220.    * Return true if at least one object in the container satisfies the specified 
  221.    * unary predicate. The time complexity is linear and the space complexity is constant.
  222.    * @param container A container to search
  223.    * @param predicate A unary predicate.
  224.    * @return true if at least one object satisfies the predicate.
  225.    */
  226.   public static boolean some( Container container, UnaryPredicate predicate )
  227.     {
  228.     return some( container.start(), container.finish(), predicate );
  229.     }
  230.  
  231.   /**
  232.    * Return true if every object in the specified range satisfies a particular predicate.
  233.    * The time complexity is linear and the space complexity is constant.
  234.    * @param first An iterator positioned at the first element in the range.
  235.    * @param last An iterator positioned immediately after the last element in the range.
  236.    * @param predicate A unary predicate.
  237.    * @return true if all objects satisfy the predicate.
  238.    * @exception IllegalArgumentException If the iterator containers are different.
  239.    */
  240.   public static boolean every( ForwardIterator first, ForwardIterator last, UnaryPredicate predicate )
  241.     {
  242.     Class firstClass = first.getContainer().getClass();
  243.     Class lastClass = last.getContainer().getClass();
  244.     if( firstClass != lastClass )
  245.       throw new IllegalArgumentException( "iterator containers must be the same" );
  246.  
  247.     ForwardIterator firstx = (ForwardIterator)first.clone();
  248.  
  249.     while( !firstx.equals( last ) )
  250.       {
  251.       if( !predicate.execute( firstx.nextElement() ) )
  252.         return false;
  253.       }
  254.  
  255.     return true;
  256.     }
  257.  
  258.   /**
  259.    * Return true if every object in the container satisfies a particular predicate.
  260.    * The time complexity is linear and the space complexity is constant.
  261.    * @param container A container to search
  262.    * @param predicate A unary predicate.
  263.    * @return true if all objects satisfy the predicate.
  264.    */
  265.   public static boolean every( Container container, UnaryPredicate predicate )
  266.     {
  267.     return every( container.start(), container.finish(), predicate );
  268.     }
  269.   }
  270.  
  271.