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