# Implementation of BasicCounting algorithm from the paper
# Datar et.al.
# "Maintaining stream statistics over sliding windows"
# http://ilpubs.stanford.edu:8090/504/1/2001-34.pdf
#
using Base.Test


"""
 Count the number of 1's in the binary vector.
"""
function numOfOnes(w)
  h::Array{Int,1} = zeros(2)
  for e in w
    h[e+1] += 1
  end
  h[2]
end


"""
 Naive counting for the benchmark.
"""
function naiveCounting(seq_length = 100, w_length = 10)
    n::Array{Int64,1} = []
    y = rand([0,1], seq_length)
    arr = zeros(2)
    for t = w_length : length(y)
        window = y[ (t-w_length + 1) : t]
        n_of_ones = numOfOnes(window)
        push!(n, n_of_ones)
    end
    n
end


function hist_int(v::Array{Int,1})
    a=unique(v)
    hist::Array{Int,1} = zeros(maximum(a))
    for e in a
        hist[e]+=1
    end
    hist
end


"""
 ..each data element has an arrival time which increments by one at each arrival ,
 with the leftmost element considered to have arrived at time 1.

 timestamp corresponds to the position of an active data element in the current
 window.. we timestamp the active data elements from right to left, with the most
 recent element being at position 1.

 histograms are constructed by counting 1's in buckets by timestamps (?)

 IMPORTANT: Histogram must be updates so that Invariants 1,2 satisfied.

"""
function basic_counting(x::Array{Int, 1}, N=10)
    n = length(x)
    TOTAL::Int=0
    LAST::Int = 0
    k=2 # k=[1/ϵ]
    # p.4: "The estimate is TOTAL minus half of LAST"
    # timestamps are naturally given by indexing buckets[] array
    buckets::Array{Int,1} = zeros(N)
    arrival_times::Array{Int,1} = zeros(N)
    # expiration_times = zeros(N)
    max_num_of_buckets = (k/2.0+1.0)*(log2(2.0*N/k+1.0)+1)
    println("max_num_of_buckets=$max_num_of_buckets")
    for t = 1:n
        if x[t]==1
            TOTAL += 1
            # 1.. If the timestamp of the last bucket indicates expiry, delete
            # that bucket and update the counter LAST containing the size of the
            # last bycket and the counter TOTAL (total size of buckets)
            buckets = circshift(buckets,1)
            if buckets[1]!=0
                TOTAL += buckets[1]
            end
            buckets[1] = x[t]
            println(buckets)
            println(TOTAL)
            arrival_times[1] = t
            arrival_times = circshift(arrival_times,1)
            # println(arrival_times,"\n")
        end
    end
end


"""
 Merge just two buckets with given indices.
 ([1,1,2,4], 1, 2) -> [2,2,4,0]
 ([1,1,2,4,0,0], 1, 2) -> [2,2,4,0,0,0]
"""
function merge_buckets!(buckets::Array{Int,1}, idx1::Int, idx2::Int)
    val = buckets[idx1]
    @assert val == buckets[idx2]
    @assert idx1 <= idx2
    buckets[idx1] = 2 * val
    buckets[idx2] = 0
    buckets[idx2:end-1] = buckets[idx2+1:end]
    buckets[end]=0
    buckets
end


"""
 Collapse/merge buckets to keep the Invariant 2.
 Example:
 ([32,16,8,8,8,2,2,1,1], val=8, num=2) -> [32,16,16,8,2,2,1,1,0]
"""
function collapse_buckets(EH_histogram::Array{Int,1}; val=1, num=1)
    @assert num >= 2
    n = length(EH_histogram)
    out::Array{Int,1} = zeros(n)
    count::Int = 0
    first_val_index::Int = 0
    last_val_index::Int = 0
    last_non_zero::Int=0
    for i = 1:n
        if EH_histogram[i] == val
            count += 1
            last_val_index = i
        end
        if EH_histogram[i]==0
            last_non_zero = i-1
        end
    end
    @assert count >= num
    if last_non_zero == 0
        last_non_zero = n
    end
    first_val_index = last_val_index - count + 1
    # shift_left = count - num + 1
    out[1:first_val_index-1] = EH_histogram[1:first_val_index-1]
    out[first_val_index] = val*num
    out[first_val_index + 1 : first_val_index + 1 + count - num - 1] = val #todo
    # @assert sum(EH_histogram) == sum(out)
    ## Untouched tail
    width_of_untouched_tail = last_non_zero - last_val_index
    ## Index of the first element of the tail
    tail_first_el = first_val_index + count - num + 1
    out[tail_first_el : tail_first_el + width_of_untouched_tail-1] = EH_histogram[last_val_index+1:last_non_zero]
    out
end


function test_collapse_buckets()
    println("... Run test_collapse_buckets()")
    @test collapse_buckets([32,16,8,8,8,2,2,1,1], val=8, num=2) == [32,16,16,8,2,2,1,1,0]
    @test collapse_buckets([32,16,16,8,2,2,1,1,0], val=2, num=2) == [32,16,16,8,4,1,1,0,0]
    @test collapse_buckets([32,16,16,8,4,1,1,0,0], val=16, num=2) == [32,32,8,4,1,1,0,0,0]
    @test collapse_buckets([1,1,1,1,0], val=1, num=2) == [2,1,1,0,0]
    @test collapse_buckets([2,1,1,0,0], val=1, num=2) == [2,2,0,0,0]
    println(".. Stop")
end


"""
 Check the Invariant 2: if there are (k/2 + 2) buckets with the number of
 elements of the same size.
 EH_histogram example : [32,16,8,8,4,4,2,1,1]
 Return: [] if there no such elements, otherwise - the element's value.
"""
function check_condition(EH_histogram::Array{Int,1}, k::Int)
    uniq_vals = unique(EH_histogram)
    h::Array{Int,1} = zeros(maximum(uniq_vals))
    out_of_condition_values::Array{Int,1} = []
    for el in EH_histogram
        if el > 0
            h[el] += 1
            if h[el] >= convert(Int, k/2 + 2)
                push!(out_of_condition_values, el)
            end
        end
    end
    return sort(unique(out_of_condition_values))
end

# convert(Int, 4/2 + 2)

""" 
 The state of the exponential histogram.
 Example:
 [3, 2, 1, 1, 1, 0, 0]
 head = 1
 tail = 5
 total = 8
 maxLen = 7
"""
mutable struct EHState
    head::Int
    tail::Int
    total::Int
    maxLen::Int
    function EHState(maxLen::Int)
        new(0,0,0,maxLen)
    end
end

function checkEHState()
    # for i = 1:n
    #     e = new_buckets[i]
    #     if e != 0
    #         # @assert e <= 2^(n-i) # todo check boundaries
    #     else
    #         break
    #     end
    # end
end

"Find tail of the buckets array"
function find_tail(buckets::Array{Int,1})
    tail::Int=-1
    flag::Bool=false
    n::Int = length(buckets)
    for k=1:n
        if flag
            break
        else
            if buckets[k] == 0
                tail = k-1
                flag = true
            end
            if k==n
                tail=n
                flag=true
            end
        end
    end
    tail
end
# find_tail([1,2,3,0,0,1])
# find_tail([1,2,3,5,5,1])

"Check buckets array structure - if it consists of consecutive
positive numbers and after that only consecutive zeros.
Or
- only zeros
- or all positive.
- exponentiality = MERGE TO ALREADY IMPLEMENTED FUNC
"
function check_buckets(buckets::Array{Int,1}) end


"Find first 2 same elements"
function find2same(buckets::Array{Int,1}, vl::Int)
    flag::Bool=false
    cand_idx::Int=0
    for k=2:length(buckets)
        if flag
            break
        else
            if buckets[k-1]==vl && buckets[k]==vl
                cand_idx = k
                flag=true
            end
        end
    end
    cand_idx
end


"""
 Fill from right to left.
 2: Translate one state to another.
 Test cases:
 [0,0,0,0,0,0,0,0,0,0], 1 -> [0,0,0,0,0,0,0,0,0,1]
 [0,0,0,0,0,0,0,0,0,1], 1 -> [0,0,0,0,0,0,0,0,1,1]
 [0,0,0,0,0,0,0,0,1,1], 1 -> [0,0,0,0,0,0,0,1,1,1]
 [0,1,1,1,1,1,1,1,1,1], 1 -> [1,1,1,1,1,1,1,1,1,1]
 [32,16,8,8,4,4,2,1,1], 1 -> [32,16,8,8,4,4,2,2,1]

 STORE 1'S IN THE BUCKETS OF SIZES OF POWER 2.
"""
function basic_counting2!(buckets::Array{Int,1},
                          ehstate::EHState,
                          x_new::Int;
                          k::Int=2)
    n = length(buckets)
    ## initialization
    if ehstate.head == 0 && ehstate.tail == 0
        buckets[end] = x_new
        ehstate.total += x_new
        ehstate.head = n
        ehstate.tail = n
    else
        if buckets[1] == 0 ## filling up
            buckets = circshift(buckets, -1)
            buckets[end] = x_new
            ehstate.total += x_new
            ehstate.head -= 1
            ehstate.tail = n
        else ## All buckets are not empty
            ehstate.total += x_new
            ##=== Start add new data
            if ehstate.tail < n
                @assert buckets[ehstate.tail+1] == 0
                @assert buckets[ehstate.tail] != 0
                buckets[ehstate.tail+1] = x_new
            else
                buckets[end] = x_new # add new data
            end
            ehstate.tail = find_tail(buckets)
            ##=== End add new data
            ch = check_condition(buckets, k)
            if ch == [] ## -> don't do collapse
                if ehstate.head==1 && ehstate.tail == n
                    buckets[1] = 0 # release memory
                    buckets = circshift(buckets, -1)
                end
                println("Don't do collapse:", buckets, " tail=", ehstate.tail)
            else # -> do collapse
                println("TOTAL (before collapse)=", ehstate.total)
                ##=== Start Find same succesive elements to collapse
                println("candidates indices (ch)=$ch")
                v :: Int = ch[1] ##??? fix - joining only 1-s
                cand_idx = find2same(buckets, v)
                ## === End Find same succesive elements to join
                if cand_idx != 0
                    println("Join ", cand_idx-1, " and ", cand_idx, " in ", buckets)
                    # println("Join ", buckets[cand_idx-1], " and ", buckets[cand_idx], " in ", buckets)
                    @assert buckets[cand_idx-1] == buckets[cand_idx]
                    buckets=collapse_buckets(buckets, val=buckets[cand_idx], num=2)
                    # -- sync circshift and collapse
                    ehstate.tail = find_tail(buckets)
                    println("After collapse: ", buckets)
                end
                ##=== End Find same succesive elements to collapse
            end
        end
    end
    buckets, ehstate
end


function test_check_condition()
    println("... Run test_check_condition()")
    @test check_condition([32,16,1,1,1], 2) == [1]
    @test check_condition([32,16,1,1,1], 4) == []
    @test check_condition([32,16,16,16,16,1,1,1], 4) == [16]
    println(".. Stop")
end

""" Sliding window demo. """
function sliding_window_demo()
    x = [1:100;]
    window=zeros(10)
    for i=1:length(x)
        window=circshift(window,1)
        window[1]=x[i]
        println(window)
    end
end

function test_basic_counting()
    println("... Run test_basic_counting()")
    r,s=basic_counting2!(zeros(Int,10), EHState(10), 1)
    for k=1:550
        println("k=$k")
        r, s = basic_counting2!(r, s, 1,k=4)
        # println(r, " total:", s.total, " head:", s.head, " tail:", s.tail)
    end
    # r = basic_counting!([32,16,8,8,4,4,4,2,1,1], 1)

    @test merge_buckets!([1,1,2,3], 1, 2) == [2,2,3,0]
    @test merge_buckets!([1,1], 1, 2) == [2,0]
    # @test basic_counting([1,1,2,4,4,8,8,16,32],1) == [32,16,8,8,4,4,2,2,1]
    # @test basic_counting([32,16,8,8,4,4,2,2,1],1) == [32,16,16,8,4,2,1]
    # @test check_condition([32,16,8,8,4,4,2,1,1] == true)
    # @test check_condition([32,16,8,8,4,4,2,2,1] == true)
    println(".. Stop ")
end

test_check_condition()
test_collapse_buckets()
test_basic_counting()

# tic()
# r = naiveCounting(1000000, 10000)
# toc()
