furze 0.0.5

use crate::encoder::Encoder;
use crate::error::FstError;
use crate::error::FstResult;
use crate::state::State;
use crate::state::{
    ARCS_AS_FIXED_ARRAY, BIT_FINAL_STATE, BIT_LAST_STATE, BIT_STATE_HAS_FINAL_OUTPUT,
    BIT_STATE_HAS_OUPPUT, BIT_STOP_NODE, BIT_TAGET_NEXT,
};
use byteorder::BigEndian;
use byteorder::ReadBytesExt;
use std::io::{Error as IOError, Result};
use varintrs::{Binary, ReadBytesVarExt};
const DROP_MSB: u8 = 0b0111_1111;
const MSB: u8 = 0b1000_0000;

#[macro_export]
macro_rules! copy {
    ($des:expr, $src:expr) => {
        copy_slice($des, $src)
    };
}

fn copy_slice<T: Copy>(des: &mut [T], src: &[T]) -> usize {
    let l = if des.len() < src.len() {
        des.len()
    } else {
        src.len()
    };
    unsafe {
        std::ptr::copy_nonoverlapping(src.as_ptr(), des.as_mut_ptr(), l);
    }
    l
}

struct ReverseReader<T: AsRef<[u8]>> {
    i: usize,
    data: T,
}

impl<T: AsRef<[u8]>> ReverseReader<T> {
    fn new(data: T) -> ReverseReader<T> {
        Self {
            i: (data.as_ref().len() - 1),
            data: data,
        }
    }

    fn reset(&mut self) {
        self.i = self.data.as_ref().len() - 1;
    }

    fn set_position(&mut self, postion: usize) {
        self.i = postion
    }

    fn skip_bytes(&mut self, skip: usize) {
        self.i = self.i - skip;
    }

    fn get_bytes(&self, start: usize, end: usize) -> &[u8] {
        &self.data.as_ref()[start..end]
    }

    fn read_byte(&mut self) -> Result<u8> {
        if self.i == 0 {
            return Err(IOError::from(std::io::ErrorKind::UnexpectedEof));
        }
        let b = self.data.as_ref()[self.i];
        self.i -= 1;
        Ok(b)
    }

    fn get_position(&self) -> usize {
        self.i
    }
}

use std::io::Read;

impl<T: AsRef<[u8]>> Read for ReverseReader<T> {
    fn read(&mut self, buf: &mut [u8]) -> Result<usize> {
        if self.i == 0 {
            return Err(IOError::from(std::io::ErrorKind::UnexpectedEof));
        }
        for x in buf.iter_mut() {
            *x = self.read_byte()?;
        }
        Ok(buf.len())
    }
}

pub(crate) struct Decoder<T: AsRef<[u8]>> {
    reader: ReverseReader<T>,
}

impl<T: AsRef<[u8]>> Decoder<T> {
    pub fn new(data: T) -> Decoder<T> {
        Self {
            reader: ReverseReader::new(data),
        }
    }

    pub(crate) fn reset(&mut self) {
        self.reader.reset()
    }

    fn near_next(&mut self, key: &[u8], state: &mut State) -> FstResult<u64> {
        let mut frist_k = 0;
        if key.len() > 0 {
            frist_k = key[0];
        }
        let mut out: u64 = 0;
        let mut greater: bool = false;
        loop {
            let frist_res = self.loop_state(frist_k, state);
            let position = self.reader.get_position();
            match frist_res {
                Err(e) => match e {
                    FstError::Greater => {
                        greater = true;
                    }
                    _ => {
                        return Err(FstError::NotFound);
                    }
                },
                Ok(()) => {}
            }
            out += state.out;
            if greater {
                loop {
                    if state.is_final {
                        break;
                    }
                    self.read_first_state(state)?;
                    out += state.out;
                }
                out += state.final_out;
            } else {
                let res = self.near_next(&key[1..], state);
                match res {
                    Ok(_out) => {
                        out += _out;
                    }
                    Err(e) => {
                        if !state.is_last {
                            self.reader.set_position(position);
                            state.reset();
                            continue;
                        }
                        return Err(FstError::NotFound);
                    }
                }
            }
            break;
        }

        Ok(out)
    }

    pub(crate) fn near(&mut self, key: &[u8]) -> FstResult<u64> {
        let mut state = State::new(0, 0);
        state.target = self.reader.get_position() as u64;
        self.near_next(key, &mut state)
    }

    pub(crate) fn get_prefix(&mut self, key: &[u8]) -> FstResult<u64> {
        let mut state = State::new(0, 0);
        state.target = self.reader.get_position() as u64;
        let mut out: u64 = 0;
        let mut f = false;
        // let mut last_k: u8 = 0;
        for _k in key.iter() {
            if let Ok(()) = self.find_target_state(*_k, &mut state) {
                out += state.out;
                f = true;
            } else {
                f = false;
                //  last_k = *_k;
                break;
            }
        }
        if !state.is_final {
            return Err(FstError::NotFound);
        }
        if !f && state.is_last {
            return Err(FstError::NotFound);
        }
        //已经遍历所有相同前缀 然后变量下一个词的时候，已经顺序遍历完最后一个字符，并且没有找到匹配

        out += state.final_out;
        Ok(out)
    }

    pub(crate) fn get(&mut self, key: &[u8]) -> FstResult<u64> {
        let mut state = State::new(0, 0);
        state.target = self.reader.get_position() as u64;
        let mut out: u64 = 0;
        for _k in key.iter() {
            self.find_target_state(*_k, &mut state)?;
            out += state.out;
        }
        if !state.is_final {
            return Err(FstError::NotFound);
        }
        out += state.final_out;
        Ok(out)
    }

    // pub(crate) fn near(&mut self, key: &[u8]) -> FstResult<u64> {
    //     let mut state = State::new(0, 0);
    //     self.near_next(key, &mut state)
    // }

    fn find_target_state(&mut self, _in: u8, state: &mut State) -> FstResult<()> {
        if state.target <= 0 {
            return Err(FstError::NotFound);
        }
        self.read_first_state(state)?;
        if state.flag(ARCS_AS_FIXED_ARRAY) {
            // do binary search
            let num_states = state.final_out;
            let mut low = 0;
            let mut high = num_states - 1;
            let start = self.reader.get_position();
            while low <= high {
                let mid = (low + high) >> 1; // (low + high)/2
                self.reader.set_position(start - (mid * 5) as usize);
                let mid_label = self.reader.read_u8()? as i32;
                let cmp = mid_label - _in as i32;
                if cmp < 0 {
                    low = mid + 1;
                } else if cmp > 0 {
                    high = mid - 1;
                } else {
                    let position = self.reader.read_u32::<BigEndian>()? as usize;
                    self.reader.set_position(position);
                    self.read_next_state(state)?;
                    return Ok(());
                }
            }
            return Err(FstError::NotFound);
        }

        loop {
            if state._in == _in {
                return Ok(());
            } else if state._in > _in {
                return Err(FstError::Greater);
            } else if state.is_last {
                return Err(FstError::NotFound);
            } else {
                self.read_next_state(state)?;
            }
        }
    }

    fn loop_state(&mut self, _in: u8, state: &mut State) -> FstResult<()> {
        if state.target <= 0 {
            return Err(FstError::NotFound);
        }
        self.read_first_state(state)?;
        if state.flag(ARCS_AS_FIXED_ARRAY) {
            let num_states = state.final_out as usize;
            self.reader.skip_bytes(num_states * 5);
            self.read_next_state(state)?;
        }
        loop {
            if state._in == _in {
                return Ok(());
            } else if state._in > _in {
                return Err(FstError::Greater);
            } else if state.is_last {
                return Err(FstError::NotFound);
            } else {
                self.read_next_state(state)?;
            }
        }
    }

    fn read_first_state(&mut self, state: &mut State) -> FstResult<()> {
        if state.target > 0 {
            self.reader.set_position(state.target as usize);
        }
        self.read_next_state(state)
    }

    fn read_next_state(&mut self, state: &mut State) -> FstResult<()> {
        state.reset();
        state.flag = self.reader.read_u8()?;
        state._in = self.reader.read_u8()?;
        if state.flag(BIT_STATE_HAS_FINAL_OUTPUT) || state.flag(ARCS_AS_FIXED_ARRAY) {
            let (v, _) = self.reader.read_vu64::<Binary>();
            state.final_out = v;
        }

        if state.flag(BIT_STATE_HAS_OUPPUT) {
            let (v, _) = self.reader.read_vu64::<Binary>();
            state.out = v;
        }
        if state.flag(BIT_STOP_NODE) {
            state.is_stop = true;
        } else {
            if !state.flag(BIT_TAGET_NEXT) && !state.flag(ARCS_AS_FIXED_ARRAY) {
                let (v, _) = self.reader.read_vu64::<Binary>();
                state.target = v;
            }
        }
        if state.flag(BIT_LAST_STATE) {
            state.is_last = true;
        }
        if state.flag(BIT_FINAL_STATE) {
            state.is_final = true;
        }

        Ok(())
    }

    // fn read_byte(&mut self) -> FstResult<u8> {
    //     self.reader.read_byte()
    // }

    // fn read_v_u64(&mut self) -> FstResult<(u64, usize)> {
    //     let mut result: u64 = 0;
    //     let mut shift = 0;
    //     let mut success = false;
    //     loop {
    //         let b = self.read_byte()?;
    //         let msb_dropped = b & DROP_MSB;
    //         result |= (msb_dropped as u64) << shift;
    //         shift += 7;
    //         if b & MSB == 0 || shift > (9 * 7) {
    //             success = b & MSB == 0;
    //             break;
    //         }
    //     }
    //     if success {
    //         Ok((result, shift / 7 as usize))
    //     } else {
    //         Err(FstError::Fail)
    //     }
    // }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_encoder() {}
}