platform/core.output2/src/org/netbeans/core/output2/SparseIntList.java - netbeans - Git at Google

 /*
  * 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.netbeans.core.output2;

 import java.util.Arrays;

 /**
  * A sparsely populated list of integers, internally implemented as two
  * arrays of integers - one containing sequential indices that have been entered,
  * and one the values associated with those integers.  Calls to get() for values
  * which have not been added will return the value of the nearest lower added
  * entry that has been added plus the interval between that entry and the index
  * requested.  So, if you have such a list, it works as follows:
  * <p>
  * Entries are added with an associated index. get(idx) returns either value
  * corresponding to idx (if exists) or value corresponding to nearest lower index
  * + difference between requested index and nearest index of existing entry.
  * <p>
  * E.g. if you call add(10, 20), then get(0) == 1, get(9) == 10, get(10) == 20,
  * get(11) == 21, and so forth.
  * <p>
  * This is used to handle caching of logical line lengths in OutWriter -
  * if we have a 400000 line file, most lines will typically not need to be
  * word wrapped.  So we don't want to create a 400000 element int[] if most
  * of the time the number of wrapped lines will turn out to be 1 - instead,
  * only lines that are actually wrapped will have a line count added to a
  * SparseIntList; its get() behavior takes care of returning correct values
  * for the non-wrapped lines in between.
  * <p>
  * SparseIntList contains entry (key, value) for each line which needs wrapping,
  * <i>key</i> is zero-based index of such line and <i>value</i> is the number
  * of logical (after wrapping) lines that correspond to physical (unwrapped)
  * lines [0, key].
  *
  * @author  Tim Boudreau
  */
 final class SparseIntList {
     private int[] keys;
     private int[] values;
     private int used = 0;
     private int lastAdded = Integer.MIN_VALUE;
     private int lastIndex = Integer.MIN_VALUE;

     /** Creates a new instance of IntMap */
     SparseIntList(int capacity) {
         allocArrays (capacity);
     }

     /** Add an integer to the list. The value must be > than the last value passed
      * to this methodd, and the index must be > than the last index passed to
      * this method.
      */
     public synchronized void add(int idx, int value) {
         if (value < lastAdded) {
             throw new IllegalArgumentException ("Contents must be presorted - " + //NOI18N
                 "added value " + value + " is less than preceding " + //NOI18N
                 "value " + lastAdded); //NOI18N
         }
         if (idx <= lastIndex) {
             throw new IllegalArgumentException ("Contents must be presorted - " + //NOI18N
                 "added index " + idx + " is less than preceding " + //NOI18N
                 "index " + lastIndex); //NOI18N
         }
         if (used >= keys.length) {
             growArrays();
         }
         values[used] = value;
         keys[used++] = idx;
         lastAdded = value;
         lastIndex = idx;

         // clear cached result
         lastGetIndex = lastGetResult = -1;
         lastGetNextKeyValue = lastGetNextKeyResult = -1;
     }

     public synchronized void updateLast(int idx, int value) {
         if (lastIndex != idx) {
             throw new IllegalArgumentException("Last index: " + lastIndex + " idx: " + idx); //NOI18N
         }
         values[used - 1] = value;
         lastAdded = value;
         lastGetIndex = lastGetResult = -1;
         lastGetNextKeyValue = lastGetNextKeyResult = -1;
     }

     public synchronized void removeLast() {
         if (used < 1) {
             throw new IllegalStateException("Cannot remove last, list is empty"); //NOI18N
         }
         used--;
         if (used > 0) {
             lastAdded = values[used - 1];
             lastIndex = keys[used - 1];
         } else {
             lastAdded = lastIndex = Integer.MIN_VALUE;
         }
         lastGetIndex = lastGetResult = -1;
         lastGetNextKeyValue = lastGetNextKeyResult = -1;
     }

     int lastAdded() {
         return lastAdded;
     }

     int lastIndex() {
         return lastIndex;
     }

     private void allocArrays (int size) {
         keys = new int[size];
         values = new int[size];
         //Fill it with Integer.MAX_VALUE so binarySearch works properly (must
         //be sorted, cannot have 0's after the actual data
         Arrays.fill(keys, Integer.MAX_VALUE);
         Arrays.fill(values, Integer.MAX_VALUE);
     }


     /** Caches the last requested get value. Often we will be called repeatedly
      * for the same value - cache it */
     private int lastGetIndex = -1;
     /** Caches the last requested result for the same reasons. */
     private int lastGetResult;

     /**
      * Get an entry in the list.  If the list is empty, it will simply return
      * (index+1) value; if the index is lower than the first entry entered
      * by a call to add (index, value) in the list, it will do the same.
      * <p>
      * If the index is greater than an added value's index, the return result
      * will be the value of that index + the requested index minus the added
      * index.
      */
     public synchronized int get(int index) {
         if (index < 0) {
             return 0;
         }

         if ((used == 0) || (used > 0 && index < keys[0])) {
             return index + 1;
         }

         if (index == lastGetIndex) {
             return lastGetResult;
         } else {
             lastGetIndex = index;
         }

         //First, see if we have a real entry for this index - if add() was
         //called passing this exact index as a value
         int pos = Arrays.binarySearch(keys, index);
         if (pos >= 0) {  // real entry
             return lastGetResult = values[pos];
         } else {
             pos = -pos - 2;         // nearest element
             return lastGetResult = values[pos] + index - keys[pos];
         }
     }


     /** Caches the last requested getNextKey() value. Often we will be called
      * repeatedly for the same value - cache it */
     private int lastGetNextKeyValue = -1;
     /** Caches the last requested result for the same reasons. */
     private int lastGetNextKeyResult;

     /** Finds key which is next to key corresponding to supplied value,
      *  if value does not exit, the key is interpolated in similar manner as in get().
      *  This is used to locate physical line which corresponds to logical line
      */
     public synchronized int getNextKey(int val) {
         if (val < 0) {
             return 0;
         }
         if (used == 0) {
             return val;
         }
         if (used > 0 && val < values[0]) {
             return val < keys[0] ? val : keys[0];
         }

         if (val == lastGetNextKeyValue) {
             return lastGetNextKeyResult;
         } else {
             lastGetNextKeyValue = val;
         }

         int pos = Arrays.binarySearch(values, val);
         if (pos < 0) {
             pos = -pos - 1;
             int key = val - values[pos - 1] + keys[pos - 1] + 1;
             return lastGetNextKeyResult = pos < used ? Math.min(key, keys[pos]) : key;
         } else {
             while (pos >= 0 && pos + 1 < values.length
                     && values[pos] == values[pos + 1]) {
                 pos++;
             }
             return lastGetNextKeyResult = keys[pos] + 1;
         }
     }

     /** Finds key for supplied value, if value does not exit, the key is
      *  interpolated in similar manner as in get()
      */
     public synchronized int getKey(int val) {
         if (val < 0) {
             return 0;
         }
         if (used == 0) {
             return val - 1;
         }

         if (used > 0 && val < values[0]) {
             return val < keys[0] ? val - 1 : keys[0];
         }

         int pos = Arrays.binarySearch(values, val);
         if (pos < 0) {
             pos = -pos - 1;
             int key = val - values[pos - 1] + keys[pos - 1];
             return pos < used ? Math.min(key, keys[pos]) : key;
         } else {
             return keys[pos];
         }
     }

     /**
      * Grow the arrays we're using to store keys/values
      */
     private void growArrays() {
         int[] oldkeys = keys;
         int[] oldvals = values;
         allocArrays(Math.round(keys.length * 1.5f));
         System.arraycopy(oldkeys, 0, keys, 0, oldkeys.length);
         System.arraycopy(oldvals, 0, values, 0, oldvals.length);
     }

     @Override
     public String toString() {
         StringBuffer result = new StringBuffer ("SparseIntList ["); //NOI18N
         result.append ("used="); //NOI18N
         result.append (used);
         result.append (" capacity="); //NOI18N
         result.append (keys.length);
         result.append (" keyValuePairs:"); //NOI18N
         for (int i=0; i < used; i++) {
             result.append (keys[i]);
             result.append (':'); //NOI18N
             result.append (values[i]);
             if (i != used-1) {
                 result.append(','); //NOI18N
             }
         }
         result.append (']');
         return result.toString();
     }
 }
	/*
	* 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.netbeans.core.output2;

	import java.util.Arrays;

	/**
	* A sparsely populated list of integers, internally implemented as two
	* arrays of integers - one containing sequential indices that have been entered,
	* and one the values associated with those integers. Calls to get() for values
	* which have not been added will return the value of the nearest lower added
	* entry that has been added plus the interval between that entry and the index
	* requested. So, if you have such a list, it works as follows:
	* <p>
	* Entries are added with an associated index. get(idx) returns either value
	* corresponding to idx (if exists) or value corresponding to nearest lower index
	* + difference between requested index and nearest index of existing entry.
	* <p>
	* E.g. if you call add(10, 20), then get(0) == 1, get(9) == 10, get(10) == 20,
	* get(11) == 21, and so forth.
	* <p>
	* This is used to handle caching of logical line lengths in OutWriter -
	* if we have a 400000 line file, most lines will typically not need to be
	* word wrapped. So we don't want to create a 400000 element int[] if most
	* of the time the number of wrapped lines will turn out to be 1 - instead,
	* only lines that are actually wrapped will have a line count added to a
	* SparseIntList; its get() behavior takes care of returning correct values
	* for the non-wrapped lines in between.
	* <p>
	* SparseIntList contains entry (key, value) for each line which needs wrapping,
	* <i>key</i> is zero-based index of such line and <i>value</i> is the number
	* of logical (after wrapping) lines that correspond to physical (unwrapped)
	* lines [0, key].
	*
	* @author Tim Boudreau
	*/
	final class SparseIntList {
	private int[] keys;
	private int[] values;
	private int used = 0;
	private int lastAdded = Integer.MIN_VALUE;
	private int lastIndex = Integer.MIN_VALUE;

	/** Creates a new instance of IntMap */
	SparseIntList(int capacity) {
	allocArrays (capacity);
	}

	/** Add an integer to the list. The value must be > than the last value passed
	* to this methodd, and the index must be > than the last index passed to
	* this method.
	*/
	public synchronized void add(int idx, int value) {
	if (value < lastAdded) {
	throw new IllegalArgumentException ("Contents must be presorted - " + //NOI18N
	"added value " + value + " is less than preceding " + //NOI18N
	"value " + lastAdded); //NOI18N
	}
	if (idx <= lastIndex) {
	throw new IllegalArgumentException ("Contents must be presorted - " + //NOI18N
	"added index " + idx + " is less than preceding " + //NOI18N
	"index " + lastIndex); //NOI18N
	}
	if (used >= keys.length) {
	growArrays();
	}
	values[used] = value;
	keys[used++] = idx;
	lastAdded = value;
	lastIndex = idx;

	// clear cached result
	lastGetIndex = lastGetResult = -1;
	lastGetNextKeyValue = lastGetNextKeyResult = -1;
	}

	public synchronized void updateLast(int idx, int value) {
	if (lastIndex != idx) {
	throw new IllegalArgumentException("Last index: " + lastIndex + " idx: " + idx); //NOI18N
	}
	values[used - 1] = value;
	lastAdded = value;
	lastGetIndex = lastGetResult = -1;
	lastGetNextKeyValue = lastGetNextKeyResult = -1;
	}

	public synchronized void removeLast() {
	if (used < 1) {
	throw new IllegalStateException("Cannot remove last, list is empty"); //NOI18N
	}
	used--;
	if (used > 0) {
	lastAdded = values[used - 1];
	lastIndex = keys[used - 1];
	} else {
	lastAdded = lastIndex = Integer.MIN_VALUE;
	}
	lastGetIndex = lastGetResult = -1;
	lastGetNextKeyValue = lastGetNextKeyResult = -1;
	}

	int lastAdded() {
	return lastAdded;
	}

	int lastIndex() {
	return lastIndex;
	}

	private void allocArrays (int size) {
	keys = new int[size];
	values = new int[size];
	//Fill it with Integer.MAX_VALUE so binarySearch works properly (must
	//be sorted, cannot have 0's after the actual data
	Arrays.fill(keys, Integer.MAX_VALUE);
	Arrays.fill(values, Integer.MAX_VALUE);
	}


	/** Caches the last requested get value. Often we will be called repeatedly
	* for the same value - cache it */
	private int lastGetIndex = -1;
	/** Caches the last requested result for the same reasons. */
	private int lastGetResult;

	/**
	* Get an entry in the list. If the list is empty, it will simply return
	* (index+1) value; if the index is lower than the first entry entered
	* by a call to add (index, value) in the list, it will do the same.
	* <p>
	* If the index is greater than an added value's index, the return result
	* will be the value of that index + the requested index minus the added
	* index.
	*/
	public synchronized int get(int index) {
	if (index < 0) {
	return 0;
	}

	if ((used == 0) \|\| (used > 0 && index < keys[0])) {
	return index + 1;
	}

	if (index == lastGetIndex) {
	return lastGetResult;
	} else {
	lastGetIndex = index;
	}

	//First, see if we have a real entry for this index - if add() was
	//called passing this exact index as a value
	int pos = Arrays.binarySearch(keys, index);
	if (pos >= 0) { // real entry
	return lastGetResult = values[pos];
	} else {
	pos = -pos - 2; // nearest element
	return lastGetResult = values[pos] + index - keys[pos];
	}
	}


	/** Caches the last requested getNextKey() value. Often we will be called
	* repeatedly for the same value - cache it */
	private int lastGetNextKeyValue = -1;
	/** Caches the last requested result for the same reasons. */
	private int lastGetNextKeyResult;

	/** Finds key which is next to key corresponding to supplied value,
	* if value does not exit, the key is interpolated in similar manner as in get().
	* This is used to locate physical line which corresponds to logical line
	*/
	public synchronized int getNextKey(int val) {
	if (val < 0) {
	return 0;
	}
	if (used == 0) {
	return val;
	}
	if (used > 0 && val < values[0]) {
	return val < keys[0] ? val : keys[0];
	}

	if (val == lastGetNextKeyValue) {
	return lastGetNextKeyResult;
	} else {
	lastGetNextKeyValue = val;
	}

	int pos = Arrays.binarySearch(values, val);
	if (pos < 0) {
	pos = -pos - 1;
	int key = val - values[pos - 1] + keys[pos - 1] + 1;
	return lastGetNextKeyResult = pos < used ? Math.min(key, keys[pos]) : key;
	} else {
	while (pos >= 0 && pos + 1 < values.length
	&& values[pos] == values[pos + 1]) {
	pos++;
	}
	return lastGetNextKeyResult = keys[pos] + 1;
	}
	}

	/** Finds key for supplied value, if value does not exit, the key is
	* interpolated in similar manner as in get()
	*/
	public synchronized int getKey(int val) {
	if (val < 0) {
	return 0;
	}
	if (used == 0) {
	return val - 1;
	}

	if (used > 0 && val < values[0]) {
	return val < keys[0] ? val - 1 : keys[0];
	}

	int pos = Arrays.binarySearch(values, val);
	if (pos < 0) {
	pos = -pos - 1;
	int key = val - values[pos - 1] + keys[pos - 1];
	return pos < used ? Math.min(key, keys[pos]) : key;
	} else {
	return keys[pos];
	}
	}

	/**
	* Grow the arrays we're using to store keys/values
	*/
	private void growArrays() {
	int[] oldkeys = keys;
	int[] oldvals = values;
	allocArrays(Math.round(keys.length * 1.5f));
	System.arraycopy(oldkeys, 0, keys, 0, oldkeys.length);
	System.arraycopy(oldvals, 0, values, 0, oldvals.length);
	}

	@Override
	public String toString() {
	StringBuffer result = new StringBuffer ("SparseIntList ["); //NOI18N
	result.append ("used="); //NOI18N
	result.append (used);
	result.append (" capacity="); //NOI18N
	result.append (keys.length);
	result.append (" keyValuePairs:"); //NOI18N
	for (int i=0; i < used; i++) {
	result.append (keys[i]);
	result.append (':'); //NOI18N
	result.append (values[i]);
	if (i != used-1) {
	result.append(','); //NOI18N
	}
	}
	result.append (']');
	return result.toString();
	}
	}