The Basic List Class: A Second Design:

Let's see if we can redesign the class so that it is more efficient: Consider the following changes: first, look at a skeleton form:

The CELL Class:

class CHAR_CELL_CORE{
    friend class CHAR_LIST_CORE;
    friend istream& operator>>(istream& in, CHAR_CELL_CORE& A)
      {A.grab(in); return(in);};
    friend istream& operator>>(istream& in, CHAR_CELL_CORE* A)
      {A->grab(in); return(in);};
    friend ostream& operator<<(ostream& out,const CHAR_CELL_CORE& A)
      {A.print(out); return(out);};
    friend ostream& operator<<(ostream& out,const CHAR_CELL_CORE* A)
      {A->print(out); return(out);};
  public:
    void load_element(TYPE x){element = x;};
    virtual istream& grab(istream& in) = 0;
    virtual ostream& print(ostream& out) const = 0;
  protected:
    char * name;
    TYPE element;
  };

class CHAR_SL_CELL : public CHAR_CELL_CORE{
    friend class CHAR_SLLIST;
  public:
    CHAR_SL_CELL(char *name_in);
    ~CHAR_SL_CELL();
    ...agents...
    ostream& print(ostream& out) const;
  protected:
    CHAR_SL_CELL *next; 
  };

class CHAR_DL_CELL : public CHAR_CELL_CORE{
    friend class CHAR_DLLIST;
  public:
    CHAR_DL_CELL(char *name_in);
    ~CHAR_DL_CELL();
    ...agents...
    istream& grab(istream& in);
    ostream& print(ostream& out) const; 
  protected:
    CHAR_DL_CELL *next;
    CHAR_DL_CELL *previous;  
  };

Note the derivation chain is now

• Parent: CHAR_CELL_CORE
  • Child: CHAR_SL_CELL
  • Child: CHAR_DL_CELL

We have also made additional changes:

• char *name is now moved to the parent class as it is common to both children.
• A grab agent has been added to handle input for the class.
• The grab and print agents are now public.
• The outputting and inputting of the objects is handled through a uniform interface given by

        friend istream& operator>>(istream& in,CHAR_LIST_CORE& A)
          {A.grab(in); return(in);};
        friend istream& operator>>(istream& in,CHAR_LIST_CORE* A)
          {A->grab(in); return(in);};
        friend ostream& operator<<(ostream& out,const CHAR_LIST_CORE& A)
          {A.print(out); return(out);};
        friend ostream& operator<<(ostream& out,const CHAR_LIST_CORE* A)
          {A->print(out); return(out);};
  

  Note these friend agents are defined in the parent; there is no need to define them in the children as when they are used, the correct child print or grab agent will be used. Also, note that this I/O mechanism is very uniform in appearance-to use it in another class all we need do is define public grab and print agents, copy the code above and change the object type! Also, note these agents are defined inline for efficiency.

The LIST Class:

The LIST class now looks like:

class CHAR_LIST_CORE{
    friend class CHAR_CELL_CORE;
    friend istream& operator>>(istream& in,CHAR_LIST_CORE& A)
      {A.grab(in); return(in);};
    friend istream& operator>>(istream& in,CHAR_LIST_CORE* A)
      {A->grab(in); return(in);};
    friend ostream& operator<<(ostream& out,const CHAR_LIST_CORE& A)
      {A.print(out); return(out);};
    friend ostream& operator<<(ostream& out,const CHAR_LIST_CORE* A)
      {A->print(out); return(out);};
  public:
    ...pure virtual agents...
    virtual istream& grab(istream& in) = 0;
    virtual ostream& print(ostream& out) const = 0;
  protected:
    char *name;
  };

class CHAR_SLLIST : public CHAR_LIST_CORE{
    const int NIL = -1;
    friend class CHAR_SL_CELL;
  public:
    CHAR_SLLIST(char *name_in);
    CHAR_SLLIST(CHAR_SLLIST&);
    ~CHAR_SLLIST();
    CHAR_SLLIST& operator=(const CHAR_SLLIST&);
    ...agents...
    istream& grab(istream& in);
    ostream& print(ostream& out) const;
  protected:
    CHAR_SL_CELL *head;
    ...agents...
  };

And a stab at a class definition for the Doubley Linked List is as follows:

  
class CHAR_DLLIST : public CHAR_LIST_CORE{
    friend class CHAR_DL_CELL;
    friend istream& operator>>(istream& in,CHAR_DLLIST& A)
      {A.grab(in); return(in);};
    friend istream& operator>>(istream& in,CHAR_DLLIST* A)
      {A->grab(in); return(in);};
    friend ostream& operator<<(ostream& out,const CHAR_DLLIST& A)
      {A.print(out); return(out);};
    friend ostream& operator<<(ostream& out,const CHAR_DLLIST* A)
      {A->print(out); return(out);};
  public:
    CHAR_DLLIST(char *name_in);
    CHAR_DLLIST(CHAR_DLLIST&);
    ~CHAR_DLLIST();
    CHAR_DLLIST& operator=(const CHAR_DLLIST&);
    ...agents...
    istream& grab(istream& in);
    ostream& print(ostream& out) const;
  protected:
    char *name;
    CHAR_DL_CELL *head;
    CHAR_DL_CELL *end;
    ...agents...
  };
#endif

Note the derivation chain is now

• Parent: CHAR_LIST_CORE
  • Child: CHAR_SLLIST
  • Child: CHAR_DLLIST

The full headers with all agents listed are given below:

The CELL Class:

class CHAR_CELL_CORE{
    friend class CHAR_LIST_CORE;
    friend istream& operator>>(istream& in, CHAR_CELL_CORE& A)
      {A.grab(in); return(in);};
    friend istream& operator>>(istream& in, CHAR_CELL_CORE* A)
      {A->grab(in); return(in);};
    friend ostream& operator<<(ostream& out,const CHAR_CELL_CORE& A)
      {A.print(out); return(out);};
    friend ostream& operator<<(ostream& out,const CHAR_CELL_CORE* A)
      {A->print(out); return(out);};
  public:
    void load_element(TYPE x){element = x;};
    virtual istream& grab(istream& in) = 0;
    virtual ostream& print(ostream& out) const = 0;
  protected:
    char * name;
    TYPE element;
  };

class CHAR_SL_CELL : public CHAR_CELL_CORE{
    friend class CHAR_SLLIST;
  public:
    CHAR_SL_CELL(char *name_in);
    ~CHAR_SL_CELL();
    void load_all(TYPE x,CHAR_SL_CELL *next_in)
                {element = x; next = next_in;};
    void load_next_pointer(CHAR_SL_CELL *next_in){next = next_in;};   
    CHAR_SL_CELL* get_next(){ return(next);};
    CHAR_SL_CELL* split(CHAR_SL_CELL *A);
    CHAR_SL_CELL* merge(CHAR_SL_CELL *A1,CHAR_SL_CELL *A2);
    CHAR_SL_CELL* mergesort(CHAR_SL_CELL *A);
    istream& grab(istream& in); 
    ostream& print(ostream& out) const;
  protected:
    CHAR_SL_CELL *next; 
  };

class CHAR_DL_CELL : public CHAR_CELL_CORE{
    friend class CHAR_DLLIST;
  public:
    CHAR_DL_CELL(char *name_in);
    ~CHAR_DL_CELL();
    void load_all(CHAR_DL_CELL *previous_in,TYPE x,CHAR_DL_CELL *next_in)
                 {element = x; next = next_in,previous = previous_in;};
    void load_previous_pointer(CHAR_DL_CELL *previous_in)
         {previous = previous_in;};
    CHAR_DL_CELL* get_previous(){return(previous);};
    istream& grab(istream& in);
    ostream& print(ostream& out) const; 
  protected:
    CHAR_DL_CELL *next;
    CHAR_DL_CELL *previous;  
  };

The LIST Class:

class CHAR_LIST_CORE{
    friend class CHAR_CELL_CORE;
    friend istream& operator>>(istream& in,CHAR_LIST_CORE& A)
      {A.grab(in); return(in);};
    friend istream& operator>>(istream& in,CHAR_LIST_CORE* A)
      {A->grab(in); return(in);};
    friend ostream& operator<<(ostream& out,const CHAR_LIST_CORE& A)
      {A.print(out); return(out);};
    friend ostream& operator<<(ostream& out,const CHAR_LIST_CORE* A)
      {A->print(out); return(out);};
  public:
    virtual int is_empty() = 0;
    virtual void delete_element(TYPE target_key) = 0;
    virtual void search_element(TYPE search_key) = 0;
    virtual void build_list(TYPE *A,int size) = 0;
    virtual int get_number_elements() = 0;
    virtual void insert_after(TYPE before,TYPE after) = 0;
    virtual void insert_before(TYPE after,TYPE before) = 0;
    virtual istream& grab(istream& in) = 0;
    virtual ostream& print(ostream& out) const = 0;
  };

class CHAR_SLLIST : public CHAR_LIST_CORE{
    friend class CHAR_SL_CELL;
  public:
    CHAR_SLLIST(char *name_in);
    CHAR_SLLIST(CHAR_SLLIST&);
    ~CHAR_SLLIST();
    CHAR_SLLIST& operator=(const CHAR_SLLIST&);
    // agents
    int is_empty(){return(head==NULL);};
    void delete_element(TYPE target_key);
    void search_element(TYPE search_key);
    void build_list(TYPE *A,int size);
    int get_number_elements();
    void insert_after(TYPE before_element,TYPE new_element);
    void insert_before(TYPE after_element,TYPE new_element);
    void mergesort();
    istream& grab(istream& in);
    ostream& print(ostream& out) const;
  protected:
    CHAR_SL_CELL *head;
    CHAR_SL_CELL* get_element_address(TYPE search_key);
    CHAR_SL_CELL* get_before_element_address(TYPE search_key);
    CHAR_SL_CELL* get_after_element_address(TYPE search_key);
  };
  
class CHAR_DLLIST : public CHAR_LIST_CORE{
    friend class CHAR_DL_CELL;
    friend istream& operator>>(istream& in,CHAR_DLLIST& A)
      {A.grab(in); return(in);};
    friend istream& operator>>(istream& in,CHAR_DLLIST* A)
      {A->grab(in); return(in);};
    friend ostream& operator<<(ostream& out,const CHAR_DLLIST& A)
      {A.print(out); return(out);};
    friend ostream& operator<<(ostream& out,const CHAR_DLLIST* A)
      {A->print(out); return(out);};
  public:
    CHAR_DLLIST(char *name_in);
    CHAR_DLLIST(CHAR_DLLIST&);
    ~CHAR_DLLIST();
    CHAR_DLLIST& operator=(const CHAR_DLLIST&);
    // agents
    int is_empty(){return(head==NULL);};
    void delete_element(TYPE target_key);
    void search_element(TYPE search_key);
    void build_list(TYPE *A,int size);
    int get_number_elements();
    void insert_after(TYPE before_element,TYPE new_element);
    void insert_before(TYPE after_element,TYPE new_element);
    void mergesort();
    istream& grab(istream& in);
    ostream& print(ostream& out) const;
  protected:
    CHAR_DL_CELL *head;
    CHAR_DL_CELL *end;
    CHAR_DL_CELL* get_element_address(TYPE search_key);
    CHAR_DL_CELL* get_before_element_address(TYPE search_key);
    CHAR_DL_CELL* get_after_element_address(TYPE search_key);
  };
#endif

The core class CHAR_LIST_CORE uses our standard defined macro TYPE to designate type and furnishes a complete definition of the agents used to manipulate and query the array list ADT. The core class has no elements and only lists methods that are pure virtual which will be instantiated properly in any children we wish to describe. There are some different things in this class definition that we need to discuss:

A Reference to CHAR_CELL_CORE:

The array list structure is the most basic of our lists types; however, the pointer based list variations will be implemented with an auxiliary class of CELLs. We want to use the same core class for all the list types, so even though we will not use the CHAR_CELL_CORE class here, we add it for convenience.

The Public Agents grab and print:

We will need access to protected members of each child class in our overloaded input and output operators. We will gain this functionality with the agents

    public:
      virtual istream& grab(istream& in) = 0;
      virtual ostream& print(ostream& out) const = 0;

These agents are pure virtual and will be instantiated in any child class we build. They will be used in conjunction with the overloaded input and output operators in a new way. In this core class we declare the usual friends:

    friend istream& operator>>(istream&,INT\_LIST_CORE&);
    friend istream& operator>>(istream&,INT\_LIST_CORE*);
    friend ostream& operator<<(ostream&,const INT\_LIST_CORE&);
    friend ostream& operator<<(ostream&,const INT\_LIST_CORE*);

Note that the agent grab is not declared const (so this agent can alter protected values of the class) and the agent print is const as when we are outputting values, we wish to impose the additional security of const arguments so that we can't accidentally change field elements in the protected scope.