home *** CD-ROM | disk | FTP | other *** search
/ ActiveX Programming Unleashed CD / AXU.iso / jgl_1_1 / src / filtering.java < prev    next >
Encoding:
Java Source  |  1996-09-11  |  13.3 KB  |  327 lines
  1. // Copyright(c) 1996 ObjectSpace, Inc.
  2. // Portions Copyright(c) 1995, 1996 Hewlett-Packard Company.
  3.  
  4. package jgl;
  5.  
  6. /**
  7.  * The Filtering class contains generic filtering algorithms.
  8.  * <p>
  9.  * @see jgl.examples.FilteringExamples
  10.  * @version 1.1
  11.  * @author ObjectSpace, Inc.
  12.  */
  13.  
  14. public final class Filtering
  15.   {
  16.   private Filtering()
  17.     {
  18.     }
  19.  
  20.   /**
  21.    * Replace all consecutive occurrences of an object in a sequence by a single
  22.    * instance of that object. Use equals() to perform the equality test. The size of the 
  23.    * sequence is not altered; if n elements are removed, the last n elements will have 
  24.    * undefined values. The time complexity is linear and the space complexity is constant.
  25.    * @param first An iterator positioned at the first element of the sequence.
  26.    * @param last An iterator positioned immediately after the last element of the sequence.
  27.    * @return An iterator positioned immediately after the last element of the "new" sequence.
  28.    */
  29.   public static ForwardIterator unique( ForwardIterator first, ForwardIterator last )
  30.     {
  31.     return unique( first, last, new EqualTo() );
  32.     }
  33.  
  34.   /**
  35.    * Replace all consecutive occurrences of an object in a container by a single
  36.    * instance of that object. Use equals() to perform the equality test. The size of the 
  37.    * container is not altered; if n elements are removed, the last n elements will have 
  38.    * undefined values. The time complexity is linear and the space complexity is constant.
  39.    * @param container The container.
  40.    * @return An iterator positioned immediately after the last element of the "new" sequence.
  41.    */
  42.   public static ForwardIterator unique( Container container )
  43.     {
  44.     return unique( container.start(), container.finish(), new EqualTo() );
  45.     }
  46.  
  47.   /**
  48.    * Replace all consecutive occurrences of an object in a sequence by a single
  49.    * instance of that object. The size of the sequence is not altered; if n elements are
  50.    * removed, the last n elements will have undefined values. The time complexity is 
  51.    * linear and the space complexity is constant.
  52.    * @param first An iterator positioned at the first element of the sequence.
  53.    * @param last An iterator positioned immediately after the last element of the sequence.
  54.    * @param predicate A binary predicate that returns true if both of its operands are "equal". 
  55.    * @return An iterator positioned immediately after the last element of the new sequence.
  56.    */
  57.   public static ForwardIterator unique( ForwardIterator first, ForwardIterator last, BinaryPredicate predicate )
  58.     {
  59.     first = (ForwardIterator) Finding.adjacentFind( first, last, predicate );
  60.     return (ForwardIterator) uniqueCopy( first, last, first, predicate );
  61.     }
  62.  
  63.   /**
  64.    * Replace all consecutive occurrences of an object in a container by a single
  65.    * instance of that object. The size of the container is not altered; if n elements are
  66.    * removed, the last n elements will have undefined values. The time complexity is 
  67.    * linear and the space complexity is constant.
  68.    * @param container The container.
  69.    * @param predicate A binary predicate that returns true if both of its operands are "equal". 
  70.    * @return An iterator positioned immediately after the last element of the "new" sequence.
  71.    */
  72.   public static ForwardIterator unique( Container container, BinaryPredicate predicate )
  73.     {
  74.     return unique( container.start(), container.finish(), predicate );
  75.     }
  76.  
  77.   /**
  78.    * Copy a sequence into another sequence, replacing all consecutive occurrences of an 
  79.    * object by a single instance of that object. Use equals() to perform the equality test.
  80.    * The time complexity is linear and the space complexity is constant.
  81.    * @param first An iterator positioned at the first element of the input sequence.
  82.    * @param last An iterator positioned immediately after the last element of the input sequence.
  83.    * @param result An iterator positioned at the first element of the output sequence.
  84.    * @return An iterator positioned immediately after the last element of the output sequence.
  85.    */
  86.   public static OutputIterator uniqueCopy( InputIterator first, InputIterator last, OutputIterator result )
  87.     {
  88.     return uniqueCopy( first, last, result, new EqualTo() );
  89.     }
  90.  
  91.   /**
  92.    * Copy a container into another sequence, replacing all consecutive occurrences of an 
  93.    * object by a single instance of that object. Use equals() to perform the equality test.
  94.    * The time complexity is linear and the space complexity is constant.
  95.    * @param container The container.
  96.    * @param result An iterator positioned at the first element of the output sequence.
  97.    * @return An iterator positioned immediately after the last element of the output sequence.
  98.    */
  99.   public static OutputIterator uniqueCopy( Container container, OutputIterator result )
  100.     {
  101.     return uniqueCopy( container.start(), container.finish(), result, new EqualTo() );
  102.     }
  103.  
  104.   /**
  105.    * Copy the contents of one container into another container, replacing all consecutive 
  106.    * occurrences of an object by a single instance of that object. Use equals() to perform 
  107.    * the equality test. The time complexity is linear and the space complexity is constant.
  108.    * @param source The source container.
  109.    * @param destination The destination container.
  110.    */
  111.   public static void uniqueCopy( Container source, Container destination )
  112.     {
  113.     uniqueCopy( source.start(), source.finish(), new InsertIterator( destination ), new EqualTo() );
  114.     }
  115.  
  116.   /**
  117.    * Copy a sequence into another sequence, replacing all consecutive occurrences of an 
  118.    * object by a single instance of that object. The time complexity is linear and the 
  119.    * space complexity is constant.
  120.    * @param first An iterator positioned at the first element of the input sequence.
  121.    * @param last An iterator positioned immediately after the last element of the input sequence.
  122.    * @param result An iterator positioned at the first element of the output sequence.
  123.    * @param predicate A binary predicate that returns true if both of its operands are "equal". 
  124.    * @return An iterator positioned immediately after the last element of the output sequence.
  125.    */
  126.   public static OutputIterator uniqueCopy( InputIterator first, InputIterator last, OutputIterator result, BinaryPredicate predicate )
  127.     {
  128.     if( first.equals( last ) )
  129.       {
  130.       return (OutputIterator) result.clone();
  131.       }
  132.     else if( result instanceof ForwardIterator )
  133.       {
  134.       ForwardIterator resultx = (ForwardIterator) result.clone();
  135.       InputIterator firstx = (InputIterator) first.clone();
  136.       resultx.put( firstx.nextElement() );
  137.  
  138.       while( !firstx.equals( last ) )
  139.         {
  140.         if( !predicate.execute( resultx.get(), firstx.get() ) )
  141.           {
  142.           resultx.advance();
  143.           resultx.put( firstx.get() );
  144.           }
  145.  
  146.         firstx.advance();        
  147.         }
  148.  
  149.       resultx.advance();
  150.       return resultx;
  151.       }
  152.     else
  153.       {
  154.       OutputIterator resultx = (OutputIterator) result.clone();
  155.       InputIterator firstx = (InputIterator) first.clone(); 
  156.       Object value = firstx.get();
  157.       resultx.put( value );
  158.       firstx.advance();
  159.  
  160.       while( !firstx.equals( last ) )
  161.         {
  162.         if( !predicate.execute( value, firstx.get() ) )
  163.           {
  164.           value = firstx.get();
  165.           resultx.advance();
  166.           resultx.put( value );
  167.           }
  168.  
  169.         firstx.advance();
  170.         }
  171.  
  172.       resultx.advance();
  173.       return resultx;
  174.       }
  175.     }
  176.  
  177.   /**
  178.    * Copy a container into another sequence, replacing all consecutive occurrences of an 
  179.    * object by a single instance of that object. The time complexity is linear and the 
  180.    * space complexity is constant.
  181.    * @param container A container.
  182.    * @param result An iterator positioned at the first element of the output sequence.
  183.    * @param predicate A binary predicate that returns true if both of its operands are "equal". 
  184.    * @return An iterator positioned immediately after the last element of the output sequence.
  185.    */
  186.   public static OutputIterator uniqueCopy( Container container, OutputIterator result, BinaryPredicate predicate )
  187.     {
  188.     return uniqueCopy( container.start(), container.finish(), result, predicate );
  189.     }
  190.  
  191.   /**
  192.    * Copy the contents of one container into another container, replacing all consecutive 
  193.    * occurrences of an object by a single instance of that object. The time complexity is 
  194.    * linear and the space complexity is constant.
  195.    * @param source The source container.
  196.    * @param destination The destination container.
  197.    * @param predicate A binary predicate that returns true if both of its operands are "equal". 
  198.    */
  199.   public static void uniqueCopy( Container source, Container destination, BinaryPredicate predicate )
  200.     {
  201.     uniqueCopy( source.start(), source.finish(), new InsertIterator( destination ), predicate );
  202.     }
  203.  
  204.   /**
  205.    * Select elements in a range. Return a container that is the same class 
  206.    * as the original and only contains the elements within the range that satisfy 
  207.    * a particular predicate. The original container is not modified.
  208.    * The time complexity is linear and the space complexity is constant.
  209.    * @param first An iterator positioned at the first element in the range.
  210.    * @param last An iterator positioned immediately after the last element in the range.
  211.    * @param predicate A unary predicate.
  212.    * @return A new container containing the elements that satisfied the predicate.
  213.    * @exception IllegalArgumentException If the iterator container types are different.
  214.    */
  215.   public static Container select( ForwardIterator first, ForwardIterator last, UnaryPredicate predicate )
  216.     {
  217.     Class firstClass = first.getContainer().getClass();
  218.     Class lastClass = last.getContainer().getClass();
  219.  
  220.     if( firstClass != lastClass )
  221.       throw new IllegalArgumentException( "iterator containers must be the same" );
  222.  
  223.     Container container = null;
  224.     
  225.     try
  226.       {
  227.       container = (Container)( firstClass.newInstance() );
  228.       }
  229.     catch( InstantiationException exception )
  230.       {
  231.       return null;
  232.       }
  233.     catch( IllegalAccessException exception )
  234.       {
  235.       return null;
  236.       }
  237.  
  238.     ForwardIterator firstx = (ForwardIterator) first.clone();
  239.     
  240.     while( !firstx.equals( last ) )
  241.       {
  242.       Object object = firstx.nextElement();
  243.  
  244.       if( predicate.execute( object ) )
  245.         container.add( object );
  246.       }
  247.  
  248.     return container;
  249.     }
  250.   
  251.   /**
  252.    * Select elements in a container. Return a container that is the same class as 
  253.    * the original and only contains the elements that satisfy a particular predicate. 
  254.    * The original container is not modified.
  255.    * The time complexity is linear and the space complexity is constant.
  256.    * @param container A container.
  257.    * @param predicate A unary predicate.
  258.    * @return A new container containing the elements that satisfied the predicate.
  259.    */
  260.   public static Container select( Container container, UnaryPredicate predicate )
  261.     {
  262.     return select( container.start(), container.finish(), predicate );
  263.     }
  264.  
  265.   /**
  266.    * Reject elements in a range. Return a container that is the same class as the 
  267.    * original and only contains the elements within the range that do not satisfy a 
  268.    * particular predicate. The original container is not modified.
  269.    * The time complexity is linear and the space complexity is constant.
  270.    * @param first An iterator positioned at the first element of the range.
  271.    * @param last An iterator positioned immediately after the last element of the range.
  272.    * @param predicate A unary predicate.
  273.    * @return A new container containing the elements that do not satisfy the predicate.
  274.    * @exception IllegalArgumentException If the iterator container types are different.
  275.    */
  276.   public static Container reject( ForwardIterator first, ForwardIterator last, UnaryPredicate predicate )
  277.     {
  278.     Class firstClass = first.getContainer().getClass();
  279.     Class lastClass = last.getContainer().getClass();
  280.  
  281.     if( firstClass != lastClass )
  282.       throw new IllegalArgumentException( "iterator containers must be the same" );
  283.  
  284.     Container container = null;
  285.  
  286.     try
  287.       {
  288.       container = (Container)( firstClass.newInstance() );
  289.       }
  290.     catch( InstantiationException exception )
  291.       {
  292.       return null;
  293.       }
  294.     catch( IllegalAccessException exception )
  295.       {
  296.       return null;
  297.       }
  298.     
  299.     ForwardIterator firstx = (ForwardIterator) first.clone();
  300.     
  301.     while( !firstx.equals( last ) )
  302.       {
  303.       Object object = firstx.nextElement();
  304.  
  305.       if( !predicate.execute( object ) )
  306.         container.add( object );
  307.       }
  308.  
  309.     return container;
  310.     }
  311.   
  312.   /**
  313.    * Reject elements in a container. Return a container that is the same class as 
  314.    * the original and only contains the elements that do not satisfy a particular predicate.
  315.    * The original container is not modified.
  316.    * The time complexity is linear and the space complexity is constant.
  317.    * @param container A container 
  318.    * @param predicate A unary predicate.
  319.    * @return A new container containing the elements that do not satisfy the predicate.
  320.    */
  321.   public static Container reject( Container container, UnaryPredicate predicate )
  322.     {
  323.     return reject( container.start(), container.finish(), predicate );
  324.     }
  325.   }
  326.  
  327.