avalon-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From dona...@apache.org
Subject cvs commit: jakarta-avalon/src/java/org/apache/avalon/util/collections ArrayEnumeration.java ArrayStack.java BinaryHeap.java CircularBuffer.java IteratorEnumeration.java ListUtils.java PriorityQueue.java SynchronizedPriorityQueue.java
Date Mon, 16 Apr 2001 08:45:12 GMT
donaldp     01/04/16 01:45:12

  Added:       src/java/org/apache/avalon/util/collections
                        ArrayEnumeration.java ArrayStack.java
                        BinaryHeap.java CircularBuffer.java
                        IteratorEnumeration.java ListUtils.java
                        PriorityQueue.java SynchronizedPriorityQueue.java
  Removed:     src/java/org/apache/avalon/util ArrayEnumeration.java
                        ArrayStack.java BinaryHeap.java CircularBuffer.java
                        IteratorEnumeration.java ListUtils.java
                        PriorityQueue.java SynchronizedPriorityQueue.java
  Log:
  Move collections related classes into a sub-package
  
  Revision  Changes    Path
  1.1                  jakarta-avalon/src/java/org/apache/avalon/util/collections/ArrayEnumeration.java
  
  Index: ArrayEnumeration.java
  ===================================================================
  /*
   * Copyright (C) The Apache Software Foundation. All rights reserved.
   *
   * This software is published under the terms of the Apache Software License
   * version 1.1, a copy of which has been included with this distribution in
   * the LICENSE file.
   */
  package org.apache.avalon.util.collections;
  
  import java.util.Enumeration;
  import java.util.List;
  import java.util.NoSuchElementException;
  
  /**
   * Enumeration wrapper for array.
   *
   * @author <a href="mailto:donaldp@apache.org">Peter Donald</a>
   */
  public final class ArrayEnumeration
      implements Enumeration
  {
      protected Object[]       m_elements;
      protected int            m_index;
  
      public ArrayEnumeration( final List elements )
      {
          m_elements = elements.toArray();
      }
  
      public ArrayEnumeration( final Object[] elements )
      {
          m_elements = elements;
      }
  
      public boolean hasMoreElements()
      {
          return ( m_index < m_elements.length );
      }
  
      public Object nextElement()
      {
          if( !hasMoreElements() )
          {
              throw new NoSuchElementException("No more elements exist");
          }
  
          return m_elements[ m_index++ ];
      }
  }
  
  
  
  
  1.1                  jakarta-avalon/src/java/org/apache/avalon/util/collections/ArrayStack.java
  
  Index: ArrayStack.java
  ===================================================================
  /*
   * Copyright (C) The Apache Software Foundation. All rights reserved.
   *
   * This software is published under the terms of the Apache Software License
   * version 1.1, a copy of which has been included with this distribution in
   * the LICENSE file.
   */
  package org.apache.avalon.util.collections;
  
  import java.util.ArrayList;
  import java.util.EmptyStackException;
  
  /**
   * Unsynchronized stakc.
   *
   * @author <a href="mailto:donaldp@apache.org">Peter Donald</a>
   */
  public class ArrayStack
      extends ArrayList
  {
      public void setSize( final int size )
      {
          if( 0 == size ) clear();
          else
          {
              removeRange( size, size() - 1 );
          }
      }
  
      /**
       * Adds the object to the top of the stack.
       *
       * @param element object to add to stack
       * @return the object
       */
      public Object push( final Object element )
      {
          add( element );
          return element;
      }
  
      /**
       * Remove element from top of stack and return it
       *
       * @return the element from stack
       * @exception EmptyStackException if no elements left on stack
       */
      public Object pop()
          throws EmptyStackException
      {
          final int size = size();
          if( 0 == size ) throw new EmptyStackException();
  
          return remove( size - 1 );
      }
  }
  
  
  
  
  1.1                  jakarta-avalon/src/java/org/apache/avalon/util/collections/BinaryHeap.java
  
  Index: BinaryHeap.java
  ===================================================================
  /*
   * Copyright (C) The Apache Software Foundation. All rights reserved.
   *
   * This software is published under the terms of the Apache Software License
   * version 1.1, a copy of which has been included with this distribution in
   * the LICENSE file.
   */
  package org.apache.avalon.util.collections;
  
  import java.util.NoSuchElementException;
  
  /**
   * Iterface for priority queues.
   * This interface does not dictate whether it is min or max heap.
   *
   * @author  <a href="mailto:donaldp@apache.org">Peter Donald</a>
   * @author  <a href="mailto:ram.chidambaram@telus.com">Ram Chidambaram</a>
   */
  public final class BinaryHeap
      implements PriorityQueue
  {
      protected final static int      DEFAULT_CAPACITY   = 13;
  
      protected int                   m_size;
      protected Comparable[]          m_elements;
      protected boolean               m_isMinHeap;
  
      public BinaryHeap()
      {
          this( DEFAULT_CAPACITY, true );
      }
  
      public BinaryHeap( final int capacity )
      {
          this( capacity, true );
      }
  
      public BinaryHeap( final boolean isMinHeap )
      {
          this( DEFAULT_CAPACITY, isMinHeap );
      }
  
      public BinaryHeap( final int capacity, final boolean isMinHeap )
      {
          m_isMinHeap = isMinHeap;
  
          //+1 as 0 is noop
          m_elements = new Comparable[ capacity + 1 ];
      }
  
      /**
       * Clear all elements from queue.
       */
      public void clear()
      {
          m_size = 0;
      }
  
      /**
       * Test if queue is empty.
       *
       * @return true if queue is empty else false.
       */
      public boolean isEmpty()
      {
          return ( 0 == m_size );
      }
  
      /**
       * Test if queue is full.
       *
       * @return true if queue is full else false.
       */
      public boolean isFull()
      {
          //+1 as element 0 is noop
          return ( m_elements.length == m_size+1 );
      }
  
      /**
       * Insert an element into queue.
       *
       * @param element the element to be inserted
       */
      public void insert( final Comparable element )
      {
          if( isFull() ) grow();
  
          //percolate element to it's place in tree
          if( m_isMinHeap ) percolateUpMinHeap( element );
          else percolateUpMaxHeap( element );
      }
  
      /**
       * Return element on top of heap but don't remove it.
       *
       * @return the element at top of heap
       * @exception NoSuchElementException if isEmpty() == true
       */
      public Comparable peek() throws NoSuchElementException
      {
          if( isEmpty() ) throw new NoSuchElementException();
          else return m_elements[ 1 ];
      }
  
      /**
       * Return element on top of heap and remove it.
       *
       * @return the element at top of heap
       * @exception NoSuchElementException if isEmpty() == true
       */
      public Comparable pop() throws NoSuchElementException
      {
          final Comparable result = peek();
          m_elements[ 1 ] = m_elements[ m_size-- ];
  
          //set the unused element to 'null' so that the garbage collector
          //can free the object if not used anywhere else.(remove reference)
          m_elements[ m_size + 1 ] = null;
  
          if( m_size != 0 )
          {
              //percolate top element to it's place in tree
              if( m_isMinHeap ) percolateDownMinHeap( 1 );
              else percolateDownMaxHeap( 1 );
          }
  
          return result;
      }
  
      /**
       * Percolate element down heap from top.
       * Assume it is a maximum heap.
       *
       * @param element the element
       */
      protected void percolateDownMinHeap( final int index )
      {
          final Comparable element = m_elements[ index ];
  
          int hole = index;
  
          while( (hole * 2) <= m_size )
          {
              int child = hole * 2;
  
              //if we have a right child and that child can not be percolated
              //up then move onto other child
              if( child != m_size &&
                  m_elements[ child + 1 ].compareTo( m_elements[ child ] ) < 0 )
              {
                  child++;
              }
  
              //if we found resting place of bubble then terminate search
              if( m_elements[ child ].compareTo( element ) >= 0 )
              {
                  break;
              }
  
              m_elements[ hole ] = m_elements[ child ];
              hole = child;
          }
  
          m_elements[ hole ] = element;
      }
  
      /**
       * Percolate element down heap from top.
       * Assume it is a maximum heap.
       *
       * @param element the element
       */
      protected void percolateDownMaxHeap( final int index )
      {
          final Comparable element = m_elements[ index ];
  
          int hole = index;
  
          while( (hole * 2) <= m_size )
          {
              int child = hole * 2;
  
              //if we have a right child and that child can not be percolated
              //up then move onto other child
              if( child != m_size &&
                  m_elements[ child + 1 ].compareTo( m_elements[ child ] ) > 0 )
              {
                  child++;
              }
  
              //if we found resting place of bubble then terminate search
              if( m_elements[ child ].compareTo( element ) <= 0 )
              {
                  break;
              }
  
              m_elements[ hole ] = m_elements[ child ];
              hole = child;
          }
  
          m_elements[ hole ] = element;
      }
  
      /**
       * Percolate element up heap from bottom.
       * Assume it is a maximum heap.
       *
       * @param element the element
       */
      protected void percolateUpMinHeap( final Comparable element )
      {
          int hole = ++m_size;
  
          m_elements[ hole ] = element;
  
          while( hole > 1 &&
                 element.compareTo( m_elements[ hole / 2 ] ) < 0 )
          {
              //save element that is being pushed down
              //as the element "bubble" is percolated up
              final int next = hole / 2;
              m_elements[ hole ] = m_elements[ next ];
              hole = next;
          }
  
          m_elements[ hole ] = element;
      }
  
      /**
       * Percolate element up heap from bottom.
       * Assume it is a maximum heap.
       *
       * @param element the element
       */
      protected void percolateUpMaxHeap( final Comparable element )
      {
          int hole = ++m_size;
  
          while( hole > 1 &&
                 element.compareTo( m_elements[ hole / 2 ] ) > 0 )
          {
              //save element that is being pushed down
              //as the element "bubble" is percolated up
              final int next = hole / 2;
              m_elements[ hole ] = m_elements[ next ];
              hole = next;
          }
  
          m_elements[ hole ] = element;
      }
  
      protected void grow()
      {
          final Comparable[] elements =
              new Comparable[ m_elements.length * 2 ];
          System.arraycopy( m_elements, 0, elements, 0, m_elements.length );
          m_elements = elements;
      }
  
      public String toString()
      {
          final StringBuffer sb = new StringBuffer();
  
          sb.append( "[ " );
  
          for( int i = 1; i < m_size + 1; i++ )
          {
              if( i != 1 ) sb.append( ", " );
              sb.append( m_elements[ i ] );
          }
  
          sb.append( " ]" );
  
          return sb.toString();
      }
  }
  
  
  
  
  1.1                  jakarta-avalon/src/java/org/apache/avalon/util/collections/CircularBuffer.java
  
  Index: CircularBuffer.java
  ===================================================================
  /*
   * Copyright (C) The Apache Software Foundation. All rights reserved.
   *
   * This software is published under the terms of the Apache Software License
   * version 1.1, a copy of which has been included with this distribution in
   * the LICENSE file.
   */
  package org.apache.avalon.util.collections;
  
  /**
   *
   * @author  Federico Barbieri <fede@apache.org>
   */
  public class CircularBuffer
  {
      protected Object[]   m_buffer;
      protected int        m_bufferSize;
      protected int        m_contentSize;
      protected int        m_head;
      protected int        m_tail;
  
      public CircularBuffer( int size )
      {
          m_buffer = new Object[size];
          m_bufferSize = size;
          m_contentSize = 0;
          m_head = 0;
          m_tail = 0;
      }
  
      public CircularBuffer()
      {
          this( 32 );
      }
  
      public boolean isEmpty()
      {
          return (m_contentSize == 0);
      }
  
      public int getContentSize()
      {
          return m_contentSize;
      }
  
      public int getBufferSize()
      {
          return m_bufferSize;
      }
  
      public void append( final Object o )
      {
          if( m_contentSize >= m_bufferSize )
          {
              int j = 0;
              int i = m_tail;
              Object[] tmp = new Object[ m_bufferSize * 2 ];
  
              while( m_contentSize > 0 )
              {
                  i++;
                  i %= m_bufferSize;
                  j++;
                  m_contentSize--;
                  tmp[ j ] = m_buffer[ i ];
              }
              m_buffer = tmp;
              m_tail = 0;
              m_head = j;
              m_contentSize = j;
              m_bufferSize *= 2;
          }
  
          m_buffer[ m_head ] = o;
          m_head++;
          m_head %= m_bufferSize;
          m_contentSize++;
      }
  
      public Object get()
      {
          if( m_contentSize <= 0 )
          {
              return null;
          }
  
          Object o = m_buffer[ m_tail ];
          m_tail++;
          m_tail %= m_bufferSize;
          m_contentSize--;
          return o;
      }
  }
  
  
  
  
  1.1                  jakarta-avalon/src/java/org/apache/avalon/util/collections/IteratorEnumeration.java
  
  Index: IteratorEnumeration.java
  ===================================================================
  /* 
   * Copyright (C) The Apache Software Foundation. All rights reserved. 
   * 
   * This software is published under the terms of the Apache Software License 
   * version 1.1, a copy of which has been included with this distribution in 
   * the LICENSE file. 
   */ 
  package org.apache.avalon.util.collections;
  
  import java.util.Enumeration;
  import java.util.Iterator;
  import java.util.NoSuchElementException;
  
  /**
   * Enumeration wrapper for iterator.
   *
   * @author <a href="mailto:donaldp@apache.org">Peter Donald</a>
   */
  public final class IteratorEnumeration
      implements Enumeration
  {
      protected Iterator       m_iterator;
  
      public IteratorEnumeration( final Iterator iterator )
      {
          m_iterator = iterator;
      }
  
      public boolean hasMoreElements()
      {
          return m_iterator.hasNext();
      }
  
      public Object nextElement()
      {
          return m_iterator.next();
      }
  }
  
  
  
  
  1.1                  jakarta-avalon/src/java/org/apache/avalon/util/collections/ListUtils.java
  
  Index: ListUtils.java
  ===================================================================
  /*
   * Copyright (C) The Apache Software Foundation. All rights reserved.
   *
   * This software is published under the terms of the Apache Software License
   * version 1.1, a copy of which has been included with this distribution in
   * the LICENSE file.
   */
  package org.apache.avalon.util.collections;
  
  import java.util.ArrayList;
  import java.util.Iterator;
  import java.util.List;
  
  /**
   * Miscelaneous utilities to manipulate Lists.
   *
   * @author  <a href="mailto:fede@apache.org">Federico Barbieri</a>
   * @author  <a href="mailto:donaldp@apache.org">Peter Donald</a>
   */
  public class ListUtils
  {
      public static List intersection( final List list1, final List list2 )
      {
          final ArrayList result = new ArrayList();
          final Iterator iterator = list2.iterator();
  
          while( iterator.hasNext() )
          {
              final Object o = iterator.next();
  
              if ( list1.contains( o ) )
              {
                  result.add( o );
              }
          }
  
          return result;
      }
  
      public static List subtract( final List list1, final List list2 )
      {
          final ArrayList result = new ArrayList( list1 );
          final Iterator iterator = list2.iterator();
  
          while( iterator.hasNext() )
          {
              result.remove( iterator.next() );
          }
  
          return result;
      }
  
      public static List sum( final List list1, final List list2 )
      {
          return subtract( union( list1, list2 ),
                           intersection( list1, list2 ) );
      }
  
      public static List union( final List list1, final List list2 )
      {
          final ArrayList result = new ArrayList( list1 );
          result.addAll( list2 );
          return result;
      }
  }
  
  
  
  1.1                  jakarta-avalon/src/java/org/apache/avalon/util/collections/PriorityQueue.java
  
  Index: PriorityQueue.java
  ===================================================================
  /*
   * Copyright (C) The Apache Software Foundation. All rights reserved.
   *
   * This software is published under the terms of the Apache Software License
   * version 1.1, a copy of which has been included with this distribution in
   * the LICENSE file.
   */
  package org.apache.avalon.util.collections;
  
  import java.util.NoSuchElementException;
  
  /**
   * Iterface for priority queues.
   * This interface does not dictate whether it is min or max heap.
   *
   * @author  <a href="mailto:donaldp@apache.org">Peter Donald</a>
   */
  public interface PriorityQueue
  {
      /**
       * Clear all elements from queue.
       */
      void clear();
  
      /**
       * Test if queue is empty.
       *
       * @return true if queue is empty else false.
       */
      boolean isEmpty();
  
      /**
       * Insert an element into queue.
       *
       * @param element the element to be inserted
       */
      void insert( Comparable element );
  
      /**
       * Return element on top of heap but don't remove it.
       *
       * @return the element at top of heap
       * @exception NoSuchElementException if isEmpty() == true
       */
      Comparable peek() throws NoSuchElementException;
  
      /**
       * Return element on top of heap and remove it.
       *
       * @return the element at top of heap
       * @exception NoSuchElementException if isEmpty() == true
       */
      Comparable pop() throws NoSuchElementException;
  }
  
  
  
  
  1.1                  jakarta-avalon/src/java/org/apache/avalon/util/collections/SynchronizedPriorityQueue.java
  
  Index: SynchronizedPriorityQueue.java
  ===================================================================
  /*
   * Copyright (C) The Apache Software Foundation. All rights reserved.
   *
   * This software is published under the terms of the Apache Software License
   * version 1.1, a copy of which has been included with this distribution in
   * the LICENSE file.
   */
  package org.apache.avalon.util.collections;
  
  import java.util.NoSuchElementException;
  
  /**
   * A thread safe version of the PriorityQueue.
   * Provides synchronized wrapper methods for all the methods
   * defined in the PriorityQueue interface.
   *
   * @author  <a href="mailto:ram.chidambaram@telus.com">Ram Chidambaram</a>
   */
  public final class SynchronizedPriorityQueue
      implements PriorityQueue
  {
      protected final PriorityQueue   m_priorityQueue;
  
      public SynchronizedPriorityQueue( final PriorityQueue priorityQueue )
      {
          m_priorityQueue = priorityQueue;
      }
  
      /**
       * Clear all elements from queue.
       */
      public synchronized void clear()
      {
          m_priorityQueue.clear();
      }
  
      /**
       * Test if queue is empty.
       *
       * @return true if queue is empty else false.
       */
      public synchronized boolean isEmpty()
      {
          return m_priorityQueue.isEmpty();
      }
  
      /**
       * Insert an element into queue.
       *
       * @param element the element to be inserted
       */
      public synchronized void insert( final Comparable element )
      {
          m_priorityQueue.insert( element );
      }
  
      /**
       * Return element on top of heap but don't remove it.
       *
       * @return the element at top of heap
       * @exception NoSuchElementException if isEmpty() == true
       */
      public synchronized Comparable peek() throws NoSuchElementException
      {
          return m_priorityQueue.peek();
      }
  
      /**
       * Return element on top of heap and remove it.
       *
       * @return the element at top of heap
       * @exception NoSuchElementException if isEmpty() == true
       */
      public synchronized Comparable pop() throws NoSuchElementException
      {
          return m_priorityQueue.pop();
      }
  
      public synchronized String toString()
      {
          return m_priorityQueue.toString();
      }
  }
  
  
  

---------------------------------------------------------------------
To unsubscribe, e-mail: avalon-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: avalon-dev-help@jakarta.apache.org


Mime
View raw message