/*
 * @(#)JPEGMetadata.java	1.27 03/12/19
 *
 * Copyright 2004 Sun Microsystems, Inc. All rights reserved.
 * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
 */

package com.sun.imageio.plugins.jpeg;

import javax.imageio.ImageTypeSpecifier;
import javax.imageio.ImageWriteParam;
import javax.imageio.IIOException;
import javax.imageio.stream.ImageInputStream;
import javax.imageio.stream.ImageOutputStream;
import javax.imageio.metadata.IIOMetadata;
import javax.imageio.metadata.IIOMetadataNode;
import javax.imageio.metadata.IIOMetadataFormat;
import javax.imageio.metadata.IIOMetadataFormatImpl;
import javax.imageio.metadata.IIOInvalidTreeException;
import javax.imageio.plugins.jpeg.JPEGQTable;
import javax.imageio.plugins.jpeg.JPEGHuffmanTable;
import javax.imageio.plugins.jpeg.JPEGImageWriteParam;

import org.w3c.dom.Node;
import org.w3c.dom.NodeList;
import org.w3c.dom.NamedNodeMap;

import java.util.List;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.ListIterator;
import java.io.IOException;
import java.awt.color.ICC_Profile;
import java.awt.color.ICC_ColorSpace;
import java.awt.color.ColorSpace;
import java.awt.image.ColorModel;
import java.awt.Point;

/**
 * Metadata for the JPEG plug-in.
 */
public class JPEGMetadata extends IIOMetadata implements Cloneable {

    //////// Private variables

    private static final boolean debug = false;

    /**
     * A copy of <code>markerSequence</code>, created the first time the
     * <code>markerSequence</code> is modified.  This is used by reset
     * to restore the original state.
     */
    private List resetSequence = null;

    /**
     * Set to <code>true</code> when reading a thumbnail stored as 
     * JPEG.  This is used to enforce the prohibition of JFIF thumbnails
     * containing any JFIF marker segments, and to ensure generation of
     * a correct native subtree during <code>getAsTree</code>.
     */
    private boolean inThumb = false;

    /**
     * Set by the chroma node construction method to signal the
     * presence or absence of an alpha channel to the transparency
     * node construction method.  Used only when constructing a
     * standard metadata tree.
     */
    private boolean hasAlpha;

    //////// end of private variables

    /////// Package-access variables

    /**
     * All data is a list of <code>MarkerSegment</code> objects.
     * When accessing the list, use the tag to identify the particular
     * subclass.  Any JFIF marker segment must be the first element
     * of the list if it is present, and any JFXX or APP2ICC marker
     * segments are subordinate to the JFIF marker segment.  This
     * list is package visible so that the writer can access it.
     * @see #MarkerSegment
     */
    List markerSequence = new ArrayList();

    /**
     * Indicates whether this object represents stream or image
     * metadata.  Package-visible so the writer can see it.
     */
    final boolean isStream;

    /////// End of package-access variables

    /////// Constructors

    /**
     * Constructor containing code shared by other constructors.
     */
    JPEGMetadata(boolean isStream, boolean inThumb) {
        super(true,  // Supports standard format
              JPEG.nativeImageMetadataFormatName,  // and a native format
              JPEG.nativeImageMetadataFormatClassName,
              null, null);  // No other formats
        this.inThumb = inThumb;
        // But if we are stream metadata, adjust the variables
        this.isStream = isStream;
        if (isStream) {
            nativeMetadataFormatName = JPEG.nativeStreamMetadataFormatName;
            nativeMetadataFormatClassName = 
                JPEG.nativeStreamMetadataFormatClassName;
        }
    }

    /*
     * Constructs a <code>JPEGMetadata</code> object by reading the
     * contents of an <code>ImageInputStream</code>.  Has package-only
     * access.
     * 
     * @param isStream A boolean indicating whether this object will be
     * stream or image metadata.
     * @param isThumb A boolean indicating whether this metadata object
     * is for an image or for a thumbnail stored as JPEG.
     * @param iis An <code>ImageInputStream</code> from which to read
     * the metadata.
     * @param reader The <code>JPEGImageReader</code> calling this
     * constructor, to which warnings should be sent.
     */
    JPEGMetadata(boolean isStream,
                 boolean isThumb,
                 ImageInputStream iis, 
                 JPEGImageReader reader) throws IOException { 
        this(isStream, isThumb);

        JPEGBuffer buffer = new JPEGBuffer(iis);

        buffer.loadBuf(0);

        // The first three bytes should be FF, SOI, FF
        if (((buffer.buf[0] & 0xff) != 0xff) 
            || ((buffer.buf[1] & 0xff) != JPEG.SOI)
            || ((buffer.buf[2] & 0xff) != 0xff)) {
            throw new IIOException ("Image format error");
        }

        boolean done = false;
        buffer.bufAvail -=2;  // Next byte should be the ff before a marker
        buffer.bufPtr = 2;
        MarkerSegment newGuy = null;
        while (!done) {
            byte [] buf;
            int ptr;
            buffer.loadBuf(1);
            if (debug) {
                System.out.println("top of loop");
                buffer.print(10);
            }
            buffer.scanForFF(reader);
            switch (buffer.buf[buffer.bufPtr] & 0xff) {
            case 0:
                if (debug) {
                    System.out.println("Skipping 0");
                }
                buffer.bufAvail--;
                buffer.bufPtr++;
                break;
            case JPEG.SOF0:
            case JPEG.SOF1:
            case JPEG.SOF2:
                if (isStream) {
                    throw new IIOException 
                        ("SOF not permitted in stream metadata");
                }
                newGuy = new SOFMarkerSegment(buffer);
                break;
            case JPEG.DQT:
                newGuy = new DQTMarkerSegment(buffer);
                break;
            case JPEG.DHT:
                newGuy = new DHTMarkerSegment(buffer);
                break;
            case JPEG.DRI:
                newGuy = new DRIMarkerSegment(buffer);
                break;
            case JPEG.APP0:
                // Either JFIF, JFXX, or unknown APP0
                buffer.loadBuf(8); // tag, length, id
                buf = buffer.buf;
                ptr = buffer.bufPtr;
                if ((buf[ptr+3] == 'J') 
                    && (buf[ptr+4] == 'F')
                    && (buf[ptr+5] == 'I')
                    && (buf[ptr+6] == 'F')
                    && (buf[ptr+7] == 0)) {
                    if (inThumb) {
                        reader.warningOccurred
                            (JPEGImageReader.WARNING_NO_JFIF_IN_THUMB);
                        // Leave newGuy null
                        // Read a dummy to skip the segment
                        JFIFMarkerSegment dummy = 
                            new JFIFMarkerSegment(buffer);
                    } else if (isStream) {
                        throw new IIOException 
                            ("JFIF not permitted in stream metadata");
                    } else if (markerSequence.isEmpty() == false) {
                        throw new IIOException
                            ("JFIF APP0 must be first marker after SOI");
                    } else {
                        newGuy = new JFIFMarkerSegment(buffer);
                    }
                } else if ((buf[ptr+3] == 'J') 
                           && (buf[ptr+4] == 'F')
                           && (buf[ptr+5] == 'X')
                           && (buf[ptr+6] == 'X')
                           && (buf[ptr+7] == 0)) {
                    if (isStream) {
                        throw new IIOException 
                            ("JFXX not permitted in stream metadata");
                    }
                    if (inThumb) {
                        throw new IIOException
                          ("JFXX markers not allowed in JFIF JPEG thumbnail");
                    }
                    JFIFMarkerSegment jfif = 
                        (JFIFMarkerSegment) findMarkerSegment
                               (JFIFMarkerSegment.class, true);
                    if (jfif == null) {
                        throw new IIOException 
                            ("JFXX encountered without prior JFIF!");
                    }
                    jfif.addJFXX(buffer, reader);
                    // newGuy remains null
                } else {
                    newGuy = new MarkerSegment(buffer);
                    newGuy.loadData(buffer);
                }
                break;
            case JPEG.APP2:
                // Either an ICC profile or unknown APP2
                buffer.loadBuf(15); // tag, length, id
                if ((buffer.buf[buffer.bufPtr+3] == 'I')
                    && (buffer.buf[buffer.bufPtr+4] == 'C')
                    && (buffer.buf[buffer.bufPtr+5] == 'C')
                    && (buffer.buf[buffer.bufPtr+6] == '_')
                    && (buffer.buf[buffer.bufPtr+7] == 'P')
                    && (buffer.buf[buffer.bufPtr+8] == 'R')
                    && (buffer.buf[buffer.bufPtr+9] == 'O')
                    && (buffer.buf[buffer.bufPtr+10] == 'F')
                    && (buffer.buf[buffer.bufPtr+11] == 'I')
                    && (buffer.buf[buffer.bufPtr+12] == 'L')
                    && (buffer.buf[buffer.bufPtr+13] == 'E')
                    && (buffer.buf[buffer.bufPtr+14] == 0)
                    ) {
                    if (isStream) {
                        throw new IIOException 
                            ("ICC profiles not permitted in stream metadata");
                    }

                    JFIFMarkerSegment jfif = 
                        (JFIFMarkerSegment) findMarkerSegment
                        (JFIFMarkerSegment.class, true);
                    if (jfif == null) {
                        throw new IIOException 
                            ("ICC APP2 encountered without prior JFIF!");
                    }
                    jfif.addICC(buffer);
                    // newGuy remains null
                } else {
                    newGuy = new MarkerSegment(buffer);
                    newGuy.loadData(buffer);
                }
                break;
            case JPEG.APP14:
                // Either Adobe or unknown APP14
                buffer.loadBuf(8); // tag, length, id
                if ((buffer.buf[buffer.bufPtr+3] == 'A')
                    && (buffer.buf[buffer.bufPtr+4] == 'd')
                    && (buffer.buf[buffer.bufPtr+5] == 'o')
                    && (buffer.buf[buffer.bufPtr+6] == 'b')
                    && (buffer.buf[buffer.bufPtr+7] == 'e')) {
                    if (isStream) {
                        throw new IIOException 
                      ("Adobe APP14 markers not permitted in stream metadata");
                    }
                    newGuy = new AdobeMarkerSegment(buffer);
                } else {
                    newGuy = new MarkerSegment(buffer);
                    newGuy.loadData(buffer);
                }

                break;
            case JPEG.COM:
                newGuy = new COMMarkerSegment(buffer);
                break;
            case JPEG.SOS:
                if (isStream) {
                    throw new IIOException 
                        ("SOS not permitted in stream metadata");
                }
                newGuy = new SOSMarkerSegment(buffer);
                break;
            case JPEG.RST0:
            case JPEG.RST1:
            case JPEG.RST2:
            case JPEG.RST3:
            case JPEG.RST4:
            case JPEG.RST5:
            case JPEG.RST6:
            case JPEG.RST7:
                if (debug) {
                    System.out.println("Restart Marker");
                }
                buffer.bufPtr++; // Just skip it
                buffer.bufAvail--;
                break;
            case JPEG.EOI:
                done = true;
                buffer.bufPtr++;
                buffer.bufAvail--;
                break;
            default:
                newGuy = new MarkerSegment(buffer);
                newGuy.loadData(buffer);
                newGuy.unknown = true;
                break;
            }
            if (newGuy != null) {
                markerSequence.add(newGuy);
                if (debug) {
                    newGuy.print();
                }
                newGuy = null;
            }
        }

        // Now that we've read up to the EOI, we need to push back 
        // whatever is left in the buffer, so that the next read 
        // in the native code will work.

        buffer.pushBack();

        if (!isConsistent()) {
            throw new IIOException("Inconsistent metadata read from stream");
        }
    }

    /**
     * Constructs a default stream <code>JPEGMetadata</code> object appropriate
     * for the given write parameters.
     */
    JPEGMetadata(ImageWriteParam param, JPEGImageWriter writer) {
        this(true, false);
        
        JPEGImageWriteParam jparam = null;
        
        if ((param != null) && (param instanceof JPEGImageWriteParam)) {
            jparam = (JPEGImageWriteParam) param;
            if (!jparam.areTablesSet()) {
                jparam = null;
            }
        }
        if (jparam != null) {
            markerSequence.add(new DQTMarkerSegment(jparam.getQTables()));
            markerSequence.add
                (new DHTMarkerSegment(jparam.getDCHuffmanTables(),
                                      jparam.getACHuffmanTables()));
        } else {
            // default tables.
            markerSequence.add(new DQTMarkerSegment(JPEG.getDefaultQTables()));
            markerSequence.add(new DHTMarkerSegment(JPEG.getDefaultHuffmanTables(true),
                                                    JPEG.getDefaultHuffmanTables(false)));
        }

        // Defensive programming
        if (!isConsistent()) {
            throw new InternalError("Default stream metadata is inconsistent");
        }
    }

    /**
     * Constructs a default image <code>JPEGMetadata</code> object appropriate
     * for the given image type and write parameters.
     */
    JPEGMetadata(ImageTypeSpecifier imageType,
                 ImageWriteParam param,
                 JPEGImageWriter writer) {
        this(false, false);

        boolean wantJFIF = true;
        boolean wantAdobe = false;
        int transform = JPEG.ADOBE_UNKNOWN;
        boolean willSubsample = true;
        boolean wantICC = false;
        boolean wantProg = false;
        boolean wantOptimized = false;
        boolean wantExtended = false;
        boolean wantQTables = true;
        boolean wantHTables = true;
        float quality = JPEG.DEFAULT_QUALITY;
        byte[] componentIDs = { 1, 2, 3, 4};
        int numComponents = 0;

        ImageTypeSpecifier destType = null;

        if (param != null) {
            destType = param.getDestinationType();
            if (destType != null) {
                if (imageType != null) {
                    // Ignore the destination type. 
                    writer.warningOccurred
                        (JPEGImageWriter.WARNING_DEST_IGNORED);
                    destType = null;
                }
            }
            // The only progressive mode that makes sense here is MODE_DEFAULT
            if (param.canWriteProgressive()) {  
                // the param may not be one of ours, so it may return false.
                // If so, the following would throw an exception
                if (param.getProgressiveMode() == ImageWriteParam.MODE_DEFAULT) {
                    wantProg = true;
                    wantOptimized = true;
                    wantHTables = false;
                }
            }

            if (param instanceof JPEGImageWriteParam) {
                JPEGImageWriteParam jparam = (JPEGImageWriteParam) param;
                if (jparam.areTablesSet()) {
                    wantQTables = false;  // If the param has them, metadata shouldn't
                    wantHTables = false;
                    if ((jparam.getDCHuffmanTables().length > 2) 
                            || (jparam.getACHuffmanTables().length > 2)) {
                        wantExtended = true;
                    }
                }
                // Progressive forces optimized, regardless of param setting
                // so consult the param re optimized only if not progressive
                if (!wantProg) {
                    wantOptimized = jparam.getOptimizeHuffmanTables();
                    if (wantOptimized) {
                        wantHTables = false;
                    }
                }
            }

            // compression quality should determine the q tables.  Note that this
            // will be ignored if we already decided not to create any.
            // Again, the param may not be one of ours, so we must check that it
            // supports compression settings
            if (param.canWriteCompressed()) {
                if (param.getCompressionMode() == ImageWriteParam.MODE_EXPLICIT) {
                    quality = param.getCompressionQuality();
                }
            }                
        }
        
        // We are done with the param, now for the image types
        
        ColorSpace cs = null;
        if (destType != null) {
            ColorModel cm = destType.getColorModel();
            numComponents = cm.getNumComponents();
            boolean hasExtraComponents = (cm.getNumColorComponents() != numComponents);
            boolean hasAlpha = cm.hasAlpha();
            cs = cm.getColorSpace();
            int type = cs.getType();
            switch(type) {
            case ColorSpace.TYPE_GRAY:
                willSubsample = false;
                if (hasExtraComponents) {  // e.g. alpha
                    wantJFIF = false;
                }
                break;
            case ColorSpace.TYPE_3CLR:
                if (cs == JPEG.YCC) {
                    wantJFIF = false;
                    componentIDs[0] = (byte) 'Y';
                    componentIDs[1] = (byte) 'C';
                    componentIDs[2] = (byte) 'c';
                    if (hasAlpha) {
                        componentIDs[3] = (byte) 'A';
                    }
                }
                break;
            case ColorSpace.TYPE_YCbCr:
                if (hasExtraComponents) { // e.g. K or alpha
                    wantJFIF = false;
                    if (!hasAlpha) { // Not alpha, so must be K
                        wantAdobe = true;
                        transform = JPEG.ADOBE_YCCK;
                    }
                }
                break;
            case ColorSpace.TYPE_RGB:  // with or without alpha
                wantJFIF = false;
                wantAdobe = true;
                willSubsample = false;
                componentIDs[0] = (byte) 'R';
                componentIDs[1] = (byte) 'G';
                componentIDs[2] = (byte) 'B';
                if (hasAlpha) {
                    componentIDs[3] = (byte) 'A';
                }
                break;
            default:  
                // Everything else is not subsampled, gets no special marker,
                // and component ids are 1 - N
                wantJFIF = false;
                willSubsample = false;
            }
        } else if (imageType != null) {
            ColorModel cm = imageType.getColorModel();
            numComponents = cm.getNumComponents();
            boolean hasExtraComponents = (cm.getNumColorComponents() != numComponents);
            boolean hasAlpha = cm.hasAlpha();
            cs = cm.getColorSpace();
            int type = cs.getType();
            switch(type) {
            case ColorSpace.TYPE_GRAY:
                willSubsample = false;
                if (hasExtraComponents) {  // e.g. alpha
                    wantJFIF = false;
                }
                break;
            case ColorSpace.TYPE_RGB:  // with or without alpha
                // without alpha we just accept the JFIF defaults
                if (hasAlpha) {
                    wantJFIF = false;
                }
                break;
            case ColorSpace.TYPE_3CLR:
                wantJFIF = false;
                willSubsample = false;
                if (cs.equals(ColorSpace.getInstance(ColorSpace.CS_PYCC))) {
                    willSubsample = true;
                    wantAdobe = true;
                    componentIDs[0] = (byte) 'Y';
                    componentIDs[1] = (byte) 'C';
                    componentIDs[2] = (byte) 'c';
                    if (hasAlpha) {
                        componentIDs[3] = (byte) 'A';
                    }
                }
                break;
            case ColorSpace.TYPE_YCbCr:
                if (hasExtraComponents) { // e.g. K or alpha
                    wantJFIF = false;
                    if (!hasAlpha) {  // then it must be K
                        wantAdobe = true;
                        transform = JPEG.ADOBE_YCCK;
                    }
                }
                break;
            case ColorSpace.TYPE_CMYK:
                wantJFIF = false;
                wantAdobe = true;
                transform = JPEG.ADOBE_YCCK;
                break;
                
            default:  
                // Everything else is not subsampled, gets no special marker,
                // and component ids are 0 - N
                wantJFIF = false;
                willSubsample = false;
            }

        }

        // do we want an ICC profile?
        if (wantJFIF && JPEG.isNonStandardICC(cs)) {
            wantICC = true;
        }

        // Now step through the markers, consulting our variables.
        if (wantJFIF) {
            JFIFMarkerSegment jfif = new JFIFMarkerSegment();
            markerSequence.add(jfif);
            if (wantICC) {
                try {
                    jfif.addICC((ICC_ColorSpace)cs);
                } catch (IOException e) {} // Can't happen here
            }
        }
        // Adobe
        if (wantAdobe) {
            markerSequence.add(new AdobeMarkerSegment(transform));
        }

        // dqt
        if (wantQTables) {
            markerSequence.add(new DQTMarkerSegment(quality, willSubsample));
        }

        // dht
        if (wantHTables) {
            markerSequence.add(new DHTMarkerSegment(willSubsample));
        }

        // sof
        markerSequence.add(new SOFMarkerSegment(wantProg,
                                                wantExtended, 
                                                willSubsample,
                                                componentIDs,
                                                numComponents)); 

        // sos
        if (!wantProg) {  // Default progression scans are done in the writer
            markerSequence.add(new SOSMarkerSegment(willSubsample, 
                                                    componentIDs,
                                                    numComponents));
        }

        // Defensive programming
        if (!isConsistent()) {
            throw new InternalError("Default image metadata is inconsistent");
        }
    }

    ////// End of constructors

    // Utilities for dealing with the marker sequence.
    // The first ones have package access for access from the writer.

    /**
     * Returns the first MarkerSegment object in the list
     * with the given tag, or null if none is found.
     */
    MarkerSegment findMarkerSegment(int tag) {
        Iterator iter = markerSequence.iterator();
        while (iter.hasNext()) {
            MarkerSegment seg = (MarkerSegment)iter.next();
            if (seg.tag == tag) {
                return seg;
            }
        }
        return null;
    }

    /**
     * Returns the first or last MarkerSegment object in the list
     * of the given class, or null if none is found.
     */
    MarkerSegment findMarkerSegment(Class cls, boolean first) {
        if (first) {
            Iterator iter = markerSequence.iterator();
            while (iter.hasNext()) {
                MarkerSegment seg = (MarkerSegment)iter.next();
                if (cls.isInstance(seg)) {
                    return seg;
                }
            }
        } else {
            ListIterator iter = markerSequence.listIterator(markerSequence.size());
            while (iter.hasPrevious()) {
                MarkerSegment seg = (MarkerSegment)iter.previous();
                if (cls.isInstance(seg)) {
                    return seg;
                }
            }
        }
        return null;
    }

    /**
     * Returns the index of the first or last MarkerSegment in the list
     * of the given class, or -1 if none is found.
     */
    private int findMarkerSegmentPosition(Class cls, boolean first) {
        if (first) {
            ListIterator iter = markerSequence.listIterator();
            for (int i = 0; iter.hasNext(); i++) {
                MarkerSegment seg = (MarkerSegment)iter.next();
                if (cls.isInstance(seg)) {
                    return i;
                }
            }
        } else {
            ListIterator iter = markerSequence.listIterator(markerSequence.size());
            for (int i = markerSequence.size()-1; iter.hasPrevious(); i--) {
                MarkerSegment seg = (MarkerSegment)iter.previous();
                if (cls.isInstance(seg)) {
                    return i;
                }
            }
        }
        return -1;
    }

    private int findLastUnknownMarkerSegmentPosition() {
        ListIterator iter = markerSequence.listIterator(markerSequence.size());
        for (int i = markerSequence.size()-1; iter.hasPrevious(); i--) {
            MarkerSegment seg = (MarkerSegment)iter.previous();
            if (seg.unknown == true) {
                return i;
            }
        }
        return -1;
    }

    // Implement Cloneable, but restrict access

    protected Object clone() {
        JPEGMetadata newGuy = null;
        try {
            newGuy = (JPEGMetadata) super.clone();
        } catch (CloneNotSupportedException e) {} // won't happen
        if (markerSequence != null) {
            newGuy.markerSequence = (List) cloneSequence();
        }
        newGuy.resetSequence = null;
        return newGuy;
    }

    /**
     * Returns a deep copy of the current marker sequence.
     */
    private List cloneSequence() {
        if (markerSequence == null) {
            return null;
        }
        List retval = new ArrayList(markerSequence.size());
        Iterator iter = markerSequence.iterator();
        while(iter.hasNext()) {
            MarkerSegment seg = (MarkerSegment)iter.next();
            retval.add(seg.clone());
        }

        return retval;
    }


    // Tree methods

    public Node getAsTree(String formatName) {
        if (formatName == null) {
            throw new IllegalArgumentException("null formatName!");
        } 
        if (isStream) {
            if (formatName.equals(JPEG.nativeStreamMetadataFormatName)) {
                return getNativeTree();
            }
        } else {
            if (formatName.equals(JPEG.nativeImageMetadataFormatName)) {
                return getNativeTree();
            }
            if (formatName.equals
                    (IIOMetadataFormatImpl.standardMetadataFormatName)) {
                return getStandardTree();
            }
        }
        throw  new IllegalArgumentException("Unsupported format name: " 
                                                + formatName);
    }

    IIOMetadataNode getNativeTree() {
        IIOMetadataNode root;
        IIOMetadataNode top;
        Iterator iter = markerSequence.iterator();
        if (isStream) {
            root = new IIOMetadataNode(JPEG.nativeStreamMetadataFormatName);
            top = root;
        } else {
            IIOMetadataNode sequence = new IIOMetadataNode("markerSequence");
            if (!inThumb) {
                root = new IIOMetadataNode(JPEG.nativeImageMetadataFormatName);
                IIOMetadataNode header = new IIOMetadataNode("JPEGvariety");
                root.appendChild(header);
                JFIFMarkerSegment jfif = (JFIFMarkerSegment)
                    findMarkerSegment(JFIFMarkerSegment.class, true);
                if (jfif != null) {
                    iter.next();  // JFIF must be first, so this skips it
                    header.appendChild(jfif.getNativeNode());
                }
                root.appendChild(sequence);
            } else {
                root = sequence;
            }
            top = sequence;
        }
        while(iter.hasNext()) {
            MarkerSegment seg = (MarkerSegment) iter.next();
            top.appendChild(seg.getNativeNode());
        }
        return root;
    }

    // Standard tree node methods

    protected IIOMetadataNode getStandardChromaNode() {
        hasAlpha = false;  // Unless we find otherwise

        // Colorspace type - follow the rules in the spec
        // First get the SOF marker segment, if there is one
        SOFMarkerSegment sof = (SOFMarkerSegment) 
            findMarkerSegment(SOFMarkerSegment.class, true);
        if (sof == null) {
            // No image, so no chroma
            return null;
        }

        IIOMetadataNode chroma = new IIOMetadataNode("Chroma");
        IIOMetadataNode csType = new IIOMetadataNode("ColorSpaceType");
        chroma.appendChild(csType);

        // get the number of channels
        int numChannels = sof.componentSpecs.length;

        IIOMetadataNode numChanNode = new IIOMetadataNode("NumChannels");
        chroma.appendChild(numChanNode);
        numChanNode.setAttribute("value", Integer.toString(numChannels));

        // is there a JFIF marker segment?
        if (findMarkerSegment(JFIFMarkerSegment.class, true) != null) {
            if (numChannels == 1) {
                csType.setAttribute("name", "GRAY");
            } else {
                csType.setAttribute("name", "YCbCr");
            }
            return chroma;
        }

        // How about an Adobe marker segment?
        AdobeMarkerSegment adobe = 
            (AdobeMarkerSegment) findMarkerSegment(AdobeMarkerSegment.class, true);
        if (adobe != null){
            switch (adobe.transform) {
            case JPEG.ADOBE_YCCK:
                csType.setAttribute("name", "YCCK");
                break;
            case JPEG.ADOBE_YCC:
                csType.setAttribute("name", "YCbCr");
                break;
            case JPEG.ADOBE_UNKNOWN:
                if (numChannels == 3) {
                    csType.setAttribute("name", "RGB");
                } else if (numChannels == 4) {
                    csType.setAttribute("name", "CMYK");
                }
                break;
            }
            return chroma;
        }

        // Neither marker.  Check components
        if (numChannels < 3) {
            csType.setAttribute("name", "GRAY");
            if (numChannels == 2) {
                hasAlpha = true;
            }
            return chroma;
        }

        boolean idsAreJFIF = true;

        for (int i = 0; i < sof.componentSpecs.length; i++) {
            int id = sof.componentSpecs[i].componentId;
            if ((id < 1) || (id >= sof.componentSpecs.length)) {
                idsAreJFIF = false;
            }
        }
        
        if (idsAreJFIF) {
            csType.setAttribute("name", "YCbCr");
            if (numChannels == 4) {
                hasAlpha = true;
            }
            return chroma;
        }

        // Check against the letters
        if ((sof.componentSpecs[0].componentId == 'R')
            && (sof.componentSpecs[1].componentId == 'G')
            && (sof.componentSpecs[2].componentId == 'B')){

            csType.setAttribute("name", "RGB");
            if ((numChannels == 4) 
                && (sof.componentSpecs[3].componentId == 'A')) {
                hasAlpha = true;
            }
            return chroma;
        }
        
        if ((sof.componentSpecs[0].componentId == 'Y')
            && (sof.componentSpecs[1].componentId == 'C')
            && (sof.componentSpecs[2].componentId == 'c')){

            csType.setAttribute("name", "PhotoYCC");
            if ((numChannels == 4) 
                && (sof.componentSpecs[3].componentId == 'A')) {
                hasAlpha = true;
            }            
            return chroma;
        }
        
        // Finally, 3-channel subsampled are YCbCr, unsubsampled are RGB
        // 4-channel subsampled are YCbCrA, unsubsampled are CMYK

        boolean subsampled = false;

        int hfactor = sof.componentSpecs[0].HsamplingFactor;
        int vfactor = sof.componentSpecs[0].VsamplingFactor;

        for (int i = 1; i<sof.componentSpecs.length; i++) {
            if ((sof.componentSpecs[i].HsamplingFactor != hfactor)
                || (sof.componentSpecs[i].VsamplingFactor != vfactor)){
                subsampled = true;
                break;
            }
        }

        if (subsampled) {
            csType.setAttribute("name", "YCbCr");
            if (numChannels == 4) {
                hasAlpha = true;
            }
            return chroma;
        }
         
        // Not subsampled.  numChannels < 3 is taken care of above
        if (numChannels == 3) {
            csType.setAttribute("name", "RGB");
        } else {
            csType.setAttribute("name", "CMYK");
        }

        return chroma;
    }

    protected IIOMetadataNode getStandardCompressionNode() {

        IIOMetadataNode compression = new IIOMetadataNode("Compression");

        // CompressionTypeName
        IIOMetadataNode name = new IIOMetadataNode("CompressionTypeName");
        name.setAttribute("value", "JPEG");
        compression.appendChild(name);

        // Lossless - false
        IIOMetadataNode lossless = new IIOMetadataNode("Lossless");
        lossless.setAttribute("value", "false");
        compression.appendChild(lossless);

        // NumProgressiveScans - count sos segments
        int sosCount = 0;
        Iterator iter = markerSequence.iterator();
        while (iter.hasNext()) {
            MarkerSegment ms = (MarkerSegment) iter.next();
            if (ms.tag == JPEG.SOS) {
                sosCount++;
            }
        }
        if (sosCount != 0) {
            IIOMetadataNode prog = new IIOMetadataNode("NumProgressiveScans");
            prog.setAttribute("value", Integer.toString(sosCount));
            compression.appendChild(prog);
        }

        return compression;
    }

    protected IIOMetadataNode getStandardDimensionNode() {
        // If we have a JFIF marker segment, we know a little
        // otherwise all we know is the orientation, which is always normal
        IIOMetadataNode dim = new IIOMetadataNode("Dimension");
        IIOMetadataNode orient = new IIOMetadataNode("ImageOrientation");
        orient.setAttribute("value", "normal");
        dim.appendChild(orient);

        JFIFMarkerSegment jfif = 
            (JFIFMarkerSegment) findMarkerSegment(JFIFMarkerSegment.class, true);
        if (jfif != null) {

            // Aspect Ratio is width of pixel / height of pixel
            float aspectRatio;
            if (jfif.resUnits == 0) {
                // In this case they just encode aspect ratio directly
                aspectRatio = ((float) jfif.Xdensity)/jfif.Ydensity;
            } else {
                // They are true densities (e.g. dpi) and must be inverted
                aspectRatio = ((float) jfif.Ydensity)/jfif.Xdensity;
            }
            IIOMetadataNode aspect = new IIOMetadataNode("PixelAspectRatio");
            aspect.setAttribute("value", Float.toString(aspectRatio));
            dim.insertBefore(aspect, orient);

            // Pixel size
            if (jfif.resUnits != 0) {
                // 1 == dpi, 2 == dpc
                float scale = (jfif.resUnits == 1) ? 25.4F : 10.0F;

                IIOMetadataNode horiz = 
                    new IIOMetadataNode("HorizontalPixelSize");
                horiz.setAttribute("value", 
                                   Float.toString(scalejfif.Xdensity));
                dim.appendChild(horiz);

                IIOMetadataNode vert = 
                    new IIOMetadataNode("VerticalPixelSize");
                vert.setAttribute("value", 
                                  Float.toString(scalejfif.Ydensity));
                dim.appendChild(vert);
            }
        }
        return dim;
    }

    protected IIOMetadataNode getStandardTextNode() {
        IIOMetadataNode text = null;
        // Add a text entry for each COM Marker Segment
        if (findMarkerSegment(JPEG.COM) != null) {
            text = new IIOMetadataNode("Text");
            Iterator iter = markerSequence.iterator();
            while (iter.hasNext()) {
                MarkerSegment seg = (MarkerSegment) iter.next();
                if (seg.tag == JPEG.COM) {
                    COMMarkerSegment com = (COMMarkerSegment) seg;
                    IIOMetadataNode entry = new IIOMetadataNode("TextEntry");
                    entry.setAttribute("keyword", "comment");
                    entry.setAttribute("value", com.getComment());
                text.appendChild(entry);
                }
            }
        }
        return text;
    }

    protected IIOMetadataNode getStandardTransparencyNode() {
        IIOMetadataNode trans = null;
        if (hasAlpha == true) {
            trans = new IIOMetadataNode("Transparency");
            IIOMetadataNode alpha = new IIOMetadataNode("Alpha");
            alpha.setAttribute("value", "nonpremultiplied"); // Always assume
            trans.appendChild(alpha);
        }
        return trans;
    }

    // Editing

    public boolean isReadOnly() {
        return false;
    }

    public void mergeTree(String formatName, Node root)
        throws IIOInvalidTreeException {
        if (formatName == null) {
            throw new IllegalArgumentException("null formatName!");
        } 
        if (root == null) {
            throw new IllegalArgumentException("null root!");
        }
        List copy = null;
        if (resetSequence == null) {
            resetSequence = cloneSequence();  // Deep copy
            copy = resetSequence;  // Avoid cloning twice
        } else {
            copy = cloneSequence();
        }
        if (isStream &&
            (formatName.equals(JPEG.nativeStreamMetadataFormatName))) {
                mergeNativeTree(root);
        } else if (!isStream &&
                   (formatName.equals(JPEG.nativeImageMetadataFormatName))) {
            mergeNativeTree(root);
        } else if (!isStream &&
                   (formatName.equals
                    (IIOMetadataFormatImpl.standardMetadataFormatName))) {
            mergeStandardTree(root);
        } else {
            throw  new IllegalArgumentException("Unsupported format name: " 
                                                + formatName);
        }
        if (!isConsistent()) {
            markerSequence = copy;
            throw new IIOInvalidTreeException
                ("Merged tree is invalid; original restored", root);
        }
    }

    private void mergeNativeTree(Node root) throws IIOInvalidTreeException {
        String name = root.getNodeName();
        if (name != ((isStream) ? JPEG.nativeStreamMetadataFormatName
                                : JPEG.nativeImageMetadataFormatName)) {
            throw new IIOInvalidTreeException("Invalid root node name: " + name, 
                                              root);
        }
        if (root.getChildNodes().getLength() != 2) { // JPEGvariety and markerSequence
            throw new IIOInvalidTreeException(
                "JPEGvariety and markerSequence nodes must be present", root);
        }
        mergeJFIFsubtree(root.getFirstChild());
        mergeSequenceSubtree(root.getLastChild());
    }

    /**
     * Merge a JFIF subtree into the marker sequence, if the subtree
     * is non-empty.
     * If a JFIF marker exists, update it from the subtree.
     * If none exists, create one from the subtree and insert it at the
     * beginning of the marker sequence.
     */
    private void mergeJFIFsubtree(Node JPEGvariety) 
        throws IIOInvalidTreeException {
        if (JPEGvariety.getChildNodes().getLength() != 0) {
            Node jfifNode = JPEGvariety.getFirstChild();
            // is there already a jfif marker segment?
            JFIFMarkerSegment jfifSeg = 
                (JFIFMarkerSegment) findMarkerSegment(JFIFMarkerSegment.class, true);
            if (jfifSeg != null) {
                jfifSeg.updateFromNativeNode(jfifNode, false);
            } else {
                // Add it as the first element in the list.
                markerSequence.add(0, new JFIFMarkerSegment(jfifNode));
            }
        }
    }

    private void mergeSequenceSubtree(Node sequenceTree) 
        throws IIOInvalidTreeException {
        NodeList children = sequenceTree.getChildNodes();
        for (int i = 0; i < children.getLength(); i++) {
            Node node = children.item(i);
            String name = node.getNodeName();
            if (name.equals("dqt")) {
                mergeDQTNode(node);
            } else if (name.equals("dht")) {
                mergeDHTNode(node);
            } else if (name.equals("dri")) {
                mergeDRINode(node);
            } else if (name.equals("com")) {
                mergeCOMNode(node);
            } else if (name.equals("app14Adobe")) {
                mergeAdobeNode(node);
            } else if (name.equals("unknown")) {
                mergeUnknownNode(node);
            } else if (name.equals("sof")) {
                mergeSOFNode(node);
            } else if (name.equals("sos")) {
                mergeSOSNode(node);
            } else {
                throw new IIOInvalidTreeException("Invalid node: " + name, node);
            }
        }
    }

    /**
     * Merge the given DQT node into the marker sequence.  If there already
     * exist DQT marker segments in the sequence, then each table in the 
     * node replaces the first table, in any DQT segment, with the same
     * table id.  If none of the existing DQT segments contain a table with
     * the same id, then the table is added to the last existing DQT segment.
     * If there are no DQT segments, then a new one is created and added
     * as follows:
     * If there are DHT segments, the new DQT segment is inserted before the
     * first one.  
     * If there are no DHT segments, the new DQT segment is inserted before
     * an SOF segment, if there is one. 
     * If there is no SOF segment, the new DQT segment is inserted before 
     * the first SOS segment, if there is one.
     * If there is no SOS segment, the new DQT segment is added to the end
     * of the sequence.
     */
    private void mergeDQTNode(Node node) throws IIOInvalidTreeException {
        // First collect any existing DQT nodes into a local list
        ArrayList oldDQTs = new ArrayList();
        Iterator iter = markerSequence.iterator();
        while (iter.hasNext()) {
            MarkerSegment seg = (MarkerSegment) iter.next();
            if (seg instanceof DQTMarkerSegment) {
                oldDQTs.add(seg);
            }
        }
        if (!oldDQTs.isEmpty()) {
            NodeList children = node.getChildNodes();
            for (int i = 0; i < children.getLength(); i++) {
                Node child = children.item(i);
                int childID = MarkerSegment.getAttributeValue(child, 
                                                              null, 
                                                              "qtableId", 
                                                              0, 3, 
                                                              true);
                DQTMarkerSegment dqt = null;
                int tableIndex = -1;
                for (int j = 0; j < oldDQTs.size(); j++) {
                    DQTMarkerSegment testDQT = (DQTMarkerSegment) oldDQTs.get(j);
                    for (int k = 0; k < testDQT.tables.size(); k++) {
                        DQTMarkerSegment.Qtable testTable = 
                            (DQTMarkerSegment.Qtable) testDQT.tables.get(k);
                        if (childID == testTable.tableID) {
                            dqt = testDQT;
                            tableIndex = k;
                            break;
                        }
                    }
                    if (dqt != null) break;
                }
                if (dqt != null) {
                    dqt.tables.set(tableIndex, dqt.getQtableFromNode(child));
                } else {
                    dqt = (DQTMarkerSegment) oldDQTs.get(oldDQTs.size()-1);
                    dqt.tables.add(dqt.getQtableFromNode(child));
                }
            }
        } else {
            DQTMarkerSegment newGuy = new DQTMarkerSegment(node);
            int firstDHT = findMarkerSegmentPosition(DHTMarkerSegment.class, true);
            int firstSOF = findMarkerSegmentPosition(SOFMarkerSegment.class, true);
            int firstSOS = findMarkerSegmentPosition(SOSMarkerSegment.class, true);
            if (firstDHT != -1) {
                markerSequence.add(firstDHT, newGuy);
            } else if (firstSOF != -1) {
                markerSequence.add(firstSOF, newGuy);
            } else if (firstSOS != -1) {
                markerSequence.add(firstSOS, newGuy);
            } else {
                markerSequence.add(newGuy);
            }
        }
    }

    /**
     * Merge the given DHT node into the marker sequence.  If there already
     * exist DHT marker segments in the sequence, then each table in the 
     * node replaces the first table, in any DHT segment, with the same
     * table class and table id.  If none of the existing DHT segments contain
     * a table with the same class and id, then the table is added to the last
     * existing DHT segment.
     * If there are no DHT segments, then a new one is created and added
     * as follows:
     * If there are DQT segments, the new DHT segment is inserted immediately
     * following the last DQT segment.
     * If there are no DQT segments, the new DHT segment is inserted before
     * an SOF segment, if there is one. 
     * If there is no SOF segment, the new DHT segment is inserted before 
     * the first SOS segment, if there is one.
     * If there is no SOS segment, the new DHT segment is added to the end
     * of the sequence.
     */
    private void mergeDHTNode(Node node) throws IIOInvalidTreeException {
        // First collect any existing DQT nodes into a local list
        ArrayList oldDHTs = new ArrayList();
        Iterator iter = markerSequence.iterator();
        while (iter.hasNext()) {
            MarkerSegment seg = (MarkerSegment) iter.next();
            if (seg instanceof DHTMarkerSegment) {
                oldDHTs.add(seg);
            }
        }
        if (!oldDHTs.isEmpty()) {
            NodeList children = node.getChildNodes();
            for (int i = 0; i < children.getLength(); i++) {
                Node child = children.item(i);
                NamedNodeMap attrs = node.getAttributes();
                int childID = MarkerSegment.getAttributeValue(child, 
                                                              attrs, 
                                                              "htableId", 
                                                              0, 3, 
                                                              true);
                int childClass = MarkerSegment.getAttributeValue(child, 
                                                                 attrs, 
                                                                 "class", 
                                                                 0, 1, 
                                                                 true);
                DHTMarkerSegment dht = null;
                int tableIndex = -1;
                for (int j = 0; j < oldDHTs.size(); j++) {
                    DHTMarkerSegment testDHT = (DHTMarkerSegment) oldDHTs.get(j);
                    for (int k = 0; k <