• JW's Most Read

Recent:

• Java Tips: The Serialization algorithm revealed
• Know your Oracle application server
• SwingX, JRuby: Survivors?
• Cloud-ready, multicore-friendly apps, Part 2
• Lean service architectures with Java EE 6

Archives:

• Hello, OSGi: Bundles for beginners (2008)
• Sockets programming in Java: A tutorial (1996)
• Understanding JPA, Part 1 (2008)
• Smartly load your properties (2003)
• REST for Java developers, Part 1 (2008)

package vector;
public class SortedVector
{
    public SortedVector (int capacity)
    {
        m_data = new int [capacity];
    }
    
    // ACCESSORS: [all methods are final]
    
    public final int size ()
    {
        return m_size;
    }
    public final int get (int index)
    {
        return m_data [index];
    }
    
    // package-private constructor:    
    SortedVector (MutableSortedVector item)
    {
        // Note: 'm_data' array is not cloned here and is rather shared
        // by reference with the original MutableSortedVector until
        // the next MutableSortedVector mutator method is invoked [if ever]
        
        m_data = item.m_data;
        m_size = item.m_size;
    }
    
    int [] m_data;
    int m_size;
}
package vector;
public final class MutableSortedVector extends SortedVector
{
    public MutableSortedVector (int capacity)
    {
        super (capacity);
    }
    public SortedVector toImmutable ()
    {
        m_shared = true; // set 'shared' flag
        return new SortedVector (this);
    }
    
    // MUTATORS:
    // Add a new value; keep them in increasing order:
    public void add (int value)
    {
        // [This simple implementation is O(size) and is used for
        // illustrative purposes only]
        
        if (m_size == m_data.length)
            throw new IllegalStateException ("maximum capacity reached");
        // If the data array is shared, it must be cloned before we can
        // proceed [copy-on-write]:
        if (m_shared)
        {
            m_data = (int []) m_data.clone ();
            m_shared = false; // reset 'shared' flag
        }               
        
        // Insert the new value after a simple linear scan:        
        int position;    
        for (position = 0; position < m_size; ++ position)
        {
            if (m_data [position] > value) break;
        }
        
        if (position < m_size)
            System.arraycopy (m_data, position,
                              m_data, position + 1, m_size - position);
            
        m_data [position] = value;
        ++ m_size;
    }
    
    private boolean m_shared; // if 'true', next mutator call must clone data
}