use crate::io;
use crate::io::Cursor;
use alloc::vec::Vec;
use bitcoin::consensus::Encodable;
use bitcoin::hashes::Hash;
use bitcoin::util::bip158::{Error as FilterError, GCSFilterReader, GCSFilterWriter};
use bitcoin::{Block, BlockHash, FilterHash, FilterHeader, OutPoint};

/// Golomb encoding parameter as in BIP-158, see also https://gist.github.com/sipa/576d5f09c3b86c3b1b75598d799fc845
const P: u8 = 19;
const M: u64 = 784931;

/// A computed or read block filter for spent outpoints in a block
#[derive(Clone)]
pub struct BlockSpendFilter {
    /// Golomb encoded filter
    pub content: Vec<u8>,
}

impl BlockSpendFilter {
    /// Compute this filter's id in a chain of filters
    pub fn filter_header(&self, previous_filter_header: &FilterHeader) -> FilterHeader {
        let filter_hash = FilterHash::hash(self.content.as_slice());
        filter_hash.filter_header(previous_filter_header)
    }

    /// Compute the filter hash
    pub fn filter_hash(&self) -> FilterHash {
        FilterHash::hash(self.content.as_slice())
    }

    /// create a new filter from pre-computed data
    pub fn new(content: &[u8]) -> BlockSpendFilter {
        BlockSpendFilter {
            content: content.to_vec(),
        }
    }

    /// Create a new filter from a block
    pub fn from_block(block: &Block) -> BlockSpendFilter {
        let mut out = Vec::new();
        {
            let mut writer = BlockFilterWriter::new(&mut out, block);
            writer.add_spent_outpoints();
            writer.finish().expect("writing to a Vec cannot fail");
        }
        BlockSpendFilter { content: out }
    }

    /// match any query pattern
    pub fn match_any(
        &self,
        block_hash: &BlockHash,
        query: &mut dyn Iterator<Item = &OutPoint>,
    ) -> bool {
        let encoded: Vec<_> = query.map(|o| encode_point(&o)).collect();
        let filter_reader = BlockFilterReader::new(block_hash);
        filter_reader
            .match_any(
                &mut Cursor::new(self.content.as_slice()),
                &mut encoded.iter().map(|x| x.as_slice()),
            )
            .expect("reading from a Vec cannot fail")
    }

    /// match all query pattern
    pub fn match_all(
        &self,
        block_hash: &BlockHash,
        query: &mut dyn Iterator<Item = &OutPoint>,
    ) -> bool {
        let encoded: Vec<_> = query.map(|o| encode_point(&o)).collect();
        let filter_reader = BlockFilterReader::new(block_hash);
        filter_reader
            .match_all(
                &mut Cursor::new(self.content.as_slice()),
                &mut encoded.iter().map(|x| x.as_slice()),
            )
            .expect("reading from a Vec cannot fail")
    }
}

fn hash_to_k0_k1(hash: &[u8; 32]) -> (u64, u64) {
    let mut k0_slice = [0; 8];
    k0_slice.copy_from_slice(&hash[0..8]);
    let mut k1_slice = [0; 8];
    k1_slice.copy_from_slice(&hash[8..16]);
    let k0 = u64::from_le_bytes(k0_slice);
    let k1 = u64::from_le_bytes(k1_slice);
    (k0, k1)
}

/// Compiles and writes a block filter
pub struct BlockFilterWriter<'a> {
    block: &'a Block,
    writer: GCSFilterWriter<'a>,
}

impl<'a> BlockFilterWriter<'a> {
    /// Create a block filter writer
    pub fn new(writer: &'a mut dyn io::Write, block: &'a Block) -> BlockFilterWriter<'a> {
        let hash = block.block_hash().into_inner();
        let (k0, k1) = hash_to_k0_k1(&hash);
        let writer = GCSFilterWriter::new(writer, k0, k1, M, P);
        BlockFilterWriter { block, writer }
    }

    /// Add spend outpoints to the filter
    pub fn add_spent_outpoints(&mut self) {
        for transaction in &self.block.txdata {
            for txin in &transaction.input {
                let buf = encode_point(&txin.previous_output);
                self.add_element(&buf);
            }
        }
    }

    /// Add arbitrary element to a filter
    pub fn add_element(&mut self, data: &[u8]) {
        self.writer.add_element(data);
    }

    /// Write block filter
    pub fn finish(&mut self) -> Result<usize, io::Error> {
        self.writer.finish()
    }
}

/// Reads and interpret a block filter
pub struct BlockFilterReader {
    reader: GCSFilterReader,
}

impl BlockFilterReader {
    /// Create a block filter reader
    pub fn new(block_hash: &BlockHash) -> BlockFilterReader {
        let hash = block_hash.into_inner();
        let (k0, k1) = hash_to_k0_k1(&hash);
        BlockFilterReader {
            reader: GCSFilterReader::new(k0, k1, M, P),
        }
    }

    /// match any query pattern
    pub fn match_any(
        &self,
        reader: &mut dyn io::Read,
        query: &mut dyn Iterator<Item = &[u8]>,
    ) -> Result<bool, FilterError> {
        self.reader.match_any(reader, query)
    }

    /// match all query pattern
    pub fn match_all(
        &self,
        reader: &mut dyn io::Read,
        query: &mut dyn Iterator<Item = &[u8]>,
    ) -> Result<bool, FilterError> {
        self.reader.match_all(reader, query)
    }
}

fn encode_point(point: &OutPoint) -> Vec<u8> {
    let mut buf = Vec::new();
    point.consensus_encode(&mut buf).unwrap();
    buf
}

#[cfg(test)]
mod tests {
    use crate::filter::BlockSpendFilter;
    use bitcoin::hashes::Hash;
    use bitcoin::{
        Block, BlockHash, BlockHeader, OutPoint, PackedLockTime, Transaction, TxIn, TxMerkleNode,
        Txid,
    };

    #[test]
    fn filter_test() {
        let mut txs = Vec::new();
        for i in 0..4000 {
            let tx = Transaction {
                version: 0,
                lock_time: PackedLockTime(0),
                input: vec![TxIn {
                    previous_output: OutPoint {
                        txid: Txid::all_zeros(),
                        vout: i,
                    },
                    script_sig: Default::default(),
                    sequence: Default::default(),
                    witness: Default::default(),
                }],
                output: vec![],
            };
            txs.push(tx);
        }
        let block = Block {
            header: BlockHeader {
                version: 0,
                prev_blockhash: BlockHash::all_zeros(),
                merkle_root: TxMerkleNode::all_zeros(),
                time: 0,
                bits: 0,
                nonce: 0,
            },
            txdata: txs,
        };
        let block_hash = block.block_hash();
        let filter = BlockSpendFilter::from_block(&block);
        assert!(filter.match_any(
            &block_hash,
            &mut vec![
                OutPoint {
                    txid: Txid::all_zeros(),
                    vout: 1234,
                },
                OutPoint {
                    txid: Txid::all_zeros(),
                    vout: 5555,
                }
            ]
            .iter()
        ));

        assert!(!filter.match_all(
            &block_hash,
            &mut vec![
                OutPoint {
                    txid: Txid::all_zeros(),
                    vout: 1234,
                },
                OutPoint {
                    txid: Txid::all_zeros(),
                    vout: 5555,
                }
            ]
            .iter()
        ));

        assert_eq!(filter.content.len(), 10530);

        let txid = Txid::hash(&[1]);

        // the first false positive is at 1212
        for i in 0..100 {
            let points = (0..1000)
                .map(|j| OutPoint {
                    txid,
                    vout: i * 1000 + j,
                })
                .collect::<Vec<_>>();

            if filter.match_any(&block_hash, &mut points.iter()) {
                panic!("false positive at {}", i);
            }
        }
    }
}