/* * CVS identifier: * * $Id: TagTreeEncoder.java,v 1.1.1.1 2002/07/22 09:26:47 grosbois Exp $ * * Class:                   TagTreeEncoder * * Description:             Encoder of tag trees * * * * COPYRIGHT: *  * This software module was originally developed by Rapha雔 Grosbois and * Diego Santa Cruz (Swiss Federal Institute of Technology-EPFL); Joel * Askel鰂 (Ericsson Radio Systems AB); and Bertrand Berthelot, David * Bouchard, F閘ix Henry, Gerard Mozelle and Patrice Onno (Canon Research * Centre France S.A) in the course of development of the JPEG2000 * standard as specified by ISO/IEC 15444 (JPEG 2000 Standard). This * software module is an implementation of a part of the JPEG 2000 * Standard. Swiss Federal Institute of Technology-EPFL, Ericsson Radio * Systems AB and Canon Research Centre France S.A (collectively JJ2000 * Partners) agree not to assert against ISO/IEC and users of the JPEG * 2000 Standard (Users) any of their rights under the copyright, not * including other intellectual property rights, for this software module * with respect to the usage by ISO/IEC and Users of this software module * or modifications thereof for use in hardware or software products * claiming conformance to the JPEG 2000 Standard. Those intending to use * this software module in hardware or software products are advised that * their use may infringe existing patents. The original developers of * this software module, JJ2000 Partners and ISO/IEC assume no liability * for use of this software module or modifications thereof. No license * or right to this software module is granted for non JPEG 2000 Standard * conforming products. JJ2000 Partners have full right to use this * software module for his/her own purpose, assign or donate this * software module to any third party and to inhibit third parties from * using this software module for non JPEG 2000 Standard conforming * products. This copyright notice must be included in all copies or * derivative works of this software module. *  * Copyright (c) 1999/2000 JJ2000 Partners. * */package jj2000.j2k.codestream.writer;import jj2000.j2k.util.*;import jj2000.j2k.io.*;import java.io.*;/** * This class implements the tag tree encoder. A tag tree codes a 2D matrix of * integer elements in an efficient way. The encoding procedure 'encode()' * codes information about a value of the matrix, given a threshold. The * procedure encodes the sufficient information to identify whether or not the * value is greater than or equal to the threshold. * * <p>The tag tree saves encoded information to a BitOutputBuffer.</p> * * <p>A particular and useful property of tag trees is that it is possible to * change a value of the matrix, provided both new and old values of the * element are both greater than or equal to the largest threshold which has * yet been supplied to the coding procedure 'encode()'. This property can be * exploited through the 'setValue()' method.</p> * * <p>This class allows saving the state of the tree at any point and * restoring it at a later time, by calling save() and restore().</p> * * <p>A tag tree can also be reused, or restarted, if one of the reset() * methods is called.</p> * * <p>The TagTreeDecoder class implements the tag tree decoder.</p> * * <p>Tag trees that have one dimension, or both, as 0 are allowed for * convenience. Of course no values can be set or coded in such cases.</p> * * @see BitOutputBuffer * * @see jj2000.j2k.codestream.reader.TagTreeDecoder * */public class TagTreeEncoder {    /** The horizontal dimension of the base level */    protected int w;    /** The vertical dimensions of the base level */    protected int h;    /** The number of levels in the tag tree */    protected int lvls;    /** The tag tree values. The first index is the level, starting at level 0     * (leafs). The second index is the element within the level, in     * lexicographical order. */    protected int treeV[][];    /** The tag tree state. The first index is the level, starting at level 0     * (leafs). The second index is the element within the level, in     * lexicographical order. */    protected int treeS[][];    /** The saved tag tree values. The first index is the level, starting at     * level 0 (leafs). The second index is the element within the level, in     * lexicographical order. */    protected int treeVbak[][];    /** The saved tag tree state. The first index is the level, starting at     * level 0 (leafs). The second index is the element within the level, in     * lexicographical order. */    protected int treeSbak[][];    /** The saved state. If true the values and states of the tree have been     * saved since the creation or last reset. */    protected boolean saved;    /**     * Creates a tag tree encoder with 'w' elements along the horizontal     * dimension and 'h' elements along the vertical direction. The total     * number of elements is thus 'vdim' x 'hdim'.     *     * <p>The values of all elements are initialized to Integer.MAX_VALUE.</p>     *     * @param h The number of elements along the horizontal direction.     *     * @param w The number of elements along the vertical direction.     * */    public TagTreeEncoder(int h, int w) {        int k;        // Check arguments        if ( w < 0 || h < 0 ) {            throw new IllegalArgumentException();        }        // Initialize elements        init(w,h);        // Set values to max        for (k = treeV.length-1; k >= 0; k--) {            ArrayUtil.intArraySet(treeV[k],Integer.MAX_VALUE);        }    }    /**     * Creates a tag tree encoder with 'w' elements along the horizontal     * dimension and 'h' elements along the vertical direction. The total     * number of elements is thus 'vdim' x 'hdim'. The values of the leafs in     * the tag tree are initialized to the values of the 'val' array.     *     * <p>The values in the 'val' array are supposed to appear in     * lexicographical order, starting at index 0.</p>     *     * @param h The number of elements along the horizontal direction.     *     * @param w The number of elements along the vertical direction.     *     * @param val The values with which initialize the leafs of the tag tree.     * */    public TagTreeEncoder(int h, int w, int val[]) {        int k;        // Check arguments        if ( w < 0 || h < 0 || val.length < w*h ) {            throw new IllegalArgumentException();        }        // Initialize elements        init(w,h);        // Update leaf values        for (k=w*h-1; k>=0; k--) {            treeV[0][k]=val[k];        }        // Calculate values at other levels        recalcTreeV();    }    /**     * Returns the number of leafs along the horizontal direction.     *     * @return The number of leafs along the horizontal direction.     * */    public final int getWidth() {        return w;    }    /**     * Returns the number of leafs along the vertical direction.     *     * @return The number of leafs along the vertical direction.     * */    public final int getHeight() {        return h;    }    /**     * Initializes the variables of this class, given the dimensions at the     * base level (leaf level). All the state ('treeS' array) and values     * ('treeV' array) are intialized to 0. This method is called by the     * constructors.     *     * @param w The number of elements along the vertical direction.     *     * @param h The number of elements along the horizontal direction.     * */    private void init(int w, int h) {        int i;        // Initialize dimensions        this.w = w;        this.h = h;        // Calculate the number of levels        if (w == 0 || h == 0) {            lvls = 0;        }        else {            lvls = 1;            while (h != 1 || w != 1) { // Loop until we reach root                w = (w+1)>>1;                h = (h+1)>>1;                lvls++;            }        }        // Allocate tree values and states (no need to initialize to 0 since        // it's the default)        treeV = new int[lvls][];        treeS = new int[lvls][];        w = this.w;        h = this.h;        for (i=0; i<lvls; i++) {            treeV[i] = new int[h*w];            treeS[i] = new int[h*w];            w = (w+1)>>1;            h = (h+1)>>1;        }    }    /**     * Recalculates the values of the elements in the tag tree, in levels 1     * and up, based on the values of the leafs (level 0).     * */    private void recalcTreeV() {        int m,n,bi,lw,tm1,tm2,lh,k;        // Loop on all other levels, updating minimum        for (k=0; k<lvls-1; k++) {            // Visit all elements in level            lw = (w+(1<<k)-1)>>k;            lh = (h+(1<<k)-1)>>k;            for (m=((lh>>1)<<1)-2;m>=0;m-=2) { // All quads with 2 lines                for (n=((lw>>1)<<1)-2;n>=0;n-=2) { // All quads with 2 columns                    // Take minimum of 4 elements and put it in higher                     // level                    bi = m*lw+n;                    tm1 = (treeV[k][bi] < treeV[k][bi+1]) ?                        treeV[k][bi] : treeV[k][bi+1];                    tm2 = (treeV[k][bi+lw] < treeV[k][bi+lw+1]) ?                        treeV[k][bi+lw] : treeV[k][bi+lw+1];                    treeV[k+1][(m>>1)*((lw+1)>>1)+(n>>1)] =                        tm1 < tm2 ? tm1 : tm2;                }                // Now we may have quad with 1 column, 2 lines                if (lw%2 != 0) {                    n = ((lw>>1)<<1);                    // Take minimum of 2 elements and put it in higher