    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.Comparator;
    021import java.util.List;
    022
    023import org.apache.commons.imaging.ImageWriteException;
    024
    025public class LongestAxisMedianCut implements MedianCut {
    026    private static final Comparator<ColorGroup> COMPARATOR = (cg1, cg2) -> {
    027        if (cg1.maxDiff == cg2.maxDiff) {
    028            return cg2.diffTotal - cg1.diffTotal;
    029        }
    030        return cg2.maxDiff - cg1.maxDiff;
    031    };
    032
    033    @Override
    034    public boolean performNextMedianCut(final List<ColorGroup> colorGroups, final boolean ignoreAlpha)
    035            throws ImageWriteException {
    036        colorGroups.sort(COMPARATOR);
    037        final ColorGroup colorGroup = colorGroups.get(0);
    038
    039        if (colorGroup.maxDiff == 0) {
    040            return false;
    041        }
    042        if (!ignoreAlpha
    043                && colorGroup.alphaDiff > colorGroup.redDiff
    044                && colorGroup.alphaDiff > colorGroup.greenDiff
    045                && colorGroup.alphaDiff > colorGroup.blueDiff) {
    046            doCut(colorGroup, ColorComponent.ALPHA, colorGroups, ignoreAlpha);
    047        } else if (colorGroup.redDiff > colorGroup.greenDiff
    048                && colorGroup.redDiff > colorGroup.blueDiff) {
    049            doCut(colorGroup, ColorComponent.RED, colorGroups, ignoreAlpha);
    050        } else if (colorGroup.greenDiff > colorGroup.blueDiff) {
    051            doCut(colorGroup, ColorComponent.GREEN, colorGroups, ignoreAlpha);
    052        } else {
    053            doCut(colorGroup, ColorComponent.BLUE, colorGroups, ignoreAlpha);
    054        }
    055        return true;
    056    }
    057
    058    private void doCut(final ColorGroup colorGroup, final ColorComponent mode,
    059            final List<ColorGroup> colorGroups, final boolean ignoreAlpha) throws ImageWriteException {
    060
    061        final List<ColorCount> colorCounts = colorGroup.getColorCounts();
    062        colorCounts.sort(new ColorCountComparator(mode));
    063        final int countHalf = (int) Math.round((double) colorGroup.totalPoints / 2);
    064        int oldCount = 0;
    065        int newCount = 0;
    066        int medianIndex;
    067        for (medianIndex = 0; medianIndex < colorCounts.size(); medianIndex++) {
    068            final ColorCount colorCount = colorCounts.get(medianIndex);
    069
    070            newCount += colorCount.count;
    071
    072            if (newCount >= countHalf) {
    073                break;
    074            }
    075            oldCount = newCount;
    076        }
    077
    078        if (medianIndex == colorCounts.size() - 1) {
    079            medianIndex--;
    080        } else if (medianIndex > 0) {
    081            final int newDiff = Math.abs(newCount - countHalf);
    082            final int oldDiff = Math.abs(countHalf - oldCount);
    083            if (oldDiff < newDiff) {
    084                medianIndex--;
    085            }
    086        }
    087
    088        colorGroups.remove(colorGroup);
    089        final List<ColorCount> colorCounts1 = new ArrayList<>(
    090                colorCounts.subList(0, medianIndex + 1));
    091        final List<ColorCount> colorCounts2 = new ArrayList<>(
    092                colorCounts.subList(medianIndex + 1,
    093                        colorCounts.size()));
    094
    095        final ColorGroup less = new ColorGroup(new ArrayList<>(colorCounts1), ignoreAlpha);
    096        colorGroups.add(less);
    097        final ColorGroup more = new ColorGroup(new ArrayList<>(colorCounts2), ignoreAlpha);
    098        colorGroups.add(more);
    099
    100        final ColorCount medianValue = colorCounts.get(medianIndex);
    101        int limit;
    102        switch (mode) {
    103            case ALPHA:
    104                limit = medianValue.alpha;
    105                break;
    106            case RED:
    107                limit = medianValue.red;
    108                break;
    109            case GREEN:
    110                limit = medianValue.green;
    111                break;
    112            case BLUE:
    113                limit = medianValue.blue;
    114                break;
    115            default:
    116                throw new Error("Bad mode.");
    117        }
    118        colorGroup.cut = new ColorGroupCut(less, more, mode, limit);
    119    }
    120}