// We follow the 'batch' method of the above paper. In this method,
// incoming items are buffered in a priority queue, called 'buffer' here,
// and once insert_threshold items are stored in the buffer it is drained
// into the 'samples' collection. Insertion will cause some extranious
// points to be held that can be merged. Once compress_threshold threshold
// items are buffered the COMPRESS operation merges these extranious points.

// We aim for the full biased quantiles method. The paper this
// implementation is based on includes a 'targeted' method but the authors
// have granted that it is flawed in private communication. As such, all
// queries for all quantiles will have the same error factor.

// This is the S(n) of the above paper. Entries are stored here and
// occasionally merged. The outlined implementation uses a linked list but
// we prefer a Vec for reasons of cache locality at the cost of worse
// computational complexity.

#[allow(non_upper_case_globals, unused_attributes, unused_qualifications)]
const _IMPL_DESERIALIZE_FOR_Entry: () =
    {
        extern crate serde as _serde;
        #[automatically_derived]
        impl <T: Copy> _serde::de::Deserialize for Entry<T> where
         T: _serde::de::Deserialize {
            fn deserialize<__D>(deserializer: &mut __D)
             -> ::std::result::Result<Entry<T>, __D::Error> where
             __D: _serde::de::Deserializer {
                #[allow(non_camel_case_types)]
                enum __Field { __field0, __field1, __field2, __ignore, }
                impl _serde::de::Deserialize for __Field {
                    #[inline]
                    fn deserialize<__D>(deserializer: &mut __D)
                     -> ::std::result::Result<__Field, __D::Error> where
                     __D: _serde::de::Deserializer {
                        struct __FieldVisitor;
                        impl _serde::de::Visitor for __FieldVisitor {
                            type
                            Value
                            =
                            __Field;
                            fn visit_usize<__E>(&mut self, value: usize)
                             -> ::std::result::Result<__Field, __E> where
                             __E: _serde::de::Error {
                                match value {
                                    0usize => { Ok(__Field::__field0) }
                                    1usize => { Ok(__Field::__field1) }
                                    2usize => { Ok(__Field::__field2) }
                                    _ => Ok(__Field::__ignore),
                                }
                            }
                            fn visit_str<__E>(&mut self, value: &str)
                             -> ::std::result::Result<__Field, __E> where
                             __E: _serde::de::Error {
                                match value {
                                    "v" => { Ok(__Field::__field0) }
                                    "g" => { Ok(__Field::__field1) }
                                    "delta" => { Ok(__Field::__field2) }
                                    _ => Ok(__Field::__ignore),
                                }
                            }
                            fn visit_bytes<__E>(&mut self, value: &[u8])
                             -> ::std::result::Result<__Field, __E> where
                             __E: _serde::de::Error {
                                match value {
                                    b"v" => { Ok(__Field::__field0) }
                                    b"g" => { Ok(__Field::__field1) }
                                    b"delta" => { Ok(__Field::__field2) }
                                    _ => Ok(__Field::__ignore),
                                }
                            }
                        }
                        deserializer.deserialize_struct_field(__FieldVisitor)
                    }
                }
                struct __Visitor<T: Copy>(::std::marker::PhantomData<T>) where
                       T: _serde::de::Deserialize;
                impl <T: Copy> _serde::de::Visitor for __Visitor<T> where
                 T: _serde::de::Deserialize {
                    type
                    Value
                    =
                    Entry<T>;
                    #[inline]
                    fn visit_seq<__V>(&mut self, mut visitor: __V)
                     -> ::std::result::Result<Entry<T>, __V::Error> where
                     __V: _serde::de::SeqVisitor {
                        let __field0 =
                            match try!(visitor . visit :: < T > (  )) {
                                Some(value) => { value }
                                None => {
                                    try!(visitor . end (  ));
                                    return Err(_serde::de::Error::invalid_length(0usize));
                                }
                            };
                        let __field1 =
                            match try!(visitor . visit :: < usize > (  )) {
                                Some(value) => { value }
                                None => {
                                    try!(visitor . end (  ));
                                    return Err(_serde::de::Error::invalid_length(1usize));
                                }
                            };
                        let __field2 =
                            match try!(visitor . visit :: < usize > (  )) {
                                Some(value) => { value }
                                None => {
                                    try!(visitor . end (  ));
                                    return Err(_serde::de::Error::invalid_length(2usize));
                                }
                            };
                        try!(visitor . end (  ));
                        Ok(Entry{v: __field0, g: __field1, delta: __field2,})
                    }
                    #[inline]
                    fn visit_map<__V>(&mut self, mut visitor: __V)
                     -> ::std::result::Result<Entry<T>, __V::Error> where
                     __V: _serde::de::MapVisitor {
                        let mut __field0: Option<T> = None;
                        let mut __field1: Option<usize> = None;
                        let mut __field2: Option<usize> = None;
                        while let Some(key) =
                                  try!(visitor . visit_key :: < __Field > (
                                       )) {
                            match key {
                                __Field::__field0 => {
                                    if __field0.is_some() {
                                        return Err(<__V::Error as
                                                       _serde::de::Error>::duplicate_field("v"));
                                    }
                                    __field0 =
                                        Some(try!(visitor . visit_value :: < T
                                                  > (  )));
                                }
                                __Field::__field1 => {
                                    if __field1.is_some() {
                                        return Err(<__V::Error as
                                                       _serde::de::Error>::duplicate_field("g"));
                                    }
                                    __field1 =
                                        Some(try!(visitor . visit_value :: <
                                                  usize > (  )));
                                }
                                __Field::__field2 => {
                                    if __field2.is_some() {
                                        return Err(<__V::Error as
                                                       _serde::de::Error>::duplicate_field("delta"));
                                    }
                                    __field2 =
                                        Some(try!(visitor . visit_value :: <
                                                  usize > (  )));
                                }
                                _ => {
                                    let _ =
                                        try!(visitor . visit_value :: < _serde
                                             :: de :: impls :: IgnoredAny > (
                                             ));
                                }
                            }
                        }
                        try!(visitor . end (  ));
                        let __field0 =
                            match __field0 {
                                Some(__field0) => __field0,
                                None => try!(visitor . missing_field ( "v" )),
                            };
                        let __field1 =
                            match __field1 {
                                Some(__field1) => __field1,
                                None => try!(visitor . missing_field ( "g" )),
                            };
                        let __field2 =
                            match __field2 {
                                Some(__field2) => __field2,
                                None =>
                                try!(visitor . missing_field ( "delta" )),
                            };
                        Ok(Entry{v: __field0, g: __field1, delta: __field2,})
                    }
                }
                const FIELDS: &'static [&'static str] = &["v", "g", "delta"];
                deserializer.deserialize_struct("Entry", FIELDS,
                                                __Visitor::<T>(::std::marker::PhantomData))
            }
        }
    };
#[allow(non_upper_case_globals, unused_attributes, unused_qualifications)]
const _IMPL_SERIALIZE_FOR_Entry: () =
    {
        extern crate serde as _serde;
        #[automatically_derived]
        impl <T: Copy> _serde::ser::Serialize for Entry<T> where
         T: _serde::ser::Serialize {
            fn serialize<__S>(&self, _serializer: &mut __S)
             -> ::std::result::Result<(), __S::Error> where
             __S: _serde::ser::Serializer {
                let mut __serde_state =
                    try!(_serializer . serialize_struct (
                         "Entry" , 0 + 1 + 1 + 1 ));
                try!(_serializer . serialize_struct_elt (
                     & mut __serde_state , "v" , & self . v ));
                try!(_serializer . serialize_struct_elt (
                     & mut __serde_state , "g" , & self . g ));
                try!(_serializer . serialize_struct_elt (
                     & mut __serde_state , "delta" , & self . delta ));
                _serializer.serialize_struct_end(__serde_state)
            }
        }
    };
#[derive(PartialEq, Clone, Debug)]
struct Entry<T: Copy> {
    v: T,
    g: usize,
    delta: usize,
}
#[allow(non_upper_case_globals, unused_attributes, unused_qualifications)]
const _IMPL_DESERIALIZE_FOR_CKMS: () =
    {
        extern crate serde as _serde;
        #[automatically_derived]
        impl <T: Copy> _serde::de::Deserialize for CKMS<T> where
         T: _serde::de::Deserialize {
            fn deserialize<__D>(deserializer: &mut __D)
             -> ::std::result::Result<CKMS<T>, __D::Error> where
             __D: _serde::de::Deserializer {
                #[allow(non_camel_case_types)]
                enum __Field {
                    __field0,
                    __field1,
                    __field2,
                    __field3,
                    __field4,
                    __field5,
                    __field6,
                    __ignore,
                }
                impl _serde::de::Deserialize for __Field {
                    #[inline]
                    fn deserialize<__D>(deserializer: &mut __D)
                     -> ::std::result::Result<__Field, __D::Error> where
                     __D: _serde::de::Deserializer {
                        struct __FieldVisitor;
                        impl _serde::de::Visitor for __FieldVisitor {
                            type
                            Value
                            =
                            __Field;
                            fn visit_usize<__E>(&mut self, value: usize)
                             -> ::std::result::Result<__Field, __E> where
                             __E: _serde::de::Error {
                                match value {
                                    0usize => { Ok(__Field::__field0) }
                                    1usize => { Ok(__Field::__field1) }
                                    2usize => { Ok(__Field::__field2) }
                                    3usize => { Ok(__Field::__field3) }
                                    4usize => { Ok(__Field::__field4) }
                                    5usize => { Ok(__Field::__field5) }
                                    6usize => { Ok(__Field::__field6) }
                                    _ => Ok(__Field::__ignore),
                                }
                            }
                            fn visit_str<__E>(&mut self, value: &str)
                             -> ::std::result::Result<__Field, __E> where
                             __E: _serde::de::Error {
                                match value {
                                    "n" => { Ok(__Field::__field0) }
                                    "insert_threshold" => {
                                        Ok(__Field::__field1)
                                    }
                                    "inserts" => { Ok(__Field::__field2) }
                                    "error" => { Ok(__Field::__field3) }
                                    "samples" => { Ok(__Field::__field4) }
                                    "sum" => { Ok(__Field::__field5) }
                                    "last_in" => { Ok(__Field::__field6) }
                                    _ => Ok(__Field::__ignore),
                                }
                            }
                            fn visit_bytes<__E>(&mut self, value: &[u8])
                             -> ::std::result::Result<__Field, __E> where
                             __E: _serde::de::Error {
                                match value {
                                    b"n" => { Ok(__Field::__field0) }
                                    b"insert_threshold" => {
                                        Ok(__Field::__field1)
                                    }
                                    b"inserts" => { Ok(__Field::__field2) }
                                    b"error" => { Ok(__Field::__field3) }
                                    b"samples" => { Ok(__Field::__field4) }
                                    b"sum" => { Ok(__Field::__field5) }
                                    b"last_in" => { Ok(__Field::__field6) }
                                    _ => Ok(__Field::__ignore),
                                }
                            }
                        }
                        deserializer.deserialize_struct_field(__FieldVisitor)
                    }
                }
                struct __Visitor<T: Copy>(::std::marker::PhantomData<T>) where
                       T: _serde::de::Deserialize;
                impl <T: Copy> _serde::de::Visitor for __Visitor<T> where
                 T: _serde::de::Deserialize {
                    type
                    Value
                    =
                    CKMS<T>;
                    #[inline]
                    fn visit_seq<__V>(&mut self, mut visitor: __V)
                     -> ::std::result::Result<CKMS<T>, __V::Error> where
                     __V: _serde::de::SeqVisitor {
                        let __field0 =
                            match try!(visitor . visit :: < usize > (  )) {
                                Some(value) => { value }
                                None => {
                                    try!(visitor . end (  ));
                                    return Err(_serde::de::Error::invalid_length(0usize));
                                }
                            };
                        let __field1 =
                            match try!(visitor . visit :: < usize > (  )) {
                                Some(value) => { value }
                                None => {
                                    try!(visitor . end (  ));
                                    return Err(_serde::de::Error::invalid_length(1usize));
                                }
                            };
                        let __field2 =
                            match try!(visitor . visit :: < usize > (  )) {
                                Some(value) => { value }
                                None => {
                                    try!(visitor . end (  ));
                                    return Err(_serde::de::Error::invalid_length(2usize));
                                }
                            };
                        let __field3 =
                            match try!(visitor . visit :: < f64 > (  )) {
                                Some(value) => { value }
                                None => {
                                    try!(visitor . end (  ));
                                    return Err(_serde::de::Error::invalid_length(3usize));
                                }
                            };
                        let __field4 =
                            match try!(visitor . visit :: < Vec < Entry < T >
                                       > > (  )) {
                                Some(value) => { value }
                                None => {
                                    try!(visitor . end (  ));
                                    return Err(_serde::de::Error::invalid_length(4usize));
                                }
                            };
                        let __field5 =
                            match try!(visitor . visit :: < Option < T > > (
                                       )) {
                                Some(value) => { value }
                                None => {
                                    try!(visitor . end (  ));
                                    return Err(_serde::de::Error::invalid_length(5usize));
                                }
                            };
                        let __field6 =
                            match try!(visitor . visit :: < Option < T > > (
                                       )) {
                                Some(value) => { value }
                                None => {
                                    try!(visitor . end (  ));
                                    return Err(_serde::de::Error::invalid_length(6usize));
                                }
                            };
                        try!(visitor . end (  ));
                        Ok(CKMS{n: __field0,
                                insert_threshold: __field1,
                                inserts: __field2,
                                error: __field3,
                                samples: __field4,
                                sum: __field5,
                                last_in: __field6,})
                    }
                    #[inline]
                    fn visit_map<__V>(&mut self, mut visitor: __V)
                     -> ::std::result::Result<CKMS<T>, __V::Error> where
                     __V: _serde::de::MapVisitor {
                        let mut __field0: Option<usize> = None;
                        let mut __field1: Option<usize> = None;
                        let mut __field2: Option<usize> = None;
                        let mut __field3: Option<f64> = None;
                        let mut __field4: Option<Vec<Entry<T>>> = None;
                        let mut __field5: Option<Option<T>> = None;
                        let mut __field6: Option<Option<T>> = None;
                        while let Some(key) =
                                  try!(visitor . visit_key :: < __Field > (
                                       )) {
                            match key {
                                __Field::__field0 => {
                                    if __field0.is_some() {
                                        return Err(<__V::Error as
                                                       _serde::de::Error>::duplicate_field("n"));
                                    }
                                    __field0 =
                                        Some(try!(visitor . visit_value :: <
                                                  usize > (  )));
                                }
                                __Field::__field1 => {
                                    if __field1.is_some() {
                                        return Err(<__V::Error as
                                                       _serde::de::Error>::duplicate_field("insert_threshold"));
                                    }
                                    __field1 =
                                        Some(try!(visitor . visit_value :: <
                                                  usize > (  )));
                                }
                                __Field::__field2 => {
                                    if __field2.is_some() {
                                        return Err(<__V::Error as
                                                       _serde::de::Error>::duplicate_field("inserts"));
                                    }
                                    __field2 =
                                        Some(try!(visitor . visit_value :: <
                                                  usize > (  )));
                                }
                                __Field::__field3 => {
                                    if __field3.is_some() {
                                        return Err(<__V::Error as
                                                       _serde::de::Error>::duplicate_field("error"));
                                    }
                                    __field3 =
                                        Some(try!(visitor . visit_value :: <
                                                  f64 > (  )));
                                }
                                __Field::__field4 => {
                                    if __field4.is_some() {
                                        return Err(<__V::Error as
                                                       _serde::de::Error>::duplicate_field("samples"));
                                    }
                                    __field4 =
                                        Some(try!(visitor . visit_value :: <
                                                  Vec < Entry < T > > > (
                                                  )));
                                }
                                __Field::__field5 => {
                                    if __field5.is_some() {
                                        return Err(<__V::Error as
                                                       _serde::de::Error>::duplicate_field("sum"));
                                    }
                                    __field5 =
                                        Some(try!(visitor . visit_value :: <
                                                  Option < T > > (  )));
                                }
                                __Field::__field6 => {
                                    if __field6.is_some() {
                                        return Err(<__V::Error as
                                                       _serde::de::Error>::duplicate_field("last_in"));
                                    }
                                    __field6 =
                                        Some(try!(visitor . visit_value :: <
                                                  Option < T > > (  )));
                                }
                                _ => {
                                    let _ =
                                        try!(visitor . visit_value :: < _serde
                                             :: de :: impls :: IgnoredAny > (
                                             ));
                                }
                            }
                        }
                        try!(visitor . end (  ));
                        let __field0 =
                            match __field0 {
                                Some(__field0) => __field0,
                                None => try!(visitor . missing_field ( "n" )),
                            };
                        let __field1 =
                            match __field1 {
                                Some(__field1) => __field1,
                                None =>
                                try!(visitor . missing_field (
                                     "insert_threshold" )),
                            };
                        let __field2 =
                            match __field2 {
                                Some(__field2) => __field2,
                                None =>
                                try!(visitor . missing_field ( "inserts" )),
                            };
                        let __field3 =
                            match __field3 {
                                Some(__field3) => __field3,
                                None =>
                                try!(visitor . missing_field ( "error" )),
                            };
                        let __field4 =
                            match __field4 {
                                Some(__field4) => __field4,
                                None =>
                                try!(visitor . missing_field ( "samples" )),
                            };
                        let __field5 =
                            match __field5 {
                                Some(__field5) => __field5,
                                None =>
                                try!(visitor . missing_field ( "sum" )),
                            };
                        let __field6 =
                            match __field6 {
                                Some(__field6) => __field6,
                                None =>
                                try!(visitor . missing_field ( "last_in" )),
                            };
                        Ok(CKMS{n: __field0,
                                insert_threshold: __field1,
                                inserts: __field2,
                                error: __field3,
                                samples: __field4,
                                sum: __field5,
                                last_in: __field6,})
                    }
                }
                const FIELDS: &'static [&'static str] =
                    &["n", "insert_threshold", "inserts", "error", "samples",
                      "sum", "last_in"];
                deserializer.deserialize_struct("CKMS", FIELDS,
                                                __Visitor::<T>(::std::marker::PhantomData))
            }
        }
    };
#[allow(non_upper_case_globals, unused_attributes, unused_qualifications)]
const _IMPL_SERIALIZE_FOR_CKMS: () =
    {
        extern crate serde as _serde;
        #[automatically_derived]
        impl <T: Copy> _serde::ser::Serialize for CKMS<T> where
         T: _serde::ser::Serialize {
            fn serialize<__S>(&self, _serializer: &mut __S)
             -> ::std::result::Result<(), __S::Error> where
             __S: _serde::ser::Serializer {
                let mut __serde_state =
                    try!(_serializer . serialize_struct (
                         "CKMS" , 0 + 1 + 1 + 1 + 1 + 1 + 1 + 1 ));
                try!(_serializer . serialize_struct_elt (
                     & mut __serde_state , "n" , & self . n ));
                try!(_serializer . serialize_struct_elt (
                     & mut __serde_state , "insert_threshold" , & self .
                     insert_threshold ));
                try!(_serializer . serialize_struct_elt (
                     & mut __serde_state , "inserts" , & self . inserts ));
                try!(_serializer . serialize_struct_elt (
                     & mut __serde_state , "error" , & self . error ));
                try!(_serializer . serialize_struct_elt (
                     & mut __serde_state , "samples" , & self . samples ));
                try!(_serializer . serialize_struct_elt (
                     & mut __serde_state , "sum" , & self . sum ));
                try!(_serializer . serialize_struct_elt (
                     & mut __serde_state , "last_in" , & self . last_in ));
                _serializer.serialize_struct_end(__serde_state)
            }
        }
    };
/// A structure to provide approximate quantiles queries in bounded memory and
/// with bounded error.
#[derive(Debug, PartialEq, Clone)]
pub struct CKMS<T: Copy> {
    n: usize,
    insert_threshold: usize,
    inserts: usize,
    error: f64,
    samples: Vec<Entry<T>>,
    sum: Option<T>,
    last_in: Option<T>,
}