class Quantizer {

    public ColorIndexer buildColorIndexer(RenderedImage image) {
        long totalPixelCount = (long) image.getWidth() * (long) image.getHeight();

        // build a histogram with a subsampling proportional to the log of the image size
        // (for very small images we pick one pixel every two, from 256 we switch to one every 3,
        // and so on)
        int subsx, subsy;
        if(subsample) {
            subsx = 1 + (int) (Math.log(image.getWidth()) / Math.log(8));
            subsy = 1 + (int) (Math.log(image.getHeight()) / Math.log(8));
        } else {
            subsx = 1;
            subsy = 1;
        }
        PackedHistogram histogram = new PackedHistogram(image, subsx, subsy);
        if (LOGGER.isLoggable(Level.FINE)) {
            LOGGER.fine("Found " + histogram.size() + " unique colors with shift "
                    + histogram.getShift());
            LOGGER.fine("Histogram count " + histogram.pixelCount() + " and pixels "
                    + totalPixelCount);
        }
        int colors = Math.min(histogram.size(), maxColors);

        // setup the first box, that median cut will split in parts
        List<Box> boxes = new ArrayList<Box>();
        boxes.add(new Box(0, histogram.size(), totalPixelCount, histogram, null));

        // perform the box subdivision, first based on box pixel count, then on the box color volume
        // following up Leptonica's paper suggestions
        int sortSwitch = Math.round(colors * THRESHOLD);
        Comparator<Box> comparator = new SumComparator();
        Comparator<Box> volumeComparator = new VolumeComparator();
        while (boxes.size() < colors) {
            // locate a box that we can split
            int boxIndex = 0;
            for (; boxIndex < boxes.size(); boxIndex++) {
                if (boxes.get(boxIndex).colors > 1) {
                    break;
                }
            }

            // did we scan all of them and found nothing? If so, each box has one color, we're done
            if (boxIndex == boxes.size()) {
                break;
            }

            // scan the box contents, find min and max of each color component
            Box box = boxes.get(boxIndex);

            // get the span of each and sort on the component that has the largest span
            int spana = box.getAlphaSpan();
            int spanr = box.getRedSpan();
            int spang = box.getGreenSpan();
            int spanb = box.getBlueSpan();
            SortComponent sort;
            if (spana > spanr && spana > spanb && spana > spang) {
                sort = SortComponent.Alpha;
            } else if (spanr > spang && spanr > spanb) {
                sort = SortComponent.Red;
            } else if (spang > spanb) {
                sort = SortComponent.Green;
            } else {
                sort = SortComponent.Blue;
            }
            box.sort(sort);

            // split the box and add it to the list
            Box newBox = box.split();
            boxes.add(newBox);

            // sort based on size or volume
            if (comparator instanceof SumComparator && boxes.size() > sortSwitch) {
                comparator = volumeComparator;
            }
            Collections.sort(boxes, comparator);
        }

        // dump all the boxes
        if (LOGGER.isLoggable(Level.FINER)) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < boxes.size(); i++) {
                Box b = boxes.get(i);
                sb.append("Box " + i + ", pixels: " + b.sum + " colors: " + b.colors + " volume: "
                        + b.getVolume() + " p*v: " + b.getVolume() * b.sum);
            }
            sb.append("\n");
            LOGGER.finer("Median cut resulted in the following boxes:\n" + sb);
        }
        
        // the png encoder goes bananas if we have a single color palette, in this
        // case we need to add an entry to the palette
        if(boxes.size() == 1) {
            boxes.add(boxes.get(0));
        }

        // all right, we have the set of boxes, now we have to pick a color from each.
        // A box might have a single color, but if it has many we have to pick and choose,
        // in such case we do a weighted sum of each component.
        // In this phase we use the real colors (so far we worked with the packed ones)
        PaletteEntry[] palette = new PaletteEntry[boxes.size()];
        int shift = histogram.getShift();
        for (int i = 0; i < boxes.size(); i++) {
            Box box = boxes.get(i);
            byte r, g, b, a;
            if (box.colors == 1) {
                // simple case, no need to mess around with averages
                int color = histogram.getColor(box.idx);
                r = (byte) red(color);
                g = (byte) green(color);
                b = (byte) blue(color);
                a = (byte) alpha(color);
            } else {
                if (MEDIAN_BOX) {
                    // just pick the middle one
                    int color = histogram.getColor(box.idx + box.colors / 2);
                    r = (byte) red(color);
                    g = (byte) green(color);
                    b = (byte) blue(color);
                    a = (byte) alpha(color);
                } else {
                    // compute the weighted sum
                    final int start = box.idx;
                    final int end = box.idx + box.colors;
                    long rs, gs, bs, as, sum;
                    rs = gs = bs = as = sum = 0;
                    for (int idx = start; idx < end; idx++) {
                        int color = histogram.getColor(idx);
                        long count = histogram.getCount(idx);
                        rs += red(color) * count;
                        gs += green(color) * count;
                        bs += blue(color) * count;
                        as += alpha(color) * count;
                        sum += count;
                    }
                    r = (byte) (rs / sum);
                    g = (byte) (gs / sum);
                    b = (byte) (bs / sum);
                    a = (byte) (as / sum);
                }

            }
            palette[i] = new PaletteEntry(r, g, b, a, i);
        }

        // sort palette, non opaque colors first, and build the rgba array
        Arrays.sort(palette);
        byte[][] rgba = new byte[4][palette.length];
        for (int i = 0; i < palette.length; i++) {
            PaletteEntry pe = palette[i];
            rgba[0][i] = pe.r;
            rgba[1][i] = pe.g;
            rgba[2][i] = pe.b;
            rgba[3][i] = pe.a;
        }

        // prepare the reverse map
        ColorIndexer simpleMapper = new SimpleColorIndexer(rgba);
        ColorMap colorMap = histogram.colorMap;
        for (ColorEntry ce : colorMap) {
            int color = ce.color;
            int r = red(color);
            int g = green(color);
            int b = blue(color);
            int a = alpha(color);
            if (shift > 0) {
                r = unshift(r, shift);
                g = unshift(g, shift);
                b = unshift(b, shift);
                a = unshift(a, shift);
            }
            int idx = simpleMapper.getClosestIndex(r, g, b, a) & 0xFF;
            ce.value = idx;
        }

        // dumpPalette(rgba);

        ColorIndexer delegate = new MappedColorIndexer(rgba, colorMap, shift);
        return new CachingColorIndexer(delegate);
    }

    public  Quantizer(int maxColors);

}