/*
 * Copyright (c) 2009, Takeyuki Nagao
 * All rights reserved.
 * 
 * Redistribution and use in source and binary forms, with or
 * without modification, are permitted provided that the
 * following conditions are met:
 * 
 *  * Redistributions of source code must retain the above
 *    copyright notice, this list of conditions and the
 *    following disclaimer.
 *  * Redistributions in binary form must reproduce the above
 *    copyright notice, this list of conditions and the
 *    following disclaimer in the documentation and/or other
 *    materials provided with the distribution.
 *    
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
 * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
 * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR
 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE
 * USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY
 * OF SUCH DAMAGE.
 */

package dvi.font;

import java.util.ArrayList;


public class SequencePacker
{
  private final ArrayList<Integer> data; // We don't modify its content.

  public SequencePacker(ArrayList<Integer> data)
  {
    this.data = data;
  }

  private byte [] _buf;
  private int _ptr;
  private int _highNyb;

  private void writeNyb(int a)
  {
    if (_highNyb != 0) {
      _buf[_ptr] |= (byte)((a & 15) << 4);
      _highNyb = 0;
    } else {
      _buf[_ptr] |= (byte)(a & 15);
      _ptr++;
      _highNyb = 1;
    }
  }

  public PackedSequence pack()
  {
    Config cfg = findBestConfig(data);
    return pack(cfg);
  }

  private PackedSequence pack(final Config cfg)
  {
    final int nybLength = cfg.nybLength;
    final byte [] buf = new byte [(nybLength + 1)>>>1];
    final int dynF = cfg.dynF;
    final int dynG = computeDynG(dynF);
    final int dynH = computeDynH(dynF);

    _buf = buf;
    _ptr = 0;
    _highNyb = 1;

    final int ds = data.size();
    for (int i=0; i<ds; i++) {
      int c = data.get(i);
      if (c == 0) continue; // ignored.

      if (c == -1) {
        writeNyb(15);
        continue;
      } else if (c < 0) {
        writeNyb(14);
        c = -c;
      }

      if (c <= dynF) {
        writeNyb(c);
      } else if (c < dynG) {
        final int cc = c + dynH;
        writeNyb(cc >>> 4);
        writeNyb(cc >>> 0);
      } else {
        final int cc = c - dynG + 16;
        int k = cc >>> 4;
        int nl = 0;
        while (k > 0) {
          writeNyb(0);
          k >>>= 4;
          nl += 4;
        }
        while (nl >= 0) {
          writeNyb(cc >>> nl);
          nl -= 4;
        }
      }
    }

    _buf = null;

    return new PackedSequence(buf, dynF, nybLength);
  }

  private static int computeDynG(int dynF)
  {
    return ((13-dynF) << 4) + dynF + 1;
  }

  private static int computeDynH(int dynF)
  {
    return ((dynF+1) << 4) - dynF - 1; // 15 * (dynF + 1)
  }

  private static final int [] cc2diffPos;

  static {
    cc2diffPos = new int[13*15];
    for (int d=0; d<13; d++) {
      for (int j=0; j<15; j++) {
        int cc = d * 15 + j;
        cc2diffPos[cc] = 12 - d;
      }
    }
  }

  private static class Config
  {
    private final int dynF;
    private final int nybLength;
    private Config(int dynF, int nybLength) {
      this.dynF = dynF;
      this.nybLength = nybLength;
    }
  }

  private static Config findBestConfig(ArrayList<Integer> data)
  {
    int len = 0;
    int [] diff = new int [13];

    // We first compute the nyb length, assuming that dynF=0.
    // At the same time, we store the difference information to diff,
    // which is used later to compute the nyb length for other
    // values of dynF.
    final int ds = data.size();
    for (int i=0; i<ds; i++) {
      int c = data.get(i);
      if (c == 0) continue; // ignored.
      if (c == -1) {
        len++;
        continue;
      } else if (c < 0) {
        len++;
        c = -c;
      }

      if (c < (1 << 4) - 2) {
        diff[c-1] -= 1;
        len += 2;
      } else if (c < (1 <<  4) - 2 + 195) {
        final int cc = c - ((1 << 4) - 2);
        diff[cc2diffPos[cc]] += 1;
        len += 2;
      } else if (c < (1 <<  8) - 2) {
        len += 3;
      } else if (c < (1 <<  8) - 2 + 195) {
        final int cc = c - ((1 << 8) - 2);
        diff[cc2diffPos[cc]] += 2;
        len += 3;
      } else if (c < (1 << 12) - 2) {
        len += 5;
      } else if (c < (1 << 12) - 2 + 195) {
        final int cc = c - ((1 << 12) - 2);
        diff[cc2diffPos[cc]] += 2;
        len += 5;
      } else if (c < (1 << 16) - 2) {
        len += 7;
      } else if (c < (1 << 16) - 2 + 195) {
        final int cc = c - ((1 << 16) - 2);
        diff[cc2diffPos[cc]] += 2;
        len += 7;
      } else if (c < (1 << 20) - 2) {
        len += 9;
      } else if (c < (1 << 20) - 2 + 195) {
        final int cc = c - ((1 << 20) - 2);
        diff[cc2diffPos[cc]] += 2;
        len += 9;
      } else if (c < (1 << 24) - 2) {
        len += 11;
      } else if (c < (1 << 24) - 2 + 195) {
        final int cc = c - ((1 << 24) - 2);
        diff[cc2diffPos[cc]] += 2;
        len += 11;
      } else if (c < (1 << 28) - 2) {
        len += 13;
      } else if (c < (1 << 28) - 2 + 195) {
        final int cc = c - ((1 << 28) - 2);
        diff[cc2diffPos[cc]] += 2;
        len += 13;
      } else {
        len += 15;
      }
    }

    int bestDynF = -1;
    int bestSize = Integer.MAX_VALUE;
    int dynF = 0;
    for (;;) {
      if (len < bestSize) {
        bestDynF = dynF;
        bestSize = len;
      }
      if (dynF >= 13)
        break;

      len += diff[dynF];
      dynF++;
    }

    Config cfg = new Config(bestDynF, bestSize);
    return cfg;
  }
}
