循环缓冲区，或环形缓冲区是一种数据结构，它使用单个固定大小的缓冲区，就好像它是端到端连接一样。

循环缓冲区首先开始为空，并具有一些预定义的长度。例如，这是一个 7 元素的缓冲区:

[ ][ ][ ][ ][ ][ ][ ]

假设 1 被写入缓冲区的中间(其实精确的起始位置在循环缓冲区中无关紧要):

[ ][ ][ ][1][ ][ ][ ]

然后假设添加了另外两个元素 - 2 和 3 - 在 1 之后，附加:

[ ][ ][ ][1][2][3][ ]

如果从缓冲区中，删除了两个元素，则删除缓冲区内最旧的值。在这种情况下，删除的两个元素是 1 和 2，缓冲区只有 3:

[ ][ ][ ][ ][ ][3][ ]

如果缓冲区有 7 个元素，那么它就完全填满了:

[6][7][8][9][3][4][5]

当缓冲区已满时，将引发错误，警告客户端，进一步写入被阻止，直到插槽空闲为止。

当缓冲区已满时，客户端可以选择使用强制写入，覆盖最旧的数据。在这种情况下，添加了另外两个元素 - A 和 B - 它们会覆盖 3 和 4:

[6][7][8][9][A][B][5]

3 和 4 已被 A 和 B 取代，使得 5 现在是缓冲区中最旧的数据。最后，如果删除了两个元素，那么返回的是 5 和 6，和剩余的缓冲区:

[ ][7][8][9][A][B][ ]

因为有可用的空间，但如果客户端再次覆盖存储 C 和 D，那么先前存储 5 和 6 的空间将被使用，而不是 7 和 8 的位置。7 仍然是最旧的元素，缓冲区又是充分.

[D][7][8][9][A][B][C]

维基百科http://en.wikipedia.org/wiki/Circular_Buffer

use std::marker::PhantomData;

pub struct CircularBuffer<T> {
   // This field is here to make the template compile and not to
   // complain about unused type parameter 'T'. Once you start
   // solving the exercise, delete this field and the 'std::marker::PhantomData'
   // import.
   field: PhantomData<T>,
}

#[derive(Debug, PartialEq)]
pub enum Error {
   EmptyBuffer,
   FullBuffer,
}

impl<T> CircularBuffer<T> {
   pub fn new(capacity: usize) -> Self {
       unimplemented!(
           "Construct a new CircularBuffer with the capacity to hold {}.",
           match capacity {
               1 => format!("1 element"),
               _ => format!("{} elements", capacity),
           }
       );
   }

   pub fn write(&mut self, _element: T) -> Result<(), Error> {
       unimplemented!("Write the passed element to the CircularBuffer or return FullBuffer error if CircularBuffer is full.");
   }

   pub fn read(&mut self) -> Result<T, Error> {
       unimplemented!("Read the oldest element from the CircularBuffer or return EmptyBuffer error if CircularBuffer is empty.");
   }

   pub fn clear(&mut self) {
       unimplemented!("Clear the CircularBuffer.");
   }

   pub fn overwrite(&mut self, _element: T) {
       unimplemented!("Write the passed element to the CircularBuffer, overwriting the existing elements if CircularBuffer is full.");
   }
}

# #![allow(unused_variables)]
#fn main() {
#[test]
fn error_on_read_empty_buffer() {
   let mut buffer = CircularBuffer::<char>::new(1);
   assert_eq!(Err(Error::EmptyBuffer), buffer.read());
}

#[test]
//#[ignore]
fn write_and_read_back_item() {
   let mut buffer = CircularBuffer::new(1);
   assert!(buffer.write('1').is_ok());
   assert_eq!(Ok('1'), buffer.read());
   assert_eq!(Err(Error::EmptyBuffer), buffer.read());
}

#[test]
//#[ignore]
fn write_and_read_back_multiple_items() {
   let mut buffer = CircularBuffer::new(2);
   assert!(buffer.write('1').is_ok());
   assert!(buffer.write('2').is_ok());
   assert_eq!(Ok('1'), buffer.read());
   assert_eq!(Ok('2'), buffer.read());
   assert_eq!(Err(Error::EmptyBuffer), buffer.read());
}

#[test]
//#[ignore]
fn alternate_write_and_read() {
   let mut buffer = CircularBuffer::new(2);
   assert!(buffer.write('1').is_ok());
   assert_eq!(Ok('1'), buffer.read());
   assert!(buffer.write('2').is_ok());
   assert_eq!(Ok('2'), buffer.read());
}

#[test]
//#[ignore]
fn clear_buffer() {
   let mut buffer = CircularBuffer::new(3);
   assert!(buffer.write('1').is_ok());
   assert!(buffer.write('2').is_ok());
   assert!(buffer.write('3').is_ok());
   buffer.clear();
   assert_eq!(Err(Error::EmptyBuffer), buffer.read());
   assert!(buffer.write('1').is_ok());
   assert!(buffer.write('2').is_ok());
   assert_eq!(Ok('1'), buffer.read());
   assert!(buffer.write('3').is_ok());
   assert_eq!(Ok('2'), buffer.read());
}

#[test]
//#[ignore]
fn full_buffer_error() {
   let mut buffer = CircularBuffer::new(2);
   assert!(buffer.write('1').is_ok());
   assert!(buffer.write('2').is_ok());
   assert_eq!(Err(Error::FullBuffer), buffer.write('3'));
}

#[test]
//#[ignore]
fn overwrite_item_in_non_full_buffer() {
   let mut buffer = CircularBuffer::new(2);
   assert!(buffer.write('1').is_ok());
   buffer.overwrite('2');
   assert_eq!(Ok('1'), buffer.read());
   assert_eq!(Ok('2'), buffer.read());
   assert_eq!(Err(Error::EmptyBuffer), buffer.read());
}

#[test]
//#[ignore]
fn overwrite_item_in_full_buffer() {
   let mut buffer = CircularBuffer::new(2);
   assert!(buffer.write('1').is_ok());
   assert!(buffer.write('2').is_ok());
   buffer.overwrite('A');
   assert_eq!(Ok('2'), buffer.read());
   assert_eq!(Ok('A'), buffer.read());
}

#[test]
//#[ignore]
fn integer_buffer() {
   let mut buffer = CircularBuffer::new(2);
   assert!(buffer.write(1).is_ok());
   assert!(buffer.write(2).is_ok());
   assert_eq!(Ok(1), buffer.read());
   assert!(buffer.write(-1).is_ok());
   assert_eq!(Ok(2), buffer.read());
   assert_eq!(Ok(-1), buffer.read());
   assert_eq!(Err(Error::EmptyBuffer), buffer.read());
}

#[test]
//#[ignore]
fn string_buffer() {
   let mut buffer = CircularBuffer::new(2);
   buffer.write("".to_string()).unwrap();
   buffer.write("Testing".to_string()).unwrap();
   assert_eq!(0, buffer.read().unwrap().len());
   assert_eq!(Ok("Testing".to_string()), buffer.read());
}

#}

# #![allow(unused_variables)]
#fn main() {
#[derive(Debug, PartialEq)]
pub enum Error {
   EmptyBuffer,
   FullBuffer,
}

pub struct CircularBuffer<T: Default + Clone> {
   buffer: Vec<T>,
   size: usize,
   start: usize,
   end: usize,
}

impl<T: Default + Clone> CircularBuffer<T> {
   // this circular buffer keeps an unallocated slot between the start and the end
   // when the buffer is full.
   pub fn new(size: usize) -> CircularBuffer<T> {
       CircularBuffer {
           buffer: vec![T::default(); size + 1],
           size: size + 1,
           start: 0,
           end: 0,
       }
   }

   pub fn read(&mut self) -> Result<T, Error> {
       if self.is_empty() {
           return Err(Error::EmptyBuffer);
       }

       let v = self.buffer.get(self.start).unwrap().clone();
       self.advance_start();
       Ok(v)
   }

   pub fn write(&mut self, byte: T) -> Result<(), Error> {
       if self.is_full() {
           return Err(Error::FullBuffer);
       }

       self.buffer[self.end] = byte;
       self.advance_end();
       Ok(())
   }

   pub fn overwrite(&mut self, byte: T) {
       if self.is_full() {
           self.advance_start();
       }

       self.buffer[self.end] = byte;
       self.advance_end();
   }

   pub fn clear(&mut self) {
       self.start = 0;
       self.end = 0;
   }

   pub fn is_empty(&self) -> bool {
       self.start == self.end
   }

   pub fn is_full(&self) -> bool {
       (self.end + 1) % self.size == self.start
   }

   fn advance_start(&mut self) {
       self.start = (self.start + 1) % self.size;
   }

   fn advance_end(&mut self) {
       self.end = (self.end + 1) % self.size;
   }
}

#}