    001/*
    002 * Licensed to the Apache Software Foundation (ASF) under one or more
    003 * contributor license agreements.  See the NOTICE file distributed with
    004 * this work for additional information regarding copyright ownership.
    005 * The ASF licenses this file to You under the Apache License, Version 2.0
    006 * (the "License"); you may not use this file except in compliance with
    007 * the License.  You may obtain a copy of the License at
    008 *
    009 *      http://www.apache.org/licenses/LICENSE-2.0
    010 *
    011 * Unless required by applicable law or agreed to in writing, software
    012 * distributed under the License is distributed on an "AS IS" BASIS,
    013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    014 * See the License for the specific language governing permissions and
    015 * limitations under the License.
    016 */
    017package org.apache.commons.imaging.palette;
    018
    019import java.util.ArrayList;
    020import java.util.Collections;
    021import java.util.Comparator;
    022import java.util.List;
    023
    024import org.apache.commons.imaging.ImageWriteException;
    025
    026public class LongestAxisMedianCut implements MedianCut {
    027    private static final Comparator<ColorGroup> COMPARATOR = (cg1, cg2) -> {
    028        if (cg1.maxDiff == cg2.maxDiff) {
    029            return cg2.diffTotal - cg1.diffTotal;
    030        }
    031        return cg2.maxDiff - cg1.maxDiff;
    032    };
    033
    034    @Override
    035    public boolean performNextMedianCut(final List<ColorGroup> colorGroups, final boolean ignoreAlpha)
    036            throws ImageWriteException {
    037        Collections.sort(colorGroups, COMPARATOR);
    038        final ColorGroup colorGroup = colorGroups.get(0);
    039
    040        if (colorGroup.maxDiff == 0) {
    041            return false;
    042        }
    043        if (!ignoreAlpha
    044                && colorGroup.alphaDiff > colorGroup.redDiff
    045                && colorGroup.alphaDiff > colorGroup.greenDiff
    046                && colorGroup.alphaDiff > colorGroup.blueDiff) {
    047            doCut(colorGroup, ColorComponent.ALPHA, colorGroups, ignoreAlpha);
    048        } else if (colorGroup.redDiff > colorGroup.greenDiff
    049                && colorGroup.redDiff > colorGroup.blueDiff) {
    050            doCut(colorGroup, ColorComponent.RED, colorGroups, ignoreAlpha);
    051        } else if (colorGroup.greenDiff > colorGroup.blueDiff) {
    052            doCut(colorGroup, ColorComponent.GREEN, colorGroups, ignoreAlpha);
    053        } else {
    054            doCut(colorGroup, ColorComponent.BLUE, colorGroups, ignoreAlpha);
    055        }
    056        return true;
    057    }
    058
    059    private void doCut(final ColorGroup colorGroup, final ColorComponent mode,
    060            final List<ColorGroup> colorGroups, final boolean ignoreAlpha) throws ImageWriteException {
    061
    062        final List<ColorCount> colorCounts = colorGroup.getColorCounts();
    063        Collections.sort(colorCounts, new ColorCountComparator(mode));
    064        final int countHalf = (int) Math.round((double) colorGroup.totalPoints / 2);
    065        int oldCount = 0;
    066        int newCount = 0;
    067        int medianIndex;
    068        for (medianIndex = 0; medianIndex < colorCounts.size(); medianIndex++) {
    069            final ColorCount colorCount = colorCounts.get(medianIndex);
    070
    071            newCount += colorCount.count;
    072
    073            if (newCount < countHalf) {
    074                oldCount = newCount;
    075            } else {
    076                break;
    077            }
    078        }
    079
    080        if (medianIndex == colorCounts.size() - 1) {
    081            medianIndex--;
    082        } else if (medianIndex > 0) {
    083            final int newDiff = Math.abs(newCount - countHalf);
    084            final int oldDiff = Math.abs(countHalf - oldCount);
    085            if (oldDiff < newDiff) {
    086                medianIndex--;
    087            }
    088        }
    089
    090        colorGroups.remove(colorGroup);
    091        final List<ColorCount> colorCounts1 = new ArrayList<>(
    092                colorCounts.subList(0, medianIndex + 1));
    093        final List<ColorCount> colorCounts2 = new ArrayList<>(
    094                colorCounts.subList(medianIndex + 1,
    095                        colorCounts.size()));
    096
    097        final ColorGroup less = new ColorGroup(new ArrayList<>(colorCounts1), ignoreAlpha);
    098        colorGroups.add(less);
    099        final ColorGroup more = new ColorGroup(new ArrayList<>(colorCounts2), ignoreAlpha);
    100        colorGroups.add(more);
    101
    102        final ColorCount medianValue = colorCounts.get(medianIndex);
    103        int limit;
    104        switch (mode) {
    105            case ALPHA:
    106                limit = medianValue.alpha;
    107                break;
    108            case RED:
    109                limit = medianValue.red;
    110                break;
    111            case GREEN:
    112                limit = medianValue.green;
    113                break;
    114            case BLUE:
    115                limit = medianValue.blue;
    116                break;
    117            default:
    118                throw new Error("Bad mode.");
    119        }
    120        colorGroup.cut = new ColorGroupCut(less, more, mode, limit);
    121    }
    122}