// Philip Kao
// IB Comsci Dossier
// TreeClassics Program
import java.io.*;
import java.awt.*;
import java.awt.event.*;
import javax.swing.*;
import java.util.*;
 
public class TreeClassics extends JFrame
{
    //include aspects of GUI
    private JTextField quantityField, thicknessField, widthField,
            plysField, modelField, heightField, tipField, groupField;
            // modelField, heightField, tipField, groupField have not been
            // implemented yet; for panel 3
    //
    private JEditorPane scrollListContent;
    private JTextArea enteredContent;
    private JList enteredItemsList, loadedList;
 
    // Labels for field input identifier
    private JLabel quantityLabel, thicknessLabel,
            widthLabel, colorLabel, plysLabel,
            productionLabel, informLabel, specifyLabel,
            plys1Label, color1Label, quantity1Label,
            model1Label, thickness1Label, width1Label,
            helper1Label, helper2Label, helper3Label,
            helper4Label, helper5Label;
 
    // The three tab panels
    private JPanel panel1, panel2, panel3;
 
    // Combobox selection system
    private JComboBox modelComboBox, colorComboBox;
 
    private JScrollPane orderScrollPane, enteredScrollPane;
 
    private JButton
        loadModelsButton, enterButton, removeTempItemsButton,
        saveListButton, deleteModelsButton, modelInfoButton,
        modelButton, thicknessButton, widthButton, colorButton,
        loadListButton;
 
    private javax.swing.JButton clearListButton,          // NOTE: saveModelB, loadModelB, delModelB pertain to the
        saveModelB,         loadModelB,         delModelB;
    private Vector<Model> modelList;
    private String[] colors = {"Green", "Teal", "Dark Blue", "White", "Gray"};
    private OrderList prodList;
 
    private TreeClassics()
    {
        // GUI Setup for program
        super("Tree Classics Production Line");
 
        this.prodList = new OrderList();
        this.modelList = new Vector<Model>();
 
        // Creating JTabbed Pane
        JTabbedPane tabbedPane = new JTabbedPane();
 
        // -------------------------PANEL 1 INTERFACE---------------------------
        // Set up Panel 1
        JLabel label1 = new JLabel();
        panel1 = new JPanel( null );
        panel1.add( label1 );
        tabbedPane.addTab( "                 Production Order                 ",
           null, panel1, "Production orders are created here");
 
        // Model number selection label
        productionLabel = new JLabel( "Model Number");
        productionLabel.setBounds( 20, 20, 100, 20 );
        panel1.add( productionLabel );
 
        // Add Combo Box into Panel 1: PRODUCTION ORDER
        modelComboBox = new JComboBox();
        modelComboBox.setBounds(20, 40, 150, 20);
        panel1.add(modelComboBox);
 
        // Add Help Button into Panel1
        modelInfoButton = new JButton( "Model Information" );
        modelInfoButton.setBounds( 20, 70, 150, 20);
        panel1.add(modelInfoButton);
 
        // Titles for Selection and treeData types
        // Quantity
        quantityLabel = new JLabel( "Quantity");
        quantityLabel.setBounds( 250, 20, 100, 20 );
        panel1.add(quantityLabel);
 
        // Thickness
        thicknessLabel = new JLabel( "Thickness");
        thicknessLabel.setBounds( 250, 75, 100, 20 );
        panel1.add(thicknessLabel);
 
        // Width
        widthLabel = new JLabel( "Width");
        widthLabel.setBounds( 370, 20, 100, 20 );
        panel1.add(widthLabel);
 
        // Color
        colorLabel = new JLabel( "Color");
        colorLabel.setBounds( 490, 20, 100, 20 );
        panel1.add(colorLabel);
 
        // Plys
        plysLabel = new JLabel( "Plys");
        plysLabel.setBounds( 370, 75, 100, 20 );
        panel1.add( plysLabel );
 
        // Color 1 Label
        color1Label = new JLabel( "Color");
        color1Label.setBounds( 320, 130, 100, 20 );
        panel1.add(color1Label);
 
        // Models 1 Label
        model1Label = new JLabel( "Model Number");
        model1Label.setBounds( 20, 130, 100, 20 );
        panel1.add(model1Label);
 
        // quantity 1 Label
        quantity1Label = new JLabel( "Quantity");
        quantity1Label.setBounds( 120, 130, 100, 20 );
        panel1.add(quantity1Label);
 
        // thickness 1 Label
        thickness1Label = new JLabel( "Thickness");
        thickness1Label.setBounds( 185, 130, 100, 20 );
        panel1.add(thickness1Label);
 
        // width 1 Label
        width1Label = new JLabel( "Width");
        width1Label.setBounds( 260, 130, 100, 20 );
        panel1.add(width1Label);
 
        // plys 1 Label
        plys1Label = new JLabel( "Plys");
        plys1Label.setBounds( 370, 130, 100, 20 );
        panel1.add(plys1Label);
 
        // Quantity field input
        quantityField = new JTextField();
        quantityField = new JTextField("0", 15 );
        quantityField.setBounds( 250, 40 , 100, 20);
        panel1.add( quantityField );
 
        // Width field input
        widthField = new JTextField();
        widthField = new JTextField("0", 15 );
        widthField.setBounds( 370, 40 , 100, 20);
        panel1.add( widthField );
 
        // Thickness field input
        thicknessField = new JTextField();
        thicknessField = new JTextField("0", 15 );
        thicknessField.setBounds( 250, 95 , 100, 20);
        panel1.add(thicknessField);
 
        // Plys field input
        plysField = new JTextField();
        plysField = new JTextField("0", 15 );
        plysField.setBounds( 370, 95 , 100, 20);
        panel1.add(plysField);
 
        // Color scroll pane input
        colorComboBox = new JComboBox( colors );
        colorComboBox.setMaximumRowCount( 5 );
        colorComboBox.setBounds( 490, 40, 100, 20 );
        colorComboBox.setSelectedIndex( 0 );
        panel1.add(colorComboBox);
 
        // Panel 1 scroll pane for entered information
        //enteredContent = new JTextArea();
        //enteredContent.setEditable(false);
        enteredItemsList = new JList(prodList);
        enteredScrollPane = new JScrollPane(enteredItemsList);
        enteredScrollPane.setBounds(20,150,400,150);
        enteredScrollPane.createVerticalScrollBar();
        panel1.add(enteredScrollPane);
 
        // Add Enter Button into Panel1
        enterButton = new JButton("Enter");
        enterButton.setBounds( 450, 150 , 100, 20);
        panel1.add(enterButton);
 
        removeTempItemsButton = new JButton("Remove Selected");
        removeTempItemsButton.setBounds( 450, 180 , 150, 20);
        panel1.add(removeTempItemsButton);
 
        // Add Save Button into Panel1
        saveListButton = new JButton( "Save List" );
        saveListButton.setBounds( 450, 210 , 150, 20);
        panel1.add(saveListButton);
 
        // Add load model button into Panel1
        loadModelsButton = new JButton("Load Model Set");
        loadModelsButton.setBounds( 450, 240, 150, 20);
        panel1.add( loadModelsButton);
 
        // Add delete model button into Panel1
        deleteModelsButton = new JButton("Delete Model Set");
        deleteModelsButton.setBounds( 450, 270, 150, 20);
        panel1.add(deleteModelsButton);
 
        // ------------------PANEL 2 INTERFACE----------------------------------
        // Set up Panel 2
        JLabel label2 = new JLabel( "Panel Two", SwingConstants.CENTER );
        panel2 = new JPanel( null );
        panel2.add( label2 );
        tabbedPane.addTab( "                    List Orders                 ",
            null, panel2, "Orders are listed and organized here");
 
        // Add Infomer Label into Panel 2
        informLabel = new JLabel( "Information of this list");
        informLabel.setBounds( 40, 20, 300, 20 );
        panel2.add( informLabel );
 
        // Add scroll pane label into Panel 2
        informLabel = new JLabel( "Model               Quantity     Thickness     Width     Color      Plys");
        informLabel.setBounds( 20, 60, 400, 20 );
        panel2.add( informLabel );
 
        // Panel 2 scroll pane
        scrollListContent = new JEditorPane();
        scrollListContent.setEditable(false);
        orderScrollPane = new JScrollPane(scrollListContent);
        orderScrollPane.setBounds(20,80,400,220);
        orderScrollPane.createVerticalScrollBar();
        panel2.add(orderScrollPane);
 
        // Add Sort by Model Button into Panel2
        modelButton = new JButton( "Sort by Model #" );
        modelButton.setBounds( 450, 80 , 150, 20);
        panel2.add( modelButton );
 
        // Add Sort by Thickness Button into Panel2
        thicknessButton = new JButton( "Sort by Thickness" );
        thicknessButton.setBounds( 450, 170 , 150, 20);
        panel2.add( thicknessButton );
 
        // Add Sort by Width Button into Panel2
        widthButton = new JButton( "Sort by Width" );
        widthButton.setBounds( 450, 110 , 150, 20);
        panel2.add( widthButton );
 
        // Add Sort by Color Button into Panel2
        colorButton = new JButton( "Sort by Color" );
        colorButton.setBounds( 450, 140 , 150, 20);
        panel2.add( colorButton );
 
        // Add Load Button into Panel2
        loadListButton = new JButton( "Load List" );
        loadListButton.setBounds( 450, 200 , 150, 20);
        panel2.add(loadListButton);
 
        // Add Clear Button into Panel2
        clearListButton = new JButton( "Clear List" );
        clearListButton.setBounds( 450, 230 , 150, 20);
        panel2.add(clearListButton);
 
        // ------------------PANEL 3 INTERFACE----------------------------------
        // Set up Panel 3: For Printing
        JLabel label3 = new JLabel( "Panel Three", SwingConstants.CENTER );
        panel3 = new JPanel( null );
        panel3.add( label3 );
        tabbedPane.addTab( "              HELP PANEL             ",
             null, panel3, "Select the set of data of models to use");
 
        // Add Specify Label into Panel 3
        specifyLabel = new JLabel( "WELCOME TO THE HELP MENU!");
        specifyLabel.setBounds( 40, 20, 200, 20 );
        panel3.add( specifyLabel );
 
        // Add Helper Label into Panel 3
        helper1Label = new JLabel( "Follow these steps and you \n won't have any problem using the program!");
        helper1Label.setBounds( 40, 50, 400, 20 );
        panel3.add( helper1Label );
 
        // Add Helper2 Label into Panel 3
        helper2Label = new JLabel( "Step 1. Load Model set");
        helper2Label.setBounds( 40, 80, 400, 20 );
        panel3.add( helper2Label );
 
        // Add Helper2 Label into Panel 3
        helper3Label = new JLabel( "Step 2. Fill in necessary fields of input");
        helper3Label.setBounds( 40, 110, 400, 20 );
        panel3.add( helper3Label );
 
        // Add Helper2 Label into Panel 3
        helper4Label = new JLabel( "Step 3. Save/Remove List of inputs");
        helper4Label.setBounds( 40, 80, 400, 20 );
        panel3.add( helper4Label );
 
 
 
        getContentPane().add( tabbedPane );
        setSize( 640, 400 );
        setVisible(true);
 
        //Panel 1 handlers------------------------------------------------------
        // Help button to check fields entry
        modelInfoButton.addActionListener (
            new ActionListener()
            { public void actionPerformed( ActionEvent e) {showModelInfo();} }
        );
 
        // Enter button to check fields entry
        enterButton.addActionListener (
            new ActionListener()
            { public void actionPerformed(ActionEvent e) {readInput();} }
        );
 
        // button to remove selected items from temp list
        removeTempItemsButton.addActionListener (
            new ActionListener()
            { public void actionPerformed(ActionEvent e) {removeTempItems();} }
        );
 
        // Save button call
        saveListButton.addActionListener (
            new ActionListener()
            { public void actionPerformed(ActionEvent e) {saveList();} }
        );
 
        // Load button call
        loadModelsButton.addActionListener(
            new ActionListener()
            { public void actionPerformed(ActionEvent e) {loadModels();} }
        );
 
        // Clear button
        deleteModelsButton.addActionListener (
            new ActionListener()
            { public void actionPerformed( ActionEvent e) {deleteModels();} }
        );
 
        //Panel 2 handlers------------------------------------------------------
        // Load button call
        loadListButton.addActionListener(
            new ActionListener()
            { public void actionPerformed(ActionEvent e) {openList();} }
        );
 
        // Clear button
        clearListButton.addActionListener (
            new ActionListener()
            { public void actionPerformed(ActionEvent e) {clearList();} }
        );
 
        // Sort by model button
        modelButton.addActionListener (
            new ActionListener()
            {
                public void actionPerformed(ActionEvent e) {prodList.sort(0);
                scrollListContent.setText(prodList.toString());
            } }
        );
 
        // Sort by thickness button
        modelButton.addActionListener (
            new ActionListener()
            {
                public void actionPerformed(ActionEvent e) {prodList.sort(1);
                scrollListContent.setText(prodList.toString());
            } }
        );
 
        // Width sort button
        widthButton.addActionListener (
            new ActionListener()
            {
                public void actionPerformed(ActionEvent e) {prodList.sort(2);
                scrollListContent.setText(prodList.toString());
            } }
        );
 
        // Color sort button
        colorButton.addActionListener (
            new ActionListener()
            {
                public void actionPerformed(ActionEvent e) {prodList.sort(3);
                scrollListContent.setText(prodList.toString());
            } }
        );
    }
 
    //read from input fields, then add item to list
    private void readInput()
    {
        String modelNo = (String)(modelComboBox.getSelectedItem());
        if (modelNo == null) return;
        try {
            int quantity = Integer.parseInt(quantityField.getText());
            double thickness = Double.parseDouble(thicknessField.getText());
            double width = Double.parseDouble(widthField.getText());
            String color = (String)(colorComboBox.getSelectedItem());
            double plys = Double.parseDouble(plysField.getText());
 
            if (quantity < 0 || thickness < 0 || width < 0 || plys < 0)
                throw new NumberFormatException("Negative attributes");
            prodList.add(
                new TreeData(modelNo, quantity, thickness, width, color, plys));
 
            // Repaints the scroll pane to display newly entered data
            enteredItemsList.setListData(prodList);
        }
        catch (NumberFormatException e)
        {   JOptionPane.showMessageDialog(this, "At least 1 field is illegal",
                  "Error", JOptionPane.ERROR_MESSAGE ); }
    }
 
    private void removeTempItems()
    {
        int[] select = enteredItemsList.getSelectedIndices();
        for (int i = select.length-1; i >= 0; i--)
        {
            int selectIndex = select[i];
            if (selectIndex < 0) return;
            prodList.removeElementAt(selectIndex);
            enteredItemsList.removeSelectionInterval(selectIndex, selectIndex);
            enteredItemsList.repaint();
        }
    }
 
    //pop up a window showing model info
    private void showModelInfo()
    {
        JOptionPane.showMessageDialog( null, "Always remember to load model info \n Create a text file using this template \n 48-209-351 1.3 300 \n 560-344-351 1.45 250 12 \n 72-554-351 1.32 200 9 \n 84-754-351 1.35 350 3 \n 96-1042-351 1.4 280 7",
                "REMINDER", JOptionPane.PLAIN_MESSAGE );
    }
 
    /**
    * CLEAR FILE
    * Clears the scroll list pane in the 2nd panel
    */
    private void clearList()
    {
        this.prodList = null; //Cleanup by garbage collector
        scrollListContent.setText("No list loaded.");
        panel2.repaint();
    }
 
    /**
     * OPEN FILE
     * Opens
     */
    private void openList()
    {
        File inFile = chooseFile(false);
        if (inFile == null) return;
 
        prodList = new OrderList(inFile, this);
        scrollListContent.setText(prodList.toString());
        //panel2.repaint();
    }
 
    //save list to file
    private void saveList()
    {
        if (prodList.size() == 0) {
            JOptionPane.showMessageDialog(this, "There is nothing to save",
                "ERROR", JOptionPane.ERROR_MESSAGE );
            return;
        }
 
        File outFile = chooseFile(true);
        if (outFile == null) return;
        if (outFile.exists())
            if (JOptionPane.showConfirmDialog(this,
                "File " + outFile.getName() + " already exists. Overwrite?",
                "WARNING", JOptionPane.YES_NO_OPTION,
                JOptionPane.WARNING_MESSAGE) == JOptionPane.NO_OPTION)
                return;
 
        try {
            FileWriter output = new FileWriter(outFile);
            String toWrite = prodList.toString();
            output.write(toWrite, 0, toWrite.length());
            output.flush();
            output.close();
        }
        catch (IOException e)
        {   JOptionPane.showMessageDialog(this, "File cannot be saved",
                  "ERROR", JOptionPane.ERROR_MESSAGE ); }
    }
 
    //load list of available models to combo box
    private void loadModels()
    {
        File inFile = chooseFile(false);
        if (inFile == null) return;
        try {
            if (!(inFile.exists()))
                throw new IOException("File does not exist");
            modelComboBox.removeAllItems();  //clean up before adding
            Scanner in = new Scanner(inFile);
            while (in.hasNextLine()) {
                Scanner lineScanner = new Scanner(in.nextLine());
                try {
                    String modelID = lineScanner.next();
                    double height = lineScanner.nextDouble();
                    int tipNum = lineScanner.nextInt();
                    int group = lineScanner.nextInt();
                    modelList.add(new Model(modelID, height, tipNum, group));
                    modelComboBox.addItem(modelID);
                }
                catch (NoSuchElementException e) { continue; }
            }
        }
        catch (IOException e)
        {   JOptionPane.showMessageDialog(this, "Error loading file",
                      "Error", JOptionPane.ERROR_MESSAGE); }
    }
 
    private File chooseFile(boolean saveDialog)
    {
        JFileChooser fileChooser = new JFileChooser();
        fileChooser.setFileSelectionMode( JFileChooser.FILES_ONLY );
 
        // open file chooser; if user clicked Cancel then return null
        int chooserDialogReturn;
        if (saveDialog)
            chooserDialogReturn = fileChooser.showSaveDialog(this);
        else
            chooserDialogReturn = fileChooser.showOpenDialog(this);
        if (chooserDialogReturn == JFileChooser.CANCEL_OPTION)
            return null;
 
        return fileChooser.getSelectedFile(); // get selected file
    }
 
    //clear model dropdown list
    private void deleteModels()
    {
        modelList.removeAllElements();
        modelComboBox.removeAllItems();
    }
 
    //================================MAIN======================================
 
    public static void main(String args[])
    {
        TreeClassics tabbedPane = new TreeClassics();
        tabbedPane.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
    }
}

/**
 * The TreeData class
 * @author Philip Kao
 * @version 5/2/06
 * IB Comsci Dossier: TreeClassics program
 */
public class TreeData
{
    private String modelNo;       // Tree model number (Format: XX-XXX-XXX)
    private int quantity;       // Quantity of desired tree model
    private double thickness;   // Thickness of plys needed for each tree (mm)
    private double width;
    private String color;
    private double plys;
 
    // Class constructor (blank data)
    public TreeData()
    {}
 
    // Class constructor (new data)
    public TreeData(String modelNo, int quantity, double thickness,
        double width, String color, double plys)
    {
        setModelNo(modelNo);
        setQuantity(quantity);
        setThickness(thickness);
        setWidth(width);
        setColor(color);
        setPlys(plys);
    }
 
    public void setQuantity(int quantity)
    {this.quantity = quantity; }
 
    public int getQuantity()
    {return quantity; }
 
    public void setModelNo(String modelNo)
    {this.modelNo = modelNo;}
 
    public String getModelNo()
    {return modelNo;}
 
    public void setThickness(double thickness)
    {this.thickness = thickness;}
 
    public double getThickness()
    {return thickness;}
 
    public void setWidth(double width)
    {this.width = width;}
 
    public double getWidth()
    {return width;}
 
    public void setColor(String color)
    {this.color = color;}
 
    public String getColor()
    {return color;}
 
    public void setPlys(double plys)
    {this.plys = plys;}
 
    public double getPlys()
    {return plys;}
 
    public String toString()
    {
        return modelNo + "\t" + quantity + "\t" + thickness + "\t" + width +
            "\t" + color + "\t" + plys;
    }
 
    public boolean equals(Object o)
    {
        if (!(o instanceof TreeData))
            throw new IllegalArgumentException("Wrong type: expects TreeData");
 
        TreeData item = (TreeData)o;
        if (item.modelNo == modelNo &&
            item.thickness == thickness &&
            item.width == width &&
            item.color.equals(color) &&
            item.plys == plys)
            return true;
        else
            return false;
    }
}

public class Model
{
    private String modelNo;
    private double height;
    private int tipNum;
    private int group;
 
    // Blank constructor
    public Model()
    {}
 
    // Enter values for model information
    public Model(String modelNo, double height, int tipNum, int group)
    {
        setModelNo(modelNo);
        setHeight(height);
        setTipNum(tipNum);
        setGroup(group);
    }
 
    // Model number methods
    public void setModelNo(String modelNo)
    {this.modelNo = modelNo;}
 
    public String getModelNo()
    {return modelNo;}
 
    // Height methods
    public void setHeight(double height)
    {this.height = height;}
 
    public double getHeight()
    {return height;}
 
    // tipNum methods
    public void setTipNum(int tipNum)
    {this.tipNum = tipNum;}
 
    public int getTipNum()
    {return tipNum;}
 
    // group methods
    public void setGroup(int group)
    {this.group = group;}
 
    public int getGroup()
    {return group;}
}

/*
 * @(#)LinkedList.java	1.96 04/02/19
 *
 * Copyright 2004 Sun Microsystems, Inc. All rights reserved.
 * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
 */
package java.util;
 
/**
 * The <code>LinkedList</code> class implements a growable array of 
 * objects. Like an array, it contains components that can be 
 * accessed using an integer index. However, the size of a 
 * <code>LinkedList</code> can grow or shrink as needed to accommodate 
 * adding and removing items after the <code>LinkedList</code> has been created.<p>
 *
 * Each LinkedList tries to optimize storage management by maintaining a 
 * <code>capacity</code> and a <code>capacityIncrement</code>. The 
 * <code>capacity</code> is always at least as large as the LinkedList 
 * size; it is usually larger because as components are added to the 
 * LinkedList, the LinkedList's storage increases in chunks the size of 
 * <code>capacityIncrement</code>. An application can increase the 
 * capacity of a LinkedList before inserting a large number of 
 * components; this reduces the amount of incremental reallocation. <p>
 *
 * As of the Java 2 platform v1.2, this class has been retrofitted to
 * implement List, so that it becomes a part of Java's collection framework.
 * Unlike the new collection implementations, LinkedList is synchronized.<p>
 *
 * The Iterators returned by LinkedList's iterator and listIterator
 * methods are <em>fail-fast</em>: if the LinkedList is structurally modified
 * at any time after the Iterator is created, in any way except through the
 * Iterator's own remove or add methods, the Iterator will throw a
 * ConcurrentModificationException.  Thus, in the face of concurrent
 * modification, the Iterator fails quickly and cleanly, rather than risking
 * arbitrary, non-deterministic behavior at an undetermined time in the future.
 * The Enumerations returned by LinkedList's elements method are <em>not</em>
 * fail-fast.
 *
 * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
 * as it is, generally speaking, impossible to make any hard guarantees in the
 * presence of unsynchronized concurrent modification.  Fail-fast iterators
 * throw <tt>ConcurrentModificationException</tt> on a best-effort basis. 
 * Therefore, it would be wrong to write a program that depended on this
 * exception for its correctness:  <i>the fail-fast behavior of iterators
 * should be used only to detect bugs.</i><p>
 *
 * This class is a member of the 
 * <a href="{@docRoot}/../guide/collections/index.html">
 * Java Collections Framework</a>.
 *
 * @author  Lee Boynton
 * @author  Jonathan Payne
 * @version 1.96, 02/19/04
 * @see Collection
 * @see List
 * @see ArrayList
 * @see LinkedList
 * @since   JDK1.0
 */
public class LinkedList<E>
    extends AbstractList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    /**
     * The array buffer into which the components of the LinkedList are
     * stored. The capacity of the LinkedList is the length of this array buffer, 
     * and is at least large enough to contain all the LinkedList's elements.<p>
     *
     * Any array elements following the last element in the LinkedList are null.
     *
     * @serial
     */
    protected Object[] elementData;
 
    /**
     * The number of valid components in this <tt>LinkedList</tt> object. 
     * Components <tt>elementData[0]</tt> through 
     * <tt>elementData[elementCount-1]</tt> are the actual items.
     *
     * @serial
     */
    protected int elementCount;
 
    /**
     * The amount by which the capacity of the LinkedList is automatically 
     * incremented when its size becomes greater than its capacity.  If 
     * the capacity increment is less than or equal to zero, the capacity
     * of the LinkedList is doubled each time it needs to grow.
     *
     * @serial
     */
    protected int capacityIncrement;
 
    /** use serialVersionUID from JDK 1.0.2 for interoperability */
    private static final long serialVersionUID = -2767605614048989439L;
 
    /**
     * Constructs an empty LinkedList with the specified initial capacity and
     * capacity increment. 
     *
     * @param   initialCapacity     the initial capacity of the LinkedList.
     * @param   capacityIncrement   the amount by which the capacity is
     *                              increased when the LinkedList overflows.
     * @exception IllegalArgumentException if the specified initial capacity
     *               is negative
     */
    public LinkedList(int initialCapacity, int capacityIncrement) {
	super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
	this.elementData = new Object[initialCapacity];
	this.capacityIncrement = capacityIncrement;
    }
 
    /**
     * Constructs an empty LinkedList with the specified initial capacity and 
     * with its capacity increment equal to zero.
     *
     * @param   initialCapacity   the initial capacity of the LinkedList.
     * @exception IllegalArgumentException if the specified initial capacity
     *               is negative
     */
    public LinkedList(int initialCapacity) {
	this(initialCapacity, 0);
    }
 
    /**
     * Constructs an empty LinkedList so that its internal data array 
     * has size <tt>10</tt> and its standard capacity increment is 
     * zero. 
     */
    public LinkedList() {
	this(10);
    }
 
    /**
     * Constructs a LinkedList containing the elements of the specified
     * collection, in the order they are returned by the collection's
     * iterator.
     *
     * @param c the collection whose elements are to be placed into this
     *       LinkedList.
     * @throws NullPointerException if the specified collection is null.
     * @since   1.2
     */
    public LinkedList(Collection<? extends E> c) {
        elementCount = c.size();
        // 10% for growth
        elementData = new Object[
                      (int)Math.min((elementCount*110L)/100,Integer.MAX_VALUE)]; 
        c.toArray(elementData);
    }
 
    /**
     * Copies the components of this LinkedList into the specified array. The 
     * item at index <tt>k</tt> in this LinkedList is copied into component 
     * <tt>k</tt> of <tt>anArray</tt>. The array must be big enough to hold 
     * all the objects in this LinkedList, else an 
     * <tt>IndexOutOfBoundsException</tt> is thrown.
     *
     * @param   anArray   the array into which the components get copied.
     * @throws  NullPointerException if the given array is null.
     */
    public synchronized void copyInto(Object[] anArray) {
	System.arraycopy(elementData, 0, anArray, 0, elementCount);
    }
 
    /**
     * Trims the capacity of this LinkedList to be the LinkedList's current 
     * size. If the capacity of this LinkedList is larger than its current 
     * size, then the capacity is changed to equal the size by replacing 
     * its internal data array, kept in the field <tt>elementData</tt>, 
     * with a smaller one. An application can use this operation to 
     * minimize the storage of a LinkedList. 
     */
    public synchronized void trimToSize() {
	modCount++;
	int oldCapacity = elementData.length;
	if (elementCount < oldCapacity) {
	    Object oldData[] = elementData;
	    elementData = new Object[elementCount];
	    System.arraycopy(oldData, 0, elementData, 0, elementCount);
	}
    }
 
    /**
     * Increases the capacity of this LinkedList, if necessary, to ensure 
     * that it can hold at least the number of components specified by 
     * the minimum capacity argument.
     *
     * <p>If the current capacity of this LinkedList is less than
     * <tt>minCapacity</tt>, then its capacity is increased by replacing its
     * internal data array, kept in the field <tt>elementData</tt>, with a
     * larger one.  The size of the new data array will be the old size plus
     * <tt>capacityIncrement</tt>, unless the value of
     * <tt>capacityIncrement</tt> is less than or equal to zero, in which case
     * the new capacity will be twice the old capacity; but if this new size
     * is still smaller than <tt>minCapacity</tt>, then the new capacity will
     * be <tt>minCapacity</tt>.
     *
     * @param minCapacity the desired minimum capacity.
     */
    public synchronized void ensureCapacity(int minCapacity) {
	modCount++;
	ensureCapacityHelper(minCapacity);
    }
 
    /**
     * This implements the unsynchronized semantics of ensureCapacity.
     * Synchronized methods in this class can internally call this 
     * method for ensuring capacity without incurring the cost of an 
     * extra synchronization.
     *
     * @see java.util.LinkedList#ensureCapacity(int)
     */ 
    private void ensureCapacityHelper(int minCapacity) {
	int oldCapacity = elementData.length;
	if (minCapacity > oldCapacity) {
	    Object[] oldData = elementData;
	    int newCapacity = (capacityIncrement > 0) ?
		(oldCapacity + capacityIncrement) : (oldCapacity * 2);
    	    if (newCapacity < minCapacity) {
		newCapacity = minCapacity;
	    }
	    elementData = new Object[newCapacity];
	    System.arraycopy(oldData, 0, elementData, 0, elementCount);
	}
    }
 
    /**
     * Sets the size of this LinkedList. If the new size is greater than the 
     * current size, new <code>null</code> items are added to the end of 
     * the LinkedList. If the new size is less than the current size, all 
     * components at index <code>newSize</code> and greater are discarded.
     *
     * @param   newSize   the new size of this LinkedList.
     * @throws  ArrayIndexOutOfBoundsException if new size is negative.
     */
    public synchronized void setSize(int newSize) {
	modCount++;
	if (newSize > elementCount) {
	    ensureCapacityHelper(newSize);
	} else {
	    for (int i = newSize ; i < elementCount ; i++) {
		elementData[i] = null;
	    }
	}
	elementCount = newSize;
    }
 
    /**
     * Returns the current capacity of this LinkedList.
     *
     * @return  the current capacity (the length of its internal 
     *          data array, kept in the field <tt>elementData</tt> 
     *          of this LinkedList).
     */
    public synchronized int capacity() {
	return elementData.length;
    }
 
    /**
     * Returns the number of components in this LinkedList.
     *
     * @return  the number of components in this LinkedList.
     */
    public synchronized int size() {
	return elementCount;
    }
 
    /**
     * Tests if this LinkedList has no components.
     *
     * @return  <code>true</code> if and only if this LinkedList has 
     *          no components, that is, its size is zero;
     *          <code>false</code> otherwise.
     */
    public synchronized boolean isEmpty() {
	return elementCount == 0;
    }
 
    /**
     * Returns an enumeration of the components of this LinkedList. The 
     * returned <tt>Enumeration</tt> object will generate all items in 
     * this LinkedList. The first item generated is the item at index <tt>0</tt>, 
     * then the item at index <tt>1</tt>, and so on. 
     *
     * @return  an enumeration of the components of this LinkedList.
     * @see     Enumeration
     * @see     Iterator
     */
    public Enumeration<E> elements() {
	return new Enumeration<E>() {
	    int count = 0;
 
	    public boolean hasMoreElements() {
		return count < elementCount;
	    }
 
	    public E nextElement() {
		synchronized (LinkedList.this) {
		    if (count < elementCount) {
			return (E)elementData[count++];
		    }
		}
		throw new NoSuchElementException("LinkedList Enumeration");
	    }
	};
    }
 
    /**
     * Tests if the specified object is a component in this LinkedList.
     *
     * @param   elem   an object.
     * @return  <code>true</code> if and only if the specified object 
     * is the same as a component in this LinkedList, as determined by the 
     * <tt>equals</tt> method; <code>false</code> otherwise.
     */
    public boolean contains(Object elem) {
	return indexOf(elem, 0) >= 0;
    }
 
    /**
     * Searches for the first occurence of the given argument, testing 
     * for equality using the <code>equals</code> method. 
     *
     * @param   elem   an object.
     * @return  the index of the first occurrence of the argument in this
     *          LinkedList, that is, the smallest value <tt>k</tt> such that 
     *          <tt>elem.equals(elementData[k])</tt> is <tt>true</tt>; 
     *          returns <code>-1</code> if the object is not found.
     * @see     Object#equals(Object)
     */
    public int indexOf(Object elem) {
	return indexOf(elem, 0);
    }
 
    /**
     * Searches for the first occurence of the given argument, beginning 
     * the search at <code>index</code>, and testing for equality using 
     * the <code>equals</code> method. 
     *
     * @param   elem    an object.
     * @param   index   the non-negative index to start searching from.
     * @return  the index of the first occurrence of the object argument in
     *          this LinkedList at position <code>index</code> or later in the
     *          LinkedList, that is, the smallest value <tt>k</tt> such that 
     *          <tt>elem.equals(elementData[k]) && (k &gt;= index)</tt> is 
     *          <tt>true</tt>; returns <code>-1</code> if the object is not 
     *          found. (Returns <code>-1</code> if <tt>index</tt> &gt;= the
     *          current size of this <tt>LinkedList</tt>.)
     * @exception  IndexOutOfBoundsException  if <tt>index</tt> is negative.
     * @see     Object#equals(Object)
     */
    public synchronized int indexOf(Object elem, int index) {
	if (elem == null) {
	    for (int i = index ; i < elementCount ; i++)
		if (elementData[i]==null)
		    return i;
	} else {
	    for (int i = index ; i < elementCount ; i++)
		if (elem.equals(elementData[i]))
		    return i;
	}
	return -1;
    }
 
    /**
     * Returns the index of the last occurrence of the specified object in
     * this LinkedList.
     *
     * @param   elem   the desired component.
     * @return  the index of the last occurrence of the specified object in
     *          this LinkedList, that is, the largest value <tt>k</tt> such that 
     *          <tt>elem.equals(elementData[k])</tt> is <tt>true</tt>; 
     *          returns <code>-1</code> if the object is not found.
     */
    public synchronized int lastIndexOf(Object elem) {
	return lastIndexOf(elem, elementCount-1);
    }
 
    /**
     * Searches backwards for the specified object, starting from the 
     * specified index, and returns an index to it. 
     *
     * @param  elem    the desired component.
     * @param  index   the index to start searching from.
     * @return the index of the last occurrence of the specified object in this
     *          LinkedList at position less than or equal to <code>index</code> in
     *          the LinkedList, that is, the largest value <tt>k</tt> such that 
     *          <tt>elem.equals(elementData[k]) && (k &lt;= index)</tt> is 
     *          <tt>true</tt>; <code>-1</code> if the object is not found.
     *          (Returns <code>-1</code> if <tt>index</tt> is negative.)
     * @exception  IndexOutOfBoundsException  if <tt>index</tt> is greater
     *             than or equal to the current size of this LinkedList.
     */
    public synchronized int lastIndexOf(Object elem, int index) {
        if (index >= elementCount)
            throw new IndexOutOfBoundsException(index + " >= "+ elementCount);
 
	if (elem == null) {
	    for (int i = index; i >= 0; i--)
		if (elementData[i]==null)
		    return i;
	} else {
	    for (int i = index; i >= 0; i--)
		if (elem.equals(elementData[i]))
		    return i;
	}
	return -1;
    }
 
    /**
     * Returns the component at the specified index.<p>
     *
     * This method is identical in functionality to the get method
     * (which is part of the List interface).
     *
     * @param      index   an index into this LinkedList.
     * @return     the component at the specified index.
     * @exception  ArrayIndexOutOfBoundsException  if the <tt>index</tt> 
     *             is negative or not less than the current size of this 
     *             <tt>LinkedList</tt> object.
     *             given.
     * @see	   #get(int)
     * @see	   List
     */
    public synchronized E elementAt(int index) {
	if (index >= elementCount) {
	    throw new ArrayIndexOutOfBoundsException(index + " >= " + elementCount);
	}
 
        return (E)elementData[index];
    }
 
    /**
     * Returns the first component (the item at index <tt>0</tt>) of 
     * this LinkedList.
     *
     * @return     the first component of this LinkedList.
     * @exception  NoSuchElementException  if this LinkedList has no components.
     */
    public synchronized E firstElement() {
	if (elementCount == 0) {
	    throw new NoSuchElementException();
	}
	return (E)elementData[0];
    }
 
    /**
     * Returns the last component of the LinkedList.
     *
     * @return  the last component of the LinkedList, i.e., the component at index
     *          <code>size()&nbsp;-&nbsp;1</code>.
     * @exception  NoSuchElementException  if this LinkedList is empty.
     */
    public synchronized E lastElement() {
	if (elementCount == 0) {
	    throw new NoSuchElementException();
	}
	return (E)elementData[elementCount - 1];
    }
 
    /**
     * Sets the component at the specified <code>index</code> of this 
     * LinkedList to be the specified object. The previous component at that 
     * position is discarded.<p>
     *
     * The index must be a value greater than or equal to <code>0</code> 
     * and less than the current size of the LinkedList. <p>
     *
     * This method is identical in functionality to the set method
     * (which is part of the List interface). Note that the set method reverses
     * the order of the parameters, to more closely match array usage.  Note
     * also that the set method returns the old value that was stored at the
     * specified position.
     *
     * @param      obj     what the component is to be set to.
     * @param      index   the specified index.
     * @exception  ArrayIndexOutOfBoundsException  if the index was invalid.
     * @see        #size()
     * @see        List
     * @see	   #set(int, java.lang.Object)
     */
    public synchronized void setElementAt(E obj, int index) {
	if (index >= elementCount) {
	    throw new ArrayIndexOutOfBoundsException(index + " >= " + 
						     elementCount);
	}
	elementData[index] = obj;
    }
 
    /**
     * Deletes the component at the specified index. Each component in 
     * this LinkedList with an index greater or equal to the specified 
     * <code>index</code> is shifted downward to have an index one 
     * smaller than the value it had previously. The size of this LinkedList 
     * is decreased by <tt>1</tt>.<p>
     *
     * The index must be a value greater than or equal to <code>0</code> 
     * and less than the current size of the LinkedList. <p>
     *
     * This method is identical in functionality to the remove method
     * (which is part of the List interface).  Note that the remove method
     * returns the old value that was stored at the specified position.
     *
     * @param      index   the index of the object to remove.
     * @exception  ArrayIndexOutOfBoundsException  if the index was invalid.
     * @see        #size()
     * @see	   #remove(int)
     * @see	   List
     */
    public synchronized void removeElementAt(int index) {
	modCount++;
	if (index >= elementCount) {
	    throw new ArrayIndexOutOfBoundsException(index + " >= " + 
						     elementCount);
	}
	else if (index < 0) {
	    throw new ArrayIndexOutOfBoundsException(index);
	}
	int j = elementCount - index - 1;
	if (j > 0) {
	    System.arraycopy(elementData, index + 1, elementData, index, j);
	}
	elementCount--;
	elementData[elementCount] = null; /* to let gc do its work */
    }
 
    /**
     * Inserts the specified object as a component in this LinkedList at the 
     * specified <code>index</code>. Each component in this LinkedList with 
     * an index greater or equal to the specified <code>index</code> is 
     * shifted upward to have an index one greater than the value it had 
     * previously. <p>
     *
     * The index must be a value greater than or equal to <code>0</code> 
     * and less than or equal to the current size of the LinkedList. (If the
     * index is equal to the current size of the LinkedList, the new element
     * is appended to the LinkedList.)<p>
     *
     * This method is identical in functionality to the add(Object, int) method
     * (which is part of the List interface). Note that the add method reverses
     * the order of the parameters, to more closely match array usage.
     *
     * @param      obj     the component to insert.
     * @param      index   where to insert the new component.
     * @exception  ArrayIndexOutOfBoundsException  if the index was invalid.
     * @see        #size()
     * @see	   #add(int, Object)
     * @see	   List
     */
    public synchronized void insertElementAt(E obj, int index) {
	modCount++;
	if (index > elementCount) {
	    throw new ArrayIndexOutOfBoundsException(index
						     + " > " + elementCount);
	}
	ensureCapacityHelper(elementCount + 1);
	System.arraycopy(elementData, index, elementData, index + 1, elementCount - index);
	elementData[index] = obj;
	elementCount++;
    }
 
    /**
     * Adds the specified component to the end of this LinkedList, 
     * increasing its size by one. The capacity of this LinkedList is 
     * increased if its size becomes greater than its capacity. <p>
     *
     * This method is identical in functionality to the add(Object) method
     * (which is part of the List interface).
     *
     * @param   obj   the component to be added.
     * @see	   #add(Object)
     * @see	   List
     */
    public synchronized void addElement(E obj) {
	modCount++;
	ensureCapacityHelper(elementCount + 1);
	elementData[elementCount++] = obj;
    }
 
    /**
     * Removes the first (lowest-indexed) occurrence of the argument 
     * from this LinkedList. If the object is found in this LinkedList, each 
     * component in the LinkedList with an index greater or equal to the 
     * object's index is shifted downward to have an index one smaller 
     * than the value it had previously.<p>
     *
     * This method is identical in functionality to the remove(Object) 
     * method (which is part of the List interface).
     *
     * @param   obj   the component to be removed.
     * @return  <code>true</code> if the argument was a component of this
     *          LinkedList; <code>false</code> otherwise.
     * @see	List#remove(Object)
     * @see	List
     */
    public synchronized boolean removeElement(Object obj) {
	modCount++;
	int i = indexOf(obj);
	if (i >= 0) {
	    removeElementAt(i);
	    return true;
	}
	return false;
    }
 
    /**
     * Removes all components from this LinkedList and sets its size to zero.<p>
     *
     * This method is identical in functionality to the clear method
     * (which is part of the List interface).
     *
     * @see	#clear
     * @see	List
     */
    public synchronized void removeAllElements() {
        modCount++;
	// Let gc do its work
	for (int i = 0; i < elementCount; i++)
	    elementData[i] = null;
 
	elementCount = 0;
    }
 
    /**
     * Returns a clone of this LinkedList. The copy will contain a
     * reference to a clone of the internal data array, not a reference 
     * to the original internal data array of this <tt>LinkedList</tt> object. 
     *
     * @return  a clone of this LinkedList.
     */
    public synchronized Object clone() {
	try {
	    LinkedList<E> v = (LinkedList<E>) super.clone();
	    v.elementData = new Object[elementCount];
	    System.arraycopy(elementData, 0, v.elementData, 0, elementCount);
	    v.modCount = 0;
	    return v;
	} catch (CloneNotSupportedException e) { 
	    // this shouldn't happen, since we are Cloneable
	    throw new InternalError();
	}
    }
 
    /**
     * Returns an array containing all of the elements in this LinkedList
     * in the correct order.
     *
     * @since 1.2
     */
    public synchronized Object[] toArray() {
	Object[] result = new Object[elementCount];
	System.arraycopy(elementData, 0, result, 0, elementCount);
	return result;
    }
 
    /**
     * Returns an array containing all of the elements in this LinkedList in the
     * correct order; the runtime type of the returned array is that of the
     * specified array.  If the LinkedList fits in the specified array, it is
     * returned therein.  Otherwise, a new array is allocated with the runtime
     * type of the specified array and the size of this LinkedList.<p>
     *
     * If the LinkedList fits in the specified array with room to spare
     * (i.e., the array has more elements than the LinkedList),
     * the element in the array immediately following the end of the
     * LinkedList is set to null.  This is useful in determining the length
     * of the LinkedList <em>only</em> if the caller knows that the LinkedList
     * does not contain any null elements.
     *
     * @param a the array into which the elements of the LinkedList are to
     *		be stored, if it is big enough; otherwise, a new array of the
     * 		same runtime type is allocated for this purpose.
     * @return an array containing the elements of the LinkedList.
     * @exception ArrayStoreException the runtime type of a is not a supertype
     * of the runtime type of every element in this LinkedList.
     * @throws NullPointerException if the given array is null.
     * @since 1.2
     */
    public synchronized <T> T[] toArray(T[] a) {
        if (a.length < elementCount)
            a = (T[])java.lang.reflect.Array.newInstance(
                                a.getClass().getComponentType(), elementCount);
 
	System.arraycopy(elementData, 0, a, 0, elementCount);
 
        if (a.length > elementCount)
            a[elementCount] = null;
 
        return a;
    }
 
    // Positional Access Operations
 
    /**
     * Returns the element at the specified position in this LinkedList.
     *
     * @param index index of element to return.
     * @return object at the specified index
     * @exception ArrayIndexOutOfBoundsException index is out of range (index
     * 		  &lt; 0 || index &gt;= size()).
     * @since 1.2
     */
    public synchronized E get(int index) {
	if (index >= elementCount)
	    throw new ArrayIndexOutOfBoundsException(index);
 
	return (E)elementData[index];
    }
 
    /**
     * Replaces the element at the specified position in this LinkedList with the
     * specified element.
     *
     * @param index index of element to replace.
     * @param element element to be stored at the specified position.
     * @return the element previously at the specified position.
     * @exception ArrayIndexOutOfBoundsException index out of range
     *		  (index &lt; 0 || index &gt;= size()).
     * @since 1.2
     */
    public synchronized E set(int index, E element) {
	if (index >= elementCount)
	    throw new ArrayIndexOutOfBoundsException(index);
 
	Object oldValue = elementData[index];
	elementData[index] = element;
	return (E)oldValue;
    }
 
    /**
     * Appends the specified element to the end of this LinkedList.
     *
     * @param o element to be appended to this LinkedList.
     * @return true (as per the general contract of Collection.add).
     * @since 1.2
     */
    public synchronized boolean add(E o) {
	modCount++;
	ensureCapacityHelper(elementCount + 1);
	elementData[elementCount++] = o;
        return true;
    }
 
    /**
     * Removes the first occurrence of the specified element in this LinkedList
     * If the LinkedList does not contain the element, it is unchanged.  More
     * formally, removes the element with the lowest index i such that
     * <code>(o==null ? get(i)==null : o.equals(get(i)))</code> (if such
     * an element exists).
     *
     * @param o element to be removed from this LinkedList, if present.
     * @return true if the LinkedList contained the specified element.
     * @since 1.2
     */
    public boolean remove(Object o) {
        return removeElement(o);
    }
 
    /**
     * Inserts the specified element at the specified position in this LinkedList.
     * Shifts the element currently at that position (if any) and any
     * subsequent elements to the right (adds one to their indices).
     *
     * @param index index at which the specified element is to be inserted.
     * @param element element to be inserted.
     * @exception ArrayIndexOutOfBoundsException index is out of range
     *		  (index &lt; 0 || index &gt; size()).
     * @since 1.2
     */
    public void add(int index, E element) {
        insertElementAt(element, index);
    }
 
    /**
     * Removes the element at the specified position in this LinkedList.
     * shifts any subsequent elements to the left (subtracts one from their
     * indices).  Returns the element that was removed from the LinkedList.
     *
     * @exception ArrayIndexOutOfBoundsException index out of range (index
     * 		  &lt; 0 || index &gt;= size()).
     * @param index the index of the element to removed.
     * @return element that was removed
     * @since 1.2
     */
    public synchronized E remove(int index) {
	modCount++;
	if (index >= elementCount)
	    throw new ArrayIndexOutOfBoundsException(index);
	Object oldValue = elementData[index];
 
	int numMoved = elementCount - index - 1;
	if (numMoved > 0)
	    System.arraycopy(elementData, index+1, elementData, index,
			     numMoved);
	elementData[--elementCount] = null; // Let gc do its work
 
	return (E)oldValue;
    }
 
    /**
     * Removes all of the elements from this LinkedList.  The LinkedList will
     * be empty after this call returns (unless it throws an exception).
     *
     * @since 1.2
     */
    public void clear() {
        removeAllElements();
    }
 
    // Bulk Operations
 
    /**
     * Returns true if this LinkedList contains all of the elements in the
     * specified Collection.
     *
     * @param   c a collection whose elements will be tested for containment
     *          in this LinkedList
     * @return true if this LinkedList contains all of the elements in the
     *	       specified collection.
     * @throws NullPointerException if the specified collection is null.
     */
    public synchronized boolean containsAll(Collection<?> c) {
        return super.containsAll(c);
    }
 
    /**
     * Appends all of the elements in the specified Collection to the end of
     * this LinkedList, in the order that they are returned by the specified
     * Collection's Iterator.  The behavior of this operation is undefined if
     * the specified Collection is modified while the operation is in progress.
     * (This implies that the behavior of this call is undefined if the
     * specified Collection is this LinkedList, and this LinkedList is nonempty.)
     *
     * @param c elements to be inserted into this LinkedList.
     * @return <tt>true</tt> if this LinkedList changed as a result of the call.
     * @throws NullPointerException if the specified collection is null.
     * @since 1.2
     */
    public synchronized boolean addAll(Collection<? extends E> c) {
	modCount++;
        Object[] a = c.toArray();
        int numNew = a.length;
	ensureCapacityHelper(elementCount + numNew);
        System.arraycopy(a, 0, elementData, elementCount, numNew);
        elementCount += numNew;
	return numNew != 0;
    }
 
    /**
     * Removes from this LinkedList all of its elements that are contained in the
     * specified Collection.
     *
     * @param c a collection of elements to be removed from the LinkedList
     * @return true if this LinkedList changed as a result of the call.
     * @throws NullPointerException if the specified collection is null.
     * @since 1.2
     */
    public synchronized boolean removeAll(Collection<?> c) {
        return super.removeAll(c);
    }
 
    /**
     * Retains only the elements in this LinkedList that are contained in the
     * specified Collection.  In other words, removes from this LinkedList all
     * of its elements that are not contained in the specified Collection. 
     *
     * @param c a collection of elements to be retained in this LinkedList
     *          (all other elements are removed)
     * @return true if this LinkedList changed as a result of the call.
     * @throws NullPointerException if the specified collection is null.
     * @since 1.2
     */
    public synchronized boolean retainAll(Collection<?> c)  {
        return super.retainAll(c);
    }
 
    /**
     * Inserts all of the elements in the specified Collection into this
     * LinkedList at the specified position.  Shifts the element currently at
     * that position (if any) and any subsequent elements to the right
     * (increases their indices).  The new elements will appear in the LinkedList  
     * in the order that they are returned by the specified Collection's
     * iterator.
     *
     * @param index index at which to insert first element
     *		    from the specified collection.
     * @param c elements to be inserted into this LinkedList.
     * @return <tt>true</tt> if this LinkedList changed as a result of the call.
     * @exception ArrayIndexOutOfBoundsException index out of range (index
     *		  &lt; 0 || index &gt; size()).
     * @throws NullPointerException if the specified collection is null.
     * @since 1.2
     */
    public synchronized boolean addAll(int index, Collection<? extends E> c) {
	modCount++;
	if (index < 0 || index > elementCount)
	    throw new ArrayIndexOutOfBoundsException(index);
 
        Object[] a = c.toArray();
	int numNew = a.length;
	ensureCapacityHelper(elementCount + numNew);
 
	int numMoved = elementCount - index;
	if (numMoved > 0)
	    System.arraycopy(elementData, index, elementData, index + numNew,
			     numMoved);
 
        System.arraycopy(a, 0, elementData, index, numNew);
	elementCount += numNew;
	return numNew != 0;
    }
 
    /**
     * Compares the specified Object with this LinkedList for equality.  Returns
     * true if and only if the specified Object is also a List, both Lists
     * have the same size, and all corresponding pairs of elements in the two
     * Lists are <em>equal</em>.  (Two elements <code>e1</code> and
     * <code>e2</code> are <em>equal</em> if <code>(e1==null ? e2==null :
     * e1.equals(e2))</code>.)  In other words, two Lists are defined to be
     * equal if they contain the same elements in the same order.
     *
     * @param o the Object to be compared for equality with this LinkedList.
     * @return true if the specified Object is equal to this LinkedList
     */
    public synchronized boolean equals(Object o) {
        return super.equals(o);
    }
 
    /**
     * Returns the hash code value for this LinkedList.
     */
    public synchronized int hashCode() {
        return super.hashCode();
    }
 
    /**
     * Returns a string representation of this LinkedList, containing
     * the String representation of each element.
     */
    public synchronized String toString() {
        return super.toString();
    }
 
    /**
     * Returns a view of the portion of this List between fromIndex,
     * inclusive, and toIndex, exclusive.  (If fromIndex and ToIndex are
     * equal, the returned List is empty.)  The returned List is backed by this
     * List, so changes in the returned List are reflected in this List, and
     * vice-versa.  The returned List supports all of the optional List
     * operations supported by this List.<p>
     *
     * This method eliminates the need for explicit range operations (of
     * the sort that commonly exist for arrays).   Any operation that expects
     * a List can be used as a range operation by operating on a subList view
     * instead of a whole List.  For example, the following idiom
     * removes a range of elements from a List:
     * <pre>
     *	    list.subList(from, to).clear();
     * </pre>
     * Similar idioms may be constructed for indexOf and lastIndexOf,
     * and all of the algorithms in the Collections class can be applied to
     * a subList.<p>
     *
     * The semantics of the List returned by this method become undefined if
     * the backing list (i.e., this List) is <i>structurally modified</i> in
     * any way other than via the returned List.  (Structural modifications are
     * those that change the size of the List, or otherwise perturb it in such
     * a fashion that iterations in progress may yield incorrect results.)
     *
     * @param fromIndex low endpoint (inclusive) of the subList.
     * @param toIndex high endpoint (exclusive) of the subList.
     * @return a view of the specified range within this List.
     * @throws IndexOutOfBoundsException endpoint index value out of range
     *         <code>(fromIndex &lt; 0 || toIndex &gt; size)</code>
     * @throws IllegalArgumentException endpoint indices out of order
     *	       <code>(fromIndex &gt; toIndex)</code>
     */
    public synchronized List<E> subList(int fromIndex, int toIndex) {
        return Collections.synchronizedList(super.subList(fromIndex, toIndex),
                                            this);
    }
 
    /**
     * Removes from this List all of the elements whose index is between
     * fromIndex, inclusive and toIndex, exclusive.  Shifts any succeeding
     * elements to the left (reduces their index).
     * This call shortens the ArrayList by (toIndex - fromIndex) elements.  (If
     * toIndex==fromIndex, this operation has no effect.)
     *
     * @param fromIndex index of first element to be removed.
     * @param toIndex index after last element to be removed.
     */
    protected synchronized void removeRange(int fromIndex, int toIndex) {
	modCount++;
	int numMoved = elementCount - toIndex;
        System.arraycopy(elementData, toIndex, elementData, fromIndex,
                         numMoved);
 
	// Let gc do its work
	int newElementCount = elementCount - (toIndex-fromIndex);
	while (elementCount != newElementCount)
	    elementData[--elementCount] = null;
    }
 
    /**
     * Save the state of the <tt>LinkedList</tt> instance to a stream (that
     * is, serialize it).  This method is present merely for synchronization.
     * It just calls the default readObject method.
     */
    private synchronized void writeObject(java.io.ObjectOutputStream s)
        throws java.io.IOException
    {
	s.defaultWriteObject();
    }
}

/**
 *
 * @author Philip Kao
 */
 
import java.io.*;
import java.util.*;
import javax.swing.*;
import java.awt.*;
 
public class OrderList extends LinkedList<TreeData>
{
    public static final int SORT_BY_MODEL_NO = 0;
    public static final int SORT_BY_THICKNESS = 1;
    public static final int SORT_BY_WIDTH = 2;
    public static final int SORT_BY_COLOR = 3;
 
    // Constructor
    public OrderList()
    {
        super(); // accomodate 5 items, extend by 5 when overflow
    }
 
   /**
    * Constructor with stuff
    * @param file
    */
    public OrderList(File inFile, Component c)
    {
        try
        {
            Scanner in = new Scanner(inFile);
            while (in.hasNextLine())
            {
                Scanner lineScanner = new Scanner(in.nextLine());
                lineScanner.useDelimiter("\t");
                try {
                    String model = lineScanner.next();
                    int quantity = lineScanner.nextInt();
                    double thickness = lineScanner.nextDouble();
                    double width = lineScanner.nextDouble();
                    String color = lineScanner.next();
                    double plys = lineScanner.nextDouble();
 
                    add(new TreeData(model, quantity, thickness, width, color, plys));
                }
                catch (NoSuchElementException e) { continue; }
            }
        }
        catch (IOException e)
        {   JOptionPane.showMessageDialog(c, "Error Opening File",
                "Error", JOptionPane.ERROR_MESSAGE ); }
    }
 
    //add item to order list; if item of same specs exists, add to quantity
    public boolean add(TreeData item)
    {
        for (int i = 0; i < size(); i++) {
            TreeData temp = get(i);
            if (temp.equals(item)) {
                temp.setQuantity(temp.getQuantity() + item.getQuantity());
                return true;
            }
        }
        return super.add(item);
    }
 
    /**
     *
     * @param sortType
     */
    public void sort(int sortType)
    {
        quicksort(0, size()-1, sortType);
    }
 
    /**
     * Sort an array using Quicksort algorithm. Adapted from method in C at
     * http://www.tcnj.edu/~mmmartin/CMSC410/qs-complexity.doc
     * @param a An array of Comparable items.
     * @param left Start point of range.
     * @param right End point of range.
     */
    private void quicksort(int left, int right, int sortType)
    {
        if (left >= right) return;
        else
        {
            int l = left;
            int r = right;
            TreeData pivot = get((l+r)/2); // choose pivot as middle item
            // partition
            do
            {
                while (compare(get(l),pivot,sortType) < 0) l++;
                while (compare(get(r),pivot,sortType) > 0) r--;
                if (l <= r)
                {
                    // swap a[l] and a[r]
                    TreeData tmp = get(l);
                    set(l, get(r));
                    set(r, tmp);
                    // move on
                    l++;
                    r--;
                }
            }
            while (l <= r);
 
            // recursively sort left and right partitions
            quicksort(left, r, sortType);
            quicksort(l, right, sortType);
        }
    }
 
    /**
     * @param a First object of field type to compare
     * @param b Second object of field type to compare
     * @param sortType Identifier for field type
     */
    private int compare(TreeData a, TreeData b, int sortType)
    {
        String s1, s2;
        double d1, d2;
 
        // Sorts by model number or color (string type)
        switch (sortType)
        {
            case SORT_BY_MODEL_NO:
                s1 = a.getModelNo();
                s2 = b.getModelNo();
                // If s1 is <= s2, returns true
                return s1.compareTo(s2);
            case SORT_BY_COLOR:
                s1 = a.getColor();
                s2 = b.getColor();
                // If s1 is <= s2, returns true
                return s1.compareTo(s2);
            case SORT_BY_THICKNESS:
                // Class compare
                d1 = a.getThickness();
                d2 = b.getThickness();
                return Double.compare(d1,d2);
            case SORT_BY_WIDTH:
                // Class compare
                d1 = a.getWidth();
                d2 = b.getWidth();
                return Double.compare(d1,d2);
        }
        return 0;
    }
 
    /**
     *
     */
    public String toString()
    {
        String listOutput = "";
        for (int i = 0; i < size(); i++)
        {
            TreeData item = get(i);
            if (item == null) break;
            listOutput += item.toString() + "\r\n";
        }
        return listOutput;
    }
 
    /**
     *
     */
    public static void main(String[] args)
    {
        OrderList list = new OrderList();
        list.sort(SORT_BY_WIDTH);
        for (int i = 0; i<5; i++)
            System.out.println(list.get(i).toString());
    }
}