/* Copyright (C) 2015 by Alexandru Cojocaru */

/* This program is free software: you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation, either version 3 of the License, or
   (at your option) any later version.

   This program 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 General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program.  If not, see <http://www.gnu.org/licenses/>. */

package main

import (
	"fmt"
	"math"
	"math/rand"
	"time"
)

// http://www.cs.umd.edu/~samir/498/vitter.pdf
func sample(s []int) int {
	r := s[0]
	for i := 1; i < len(s); i++ {
		j := rand.Int() % (i + 1)
		if j == 0 {
			r = s[i]
		}
	}
	return r
}

type item struct {
	w int
	v int
}

// A-ES algorithm described in: http://arxiv.org/abs/1012.0256
func weightedSample(s []item) int {
	var r int
	var k float64
	for _, i := range s {
		g := math.Pow(rand.Float64(), 1/float64(i.w))
		if g > k {
			r = i.v
			k = g
		}
	}
	return r
}

func main() {
	rand.Seed(time.Now().UnixNano())
	fmt.Printf("%d\n", sample([]int{1, 2, 3, 4, 5, 6, 7, 8, 9}))
	fmt.Printf("%d\n", weightedSample([]item{{3, 1}, {2, 2}, {1, 3}}))
}