// Package linkedlist implements a doubly-linked list.
package linkedlist
import (
	"fmt"
)
// Node is a double-linked element.
type Node struct {
	Val  interface{}
	prev *Node
	next *Node
}
// List represents a linked list.
type List struct {
	first *Node
	last  *Node
}
// ErrEmptyList is returned when the list is already empty, no item can be removed.
var ErrEmptyList = fmt.Errorf("empty list")
// Next returns the pointer for the next Node.
func (e *Node) Next() *Node {
	return e.next
}
// Prev returns the pointer for the previous Node.
func (e *Node) Prev() *Node {
	return e.prev
}
// First returns the first element in the List.
func (l *List) First() *Node {
	return l.first
}
// Last returns the last element in the List.
func (l *List) Last() *Node {
	return l.last
}
// NewList returns a List with Node values filled up with args.
func NewList(args ...interface{}) *List {
	if len(args) == 0 {
		return &List{nil, nil}
	}
	elements := make([]*Node, len(args))
	for i, item := range args {
		elements[i] = &Node{Val: item}
		if i > 0 {
			elements[i].prev = elements[i-1]
		}
		if i > 0 && i < len(elements) {
			elements[i-1].next = elements[i]
		}
	}
	return &List{first: elements[0], last: elements[len(elements)-1]}
}
// Reverse reverses the List.
func (l *List) Reverse() *List {
	for elem := l.first; elem != nil; elem = elem.prev {
		// next item is elem.prev because the swap within the cycle
		elem.prev, elem.next = elem.next, elem.prev
	}
	l.first, l.last = l.last, l.first
	return l
}
// PushFront inserts an item to the front of the List.
func (l *List) PushFront(item interface{}) *List {
	new := &Node{Val: item, prev: nil, next: l.first}
	// if old first exists: first item will be second, set its previous to new first
	if l.first != nil {
		l.first.prev = new
	}
	// set last item if unset
	if l.last == nil {
		if l.first != nil {
			l.last = l.first
		} else {
			// it was a List{nil, nil}, so new is the first and last item too
			l.last = new
		}
	}
	l.first = new
	return l
}
// PushBack inserts an item to the end of List.
func (l *List) PushBack(item interface{}) *List {
	new := &Node{Val: item, prev: l.last, next: nil}
	// if old last exists: last will be last-1, set its next to new last
	if l.last != nil {
		l.last.next = new
	}
	// set first item if unset
	if l.first == nil {
		if l.last != nil {
			l.first = l.last
		} else {
			l.first = new
		}
	}
	if l.last != nil {
		l.last.next = new
	}
	l.last = new
	return l
}
// PopFront removes first item from List.
func (l *List) PopFront() (interface{}, error) {
	if l.first == nil {
		return nil, ErrEmptyList
	}
	ret := l.first.Val
	if l.first.next != nil {
		l.first.next.prev = nil
	}
	l.first = l.first.next
	if l.first == nil {
		l.last = nil
	}
	return ret, nil
}
// PopBack removes last item from List.
func (l *List) PopBack() (interface{}, error) {
	if l.last == nil {
		return nil, ErrEmptyList
	}
	ret := l.last.Val
	if l.last.prev != nil {
		l.last.prev.next = nil
	}
	l.last = l.last.prev
	if l.last == nil {
		l.first = nil
	}
	return ret, nil
}