/*
 * CDDL HEADER START
 *
 * The contents of this file are subject to the terms of the
 * Common Development and Distribution License (the "License").
 * You may not use this file except in compliance with the License.
 *
 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
 * or http://www.opensolaris.org/os/licensing.
 * See the License for the specific language governing permissions
 * and limitations under the License.
 *
 * When distributing Covered Code, include this CDDL HEADER in each
 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
 * If applicable, add the following below this CDDL HEADER, with the
 * fields enclosed by brackets "[]" replaced with your own identifying
 * information: Portions Copyright [yyyy] [name of copyright owner]
 *
 * CDDL HEADER END
 */

/*
 * Copyright 2008 Sun Microsystems, Inc.  All rights reserved.
 * Use is subject to license terms.
 *
 * ident	"%Z%%M%	%I%	%E% SMI"
 */
package org.opensolaris.os.dtrace;

import java.util.*;
import java.io.*;
import java.beans.*;

/**
 * A frequency distribution aggregated by the DTrace {@code quantize()}
 * or {@code lquantize()} action.  Each aggregated value falls into a
 * range known as a bucket and counts toward the frequency of that
 * bucket.  Bucket ranges are consecutive, with the maximum of one
 * bucket's range always one less than the minimum of the next bucket's
 * range.  By convention each bucket is identified by the minimum of its
 * range.
 *
 * @author Tom Erickson
 */
public abstract class Distribution implements AggregationValue,
       Iterable <Distribution.Bucket>, Serializable
{
    static final long serialVersionUID = 1186243118882654932L;

    /** @serial */
    private List <Bucket> buckets;
    private transient double total;
    private transient boolean initialized;

    /**
     * Package level access, called by subclasses LinearDistribution and
     * LogDistribution, but not available outside the API.
     *
     * @param base  the lower bound of this distribution, or zero if not
     * applicable
     * @param constant  the constant term of the distribution function
     * used to calculate the lower bound of any bucket given the lower
     * bound of the previous bucket, for example the step in a linear
     * distribution or the log base in a logarithmic distribution.
     * @param frequencies  for each bucket, the number of aggregated
     * values falling into that bucket's range; each element must be a
     * positive integer
     * @throws NullPointerException if frequencies is null
     * @throws IllegalArgumentException if any element of frequencies
     * does not have the expected range as defined by checkBucketRange()
     */
    Distribution(long base, long constant, long[] frequencies)
    {
	total = 0;
	long frequency;
	for (int i = 0, len = frequencies.length; i < len; ++i) {
	    frequency = frequencies[i];
	    total += frequency;
	}

	buckets = createBuckets(base, constant, frequencies);
	initialized = true;
    }

    /**
     * Supports XML persistence of subclasses.  Sub-class implementation
     * must call initialize() after setting any state specific to that
     * subclass for determining bucket ranges.
     *
     * @throws NullPointerException if frequencies is null
     * @throws IllegalArgumentException if any element of frequencies
     * does not have the expected range as defined by checkBucketRange()
     */
    Distribution(List <Bucket> frequencies)
    {
	// defensively copy frequencies list
	int len = frequencies.size();
	// don't need gratuitous capacity % added by constructor that
	// takes a Collection argument; list will not be modified
	buckets = new ArrayList <Bucket> (len);
	buckets.addAll(frequencies);
    }

    final void
    initialize()
    {
        // Called by constructor and readObject() (deserialization).
	// 1. Check class invariants, throw exception if deserialized
	//    state inconsistent with a Distribution that can result
	//    from the public constructor.
	// 2. Compute total (transient property derived from buckets)
	total = 0;
	long frequency;
	Bucket bucket;
	int len = buckets.size();
	for (int i = 0; i < len; ++i) {
	    bucket = buckets.get(i);
	    frequency = bucket.getFrequency();
	    // relies on package-private getBucketRange()
	    // implementation
	    checkBucketRange(i, len, bucket);
	    total += frequency;
	}
	initialized = true;
    }

    // Must be called by public instance methods (since the AbstractList
    // methods all depend on get() and size(), it is sufficient to call
    // checkInit() only in those inherited methods).
    private void
    checkInit()
    {
	if (!initialized) {
	    throw new IllegalStateException("Uninitialized");
	}
    }

    /**
     * Gets a two element array: the first elelemt is the range minimum
     * (inclusive), the second element is the range maximum (inclusive).
     * Implemented by subclasses LinearDistribution and LogDistribution
     * to define bucket ranges for this distribution and not available
     * outside the API.  Used by the private general purpose constructor
     * called from native code.  Implementation must not use
     * subclass-specific state, since subclass state has not yet been
     * allocated.
     *
     * @see #Distribution(long base, long constant, long[] frequencies)
     */
    abstract long[]
    getBucketRange(int i, int len, long base, long constant);

    /**
     * Used by public constructors and deserialization only after
     * state specific to the subclass is available to the method.
     */
    abstract long[]
    getBucketRange(int i, int len);

    private List <Distribution.Bucket>
    createBuckets(long base, long constant, long[] frequencies)
    {
	int len = frequencies.length;
	Bucket bucket;
	List <Bucket> buckets = new ArrayList <Bucket> (len);
	long min; // current bucket
	long max; // next bucket minus one
	long[] range; // two element array: { min, max }

	for (int i = 0; i < len; ++i) {
	    range = getBucketRange(i, len, base, constant);
	    min = range[0];
	    max = range[1];
	    bucket = new Distribution.Bucket(min, max, frequencies[i]);
	    buckets.add(bucket);
	}

	return buckets;
    }

    /**
     * Validates that bucket has the expected range for the given bucket
     * index.  Uses {@code base} and {@code constant} constructor args
     * to check invariants specific to each subclass, since state
     * derived from these args in a subclass is not yet available in the
     * superclass constructor.
     *
     * @throws IllegalArgumentException if bucket does not have the
     * expected range for the given bucket index {@code i}
     */
    private void
    checkBucketRange(int i, int bucketCount, Distribution.Bucket bucket,
	    long base, long constant)
    {
	long[] range = getBucketRange(i, bucketCount, base, constant);
	checkBucketRange(i, bucket, range);
    }

    private void
    checkBucketRange(int i, int bucketCount, Distribution.Bucket bucket)
    {
	long[] range = getBucketRange(i, bucketCount);
	checkBucketRange(i, bucket, range);
    }

    private void
    checkBucketRange(int i, Distribution.Bucket bucket, long[] range)
    {
	long min = range[0];
	long max = range[1];

	if (bucket.getMin() != min) {
	    throw new IllegalArgumentException("bucket min " +
		    bucket.getMin() + " at index " + i + ", expected " + min);
	}
	if (bucket.getMax() != max) {
	    throw new IllegalArgumentException("bucket max " +
		    bucket.getMax() + " at index " + i + ", expected " + max);
	}
    }

    /**
     * Gets a modifiable list of this distribution's buckets ordered by
     * bucket range.  Modifying the returned list has no effect on this
     * distribution.  Supports XML persistence.
     *
     * @return a modifiable list of this distribution's buckets ordered
     * by bucket range
     */
    public List <Bucket>
    getBuckets()
    {
	checkInit();
	return new ArrayList <Bucket> (buckets);
    }

    /**
     * Gets a read-only {@code List} view of this distribution.
     *
     * @return a read-only {@code List} view of this distribution
     */
    public List <Bucket>
    asList()
    {
	checkInit();
	return Collections. <Bucket> unmodifiableList(buckets);
    }

    /**
     * Gets the number of buckets in this distribution.
     *
     * @return non-negative bucket count
     */
    public int
    size()
    {
	checkInit();
	return buckets.size();
    }

    /**
     * Gets the bucket at the given distribution index (starting at
     * zero).
     *
     * @return non-null distribution bucket at the given zero-based
     * index
     */
    public Bucket
    get(int index)
    {
	checkInit();
	return buckets.get(index);
    }

    /**
     * Gets an iterator over the buckets of this distribution.
     *
     * @return an iterator over the buckets of this distribution
     */
    public Iterator<Bucket>
    iterator()
    {
	checkInit();
	return buckets.iterator();
    }

    /**
     * Compares the specified object with this {@code Distribution}
     * instance for equality.  Defines equality as having the same
     * buckets with the same values.
     *
     * @return {@code true} if and only if the specified object is of
     * type {@code Distribution} and both instances have the same size
     * and equal buckets at corresponding distribution indexes
     */
    public boolean
    equals(Object o)
    {
	checkInit();
	if (o instanceof Distribution) {
	    Distribution d = (Distribution)o;
	    return buckets.equals(d.buckets);
	}
	return false;
    }

    /**
     * Overridden to ensure that equals instances have equal hash codes.
     */
    public int
    hashCode()
    {
	checkInit();
	return buckets.hashCode();
    }

    /**
     * Gets the total frequency across all buckets.
     *
     * @return sum of the frequency of all buckets in this distribution
     */
    public double
    getTotal()
    {
	checkInit();
	return total;
    }

    /**
     * Gets the numeric value of this distribution used to compare
     * distributions by overall magnitude, defined as the sum total of
     * each bucket's frequency times the minimum of its range.
     */
    public abstract Number getValue();

    /**
     * Called by native code
     */
    private void
    normalizeBuckets(long normal)
    {
	for (Bucket b : buckets) {
	    b.frequency /= normal;
	}
    }

    /**
     * A range inclusive at both endpoints and a count of aggregated
     * values that fall in that range.  Buckets in a {@link
     * Distribution} are consecutive, such that the max of one bucket is
     * always one less than the min of the next bucket (or {@link
     * Long#MAX_VALUE} if it is the last bucket in the {@code
     * Distribution}).
     * <p>
     * Immutable.  Supports persistence using {@link java.beans.XMLEncoder}.
     */
    public static final class Bucket implements Serializable {
	static final long serialVersionUID = 4863264115375406295L;

	/** @serial */
	private final long min;
	/** @serial */
	private final long max;
	/** @serial */
	private long frequency; // non-final so native code can normalize

	static {
	    try {
		BeanInfo info = Introspector.getBeanInfo(Bucket.class);
		PersistenceDelegate persistenceDelegate =
			new DefaultPersistenceDelegate(
			new String[] {"min", "max", "frequency"})
		{
		    /*
		     * Need to prevent DefaultPersistenceDelegate from using
		     * overridden equals() method, resulting in a
		     * StackOverFlowError.  Revert to PersistenceDelegate
		     * implementation.  See
		     * http://forum.java.sun.com/thread.jspa?threadID=
		     * 477019&tstart=135
		     */
		    protected boolean
		    mutatesTo(Object oldInstance, Object newInstance)
		    {
			return (newInstance != null && oldInstance != null &&
				(oldInstance.getClass() ==
				newInstance.getClass()));
		    }
		};
		BeanDescriptor d = info.getBeanDescriptor();
		d.setValue("persistenceDelegate", persistenceDelegate);
	    } catch (IntrospectionException e) {
		System.out.println(e);
	    }
	}

	/**
	 * Creates a distribution bucket with the given range and
	 * frequency.
	 *
	 * @param rangeMinimumInclusive sets the lower bound (inclusive)
	 * returned by {@link #getMin()}
	 * @param rangeMaximumInclusive sets the upper bound (inclusive)
	 * returned by {@link #getMax()}
	 * @param valuesInRange sets the value frequency in this
	 * bucket's range returned by {@link #getFrequency()}
	 * @throws IllegalArgumentException if {@code
	 * rangeMaximumInclusive} is less than {@code
	 * rangeMinimumInclusive}
	 */
	public
	Bucket(long rangeMinimumInclusive, long rangeMaximumInclusive,
		long valuesInRange)
	{
	    if (rangeMaximumInclusive < rangeMinimumInclusive) {
		throw new IllegalArgumentException("upper bound " +
			rangeMaximumInclusive + " is less than lower bound " +
			rangeMinimumInclusive);
	    }

	    min = rangeMinimumInclusive;
	    max = rangeMaximumInclusive;
	    frequency = valuesInRange;
	}

	/**
	 * Gets the lower bound of this bucket's range (inclusive).
	 */
	public long
	getMin()
	{
	    return min;
	}

	/**
	 * Gets the upper bound of this bucket's range (inclusive).
	 */
	public long
	getMax()
	{
	    return max;
	}

	/**
	 * Gets the number of values in a {@link Distribution} that fall
	 * into the range defined by this bucket.
	 */
	public long
	getFrequency()
	{
	    return frequency;
	}

	/**
	 * Compares the specified object with this distribution bucket
	 * for equality.  Defines equality of two distribution buckets
	 * as having the same range and the same frequency.
	 *
	 * @return false if the specified object is not a {@code
	 * Distribution.Bucket}
	 */
	@Override
	public boolean
	equals(Object o)
	{
	    if (o instanceof Bucket) {
		Bucket b = (Bucket)o;
		return ((min == b.min) &&
			(max == b.max) &&
			(frequency == b.frequency));
	    }
	    return false;
	}

	/**
	 * Overridden to ensure that equal buckets have equal hashcodes.
	 */
	@Override
	public int
	hashCode()
	{
	    int hash = 17;
	    hash = (37 * hash) + ((int)(min ^ (min >>> 32)));
	    hash = (37 * hash) + ((int)(max ^ (max >>> 32)));
	    hash = (37 * hash) + ((int)(frequency ^ (frequency >>> 32)));
	    return hash;
	}

	private void
	readObject(ObjectInputStream s)
		throws IOException, ClassNotFoundException
	{
	    s.defaultReadObject();
	    // check class invariants (as constructor does)
	    if (max < min) {
		throw new InvalidObjectException("upper bound " +
			max + " is less than lower bound " + min);
	    }
	}

	/**
	 * Gets a string representation of this distribution bucket
	 * useful for logging and not intended for display.  The exact
	 * details of the representation are unspecified and subject to
	 * change, but the following format may be regarded as typical:
	 * <pre><code>
	 * class-name[property1 = value1, property2 = value2]
	 * </code></pre>
	 */
	public String
	toString()
	{
	    StringBuilder buf = new StringBuilder();
	    buf.append(Bucket.class.getName());
	    buf.append("[min = ");
	    buf.append(min);
	    buf.append(", max = ");
	    buf.append(max);
	    buf.append(", frequency = ");
	    buf.append(frequency);
	    buf.append(']');
	    return buf.toString();
	}
    }

    /**
     * Gets a list of buckets of interest by excluding empty buckets at
     * both ends of the distribution.  Leaves one empty bucket on each
     * end if possible to convey the distribution context more
     * effectively in a display.
     *
     * @return an unmodifiable sublist that includes the range starting
     * from the first bucket with a non-zero frequency and ending with
     * the last bucket with a non-zero frequency, plus one empty bucket
     * before and after that range if possible
     */
    public List <Bucket>
    getDisplayRange()
    {
	checkInit();
	int min = -1;
	int max = -1;
	int len = size();
	Bucket b;
	// Get first non-empty bucket
	for (int i = 0; i < len; ++i) {
	    b = buckets.get(i);
	    if (b.getFrequency() > 0L) {
		min = i;
		break;
	    }
	}
	if (min < 0) {
	    return Collections. <Bucket> emptyList();
	}
	// Get last non-empty bucket
	for (int i = (len - 1); i >= 0; --i) {
	    b = buckets.get(i);
	    if (b.getFrequency() > 0L) {
		max = i;
		break;
	    }
	}
	// If possible, pad non-empty range with one empty bucket at
	// each end.
	if (min > 0) {
	    --min;
	}
	if (max < (len - 1)) {
	    ++max;
	}

	// subList inclusive at low index, exclusive at high index
	return Collections. <Bucket>
		unmodifiableList(buckets).subList(min, max + 1);
    }

    private void
    readObject(ObjectInputStream s)
            throws IOException, ClassNotFoundException
    {
	s.defaultReadObject();

	// Defensively copy buckets _before_ validating.  Subclass
	// validates by calling initialize() after reading any state
	// specific to that subclass needed for validation.
	int len = buckets.size();
	ArrayList <Bucket> copy = new ArrayList <Bucket> (len);
	copy.addAll(buckets);
	buckets = copy;
    }

    /**
     * Gets a string representation of this {@code Distribution} useful
     * for logging and not intended for display.  The exact details of
     * the representation are unspecified and subject to change, but the
     * following format may be regarded as typical:
     * <pre><code>
     * class-name[property1 = value1, property2 = value2]
     * </code></pre>
     */
    public String
    toString()
    {
	checkInit();
	StringBuilder buf = new StringBuilder();
	buf.append(Distribution.class.getName());
	buf.append("[buckets = ");
	List <Bucket> list = getDisplayRange();
	if (list.isEmpty()) {
	    buf.append("<empty>");
	} else {
	    buf.append(Arrays.toString(getDisplayRange().toArray()));
	}
	buf.append(", total = ");
	buf.append(getTotal());
	buf.append(']');
	return buf.toString();
    }
}