/*
    * Licensed to the Apache Software Foundation (ASF) under one or more
    * contributor license agreements.  See the NOTICE file distributed with
    * this work for additional information regarding copyright ownership.
    * The ASF licenses this file to You under the Apache License, Version 2.0
    * (the "License"); you may not use this file except in compliance with
    * the License.  You may obtain a copy of the License at
    *
    *      http://www.apache.org/licenses/LICENSE-2.0
   *
   * Unless required by applicable law or agreed to in writing, software
   * distributed under the License is distributed on an "AS IS" BASIS,
   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   * See the License for the specific language governing permissions and
   * limitations under the License.
   */
  package org.apache.commons.imaging.palette;
  
  import java.awt.color.ColorSpace;
  import java.awt.image.BufferedImage;
  import java.awt.image.ColorModel;
  import java.util.ArrayList;
  import java.util.Arrays;
  import java.util.HashSet;
  import java.util.List;
  import java.util.Set;
  import java.util.logging.Level;
  import java.util.logging.Logger;
  
  import org.apache.commons.imaging.ImagingException;
  import org.apache.commons.imaging.common.Allocator;
  
  /**
   * Factory for creating palettes.
   */
  public class PaletteFactory {
  
      private static final class DivisionCandidate {
          // private final ColorSpaceSubset src;
          private final ColorSpaceSubset dstA;
          private final ColorSpaceSubset dstB;
  
          DivisionCandidate(final ColorSpaceSubset dstA, final ColorSpaceSubset dstB) {
              // this.src = src;
              this.dstA = dstA;
              this.dstB = dstB;
          }
      }
  
      private static final Logger LOGGER = Logger.getLogger(PaletteFactory.class.getName());
  
      public static final int COMPONENTS = 3; // in bits
  
      public int countTransparentColors(final BufferedImage src) {
          final ColorModel cm = src.getColorModel();
          if (!cm.hasAlpha()) {
              return 0;
          }
  
          final int width = src.getWidth();
          final int height = src.getHeight();
  
          int first = -1;
  
          for (int y = 0; y < height; y++) {
              for (int x = 0; x < width; x++) {
                  final int rgb = src.getRGB(x, y);
                  final int alpha = 0xff & rgb >> 24;
                  if (alpha < 0xff) {
                      if (first < 0) {
                          first = rgb;
                      } else if (rgb != first) {
                          return 2; // more than one transparent color;
                      }
                  }
              }
          }
  
          if (first < 0) {
              return 0;
          }
          return 1;
      }
  
      public int countTrasparentColors(final int[] rgbs) {
          int first = -1;
  
          for (final int rgb : rgbs) {
              final int alpha = 0xff & rgb >> 24;
              if (alpha < 0xff) {
                  if (first < 0) {
                      first = rgb;
                  } else if (rgb != first) {
                      return 2; // more than one transparent color;
                  }
              }
          }
  
          if (first < 0) {
             return 0;
         }
         return 1;
     }
 
     private void divide(final List<ColorSpaceSubset> v, final int desiredCount, final int[] table, final int precision) {
         final List<ColorSpaceSubset> ignore = new ArrayList<>();
 
         while (true) {
             int maxArea = -1;
             ColorSpaceSubset maxSubset = null;
 
             for (final ColorSpaceSubset subset : v) {
                 if (ignore.contains(subset)) {
                     continue;
                 }
                 final int area = subset.total;
 
                 if (maxSubset == null || area > maxArea) {
                     maxSubset = subset;
                     maxArea = area;
                 }
             }
 
             if (maxSubset == null) {
                 return;
             }
             if (LOGGER.isLoggable(Level.FINEST)) {
                 LOGGER.finest("\t" + "area: " + maxArea);
             }
 
             final DivisionCandidate dc = divideSubset2(table, maxSubset, precision);
             if (dc != null) {
                 v.remove(maxSubset);
                 v.add(dc.dstA);
                 v.add(dc.dstB);
             } else {
                 ignore.add(maxSubset);
             }
 
             if (v.size() == desiredCount) {
                 return;
             }
         }
     }
 
     private DivisionCandidate divideSubset2(final int[] table, final ColorSpaceSubset subset, final int precision) {
         final List<DivisionCandidate> dcs = new ArrayList<>(divideSubset2(table, subset, 0, precision));
 
         dcs.addAll(divideSubset2(table, subset, 1, precision));
         dcs.addAll(divideSubset2(table, subset, 2, precision));
 
         DivisionCandidate bestV = null;
         double bestScore = Double.MAX_VALUE;
 
         for (final DivisionCandidate dc : dcs) {
             final ColorSpaceSubset first = dc.dstA;
             final ColorSpaceSubset second = dc.dstB;
             final int area1 = first.total;
             final int area2 = second.total;
 
             final int diff = Math.abs(area1 - area2);
             final double score = (double) diff / (double) Math.max(area1, area2);
 
             if (bestV == null || score < bestScore) {
                 bestV = dc;
                 bestScore = score;
             }
 
         }
 
         return bestV;
     }
 
     private List<DivisionCandidate> divideSubset2(final int[] table, final ColorSpaceSubset subset, final int component, final int precision) {
         if (LOGGER.isLoggable(Level.FINEST)) {
             subset.dump("trying (" + component + "): ");
         }
 
         final int total = subset.total;
 
         final int[] sliceMins = Arrays.copyOf(subset.mins, subset.mins.length);
         final int[] sliceMaxs = Arrays.copyOf(subset.maxs, subset.maxs.length);
 
         int sum1 = 0;
         int slice1;
         int last = 0;
 
         for (slice1 = subset.mins[component]; slice1 != subset.maxs[component] + 1; slice1++) {
             sliceMins[component] = slice1;
             sliceMaxs[component] = slice1;
 
             last = getFrequencyTotal(table, sliceMins, sliceMaxs, precision);
 
             sum1 += last;
 
             if (sum1 >= total / 2) {
                 break;
             }
         }
 
         final int sum2 = sum1 - last;
         final int slice2 = slice1 - 1;
 
         final DivisionCandidate dc1 = finishDivision(subset, component, precision, sum1, slice1);
         final DivisionCandidate dc2 = finishDivision(subset, component, precision, sum2, slice2);
 
         final List<DivisionCandidate> result = new ArrayList<>();
 
         if (dc1 != null) {
             result.add(dc1);
         }
         if (dc2 != null) {
             result.add(dc2);
         }
 
         return result;
     }
 
     private DivisionCandidate finishDivision(final ColorSpaceSubset subset, final int component, final int precision, final int sum, final int slice) {
         if (LOGGER.isLoggable(Level.FINEST)) {
             subset.dump("trying (" + component + "): ");
         }
 
         final int total = subset.total;
 
         if (slice < subset.mins[component] || slice >= subset.maxs[component]) {
             return null;
         }
 
         if (sum < 1 || sum >= total) {
             return null;
         }
 
         final int[] sliceMins = Arrays.copyOf(subset.mins, subset.mins.length);
         final int[] sliceMaxs = Arrays.copyOf(subset.maxs, subset.maxs.length);
 
         sliceMaxs[component] = slice;
         sliceMins[component] = slice + 1;
 
         if (LOGGER.isLoggable(Level.FINEST)) {
             LOGGER.finest("total: " + total);
             LOGGER.finest("first total: " + sum);
             LOGGER.finest("second total: " + (total - sum));
             // System.out.println("start: " + start);
             // System.out.println("end: " + end);
             LOGGER.finest("slice: " + slice);
 
         }
 
         final ColorSpaceSubset first = new ColorSpaceSubset(sum, precision, subset.mins, sliceMaxs);
         final ColorSpaceSubset second = new ColorSpaceSubset(total - sum, precision, sliceMins, subset.maxs);
 
         return new DivisionCandidate(first, second);
 
     }
 
     private int getFrequencyTotal(final int[] table, final int[] mins, final int[] maxs, final int precision) {
         int sum = 0;
 
         for (int blue = mins[2]; blue <= maxs[2]; blue++) {
             final int b = blue << 2 * precision;
             for (int green = mins[1]; green <= maxs[1]; green++) {
                 final int g = green << 1 * precision;
                 for (int red = mins[0]; red <= maxs[0]; red++) {
                     final int index = b | g | red;
 
                     sum += table[index];
                 }
             }
         }
 
         return sum;
     }
 
     public boolean hasTransparency(final BufferedImage src) {
         return hasTransparency(src, 255);
     }
 
     public boolean hasTransparency(final BufferedImage src, final int threshold) {
         final int width = src.getWidth();
         final int height = src.getHeight();
 
         if (!src.getColorModel().hasAlpha()) {
             return false;
         }
 
         for (int y = 0; y < height; y++) {
             for (int x = 0; x < width; x++) {
                 final int argb = src.getRGB(x, y);
                 final int alpha = 0xff & argb >> 24;
                 if (alpha < threshold) {
                     return true;
                 }
             }
         }
         return false;
     }
 
     public boolean isGrayscale(final BufferedImage src) {
         final int width = src.getWidth();
         final int height = src.getHeight();
 
         if (ColorSpace.TYPE_GRAY == src.getColorModel().getColorSpace().getType()) {
             return true;
         }
 
         for (int y = 0; y < height; y++) {
             for (int x = 0; x < width; x++) {
                 final int argb = src.getRGB(x, y);
 
                 final int red = 0xff & argb >> 16;
                 final int green = 0xff & argb >> 8;
                 final int blue = 0xff & argb >> 0;
 
                 if (red != green || red != blue) {
                     return false;
                 }
             }
         }
         return true;
     }
 
     /**
      * Builds an exact complete opaque palette containing all the colors in {@code src}, using an algorithm that is faster than
      * {@linkplain #makeExactRgbPaletteSimple} for large images but uses 2 mebibytes of working memory. Treats all the colors as opaque.
      *
      * @param src the image whose palette to build
      * @return the palette
      */
     public Palette makeExactRgbPaletteFancy(final BufferedImage src) {
         // map what rgb values have been used
 
         final byte[] rgbmap = Allocator.byteArray(256 * 256 * 32);
 
         final int width = src.getWidth();
         final int height = src.getHeight();
 
         for (int y = 0; y < height; y++) {
             for (int x = 0; x < width; x++) {
                 final int argb = src.getRGB(x, y);
                 final int rggbb = 0x1fffff & argb;
                 final int highred = 0x7 & argb >> 21;
                 final int mask = 1 << highred;
                 rgbmap[rggbb] |= mask;
             }
         }
 
         int count = 0;
         for (final byte element : rgbmap) {
             final int eight = 0xff & element;
             count += Integer.bitCount(eight);
         }
 
         if (LOGGER.isLoggable(Level.FINEST)) {
             LOGGER.finest("Used colors: " + count);
         }
 
         final int[] colormap = Allocator.intArray(count);
         int mapsize = 0;
         for (int i = 0; i < rgbmap.length; i++) {
             final int eight = 0xff & rgbmap[i];
             int mask = 0x80;
             for (int j = 0; j < 8; j++) {
                 final int bit = eight & mask;
                 mask >>>= 1;
 
                 if (bit > 0) {
                     final int rgb = i | 7 - j << 21;
 
                     colormap[mapsize++] = rgb;
                 }
             }
         }
 
         Arrays.sort(colormap);
         return new SimplePalette(colormap);
     }
 
     /**
      * Builds an exact complete opaque palette containing all the colors in {@code src}, and fails by returning {@code null} if there are more than {@code max}
      * colors necessary to do this.
      *
      * @param src the image whose palette to build
      * @param max the maximum number of colors the palette can contain
      * @return the complete palette of {@code max} or less colors, or {@code null} if more than {@code max} colors are necessary
      */
     public SimplePalette makeExactRgbPaletteSimple(final BufferedImage src, final int max) {
         // This is not efficient for large values of max, say, max > 256;
         final Set<Integer> rgbs = new HashSet<>();
 
         final int width = src.getWidth();
         final int height = src.getHeight();
 
         for (int y = 0; y < height; y++) {
             for (int x = 0; x < width; x++) {
                 final int argb = src.getRGB(x, y);
                 final int rgb = 0xffffff & argb;
 
                 if (rgbs.add(rgb) && rgbs.size() > max) {
                     return null;
                 }
             }
         }
 
         final int[] result = Allocator.intArray(rgbs.size());
         int next = 0;
         for (final int rgb : rgbs) {
             result[next++] = rgb;
         }
         Arrays.sort(result);
 
         return new SimplePalette(result);
     }
 
     /**
      * Builds an inexact possibly translucent palette of at most {@code max} colors in {@code src} using the traditional Median Cut algorithm. Color bounding
      * boxes are split along the longest axis, with each step splitting the box. All bits in each component are used. The Algorithm is slower and seems exact
      * than {@linkplain #makeQuantizedRgbPalette(BufferedImage, int)}.
      *
      * @param src         the image whose palette to build
      * @param transparent whether to consider the alpha values
      * @param max         the maximum number of colors the palette can contain
      * @return the palette of at most {@code max} colors
      * @throws ImagingException if it fails to process the palette
      */
     public Palette makeQuantizedRgbaPalette(final BufferedImage src, final boolean transparent, final int max) throws ImagingException {
         return new MedianCutQuantizer(!transparent).process(src, max, new LongestAxisMedianCut());
     }
 
     /**
      * Builds an inexact opaque palette of at most {@code max} colors in {@code src} using a variation of the Median Cut algorithm. Accurate to 6 bits per
      * component, and works by splitting the color bounding box most heavily populated by colors along the component which splits the colors in that box most
      * evenly.
      *
      * @param src the image whose palette to build
      * @param max the maximum number of colors the palette can contain
      * @return the palette of at most {@code max} colors
      */
     public Palette makeQuantizedRgbPalette(final BufferedImage src, final int max) {
         final int precision = 6; // in bits
 
         final int tableScale = precision * COMPONENTS;
         final int tableSize = 1 << tableScale;
         final int[] table = Allocator.intArray(tableSize);
 
         final int width = src.getWidth();
         final int height = src.getHeight();
 
         final List<ColorSpaceSubset> subsets = new ArrayList<>();
         final ColorSpaceSubset all = new ColorSpaceSubset(width * height, precision);
         subsets.add(all);
 
         if (LOGGER.isLoggable(Level.FINEST)) {
             final int preTotal = getFrequencyTotal(table, all.mins, all.maxs, precision);
             LOGGER.finest("pre total: " + preTotal);
         }
 
         // step 1: count frequency of colors
         for (int y = 0; y < height; y++) {
             for (int x = 0; x < width; x++) {
                 final int argb = src.getRGB(x, y);
 
                 final int index = pixelToQuantizationTableIndex(argb, precision);
 
                 table[index]++;
             }
         }
 
         if (LOGGER.isLoggable(Level.FINEST)) {
             final int allTotal = getFrequencyTotal(table, all.mins, all.maxs, precision);
             LOGGER.finest("all total: " + allTotal);
             LOGGER.finest("width * height: " + width * height);
         }
 
         divide(subsets, max, table, precision);
 
         if (LOGGER.isLoggable(Level.FINEST)) {
             LOGGER.finest("subsets: " + subsets.size());
             LOGGER.finest("width*height: " + width * height);
         }
 
         for (int i = 0; i < subsets.size(); i++) {
             final ColorSpaceSubset subset = subsets.get(i);
 
             subset.setAverageRgb(table);
 
             if (LOGGER.isLoggable(Level.FINEST)) {
                 subset.dump(i + ": ");
             }
         }
 
         subsets.sort(ColorSpaceSubset.RGB_COMPARATOR);
 
         return new QuantizedPalette(subsets, precision);
     }
 
     private int pixelToQuantizationTableIndex(int argb, final int precision) {
         int result = 0;
         final int precisionMask = (1 << precision) - 1;
 
         for (int i = 0; i < COMPONENTS; i++) {
             int sample = argb & 0xff;
             argb >>= 8;
 
             sample >>= 8 - precision;
             result = result << precision | sample & precisionMask;
         }
 
         return result;
     }
 
 }