#ifndef _DLIST_H_
#define _DLIST_H_

#include <stdexcept>

////////////////////////////////////////////////////////////////
//
// YOU DO *NOT* NEED TO MODIFY THIS FILE
//
// IF YOU *DO* MODIFY THIS FILE YOUR SOLUTION WILL BE REJECTED
//
////////////////////////////////////////////////////////////////

class List
{
public:
  List();
  ~List();

  // The operations available on the list
  void insert(int val);
  void printLR() const;
  void printRL() const;
  void bubblesort();
  bool empty() const;

  // Copy/assignment of lists are forbidden for simplicity
  List(List const&) = delete;
  List& operator=(List const&) = delete;
  
private:

  // Represents one element in the list. Contain no data.
  // Used for the "dummy" first and last elements.
  class Node
  {
  public:
    Node(Node* l = nullptr, Node* r = nullptr)
      : left(l), right(r) {}
    
    virtual ~Node() { delete right; }

    virtual int getData() const {
      throw std::logic_error("ERROR: getData: accessing data from non-data node");
    }
    
    Node(Node const&) = delete;
    Node& operator=(Node const&) = delete;
    
    Node* left;
    Node* right;
  };

  // Subclass to store the data. The data is large and should not be copied.
  // We have it as const member so compiler can help by forbidding overwrites.
  class Data_Node : public Node
  {
  public:
    Data_Node(int val, Node* l = nullptr, Node* r = nullptr)
      : Node(l, r), value(val) {}
    
    virtual int getData() const { return value; }
    
  private:
    const int value; // MUST REMAIN CONST AND PRIVATE

    // Imagine 'value' above is a *HUGE* variable that require
    // *MINUTES* to copy. Thus you *SHALL NOT* copy it.
  };
  
  Node* leftmost;
  Node* rightmost;
};

#endif