package mapmaker;

public class Compressor {

  /** provides information to resize an array to a given size by 
   * inserting or removing elements in it; which elements are 
   * allowed to be removed is given in advance;
   * if number of non-removable elements is larger that targeted
   * size, resizes to an array containing only the non-removeables;
   * returns an array of size equal to the new array size, with each
   * element equal to -1 if none of the old elements got transfered
   * to this position, or equal to that element's previous index 
   * in the given array otherwise
   * @param compressable is of length of the old array, indicates for
   * each element wether it's allowed to be removed or not
   * @param size the size the new array should have if possible
   */
  public static int[] compress(boolean[] removable, int size) {
    int minSize = 0;
    for (int i = 0; i < removable.length; i++)
      if (!removable[i])
	minSize++;
    // three cases: no removal, max removal, or something in between
    // no removal:
    if (size >= removable.length) {
      int[] compressed = new int[size];
      for (int i = 0; i < compressed.length; i++) 
	if (i < removable.length)
	  compressed[i] = i;
	else
	  compressed[i] = -1;
      return compressed;
    }
    // max removal:
    if (size <= minSize) {
      int[] compressed = new int[minSize];
      int pos = 0;
      for (int i = 0; i < compressed.length; i++) {
	// find next non-removable element
	while (removable[pos])
	  pos++;
	compressed[i] = pos;
	pos++;
      }
      return compressed;
    }
    // something in between:
    // Strategy: remove elements from the outside first
    int[] compressed = new int[size];
    int maxRemovable = size - minSize; // nr of removable elements to copy
    // find last non-removable element
    int lastPos = size - 1;
    while (lastPos >= 0 && removable[lastPos])
      lastPos--;
    // find first non-removable element
    int firstPos = 0;
    while (firstPos < compressed.length && removable[firstPos])
      firstPos++;
    // calculate maximum ammout of beginning elements to skip
    int maxSkip = (lastPos + 1) - size;
    if (maxSkip < 0)
      maxSkip = 0;
    // pos = min(maxSkip, firstPos)
    int pos = maxSkip < firstPos ? maxSkip : firstPos;
    // start coppying positions at pos, copy removable positions
    // until maxRemovable reached
    int removed = 0;
    for (int i = 0; i < compressed.length; i++) {
      if (removed >= maxRemovable)
	while (removable[pos])
	  pos++;
      else
	if (removable[pos])
	  removed++;
      compressed[i] = pos++;
    }
    return compressed;
  } // compress
    
} // Compressor