# ex: set ts=2:
#
# Copyright Ryan Flynn <parseerror@gmail.com>
# Released under Public Domain. Use it! Credit would be nice.
#
# IdealHumanRandomIterator - select "random" members of a population, favoring
# those least-recently selected, to appease silly humans who hate repeats
#
# Abstract:
# given a decently-sized set of items (say, 100 famous quotes), an
# average persons's idea of N "random" entries is not actually random.
# people don't want items to appear twice in a row, or too frequently
# (even though true randomness means this is just as likely as any other order).
#
# instead, design a scheme whereby LRU items are weighted more heavily,
# to "encourage" subsequent selections to not repeat.
#
class IdealHumanRandomIterator
  @items = []

  def initialize(list)
    @items = list
  end

  # Given length L, generate a random number in the range [0,len-1), heavily
  # weighted towards the low end.
  def self.nexti(len)
    len += 1 if len % 2 == 1
    index = len > 2 ? rand(len/2) : 0
    return index
  end

  # return a psuedo-random member of items. subsequent calls should never
  # return the same item.
  def next()
    index = IdealHumanRandomIterator.nexti(@items.length)
    @items.push @items.delete_at(index)
    return @items.last
  end
end

if $0 == __FILE__
  puts "Unit tests..."
  N = 10
  p (0..N-1).map{|n| IdealHumanRandomIterator.nexti(N) }.sort.reverse
  puts "Range..."
  raise "nexti(0) must be 0" unless 0 == IdealHumanRandomIterator.nexti(0)
  raise "nexti(1) must be 0" unless 0 == IdealHumanRandomIterator.nexti(1)
  [0,1,2,4,8,16,32].each do |n|
    acc=[0]*10
    500.times{ i=IdealHumanRandomIterator.nexti(1 << n);acc[i]=acc[i]+1 if i < acc.size }
    printf "2**%2u %3u [%s]\n", n, eval(acc.join("+")), acc.map{|x|sprintf "%3u", x}.join(" ")
  end
  puts "Complexity..."
  Pool = "0123456789".split(//)
  printf "%2s %3s %5s %s\n", "#", "Rep", "Cmplx", "String"

  for i in (0..Pool.length-1)
    pool = Pool[0..i]
    ideal = IdealHumanRandomIterator.new(pool)
    n = (1..70).map{|_| ideal.next() }
    # for any pool of > 1 items we should have zero repeats
    repeats = n.length - n.to_s.gsub(/(.)\1+/, '\1').length
    complexity = n.to_s.gsub(/(.+?)\1+/, '\1')
    printf "%2u %3u %5d %s\n", i, repeats, complexity.length, n.to_s
    if i > 0
      #raise "No item should ever repeat" if repeats > 0
      if i > 2
        # for sets of more than 2 items check that the resulting string
        # is not a mere concatenation of a few duplicated substrings
        if complexity.length < n.length / 2
          puts complexity
          raise "Too non-random"
        end
      end
    end
  end
  puts "OK."
end