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