//
//  WeightMap.java
//  Anneal
//
//  Created by sw on Thu Sep 12 2002.
//  Copyright (c) 2001 __MyCompanyName__. All rights reserved.
//
//  WeightMap keeps an array of int "weights", and also
//  summary information, so that it can calculate the 
//  following things fast:
//
//  totalLeftOf( i ) = the total of the weights of elements 
//     0..(i-1) for any i between 0 and n, where n is
//     the number of elements. 
//     totalLeftOf(0) == 0  and  totalLeftOf(n) = sum of all.
//  
//  firstRightOf( t ) = finds the smallest i such that 
//     totalLeftOf( i ) >= t, assuming all weights >= 0.
//
//  If r is a random int between 1 and totalLeftOf(n),
//  (and all weights are >= 0)
//  then ( firstRightOf(r) - 1 ) is a random element with
//  probability of each proportional to its weight.
//
//  pick( RandomRange rg ) picks a random element this way.
//     If no elements have weight, an error is thrown.

package net.tiac.home.sw.anneal;

import java.lang.Integer;
import java.awt.*;
import java.awt.event.*;
import java.applet.Applet;

public class WeightMap {
    private int n, levels;
    private int [] [] sums;
    
    public WeightMap( int n ) {
        int m;
        
        this.n = n;
        levels = 1;
        for( m = n;  m > 1;  m = ( m + 1 ) / 2 ) {
            levels++;
        }
        
        sums = new int [levels] [];
        m = n;
        for( int level = 0;  level < levels;  level++ ) {
            m = ( m + 1 ) / 2;
            sums[ level ] = new int [ m ];
        }
    }
        
    public void checkBetween( int z, int i, int m ) {
        if( i < z  ||  i > m )  {
            throw( new Error( "" + 1 + " is <" + z + " or > " + m ) );
        }
    }
        
    // Here's how this implemention works:
    // The weights are grouped hierarchically into pairs, and
    // only the left members of pairs are stored, so
    // sums[0] holds all the weights whose indexes are even;
    // sums[1] holds sums of pairs of weights whose indexes,
    //         divided by two, are even (i.e. 0, 1, 4, 5, 8, 9...);
    // sums[2] holds sums of sets of four
    //         (0,1,2,3, 8,9,10,11, 16,17,18,19, 24,25,26,27...);
    // ... 
    // sums[ levels-1 ] [0] is the total of all the weights.
    
    public int getTotal( ) {
        return( sums[ levels - 1 ][ 0 ] );
    }
        
    
    public int totalLeftOf( int i ) {
        int t = 0;

        checkBetween( 0, i, n );
        for( int level = 0;  i > 0  &&  level < levels;  level++ ) {
            if( ( i & 1 ) == 1 ) {
                t += sums[ level ] [ i / 2 ];
            }
            i = i / 2;
        }
        return( t );
    }

        
    public int get( int i ) {
        // Not optimal but easy to write & believe in.
        return( totalLeftOf( i + 1 ) - totalLeftOf( i ) );
    }

        
    public void set( int i, int w )  {
        int diff = w - get( i );
        
        for( int level = 0;  level < levels;  level++ ) {
            if( ( i & 1 ) == 0 ) {
                sums[ level ] [ i / 2 ] += diff;
            }
            i = i / 2;
        }
    }
    
    public int firstRightOf( int t ) {
        int i;
        int level;
        
        checkBetween( 0, t, getTotal( ) );
        if( t == 0 )  return( 0 );
        i = 0;
        for( level = levels - 2;  level >= 0;  level-- ) {
            if( sums[ level ] [ i ] < t ) {
                t -= sums[ level ] [ i ];
                i = i * 2 + 1;
            } else {
                i = i * 2;
            }
        }
        return( i + 1 );  // The one to the right.
    }
    
    
    public int pick( RandomRange rg ) {
        int total = getTotal( );
        
        if( total <= 0 ) {
            throw( new Error( "Total " + total + " <= 0" ) );
        }
        return( firstRightOf( rg.nextInt( total ) + 1 ) - 1 );
    }
    
}