Implementation of count (in Julia v0.3)

butterflycount.jl

# Implementation of count (in Julia v0.3)
# Christophe MEYER 2015

# count the number of times v appears in the sorted vector A
function count(A, v)
  assert(issorted(A))
  lower = findbound(A, v, :lower)
  upper = findbound(A, v, :upper)
  found = lower > 0 && upper > 0
  if found
    return upper-lower+1
  else
    return 0
  end
end

# find the index where the value v appears in the sorted vector A
# returns -1 if not present
# v can be present multiple times,
# set bound to :lower (resp. :higher) to find the first (resp. the last) occurence
# look in subarray of A with range given by lower (inclusive) and upper (inclusive)
function findbound(A, v, bound=:lower, lower=1, upper=length(A))
  if upper-lower < 0 # empty range
    return -1 # for sure not present in empty range
  elseif 1 == upper-lower+1 # leaf of recursion when just 1 element
    if A[lower] != v
      return -1
    else
      return lower
    end
  end
  imiddle = div(lower+upper,2) # interger div
  m = A[imiddle]
  if v < m 
    return findbound(A, v, bound, 1, imiddle-1)
  elseif v > m
    return findbound(A, v, bound, imiddle+1, upper)
  elseif bound==:lower
    if imiddle == 1 || A[imiddle-1]<v
      return imiddle
    else
      return findbound(A, v, bound, 1, imiddle-1)
    end
  elseif bound==:upper
    if imiddle == upper || A[imiddle+1]>v
      return imiddle
    else
      return findbound(A, v, bound, imiddle+1, upper)
    end
  end
end

function tests()
  A = [1 1 2 2 3 3 4]
  assert(1 == findbound(A, 1, :lower))
  assert(2 == findbound(A, 1, :upper))
  assert(3 == findbound(A, 2, :lower))
  assert(4 == findbound(A, 2, :upper))
  assert(7 == findbound(A, 4, :lower))
  assert(7 == findbound(A, 4, :upper))
  assert(-1 == findbound(A, 5, :upper))
  assert(2 == count(A, 2))
  assert(1 == count(A, 4))
  assert(0 == count(A, 5))
end

tests()