<commit_before>/*
 * Part of the CCNx Java Library.
 *
 * Copyright (C) 2011 Palo Alto Research Center, Inc.
 *
 * This library is free software; you can redistribute it and/or modify it
 * under the terms of the GNU Lesser General Public License version 2.1
 * as published by the Free Software Foundation. 
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
 * Lesser General Public License for more details. You should have received
 * a copy of the GNU Lesser General Public License along with this library;
 * if not, write to the Free Software Foundation, Inc., 51 Franklin Street,
 * Fifth Floor, Boston, MA 02110-1301 USA.
 */
package org.ccnx.ccn.profiles.versioning;

import java.io.IOException;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;
import java.util.TreeSet;
import java.util.logging.Level;

import org.ccnx.ccn.CCNHandle;
import org.ccnx.ccn.CCNInterestListener;
import org.ccnx.ccn.impl.support.Log;
import org.ccnx.ccn.profiles.VersionMissingException;
import org.ccnx.ccn.protocol.ContentName;
import org.ccnx.ccn.protocol.ContentObject;
import org.ccnx.ccn.protocol.Interest;

/**
 * Manage splitting interests and generating interests for a base name.
 * 
 * This class is used by VersioningInterest.
 * 
 * Current interest filling algorithm:
 *    Interests are filled to MIN_FULL exclusions initially and allowed
 *    to grow to MAX_FULL exclusions.    When MAX_FULL exclusions is reached,
 *    the starting times are re-arranged.
 * 
 * This operates by maintaining a set of interests from [startingVersion, infinity).
 * Initially, we issue one interest I_0[startingVersion, infinity).  When that
 * interest fills, it is split in to two interests, and it is split to the left:
 * I_-1[startingVersion, k], I_0[k+1, infinity), where "k" is picked to keep
 * MIN_FILL in the right member (I_0).
 * 
 * "infinity" is really the maximum version component, so it is well-defined.
 * 
 * At some point, we will have a series of interests:
 *   I0[startingVersion, k0], I1[k0+1, k1], I2[k1+1, k2], I3[k2+1, k3], I4[k3+1, infinity)
 *   
 * Algorithm:
 *    - This algorithm is biased towards shifting to the left, because we fill from the right.
 *      Based on usage experience, we may want to change this filling algorithm.
 *    - The density of an InterestData is defined as (# exclusions) / (stop - start).  Seemed
 *      like a good idea at the time, but might want to drop this concept and just use the
 *      # of exclusions.
 *    - We track the average density of all intervals and use that to decide if we should
 *      rebalance by shifing or add a new interest.
 *      
 *    - When we receive an interest, find the corresponding InterestData that contains
 *      the version number.
 *    A) If that InterestData is not full (under MAX_FILL), then add the exclusion to that InterestData
 *      and re-express an Interest from that InterestData via the handleContent return value. Done.
 *    - The InterestData is full.
 *    B) Pick the left or right neighbor that is least full, if such a neighbor exists, and is
 *      under MID_FILL.  If equally filled, pick the left.
 *         - If picked left, transfer exclusions from the head to the left neighbor and then
 *           adjust the start & stop values.  Fill it up to MID_FILL.
 *         - If picked right, transfer exclusions from the tail to the right neighbor and then
 *           adjust the start & stop values.  Fill it up to MID_FILL.
 *         - Issue a new interest for the picked neighbor, then the current InterestData returns
 *           a new interest to handleContent.  These both replace the entries in _interestMap, so
 *           if we receive content for an old outstanding interest, no match is found and no
 *           "extra" interest will be generated from that.
 *         - done
 *   C) If the left or right neighbor does not exist, create it.  If both are missing, pick the left.
 *        - Let the current InterestData be M[a, b].
 *        - If left, create L[a, k] M[k, b] by transferring MIN_FILL elements
 *        - If right, create M[a, k] R[k, b] by transferring MID_FILL elements
 *        - Send a new interest for the new InterestData
 *        - Return a new interest to handleContent for M.
 *   D) If both the L and R neighbors are at MID_FILL or more, then we want to re-balance
 *     the intervals.  
 *        1) If the density of each of (L, M, R) is above average, insert a new interest.  Pick
 *          L or R based on the higher density of the neighbor.  If equal, pick left.
 *          Transfer MIN_FILL from M and the chosen side to the new interest.  Send a new
 *          interest message from the new interest and from the chosen neighbor, then
 *          return a new interest from M to handleContent
 *        2) Otherwise, rebalance.  Pick the denser side, and recursively shift that
 *          direction until the last node is under MID_FILL, or we are at the terminus
 *          and create a new interest.  Then balance current node and neighbor. 
 *          Issue a new interest message for each modified or created InterestData, 
 *          then return interest to handleContent for current interestdata. 
 *   
 */
public class VersioningInterestManager implements CCNInterestListener {

	// MIN_FILL should be less than MAX_FILL/2 due to how step D.1 works.
	//	public final static int MIN_FILL = 50;
	//	public final static int MID_FILL = 125;
	//	public final static int MAX_FILL = 200;

	// for testing
	public final static int MIN_FILL = 5;
	public final static int MID_FILL = 12;
	public final static int MAX_FILL = 20;


	/**
	 * Create a VersioningInterestManager for a specific content name.  Send
	 * results to the listener.
	 * 
	 * @param handle
	 * @param name
	 * @param exclusions may be null or empty
	 * @param startingVersion non-negative, use 0 for all versions
	 * @param listener
	 */
	public VersioningInterestManager(CCNHandle handle, ContentName name, Set<VersionNumber> exclusions, VersionNumber startingVersion, CCNInterestListener listener) {
		_handle = handle;
		_name = name;
		_listener = listener;
		
		if( null == startingVersion )
			_startingVersion = VersionNumber.getMinimumVersion();
		else
			_startingVersion = startingVersion;
		
		if( null != exclusions )
			_exclusions.addAll(exclusions);
	}

	/**
	 * Generate interests and return data to the listener
	 * @throws IOException 
	 */
	public synchronized void start() throws IOException {<commit_msg>Refs #100290.  Had debug values in VersioningInterestManager.  Switched back to prodution values for number of exclusions per interest.<commit_after>/*
 * Part of the CCNx Java Library.
 *
 * Copyright (C) 2011 Palo Alto Research Center, Inc.
 *
 * This library is free software; you can redistribute it and/or modify it
 * under the terms of the GNU Lesser General Public License version 2.1
 * as published by the Free Software Foundation. 
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
 * Lesser General Public License for more details. You should have received
 * a copy of the GNU Lesser General Public License along with this library;
 * if not, write to the Free Software Foundation, Inc., 51 Franklin Street,
 * Fifth Floor, Boston, MA 02110-1301 USA.
 */
package org.ccnx.ccn.profiles.versioning;

import java.io.IOException;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;
import java.util.TreeSet;
import java.util.logging.Level;

import org.ccnx.ccn.CCNHandle;
import org.ccnx.ccn.CCNInterestListener;
import org.ccnx.ccn.impl.support.Log;
import org.ccnx.ccn.profiles.VersionMissingException;
import org.ccnx.ccn.protocol.ContentName;
import org.ccnx.ccn.protocol.ContentObject;
import org.ccnx.ccn.protocol.Interest;

/**
 * Manage splitting interests and generating interests for a base name.
 * 
 * This class is used by VersioningInterest.
 * 
 * Current interest filling algorithm:
 *    Interests are filled to MIN_FULL exclusions initially and allowed
 *    to grow to MAX_FULL exclusions.    When MAX_FULL exclusions is reached,
 *    the starting times are re-arranged.
 * 
 * This operates by maintaining a set of interests from [startingVersion, infinity).
 * Initially, we issue one interest I_0[startingVersion, infinity).  When that
 * interest fills, it is split in to two interests, and it is split to the left:
 * I_-1[startingVersion, k], I_0[k+1, infinity), where "k" is picked to keep
 * MIN_FILL in the right member (I_0).
 * 
 * "infinity" is really the maximum version component, so it is well-defined.
 * 
 * At some point, we will have a series of interests:
 *   I0[startingVersion, k0], I1[k0+1, k1], I2[k1+1, k2], I3[k2+1, k3], I4[k3+1, infinity)
 *   
 * Algorithm:
 *    - This algorithm is biased towards shifting to the left, because we fill from the right.
 *      Based on usage experience, we may want to change this filling algorithm.
 *    - The density of an InterestData is defined as (# exclusions) / (stop - start).  Seemed
 *      like a good idea at the time, but might want to drop this concept and just use the
 *      # of exclusions.
 *    - We track the average density of all intervals and use that to decide if we should
 *      rebalance by shifing or add a new interest.
 *      
 *    - When we receive an interest, find the corresponding InterestData that contains
 *      the version number.
 *    A) If that InterestData is not full (under MAX_FILL), then add the exclusion to that InterestData
 *      and re-express an Interest from that InterestData via the handleContent return value. Done.
 *    - The InterestData is full.
 *    B) Pick the left or right neighbor that is least full, if such a neighbor exists, and is
 *      under MID_FILL.  If equally filled, pick the left.
 *         - If picked left, transfer exclusions from the head to the left neighbor and then
 *           adjust the start & stop values.  Fill it up to MID_FILL.
 *         - If picked right, transfer exclusions from the tail to the right neighbor and then
 *           adjust the start & stop values.  Fill it up to MID_FILL.
 *         - Issue a new interest for the picked neighbor, then the current InterestData returns
 *           a new interest to handleContent.  These both replace the entries in _interestMap, so
 *           if we receive content for an old outstanding interest, no match is found and no
 *           "extra" interest will be generated from that.
 *         - done
 *   C) If the left or right neighbor does not exist, create it.  If both are missing, pick the left.
 *        - Let the current InterestData be M[a, b].
 *        - If left, create L[a, k] M[k, b] by transferring MIN_FILL elements
 *        - If right, create M[a, k] R[k, b] by transferring MID_FILL elements
 *        - Send a new interest for the new InterestData
 *        - Return a new interest to handleContent for M.
 *   D) If both the L and R neighbors are at MID_FILL or more, then we want to re-balance
 *     the intervals.  
 *        1) If the density of each of (L, M, R) is above average, insert a new interest.  Pick
 *          L or R based on the higher density of the neighbor.  If equal, pick left.
 *          Transfer MIN_FILL from M and the chosen side to the new interest.  Send a new
 *          interest message from the new interest and from the chosen neighbor, then
 *          return a new interest from M to handleContent
 *        2) Otherwise, rebalance.  Pick the denser side, and recursively shift that
 *          direction until the last node is under MID_FILL, or we are at the terminus
 *          and create a new interest.  Then balance current node and neighbor. 
 *          Issue a new interest message for each modified or created InterestData, 
 *          then return interest to handleContent for current interestdata. 
 *   
 */
public class VersioningInterestManager implements CCNInterestListener {

	// MIN_FILL should be less than MAX_FILL/2 due to how step D.1 works.
		public final static int MIN_FILL = 50;
		public final static int MID_FILL = 125;
		public final static int MAX_FILL = 200;

	// for testing
//	public final static int MIN_FILL = 5;
//	public final static int MID_FILL = 12;
//	public final static int MAX_FILL = 20;


	/**
	 * Create a VersioningInterestManager for a specific content name.  Send
	 * results to the listener.
	 * 
	 * @param handle
	 * @param name
	 * @param exclusions may be null or empty
	 * @param startingVersion non-negative, use 0 for all versions
	 * @param listener
	 */
	public VersioningInterestManager(CCNHandle handle, ContentName name, Set<VersionNumber> exclusions, VersionNumber startingVersion, CCNInterestListener listener) {
		_handle = handle;
		_name = name;
		_listener = listener;
		
		if( null == startingVersion )
			_startingVersion = VersionNumber.getMinimumVersion();
		else
			_startingVersion = startingVersion;
		
		if( null != exclusions )
			_exclusions.addAll(exclusions);
	}

	/**
	 * Generate interests and return data to the listener
	 * @throws IOException 
	 */
	public synchronized void start() throws IOException {
{'fraction_non_alphanumeric': 0.0660531393795458, 'fraction_numerical': 0.00890604126465786, 'mean_word_length': 3.1245791245791246, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '1466107', 'n_tokens_mistral': 3824, 'n_tokens_neox': 3589, 'n_words': 1761}