Code Listings Chapter 12

Listing 12-1  A  C++ interface for sorted lists

/** Interface for the ADT sorted list
@file SortedListInterface.h */
#ifndef _SORTED_LIST_INTERFACE
#define SORTED_LIST_INTERFACE
template < class ItemType > class SortedListInterface
{
public:

/** Inserts an entry into this sorted list in its proper order
so that the list remains sorted.
@pre None.
@post newEntry is in the list, and the list is sorted.
@param newEntry The entry to insert into the sorted list. */
  virtual void insertSorted (const ItemType & newEntry) = 0;

/** Removes the first or only occurrence of the given entry from this
sorted list.
@pre None.
@post If the removal is successful, the first occurrence of the
given entry is no longer in the sorted list, and the returned
value is true. Otherwise, the sorted list is unchanged and the
returned value is false.
@param anEntry The entry to remove.
@return True if removal is successful, or false if not. */
  virtual bool removeSorted (const ItemType & anEntry) = 0;

/** Gets the position of the first or only occurrence of the given
entry in this sorted list. In case the entry is not in the list,
determines where it should be if it were added to the list.
@pre None.
@post The position where the given entry is or belongs is returned.
The sorted list is unchanged.
@param anEntry The entry to locate.
@return Either the position of the given entry, if it occurs in the
sorted list, or the position where the entry would occur, but as a
negative integer. */
  virtual int getPosition (const ItemType & anEntry) = 0;

/** Sees whether this list is empty.
@return True if the list is empty; otherwise returns false. */
  virtual bool isEmpty ()const = 0;

/** Gets the current number of entries in this list.
@return The integer number of entries currently in the list. */
  virtual int getLength () const = 0;

/** Inserts an entry into this list at a given position.
@pre None.
@post If 1 <= position <= getLength() + 1 and the insertion is
successful, newEntry is at the given position in the list,
other entries are renumbered accordingly, and the returned
value is true.
@param newPosition The list position at which to insert newEntry.
@param newEntry The entry to insert into the list.
@return True if insertion is successful, or false if not. */
  virtual bool insert (int newPosition, const ItemType & newEntry) = 0;

/** Removes the entry at a given position from this list.
@pre None.
@post If 1 <= position <= getLength() and the removal is successful,
the entry at the given position in the list is removed, other
items are renumbered accordingly, and the returned value is true.
@param position The list position of the entry to remove.
@return True if removal is successful, or false if not. */
  virtual bool remove (int position) = 0;

/** Removes all entries from this list.
@post List contains no entries and the count of items is 0. */
  virtual void clear () = 0;

/** Gets the entry at the given position in this list.
@pre 1 <= position <= getLength().
@post The desired entry has been returned.
@param position The list position of the desired entry.
@return The entry at the given position. */
  virtual ItemType getEntry (int position) const = 0;

/** Replaces the entry at the given position in this list.
@pre 1 <= position <= getLength().
@post The entry at the given position is newEntry.
@param position The list position of the entry to replace.
@param newEntry The replacement entry. */
  virtual void setEntry (int position, const ItemType & newEntry) = 0;

};  // end SortedListInterface
#endif

Listing 12-2 The header file for the class LinkedSortedList .

/** ADT sorted list: Link-based implementation.
@file LinkedSortedList.h */
#ifndef _LINKED_SORTED_LIST
#define _LINKED_SORTED_LIST
#include "SortedListInterface.h"
#include "Node.h"
#include "PrecondViolatedExcep.h"
template < class ItemType > class LinkedSortedList:public SortedListInterface < ItemType >
{
private:
  Node < ItemType > *headPtr;	// Pointer to first node in the chain
  int itemCount;	// Current count of list items
// Locates the node that is before the node that should or does
// contain the given entry.
// @param anEntry The entry to find.
// @return Either a pointer to the node before the node that contains
// or should contain the given entry, or nullptr if no prior node exists.
  Node < ItemType > *getNodeBefore (const ItemType & anEntry) const;
// Locates the node at a given position within the chain.
  Node < ItemType > *getNodeAt (int position) const;
// Returns a pointer to a copy of the chain to which origChainPtr points.
  Node < ItemType > *copyChain (const Node < ItemType > *origChainPtr);

public:
  LinkedSortedList ();
  LinkedSortedList (const LinkedSortedList < ItemType > &aList);
  virtual ~ LinkedSortedList ();
  void insertSorted (const ItemType & newEntry);
  bool removeSorted (const ItemType & anEntry);
  int getPosition (const ItemType & newEntry) const;

// The following methods are the same as given in ListInterface:
  bool isEmpty () const;
  int getLength () const;
  bool remove (int position);
  void clear ();
  ItemType getEntry (int position) const throw (PrecondViolatedExcep);
};  // end LinkedSortedList

#include "LinkedSortedList.cpp"
#endif

/** ADT sorted list using the ADT list.
@file SortedListHasA.h */
#ifndef _SORTED_LIST_HAS_A
#define _SORTED_LIST_HAS_A
#include "SortedListInterface.h"
#include "ListInterface.h"
#include "Node.h"
#include "PrecondViolatedExcep.h"
template < class ItemType > class SortedListHasA:public SortedListInterface < ItemType >
{
private:
  ListInterface < ItemType > *listPtr;
public:
  SortedListHasA ();
  SortedListHasA (const SortedListHasA < ItemType > &sList);
  virtual ~ SortedListHasA ();
  void insertSorted (const ItemType & newEntry);
  bool removeSorted (const ItemType & anEntry);
  int getPosition (const ItemType & newEntry) const;

/** Sees whether this list is empty.
@return True if the list is empty; otherwise returns false. */
  virtual bool isEmpty ()const = 0;

/** Gets the current number of entries in this list.
@return The integer number of entries currently in the list. */
  virtual int getLength () const = 0;

/** Inserts an entry into this list at a given position.
@pre None.
@post If 1 <= position <= getLength() + 1 and the insertion is
successful, newEntry is at the given position in the list,
other entries are renumbered accordingly, and the returned
value is true.
@param newPosition The list position at which to insert newEntry.
@param newEntry The entry to insert into the list.
@return True if insertion is successful, or false if not. */
  virtual bool insert (int newPosition, const ItemType & newEntry) = 0;

/** Removes the entry at a given position from this list.
@pre None.
@post If 1 <= position <= getLength() and the removal is successful,
the entry at the given position in the list is removed, other
items are renumbered accordingly, and the returned value is true.
@param position The list position of the entry to remove.
@return True if removal is successful, or false if not. */
  virtual bool remove (int position) = 0;

/** Removes all entries from this list.
@post List contains no entries and the count of items is 0. */
  virtual void clear () = 0;

/** Gets the entry at the given position in this list.
@pre 1 <= position <= getLength().
@post The desired entry has been returned.
@param position The list position of the desired entry.
@return The entry at the given position. */
  virtual ItemType getEntry (int position) const = 0;

/** Replaces the entry at the given position in this list.
@pre 1 <= position <= getLength().
@post The entry at the given position is newEntry.
@param position The list position of the entry to replace.
@param newEntry The replacement entry. */
  virtual void setEntry (int position, const ItemType & newEntry) = 0;
};  // end SortedListHasA

#include "SortedListHasA.cpp"
#endif

/** ADT sorted list using ADT list.
@file SortedListIsA.h */
#ifndef _SORTED_LIST_IS_A
#define _SORTED_LIST_IS_A
#include "LinkedList.h"
#include "Node.h"
#include "PrecondViolatedExcep.h"
template < class ItemType > class SortedListIsA:public LinkedList < ItemType >
{
public:
  SortedListIsA ();
  SortedListIsA (const SortedListIsA < ItemType > &sList);

  virtual ~ SortedListIsA ();
  void insertSorted (const ItemType & newEntry);

  bool removeSorted (const ItemType & anEntry);

  int getPosition (const ItemType & anEntry) const;

// The inherited methods remove, clear, getEntry, isEmpty, and
// getLength have the same specifications as given in ListInterface.
// The following methods must be overridden to disable their
// effect on a sorted list:
  bool insert (int newPosition, const ItemType & newEntry);

  void setEntry (int position, const ItemType & newEntry) throw (PrecondViolatedExcep);
};  // end SortedListIsA

#include "SortedListIsA.cpp"
#endif

/** ADT sorted list using ADT list.
@file SortedListAsA.h */
#ifndef _SORTED_LIST_AS_A
#define _SORTED_LIST_AS_A
#include "SortedListInterface.h"
#include "ListInterface.h"
#include "Node.h"
#include "PrecondViolatedExcep.h"

template < class ItemType > class SortedListAsA:public SortedListInterface < ItemType >,
                            private LinkedList < ItemType >
{
public:
  SortedListAsA ();
  SortedListAsA (const SortedListAsA < ItemType > &sList);

  virtual ~ SortedListAsA ();

  void insertSorted (const ItemType & newEntry);

  bool removeSorted (const ItemType & anEntry);

  int getPosition (const ItemType & anEntry) const;
};  // end SortedListAsA

#include "SortedListAsA.cpp"
#endif