"""
-------------------------------------------------------
[function library file name]
[description of functions]
-------------------------------------------------------
Author:  Matthew Fung
ID: 140422730
Email:   fung2730@mylaurier.ca
Version: 2015-02-19
-------------------------------------------------------
"""
import copy


class _DequeNode:

    def __init__(self, value, previous_node, next_node):
        """
        -------------------------------------------------------
        Initializes a deque node.
        Use: node = _DequeNode(value, next_node)
        -------------------------------------------------------
        Preconditions:
          _value - data value for node
          _next - next node
          _previous - previous node
        Postconditions:
          Initializes a deque node that contains a copy of value, a link to the previous node
          and a link to the next node in the deque.
        -------------------------------------------------------
        """
        self._value = copy.deepcopy(value)
        self._previous = previous_node
        self._next = next_node
        return

class Deque:

    def __init__( self ):
        """
        -------------------------------------------------------
        Initializes an empty Deque. Data is stored in a linked list.
        Use: q = Deque()
        -------------------------------------------------------
        Postconditions:
          Initializes an empty Deque.
        -------------------------------------------------------
        """
        self._front = None
        self._rear = None
        self._size = 0
        return

    def __len__(self):
        """
        -------------------------------------------------------
        Returns the size of the Deque.
        Use: n = len( q )
        -------------------------------------------------------
        Postconditions:
          Returns the number of values in the deque.
        -------------------------------------------------------
        """
        return self._size

    def is_empty(self):
        """
        -------------------------------------------------------
        Determines if the deque is empty.
        Use: b = q.is_empty()
        -------------------------------------------------------
        Postconditions:
          Returns True if the deque is empty, False otherwise.
        -------------------------------------------------------
        """
        return self._size == 0

    def insert_front( self, value ):
        """
        -------------------------------------------------------
        Inserts a copy of value into the front of the deque.
        Use: q.insert_front( value )
        -------------------------------------------------------
        Preconditions:
          value - a data element
        Postconditions:
          value is added to the front of the deque.
        -------------------------------------------------------
        """
        node = _DequeNode(value, self._rear, self._front)
        self._front = node
        self._size += 1
        return

    def insert_rear( self, value ):
        """
        -------------------------------------------------------
        Inserts a copy of value into the rear of the deque.
        Use: q.insert_rear( value )
        -------------------------------------------------------
        Preconditions:
          value - a data element
        Postconditions:
          value is added to the rear of the deque.
        -------------------------------------------------------
        """
        node = _DequeNode(value, self._front, self._rear)
        self._rear = node
        self._size += 1
        return

    def remove_front( self ):
        """
        -------------------------------------------------------
        Removes the front of the deque.
        -------------------------------------------------------
        Postconditions:
            Returns the value at the front of deque - the value is
            removed from queue. Returns None if deque is empty.
        -------------------------------------------------------
        """

        if self._front is None:
            value=None
        else:
            value=self._front._value
            self._front=self._front._next

        self._size -= 1

        return value

    def remove_rear( self ):
        """
        -------------------------------------------------------
        Removes the rear of the deque.
        -------------------------------------------------------
        Postconditions:
            Returns the value at the rear of deque - the value is
            removed from deque. Returns None if deque is empty.
        -------------------------------------------------------
        """

        if self._rear is None:
            value=None
        else:
            value=self._front._value
            self._rear=self._rear._previous

        self._size -= 1

        return value

    def peek_front( self ):
        """
        -------------------------------------------------------
        Peeks at the front of deque.
        Use: v = q.peek_front()
        -------------------------------------------------------
        Postconditions:
          Returns a copy of the value at the front of deque -
          the value is not removed from deque. Returns None
          if deque is empty.
        -------------------------------------------------------
        """
        if self._size == 0:
            value = None
        else:
            value = copy.deepcopy(self._front._value)
        return value

    def peek_rear( self ):
        """
        -------------------------------------------------------
        Peeks at the rear of deque.
        Use: v = q.peek_rear()
        -------------------------------------------------------
        Postconditions:
          Returns a copy of the value at the rear of deque -
          the value is not removed from deque. Returns None
          if deque is empty.
        -------------------------------------------------------
        """
        if self._size == 0:
            value = None
        else:
            value = copy.deepcopy(self._rear._value)
        return value