[Draft 1] serialization

serialize.jl

using Base.Order

"""
    serialize(order::Ordering, x)

Map `x` to an un unsigned int, maintaining sort order.

The map should be reversible with [`deserialize`](@ref) when `!lt(order, a, b)` is
[antisymmetric](@ref https://en.wikipedia.org/wiki/Antisymmetric_relation)
for `a, b <: typeof(x)`. Satisfies lt(order, a, b) === (serialize(order, a) < serialize(order, b)).
Return missing if unimplemented.

See also: [`serializable`](@ref) [`deserialize`](@ref)
"""
serialize(order::Ordering, x) = missing

"""
    serializable(order::Ordering, x)

Return wheather [`serialize`](@ref) is implemented for the provided arguments

See also: [`deserializable`](@ref)
"""
serializable(order::Ordering, x) = !ismissing(serialize(order, x))
serializable(order::Ordering, x::Type) = !ismissing(serialize(order, zero(x)))
Serialize(order::Ordering, x::Type) = typeof(serialize(order, zero(x)))

"""
    deserialize(T::Type, order::Ordering, u::Unsigned)

Reconstruct the unique value `x::T` that serializes to `u`. If implemented,
satisfies `x === deserialize(T, order, serialize(order, x::T))` for all `x <: T`.
Return missing if unimplemented.

See also: [`serialize`](@ref) [`deserializable`](@ref)
"""
deserialize(T::Type, order::Ordering, u::Unsigned) = missing
deserialize(T::Type, order::Ordering, u::Missing) = missing

"""
    deserializable(T::Type, order::Ordering, u)

Return wheather [`deserialize`](@ref) is implemented for the provided arguments

See also: [`serializable`](@ref)
"""
deserializable(T::Type, order::Ordering, u=serialize(order, zero(T))) = !ismissing(deserialize(T, order, u))


# TODO how do we do (de)serializable. The current implementation is broken b.c. in the case
# of non-homogonous arrays we need to take an eltype as argument (and refurn false), not an element
# and perhaps return true.

# It is possible to used serializible and deserializible
# or to use missing, but this system is pretty nice if it's safe
# isempty(Base.return_types(serialize, (O, El))) (it's not safe.)
# what is the best way to recognize serializibility?

# 1) Manual
#   a) general definition of seializable as false
#   b) serialize is defined `function serialize end` without defaults
#   c) wherever serialize is specialized, so is serializable
#   +) performant, straightforward
#   -) more code, users need to specialize serializable & serialize
# 2) Run it
#   a) serialize is defined to regturn missing by default
#   b) serializable runs serialize concretely
#   +) concise, easy to extend serialize
#   -) *no support for eltype*, performance overhead
# 3) Muck with Base.return_types etc.
#   a) idk
#   +) easy for user to specialize serialize & supports eltype.
#   -) mucking around



#TODO support Bool somewhere
#NOTE fails on negative NaN
#ForwardOrdering of various types
serialize(::ForwardOrdering, x::Unsigned) = x
deserialize(::Type{T}, ::ForwardOrdering, u::Unsigned) where T <: Unsigned = u

serialize(::ForwardOrdering, x::Signed) = unsigned(xor(x, typemin(x))) #TODO compat julia 0.4
deserialize(::Type{T}, ::ForwardOrdering, u::Unsigned) where T <: Signed = xor(signed(u), typemin(T))

#TODO support Float16 (double check that tests pass on NaN)
for (float, int) in ((Float16, Int16), (Float32, Int32), (Float64, Int64))
    #NOTE we could change ForwardOrdering => Union{Base.Sort.Float.Left, ForwardOrdering}
    # which would be consistant,
    # but we should never both serialize and use Base.Sort.Float.fpsort!
    @eval function serialize(::ForwardOrdering, x::$float)
        y = reinterpret($int, x) #TODO this is not reversible
        unsigned(y < 0 ? ~y : xor(y, typemin(y))) - ~reinterpret(unsigned($int), $float(-Inf))
    end
    @eval function deserialize(T::Type{$float}, ::ForwardOrdering, u::unsigned($int))
        y = reinterpret($int, u + ~reinterpret(unsigned($int), $float(-Inf)))
        reinterpret(T, y < 0 ? xor(y, typemin(y)) : ~y)
    end

    #=TODO in Base/sort.jl
    - struct Right <: Ordering end
    - right(::DirectOrdering) = Right()
    + right(::DirectOrdering) = Reverse(Left())
    - lt(::Right, x::T, y::T) where {T<:Floats} = slt_int(x, y)
    =#
end

#Extend to other orderings
serialize(rev::ReverseOrdering, x) = ~serialize(rev.fwd, x)
deserialize(T::Type, rev::ReverseOrdering, u::Unsigned) = deserialize(T, rev.fwd, ~u)

#TODO maybe include
#serialize(::ReverseOrdering{ForwardOrdering}, x::Real) = ~serialize(Forward, x) # maybe unnecessary; needs benchmark

serialize(o::By,   x     ) = serialize(o.order, o.by(x))
# deserailizing a By Ordering requires inverting the by funcion. A user can implement
# deserialization on specific By Orderings like this:
function deserialize(T::Type, o::By{F, O}, u::Unsigned) where {F <: typeof(identity), O <: Ordering}
    deserialize(T, o.order, u)
end

# Perm orderings break ties with index. In general this is hard to serialize.
#serialize(o::Perm, i::Int) = serialize(o.order, o.data[i])