func (q *Deque) next(i int) int {
	return (i + 1) & (len(q.buf) - 1)  
}
next returns the next buffer position wrapping around buffer.
package deque
const minCapacity = 16
type Deque struct {
	buf   []interface{}
	head  int
	tail  int
	count int
}
func (q *Deque) Len() int {
	return q.count
}
func (q *Deque) PushBack(elem interface{}) {
	q.growIfFull()
	q.buf[q.tail] = elem
	q.tail = q.next(q.tail)
	q.count++
}
func (q *Deque) PushFront(elem interface{}) {
	q.growIfFull()
	q.head = q.prev(q.head)
	q.buf[q.head] = elem
	q.count++
}
func (q *Deque) PopFront() interface{} {
	if q.count <= 0 {
		panic("deque: PopFront() called on empty queue")
	}
	ret := q.buf[q.head]
	q.buf[q.head] = nil
	q.head = q.next(q.head)
	q.count--
	q.shrinkIfExcess()
	return ret
}
func (q *Deque) PopBack() interface{} {
	if q.count <= 0 {
		panic("deque: PopBack() called on empty queue")
	}
	q.tail = q.prev(q.tail)
	ret := q.buf[q.tail]
	q.buf[q.tail] = nil
	q.count--
	q.shrinkIfExcess()
	return ret
}
func (q *Deque) Front() interface{} {
	if q.count <= 0 {
		panic("deque: Front() called when empty")
	}
	return q.buf[q.head]
}
func (q *Deque) Back() interface{} {
	if q.count <= 0 {
		panic("deque: Back() called when empty")
	}
	return q.buf[q.prev(q.tail)]
}
func (q *Deque) At(i int) interface{} {
	if i < 0 || i >= q.count {
		panic("deque: At() called with index out of range")
	}
	return q.buf[(q.head+i)&(len(q.buf)-1)]
}
func (q *Deque) Clear() {
	modBits := len(q.buf) - 1
	for h := q.head; h != q.tail; h = (h + 1) & modBits {
		q.buf[h] = nil
	}
	q.head = 0
	q.tail = 0
	q.count = 0
}
func (q *Deque) Rotate(n int) {
	if q.count <= 1 {
		return
	}
	n %= q.count
	if n == 0 {
		return
	}
	modBits := len(q.buf) - 1
	if q.head == q.tail {
		q.head = (q.head + n) & modBits
		q.tail = (q.tail + n) & modBits
		return
	}
	if n < 0 {
		for ; n < 0; n++ {
			q.head = (q.head - 1) & modBits
			q.tail = (q.tail - 1) & modBits
			q.buf[q.head] = q.buf[q.tail]
			q.buf[q.tail] = nil
		}
		return
	}
	for ; n > 0; n-- {
		q.buf[q.tail] = q.buf[q.head]
		q.buf[q.head] = nil
		q.head = (q.head + 1) & modBits
		q.tail = (q.tail + 1) & modBits
	}
}
func (q *Deque) prev(i int) int {
	return (i - 1) & (len(q.buf) - 1)  
}