Treceți la conținutul principal

ALGORITMI CPP CODES

//
//   This file contains the C++ code from Program 2.1 of
//   "Data Structures and Algorithms
//    with Object-Oriented Design Patterns in C++"
//   by Bruno R. Preiss.
//
//   Copyright (c) 1998 by Bruno R. Preiss, P.Eng.  All rights reserved.
//
//   http://www.pads.uwaterloo.ca/Bruno.Preiss/books/opus4/programs/pgm02_01.cpp
//
unsigned int Sum (unsigned int n)
{
    unsigned int result = 0;
    for (unsigned int i = 1; i <= n; ++i)
result += i;
    return result;
}
//
//   This file contains the C++ code from Program 2.2 of
//   "Data Structures and Algorithms
//    with Object-Oriented Design Patterns in C++"
//   by Bruno R. Preiss.
//
//   Copyright (c) 1998 by Bruno R. Preiss, P.Eng.  All rights reserved.
//
//   http://www.pads.uwaterloo.ca/Bruno.Preiss/books/opus4/programs/pgm02_02.cpp
//
int Horner (int a [], unsigned int n, int x)
{
    int result = a [n];
    for (int i = n - 1; i >= 0; --i)
result = result * x + a [i];
    return result;
}
//
//   This file contains the C++ code from Program 2.3 of
//   "Data Structures and Algorithms
//    with Object-Oriented Design Patterns in C++"
//   by Bruno R. Preiss.
//
//   Copyright (c) 1998 by Bruno R. Preiss, P.Eng.  All rights reserved.
//
//   http://www.pads.uwaterloo.ca/Bruno.Preiss/books/opus4/programs/pgm02_03.cpp
//
unsigned int Factorial (unsigned int n)
{
    if (n == 0)
return 1;
    else
return n * Factorial (n - 1);
}
//
//   This file contains the C++ code from Program 2.4 of
//   "Data Structures and Algorithms
//    with Object-Oriented Design Patterns in C++"
//   by Bruno R. Preiss.
//
//   Copyright (c) 1998 by Bruno R. Preiss, P.Eng.  All rights reserved.
//
//   http://www.pads.uwaterloo.ca/Bruno.Preiss/books/opus4/programs/pgm02_04.cpp
//
unsigned int FindMaximum (unsigned int a [], unsigned int n)
{
    unsigned int result = a [0];
    for (unsigned int i = 1; i < n; ++i)
if (a [i] > result)
   result = a [i];
    return result;
}
//
//   This file contains the C++ code from Program 2.5 of
//   "Data Structures and Algorithms
//    with Object-Oriented Design Patterns in C++"
//   by Bruno R. Preiss.
//
//   Copyright (c) 1998 by Bruno R. Preiss, P.Eng.  All rights reserved.
//
//   http://www.pads.uwaterloo.ca/Bruno.Preiss/books/opus4/programs/pgm02_05.cpp
//
#include <iostream>
#include <cmath>

int main (int, char* [])
{
    double result = 0;
    for (unsigned long int i = 1; i <= 500000; ++i)
result += 1./i - std::log ((i + 1.)/i);
    cout << "gamma = " << result << endl;
    return 0;
}
//
//   This file contains the C++ code from Program 2.6 of
//   "Data Structures and Algorithms
//    with Object-Oriented Design Patterns in C++"
//   by Bruno R. Preiss.
//
//   Copyright (c) 1998 by Bruno R. Preiss, P.Eng.  All rights reserved.
//
//   http://www.pads.uwaterloo.ca/Bruno.Preiss/books/opus4/programs/pgm02_06.cpp
//
int GeometricSeriesSum (int x, unsigned int n)
{
    int sum = 0;
    for (unsigned int i = 0; i <= n; ++i)
    {
int prod = 1;
for (unsigned int j = 0; j < i; ++j)
   prod *= x;
sum += prod;
    }
    return sum;
}
//
//   This file contains the C++ code from Program 2.7 of
//   "Data Structures and Algorithms
//    with Object-Oriented Design Patterns in C++"
//   by Bruno R. Preiss.
//
//   Copyright (c) 1998 by Bruno R. Preiss, P.Eng.  All rights reserved.
//
//   http://www.pads.uwaterloo.ca/Bruno.Preiss/books/opus4/programs/pgm02_07.cpp
//
int GeometricSeriesSum (int x, unsigned int n)
{
    int sum = 0;
    for (unsigned int i = 0; i <= n; ++i)
sum = sum * x + 1;
    return sum;
}
//
//   This file contains the C++ code from Program 2.8 of
//   "Data Structures and Algorithms
//    with Object-Oriented Design Patterns in C++"
//   by Bruno R. Preiss.
//
//   Copyright (c) 1998 by Bruno R. Preiss, P.Eng.  All rights reserved.
//
//   http://www.pads.uwaterloo.ca/Bruno.Preiss/books/opus4/programs/pgm02_08.cpp
//
int Power (int x, unsigned int n)
{
    if (n == 0)
return 1;
    else if (n % 2 == 0) // n is even
return Power (x * x, n / 2);
    else // n is odd
return x * Power (x * x, n / 2);
}
//
//   This file contains the C++ code from Program 2.9 of
//   "Data Structures and Algorithms
//    with Object-Oriented Design Patterns in C++"
//   by Bruno R. Preiss.
//
//   Copyright (c) 1998 by Bruno R. Preiss, P.Eng.  All rights reserved.
//
//   http://www.pads.uwaterloo.ca/Bruno.Preiss/books/opus4/programs/pgm02_09.cpp
//
int Power (int, unsigned int);

int GeometricSeriesSum (int x, unsigned int n)
{
    return (Power (x, n + 1) - 1) / (x - 1);
}
//
//   This file contains the C++ code from Program 3.2 of
//   "Data Structures and Algorithms
//    with Object-Oriented Design Patterns in C++"
//   by Bruno R. Preiss.
//
//   Copyright (c) 1998 by Bruno R. Preiss, P.Eng.  All rights reserved.
//
//   http://www.pads.uwaterloo.ca/Bruno.Preiss/books/opus4/programs/pgm03_02.cpp
//
void PrefixSums (int a [], unsigned int n)
{
    for (int j = n - 1; j >= 0; --j)
    {
int sum = 0;
for (unsigned int i = 0; i <= j; ++i)
   sum += a[i];
a [j] = sum;
    }
}
//
//   This file contains the C++ code from Program 3.3 of
//   "Data Structures and Algorithms
//    with Object-Oriented Design Patterns in C++"
//   by Bruno R. Preiss.
//
//   Copyright (c) 1998 by Bruno R. Preiss, P.Eng.  All rights reserved.
//
//   http://www.pads.uwaterloo.ca/Bruno.Preiss/books/opus4/programs/pgm03_03.cpp
//
unsigned int Fibonacci (unsigned int n)
{
    int previous = -1;
    int result = 1;
    for (unsigned int i = 0; i <= n; ++i)
    {
int const sum = result + previous;
previous = result;
result = sum;
    }
    return result;
}
//
//   This file contains the C++ code from Program 3.4 of
//   "Data Structures and Algorithms
//    with Object-Oriented Design Patterns in C++"
//   by Bruno R. Preiss.
//
//   Copyright (c) 1998 by Bruno R. Preiss, P.Eng.  All rights reserved.
//
//   http://www.pads.uwaterloo.ca/Bruno.Preiss/books/opus4/programs/pgm03_04.cpp
//
unsigned int Fibonacci (unsigned int n)
{
    if (n == 0 || n == 1)
return n;
    else
return Fibonacci (n - 1U) + Fibonacci (n - 2U);
}
//
//   This file contains the C++ code from Program 3.5 of
//   "Data Structures and Algorithms
//    with Object-Oriented Design Patterns in C++"
//   by Bruno R. Preiss.
//
//   Copyright (c) 1998 by Bruno R. Preiss, P.Eng.  All rights reserved.
//
//   http://www.pads.uwaterloo.ca/Bruno.Preiss/books/opus4/programs/pgm03_05.cpp
//
unsigned int const m = ?;

void BucketSort (unsigned int a [], unsigned int n)
{
    int buckets [m];

    for (unsigned int j = 0; j < m; ++j)
buckets [j] = 0;
    for (unsigned int i = 0; i < n; ++i)
++buckets [a [i]];
    for (unsigned int i = 0, j = 0; j < m; ++j)
for (unsigned int k = buckets [j]; k > 0; --k)
   a [i++] = j;
}
//
//   This file contains the C++ code from Program 4.1 of
//   "Data Structures and Algorithms
//    with Object-Oriented Design Patterns in C++"
//   by Bruno R. Preiss.
//
//   Copyright (c) 1998 by Bruno R. Preiss, P.Eng.  All rights reserved.
//
//   http://www.pads.uwaterloo.ca/Bruno.Preiss/books/opus4/programs/pgm04_01.cpp
//
template <class T>
class Array
{
protected:
    T* data;
    unsigned int base;
    unsigned int length;
public:
    Array ();
    Array (unsigned int, unsigned int = 0);
    ~Array ();

    Array (Array const&);
    Array& operator = (Array const&);

    T const& operator [] (unsigned int) const;
    T& operator [] (unsigned int);

    T const* Data () const;
    unsigned int Base () const;
    unsigned int Length () const;

    void SetBase (unsigned int);
    void SetLength (unsigned int);
};
//
//   This file contains the C++ code from Program 4.2 of
//   "Data Structures and Algorithms
//    with Object-Oriented Design Patterns in C++"
//   by Bruno R. Preiss.
//
//   Copyright (c) 1998 by Bruno R. Preiss, P.Eng.  All rights reserved.
//
//   http://www.pads.uwaterloo.ca/Bruno.Preiss/books/opus4/programs/pgm04_02.cpp
//
template <class T>
Array<T>::Array () :
    data (new T [0]),
    base (0),
    length (0)
    {}
//
//   This file contains the C++ code from Program 4.5 of
//   "Data Structures and Algorithms
//    with Object-Oriented Design Patterns in C++"
//   by Bruno R. Preiss.
//
//   Copyright (c) 1998 by Bruno R. Preiss, P.Eng.  All rights reserved.
//
//   http://www.pads.uwaterloo.ca/Bruno.Preiss/books/opus4/programs/pgm04_05.cpp
//
template <class T>
Array<T>::~Array ()
    { delete [] data; }
//
//   This file contains the C++ code from Program 4.6 of
//   "Data Structures and Algorithms
//    with Object-Oriented Design Patterns in C++"
//   by Bruno R. Preiss.
//
//   Copyright (c) 1998 by Bruno R. Preiss, P.Eng.  All rights reserved.
//
//   http://www.pads.uwaterloo.ca/Bruno.Preiss/books/opus4/programs/pgm04_06.cpp
//
template <class T>
T const* Array<T>::Data () const
    { return data; }

template <class T>
unsigned int Array<T>::Base () const
    { return base; }

template <class T>
unsigned int Array<T>::Length () const
    { return length; }
//
//   This file contains the C++ code from Program 4.7 of
//   "Data Structures and Algorithms
//    with Object-Oriented Design Patterns in C++"
//   by Bruno R. Preiss.
//
//   Copyright (c) 1998 by Bruno R. Preiss, P.Eng.  All rights reserved.
//
//   http://www.pads.uwaterloo.ca/Bruno.Preiss/books/opus4/programs/pgm04_07.cpp
//
template <class T>
T const& Array<T>::operator [] (unsigned int position) const
{
    unsigned int const offset = position - base;
    if (offset >= length)
throw out_of_range ("invalid position");
    return data [offset];
}

template <class T>
T& Array<T>::operator [] (unsigned int position)
{
    unsigned int const offset = position - base;
    if (offset >= length)
throw out_of_range ("invalid position");
    return data [offset];
}



//
//   This file contains the C++ code from Program 4.8 of
//   "Data Structures and Algorithms
//    with Object-Oriented Design Patterns in C++"
//   by Bruno R. Preiss.
//
//   Copyright (c) 1998 by Bruno R. Preiss, P.Eng.  All rights reserved.
//
//   http://www.pads.uwaterloo.ca/Bruno.Preiss/books/opus4/programs/pgm04_08.cpp
//
template <class T>
void Array<T>::SetBase (unsigned int newBase)
    { base = newBase; }

template <class T>
void Array<T>::SetLength (unsigned int newLength)
{
    T* const newData = new T [newLength];
    unsigned int const min =
length < newLength ? length : newLength;
    for (unsigned int i = 0; i < min; ++i)
newData [i] = data [i];
    delete [] data;
    data = newData;
    length = newLength;
}
//
//   This file contains the C++ code from Program 4.9 of
//   "Data Structures and Algorithms
//    with Object-Oriented Design Patterns in C++"
//   by Bruno R. Preiss.
//
//   Copyright (c) 1998 by Bruno R. Preiss, P.Eng.  All rights reserved.
//
//   http://www.pads.uwaterloo.ca/Bruno.Preiss/books/opus4/programs/pgm04_09.cpp
//
template <class T>
class LinkedList;

template <class T>
class ListElement
{
    T datum;
    ListElement* next;

    ListElement (T const&, ListElement*);
public:
    T const& Datum () const;
    ListElement const* Next () const;

    friend LinkedList<T>;
};

template <class T>
class LinkedList
{
    ListElement<T>* head;
    ListElement<T>* tail;
public:
    LinkedList ();
    ~LinkedList ();

    LinkedList (LinkedList const&);
    LinkedList& operator = (LinkedList const&);

    ListElement<T> const* Head () const;
    ListElement<T> const* Tail () const;
    bool IsEmpty () const;
    T const& First () const;
    T const& Last () const;

    void Prepend (T const&);
    void Append (T const&);
    void Extract (T const&);
    void Purge ();
    void InsertAfter (ListElement<T> const*, T const&);
    void InsertBefore (ListElement<T> const*, T const&);
};
//
//   This file contains the C++ code from Program 4.10 of
//   "Data Structures and Algorithms
//    with Object-Oriented Design Patterns in C++"
//   by Bruno R. Preiss.
//
//   Copyright (c) 1998 by Bruno R. Preiss, P.Eng.  All rights reserved.
//
//   http://www.pads.uwaterloo.ca/Bruno.Preiss/books/opus4/programs/pgm04_10.cpp
//
template <class T>
ListElement<T>::ListElement (
    T const& _datum, ListElement<T>* _next) :
    datum (_datum), next (_next)
    {}

template <class T>
T const& ListElement<T>::Datum () const
    { return datum; }

template <class T>
ListElement<T> const* ListElement<T>::Next () const
    { return next; }
//
//   This file contains the C++ code from Program 4.11 of
//   "Data Structures and Algorithms
//    with Object-Oriented Design Patterns in C++"
//   by Bruno R. Preiss.
//
//   Copyright (c) 1998 by Bruno R. Preiss, P.Eng.  All rights reserved.
//
//   http://www.pads.uwaterloo.ca/Bruno.Preiss/books/opus4/programs/pgm04_11.cpp
//
template <class T>
LinkedList<T>::LinkedList () :
    head (0),
    tail (0)
    {}
//
//   This file contains the C++ code from Program 4.12 of
//   "Data Structures and Algorithms
//    with Object-Oriented Design Patterns in C++"
//   by Bruno R. Preiss.
//
//   Copyright (c) 1998 by Bruno R. Preiss, P.Eng.  All rights reserved.
//
//   http://www.pads.uwaterloo.ca/Bruno.Preiss/books/opus4/programs/pgm04_12.cpp
//
template <class T>
void LinkedList<T>::Purge ()
{
    while (head != 0)
    {
ListElement<T>* const tmp = head;
head = head->next;
delete tmp;
    }
    tail = 0;
}

template <class T>
LinkedList<T>::~LinkedList ()
    { Purge (); }
//
//   This file contains the C++ code from Program 4.13 of
//   "Data Structures and Algorithms
//    with Object-Oriented Design Patterns in C++"
//   by Bruno R. Preiss.
//
//   Copyright (c) 1998 by Bruno R. Preiss, P.Eng.  All rights reserved.
//
//   http://www.pads.uwaterloo.ca/Bruno.Preiss/books/opus4/programs/pgm04_13.cpp
//
template <class T>
ListElement<T> const* LinkedList<T>::Head () const
    { return head; }

template <class T>
ListElement<T> const* LinkedList<T>::Tail () const
    { return tail; }

template <class T>
bool LinkedList<T>::IsEmpty () const
    { return head == 0; }
//
//   This file contains the C++ code from Program 4.14 of
//   "Data Structures and Algorithms
//    with Object-Oriented Design Patterns in C++"
//   by Bruno R. Preiss.
//
//   Copyright (c) 1998 by Bruno R. Preiss, P.Eng.  All rights reserved.
//
//   http://www.pads.uwaterloo.ca/Bruno.Preiss/books/opus4/programs/pgm04_14.cpp
//
template <class T>
T const& LinkedList<T>::First () const
{
    if (head == 0)
throw domain_error ("list is empty");
    return head->datum;
}

template <class T>
T const& LinkedList<T>::Last () const
{
    if (tail == 0)
throw domain_error ("list is empty");
    return tail->datum;
}
//
//   This file contains the C++ code from Program 4.16 of
//   "Data Structures and Algorithms
//    with Object-Oriented Design Patterns in C++"
//   by Bruno R. Preiss.
//
//   Copyright (c) 1998 by Bruno R. Preiss, P.Eng.  All rights reserved.
//
//   http://www.pads.uwaterloo.ca/Bruno.Preiss/books/opus4/programs/pgm04_16.cpp
//
template <class T>
void LinkedList<T>::Append (T const& item)
{
    ListElement<T>* const tmp = new ListElement<T> (item, 0);
    if (head == 0)
head = tmp;
    else
tail->next = tmp;
    tail = tmp;
}
//
//   This file contains the C++ code from Program 4.17 of
//   "Data Structures and Algorithms
//    with Object-Oriented Design Patterns in C++"
//   by Bruno R. Preiss.
//
//   Copyright (c) 1998 by Bruno R. Preiss, P.Eng.  All rights reserved.
//
//   http://www.pads.uwaterloo.ca/Bruno.Preiss/books/opus4/programs/pgm04_17.cpp
//
template <class T>
LinkedList<T>::LinkedList (LinkedList<T> const& linkedList) :
    head (0),
    tail (0)
{
    ListElement<T> const* ptr;
    for (ptr = linkedList.head; ptr != 0; ptr = ptr->next)
Append (ptr->datum);
}

template <class T>
LinkedList<T>& LinkedList<T>::operator = (
    LinkedList<T> const& linkedList)
{
    if (&linkedList != this)
    {
Purge ();
ListElement<T> const* ptr;
for (ptr = linkedList.head; ptr != 0; ptr = ptr->next)
   Append (ptr->datum);
    }
    return *this;
}
//
//   This file contains the C++ code from Program 4.18 of
//   "Data Structures and Algorithms
//    with Object-Oriented Design Patterns in C++"
//   by Bruno R. Preiss.
//
//   Copyright (c) 1998 by Bruno R. Preiss, P.Eng.  All rights reserved.
//
//   http://www.pads.uwaterloo.ca/Bruno.Preiss/books/opus4/programs/pgm04_18.cpp
//
template <class T>
void LinkedList<T>::Extract (T const& item)
{
    ListElement<T>* ptr = head;
    ListElement<T>* prevPtr = 0;
    while (ptr != 0 && ptr->datum != item)
    {
prevPtr = ptr;
ptr = ptr->next;
    }
    if (ptr == 0)
throw invalid_argument ("item not found");
    if (ptr == head)
head = ptr->next;
    else
prevPtr->next = ptr->next;
    if (ptr == tail)
tail = prevPtr;
    delete ptr;
}
//
//   This file contains the C++ code from Program 4.19 of
//   "Data Structures and Algorithms
//    with Object-Oriented Design Patterns in C++"
//   by Bruno R. Preiss.
//
//   Copyright (c) 1998 by Bruno R. Preiss, P.Eng.  All rights reserved.
//
//   http://www.pads.uwaterloo.ca/Bruno.Preiss/books/opus4/programs/pgm04_19.cpp
//
template <class T>
void LinkedList<T>::InsertAfter (
    ListElement<T> const* arg, T const& item)
{
    ListElement<T>* ptr = const_cast<ListElement<T>*> (arg);
    if (ptr == 0)
throw invalid_argument ("invalid position");
    ListElement<T>* const tmp =
new ListElement<T> (item, ptr->next);
    ptr->next = tmp;
    if (tail == ptr)
tail = tmp;
}

template <class T>
void LinkedList<T>::InsertBefore (
    ListElement<T> const* arg, T const& item)
{
    ListElement<T>* ptr = const_cast<ListElement<T>*> (arg);
    if (ptr == 0)
throw invalid_argument ("invalid position");
    ListElement<T>* const tmp = new ListElement<T> (item, ptr);
    if (head == ptr)
head = tmp;
    else
    {
ListElement<T>* prevPtr = head;
while (prevPtr != 0 && prevPtr->next != ptr)
   prevPtr = prevPtr->next;
if (prevPtr == 0)
   throw invalid_argument ("invalid position");
prevPtr->next = tmp;
    }
}
//
//   This file contains the C++ code from Program 4.20 of
//   "Data Structures and Algorithms
//    with Object-Oriented Design Patterns in C++"
//   by Bruno R. Preiss.
//
//   Copyright (c) 1998 by Bruno R. Preiss, P.Eng.  All rights reserved.
//
//   http://www.pads.uwaterloo.ca/Bruno.Preiss/books/opus4/programs/pgm04_20.cpp
//
template <class T>
class Array2D
{
protected:
    unsigned int numberOfRows;
    unsigned int numberOfColumns;
    Array<T> array;
public:
    class Row
    {
Array2D& array2D;
unsigned int const row;
    public:
Row (Array2D& _array2D, unsigned int _row) :
   array2D (_array2D), row (_row) {}
T& operator [] (unsigned int column) const
   { return array2D.Select (row, column); }
    };

    Array2D (unsigned int, unsigned int);
    T& Select (unsigned int, unsigned int);
    Row operator [] (unsigned int);
};
//
//   This file contains the C++ code from Program 4.21 of
//   "Data Structures and Algorithms
//    with Object-Oriented Design Patterns in C++"
//   by Bruno R. Preiss.
//
//   Copyright (c) 1998 by Bruno R. Preiss, P.Eng.  All rights reserved.
//
//   http://www.pads.uwaterloo.ca/Bruno.Preiss/books/opus4/programs/pgm04_21.cpp
//
template <class T>
Array2D<T>::Array2D (unsigned int m, unsigned int n) :
    numberOfRows (m),
    numberOfColumns (n),
    array (m * n)
    {}

template <class T>
T& Array2D<T>::Select (unsigned int i, unsigned int j)
{
    if (i >= numberOfRows)
throw out_of_range ("invalid row");
    if (j >= numberOfColumns)
throw out_of_range ("invalid column");
    return array [i * numberOfColumns + j];
}

template <class T>
Array2D<T>::Row Array2D<T>::operator [] (unsigned int row)
    { return Row (*this, row); }
//
//   This file contains the C++ code from Program 4.22 of
//   "Data Structures and Algorithms
//    with Object-Oriented Design Patterns in C++"
//   by Bruno R. Preiss.
//
//   Copyright (c) 1998 by Bruno R. Preiss, P.Eng.  All rights reserved.
//
//   http://www.pads.uwaterloo.ca/Bruno.Preiss/books/opus4/programs/pgm04_22.cpp
//
template <class T>
class Matrix : public Array2D<T>
{
public:
    Matrix (unsigned int, unsigned int);
    Matrix operator * (Matrix const&) const;
    Matrix operator + (Matrix const&) const;
};
//
//   This file contains the C++ code from Program 4.23 of
//   "Data Structures and Algorithms
//    with Object-Oriented Design Patterns in C++"
//   by Bruno R. Preiss.
//
//   Copyright (c) 1998 by Bruno R. Preiss, P.Eng.  All rights reserved.
//
//   http://www.pads.uwaterloo.ca/Bruno.Preiss/books/opus4/programs/pgm04_23.cpp
//
template <class T>
Matrix<T> Matrix<T>::operator * (Matrix<T> const& arg) const
{
    if (numberOfColumns != arg.numberOfRows)
throw invalid_argument ("incompatible matrices");
    Matrix<T> result (numberOfRows, arg.numberOfColumns);
    for (unsigned int i = 0; i < numberOfRows; ++i)
    {
for (unsigned int j = 0; j < arg.numberOfColumns; ++j)
{
   T sum = 0;
   for (unsigned int k = 0; k < numberOfColumns; ++k)
sum += (*this) [i][k] * arg [k][j];
   result [i][j] = sum;
}
    }
    return result;
}
//
//   This file contains the C++ code from Program 5.1 of
//   "Data Structures and Algorithms
//    with Object-Oriented Design Patterns in C++"
//   by Bruno R. Preiss.
//
//   Copyright (c) 1998 by Bruno R. Preiss, P.Eng.  All rights reserved.
//
//   http://www.pads.uwaterloo.ca/Bruno.Preiss/books/opus4/programs/pgm05_01.cpp
//
class Object
{
protected:
    virtual int CompareTo (Object const&) const = 0;
public:
    virtual ~Object ();
    virtual bool IsNull () const;
    virtual int Compare (Object const&) const;
    virtual HashValue Hash () const = 0;
    virtual void Put (ostream&) const = 0;
};
//
//   This file contains the C++ code from Program 5.2 of
//   "Data Structures and Algorithms
//    with Object-Oriented Design Patterns in C++"
//   by Bruno R. Preiss.
//
//   Copyright (c) 1998 by Bruno R. Preiss, P.Eng.  All rights reserved.
//
//   http://www.pads.uwaterloo.ca/Bruno.Preiss/books/opus4/programs/pgm05_02.cpp
//
inline bool operator == (Object const& left, Object const& right)
    { return left.Compare (right) == 0; }

inline bool operator != (Object const& left, Object const& right)
    { return left.Compare (right) != 0; }

inline bool operator <= (Object const& left, Object const& right)
    { return left.Compare (right) <= 0; }

inline bool operator <  (Object const& left, Object const& right)
    { return left.Compare (right) <  0; }

inline bool operator >= (Object const& left, Object const& right)
    { return left.Compare (right) >= 0; }

inline bool operator >  (Object const& left, Object const& right)
    { return left.Compare (right) >  0; }

inline ostream& operator << (ostream& s, Object const& object)
    { object.Put (s); return s; }
//
//   This file contains the C++ code from Program 5.3 of
//   "Data Structures and Algorithms
//    with Object-Oriented Design Patterns in C++"
//   by Bruno R. Preiss.
//
//   Copyright (c) 1998 by Bruno R. Preiss, P.Eng.  All rights reserved.
//
//   http://www.pads.uwaterloo.ca/Bruno.Preiss/books/opus4/programs/pgm05_03.cpp
//
#include <typeinfo>

Object::~Object ()
    {}

bool Object::IsNull () const
    { return false; }

int Object::Compare (Object const& object) const
{
    if (typeid (*this) == typeid (object))
return CompareTo (object);
    else if (typeid (*this).before (typeid (object)))
return -1;
    else
return 1;
}
//
//   This file contains the C++ code from Program 5.4 of
//   "Data Structures and Algorithms
//    with Object-Oriented Design Patterns in C++"
//   by Bruno R. Preiss.
//
//   Copyright (c) 1998 by Bruno R. Preiss, P.Eng.  All rights reserved.
//
//   http://www.pads.uwaterloo.ca/Bruno.Preiss/books/opus4/programs/pgm05_04.cpp
//
class NullObject : public Object
{
    static NullObject instance;

    NullObject ();
protected:
    int CompareTo (Object const&) const;
public:
    bool IsNull () const;
    HashValue Hash () const;
    void Put (ostream& s) const;

    static NullObject& Instance ();
};
//
//   This file contains the C++ code from Program 5.5 of
//   "Data Structures and Algorithms
//    with Object-Oriented Design Patterns in C++"
//   by Bruno R. Preiss.
//
//   Copyright (c) 1998 by Bruno R. Preiss, P.Eng.  All rights reserved.
//
//   http://www.pads.uwaterloo.ca/Bruno.Preiss/books/opus4/programs/pgm05_05.cpp
//
NullObject NullObject::instance;

NullObject::NullObject ()
    {}

bool NullObject::IsNull () const
    { return true; }

int NullObject::CompareTo (Object const&) const
    { return 0; } 

HashValue NullObject::Hash () const
    { return 0; }

void NullObject::Put (ostream& s) const
    { s << "NullObject"; }

NullObject& NullObject::Instance ()
    { return instance; }
//
//   This file contains the C++ code from Program 5.6 of
//   "Data Structures and Algorithms
//    with Object-Oriented Design Patterns in C++"
//   by Bruno R. Preiss.
//
//   Copyright (c) 1998 by Bruno R. Preiss, P.Eng.  All rights reserved.
//
//   http://www.pads.uwaterloo.ca/Bruno.Preiss/books/opus4/programs/pgm05_06.cpp
//
template <class T>
class Wrapper : public Object
{
protected:
    T datum;

    int CompareTo (Object const&) const;
public:
    Wrapper ();
    Wrapper (T const&);
    Wrapper& operator = (T const&);
    operator T const& () const;
    HashValue Hash () const;
    void Put (ostream&) const;
};
//
//   This file contains the C++ code from Program 5.7 of
//   "Data Structures and Algorithms
//    with Object-Oriented Design Patterns in C++"
//   by Bruno R. Preiss.
//
//   Copyright (c) 1998 by Bruno R. Preiss, P.Eng.  All rights reserved.
//
//   http://www.pads.uwaterloo.ca/Bruno.Preiss/books/opus4/programs/pgm05_07.cpp
//
template <class T>
Wrapper<T>::Wrapper () :
    datum ()
    {}

template <class T>
Wrapper<T>::Wrapper (T const& d) :
    datum (d)
    {}

template <class T>
Wrapper<T>& Wrapper<T>::operator = (T const& d)
{
    datum = d;
    return *this;
}

template <class T>
Wrapper<T>::operator T const& () const
    { return datum; }

template <class T>
int Wrapper<T>::CompareTo (Object const& obj) const
{
    Wrapper<T> const& arg =
dynamic_cast<Wrapper<T> const&> (obj);
    return ::Compare (datum, arg.datum);
}

template <class T>
void Wrapper<T>::Put (ostream& s) const
    { s << datum; }
//
//   This file contains the C++ code from Program 5.8 of
//   "Data Structures and Algorithms
//    with Object-Oriented Design Patterns in C++"
//   by Bruno R. Preiss.
//
//   Copyright (c) 1998 by Bruno R. Preiss, P.Eng.  All rights reserved.
//
//   http://www.pads.uwaterloo.ca/Bruno.Preiss/books/opus4/programs/pgm05_08.cpp
//
typedef Wrapper<int> Int;
typedef Wrapper<char> Char;
typedef Wrapper<double> Double;
typedef Wrapper<std::string> String;
//
//   This file contains the C++ code from Program 5.9 of
//   "Data Structures and Algorithms
//    with Object-Oriented Design Patterns in C++"
//   by Bruno R. Preiss.
//
//   Copyright (c) 1998 by Bruno R. Preiss, P.Eng.  All rights reserved.
//
//   http://www.pads.uwaterloo.ca/Bruno.Preiss/books/opus4/programs/pgm05_09.cpp
//
class Container : public virtual Object, public virtual Ownership
{
protected:
    unsigned int count;

    Container ();
public:
    virtual unsigned int Count () const;
    virtual bool IsEmpty () const;
    virtual bool IsFull () const;
    virtual HashValue Hash () const;
    virtual void Put (ostream&) const;
    virtual Iterator& NewIterator () const;

    virtual void Purge () = 0;
    virtual void Accept (Visitor&) const = 0;
};
//
//   This file contains the C++ code from Program 5.10 of
//   "Data Structures and Algorithms
//    with Object-Oriented Design Patterns in C++"
//   by Bruno R. Preiss.
//
//   Copyright (c) 1998 by Bruno R. Preiss, P.Eng.  All rights reserved.
//
//   http://www.pads.uwaterloo.ca/Bruno.Preiss/books/opus4/programs/pgm05_10.cpp
//
Container::Container () :
    count (0)
    {}

unsigned int Container::Count () const
    { return count; }

bool Container::IsEmpty () const
    { return Count () == 0; }

bool Container::IsFull () const
    { return false; }
//
//   This file contains the C++ code from Program 5.11 of
//   "Data Structures and Algorithms
//    with Object-Oriented Design Patterns in C++"
//   by Bruno R. Preiss.
//
//   Copyright (c) 1998 by Bruno R. Preiss, P.Eng.  All rights reserved.
//
//   http://www.pads.uwaterloo.ca/Bruno.Preiss/books/opus4/programs/pgm05_11.cpp
//
class Visitor
{
public:
    virtual void Visit (Object&) = 0;
    virtual bool IsDone () const
{ return false; }
};
//
//   This file contains the C++ code from Program 5.12 of
//   "Data Structures and Algorithms
//    with Object-Oriented Design Patterns in C++"
//   by Bruno R. Preiss.
//
//   Copyright (c) 1998 by Bruno R. Preiss, P.Eng.  All rights reserved.
//
//   http://www.pads.uwaterloo.ca/Bruno.Preiss/books/opus4/programs/pgm05_12.cpp
//
#include <typeinfo>

class PuttingVisitor : public Visitor
{
    ostream& stream;
    bool comma;
public:
    PuttingVisitor (ostream& s) : stream (s), comma (false)
{}
    void Visit (Object& object)
    {
if (comma)
   stream << ", ";
stream << object;
comma = true;
    }
};

void Container::Put (ostream& s) const
{
    PuttingVisitor visitor (s);

    s << typeid (*this).name () << " {";
    Accept (visitor);
    s << "}";
}
//
//   This file contains the C++ code from Program 5.13 of
//   "Data Structures and Algorithms
//    with Object-Oriented Design Patterns in C++"
//   by Bruno R. Preiss.
//
//   Copyright (c) 1998 by Bruno R. Preiss, P.Eng.  All rights reserved.
//
//   http://www.pads.uwaterloo.ca/Bruno.Preiss/books/opus4/programs/pgm05_13.cpp
//
class Iterator
{
public:
    virtual ~Iterator ();
    virtual void Reset () = 0;
    virtual bool IsDone () const = 0;
    virtual Object& operator * () const = 0;
    virtual void operator ++ () = 0;
};
//
//   This file contains the C++ code from Program 5.14 of
//   "Data Structures and Algorithms
//    with Object-Oriented Design Patterns in C++"
//   by Bruno R. Preiss.
//
//   Copyright (c) 1998 by Bruno R. Preiss, P.Eng.  All rights reserved.
//
//   http://www.pads.uwaterloo.ca/Bruno.Preiss/books/opus4/programs/pgm05_14.cpp
//
class NullIterator : public Iterator
{
public:
    NullIterator ();
    void Reset ();
    bool IsDone () const;
    Object& operator * () const;
    void operator ++ ();
};
//
//   This file contains the C++ code from Program 5.15 of
//   "Data Structures and Algorithms
//    with Object-Oriented Design Patterns in C++"
//   by Bruno R. Preiss.
//
//   Copyright (c) 1998 by Bruno R. Preiss, P.Eng.  All rights reserved.
//
//   http://www.pads.uwaterloo.ca/Bruno.Preiss/books/opus4/programs/pgm05_15.cpp
//
NullIterator::NullIterator ()
    {}

void NullIterator::Reset ()
    {}

bool NullIterator::IsDone () const
    { return true; }

Object& NullIterator::operator * () const
    { return NullObject::Instance (); }

void NullIterator::operator ++ ()
    {}
//
//   This file contains the C++ code from Program 5.16 of
//   "Data Structures and Algorithms
//    with Object-Oriented Design Patterns in C++"
//   by Bruno R. Preiss.
//
//   Copyright (c) 1998 by Bruno R. Preiss, P.Eng.  All rights reserved.
//
//   http://www.pads.uwaterloo.ca/Bruno.Preiss/books/opus4/programs/pgm05_16.cpp
//
Iterator& Container::NewIterator () const
    { return *new NullIterator (); }
//
//   This file contains the C++ code from Program 5.17 of
//   "Data Structures and Algorithms
//    with Object-Oriented Design Patterns in C++"
//   by Bruno R. Preiss.
//
//   Copyright (c) 1998 by Bruno R. Preiss, P.Eng.  All rights reserved.
//
//   http://www.pads.uwaterloo.ca/Bruno.Preiss/books/opus4/programs/pgm05_17.cpp
//
class Ownership
{
    bool isOwner;
protected:
    Ownership () : isOwner (true)
{}
    Ownership (Ownership& arg) : isOwner (arg.isOwner)
{ arg.isOwner = false; }
public:
    void AssertOwnership ()
{ isOwner = true; }
    void RescindOwnership ()
{ isOwner = false; }
    bool IsOwner () const
{ return isOwner; }
};
//
//   This file contains the C++ code from Program 5.18 of
//   "Data Structures and Algorithms
//    with Object-Oriented Design Patterns in C++"
//   by Bruno R. Preiss.
//
//   Copyright (c) 1998 by Bruno R. Preiss, P.Eng.  All rights reserved.
//
//   http://www.pads.uwaterloo.ca/Bruno.Preiss/books/opus4/programs/pgm05_18.cpp
//
class Association : public Object, public Ownership
{
protected:
    Object* key;
    Object* value;

    int CompareTo (Object const&) const;
public:
    Association (Object&);
    Association (Object&, Object&);
    ~Association ();

    Object& Key () const;
    Object& Value () const;

    HashValue Hash () const;
    void Put (ostream&) const;
};
//
//   This file contains the C++ code from Program 5.19 of
//   "Data Structures and Algorithms
//    with Object-Oriented Design Patterns in C++"
//   by Bruno R. Preiss.
//
//   Copyright (c) 1998 by Bruno R. Preiss, P.Eng.  All rights reserved.
//
//   http://www.pads.uwaterloo.ca/Bruno.Preiss/books/opus4/programs/pgm05_19.cpp
//
Association::Association (Object& _key) :
    key (&_key),
    value (0)
    {}

Association::Association (Object& _key, Object& _value) :
    key (&_key),
    value (&_value)
    {}

Association::~Association ()
{
    if (IsOwner ())
    {
delete key;
delete value;
    }
}
//
//   This file contains the C++ code from Program 5.21 of
//   "Data Structures and Algorithms
//    with Object-Oriented Design Patterns in C++"
//   by Bruno R. Preiss.
//
//   Copyright (c) 1998 by Bruno R. Preiss, P.Eng.  All rights reserved.
//
//   http://www.pads.uwaterloo.ca/Bruno.Preiss/books/opus4/programs/pgm05_21.cpp
//
class SearchableContainer : public virtual Container
{
public:
    virtual bool IsMember (Object const&) const = 0;
    virtual void Insert (Object&) = 0;
    virtual void Withdraw (Object&) = 0;
    virtual Object& Find (Object const&) const = 0;
};
//
//   This file contains the C++ code from Program 6.2 of
//   "Data Structures and Algorithms
//    with Object-Oriented Design Patterns in C++"
//   by Bruno R. Preiss.
//
//   Copyright (c) 1998 by Bruno R. Preiss, P.Eng.  All rights reserved.
//
//   http://www.pads.uwaterloo.ca/Bruno.Preiss/books/opus4/programs/pgm06_02.cpp
//
class StackAsArray : public Stack
{
    Array<Object*> array;

    class Iter;
public:
    StackAsArray (unsigned int);
    // ...
    friend class Iter;
};

class StackAsArray::Iter : public Iterator
{
    StackAsArray const& stack;
    unsigned int position;
public:
    Iter (StackAsArray const&);
    // ...
};





//
//   This file contains the C++ code from Program 6.3 of
//   "Data Structures and Algorithms
//    with Object-Oriented Design Patterns in C++"
//   by Bruno R. Preiss.
//
//   Copyright (c) 1998 by Bruno R. Preiss, P.Eng.  All rights reserved.
//
//   http://www.pads.uwaterloo.ca/Bruno.Preiss/books/opus4/programs/pgm06_03.cpp
//
StackAsArray::StackAsArray (unsigned int size) :
    array (size)
    {}

void StackAsArray::Purge ()
{
    if (IsOwner ())
    {
for (unsigned int i = 0; i < count; ++i)
   delete array [i];
    }
    count = 0;
}

StackAsArray::~StackAsArray ()
    { Purge (); }
//
//   This file contains the C++ code from Program 6.4 of
//   "Data Structures and Algorithms
//    with Object-Oriented Design Patterns in C++"
//   by Bruno R. Preiss.
//
//   Copyright (c) 1998 by Bruno R. Preiss, P.Eng.  All rights reserved.
//
//   http://www.pads.uwaterloo.ca/Bruno.Preiss/books/opus4/programs/pgm06_04.cpp
//
void StackAsArray::Push (Object& object)
{
    if (count == array.Length ())
throw domain_error ("stack is full");
    array [count++] = &object;
}

Object& StackAsArray::Pop ()
{
    if (count == 0)
throw domain_error ("stack is empty");
    return *array [--count];
}

Object& StackAsArray::Top () const
{
    if (count == 0)
throw domain_error ("stack is empty");
    return *array [count - 1U];
}
//
//   This file contains the C++ code from Program 6.5 of
//   "Data Structures and Algorithms
//    with Object-Oriented Design Patterns in C++"
//   by Bruno R. Preiss.
//
//   Copyright (c) 1998 by Bruno R. Preiss, P.Eng.  All rights reserved.
//
//   http://www.pads.uwaterloo.ca/Bruno.Preiss/books/opus4/programs/pgm06_05.cpp
//
void StackAsArray::Accept (Visitor& visitor) const
{
    for (unsigned int i = 0;
i < count && !visitor.IsDone (); ++i)
    {
visitor.Visit (*array [i]);
    }
}
//
//   This file contains the C++ code from Program 6.6 of
//   "Data Structures and Algorithms
//    with Object-Oriented Design Patterns in C++"
//   by Bruno R. Preiss.
//
//   Copyright (c) 1998 by Bruno R. Preiss, P.Eng.  All rights reserved.
//
//   http://www.pads.uwaterloo.ca/Bruno.Preiss/books/opus4/programs/pgm06_06.cpp
//
StackAsArray::Iter::Iter (StackAsArray const& _stack) :
    stack (_stack)
    { Reset (); }

bool StackAsArray::Iter::IsDone () const
    { return position >= stack.count; }

Object& StackAsArray::Iter::operator * () const
{
    if (position < stack.count)
return *stack.array [position];
    else
return NullObject::Instance ();
}

void StackAsArray::Iter::operator ++ ()
{
    if (position < stack.count)
++position;
}

void StackAsArray::Iter::Reset ()
    { position = 0; }
//
//   This file contains the C++ code from Program 6.7 of
//   "Data Structures and Algorithms
//    with Object-Oriented Design Patterns in C++"
//   by Bruno R. Preiss.
//
//   Copyright (c) 1998 by Bruno R. Preiss, P.Eng.  All rights reserved.
//
//   http://www.pads.uwaterloo.ca/Bruno.Preiss/books/opus4/programs/pgm06_07.cpp
//
class StackAsLinkedList : public Stack
{
    LinkedList<Object*> list;

    class Iter;
public:
    StackAsLinkedList ();
    // ...
    friend class Iter;
};

class StackAsLinkedList::Iter : public Iterator
{
    StackAsLinkedList const& stack;
    ListElement<Object*> const* position;
public:
    Iter (StackAsLinkedList const&);
    // ...
};
//
//   This file contains the C++ code from Program 6.8 of
//   "Data Structures and Algorithms
//    with Object-Oriented Design Patterns in C++"
//   by Bruno R. Preiss.
//
//   Copyright (c) 1998 by Bruno R. Preiss, P.Eng.  All rights reserved.
//
//   http://www.pads.uwaterloo.ca/Bruno.Preiss/books/opus4/programs/pgm06_08.cpp
//
StackAsLinkedList::StackAsLinkedList () :
    list ()
    {}

void StackAsLinkedList::Purge ()
{
    if (IsOwner ())
    {
ListElement<Object*> const* ptr;

for (ptr = list.Head (); ptr != 0; ptr = ptr->Next ())
   delete ptr->Datum ();
    }
    list.Purge ();
    count = 0;
}

StackAsLinkedList::~StackAsLinkedList ()
    { Purge (); }
//
//   This file contains the C++ code from Program 6.9 of
//   "Data Structures and Algorithms
//    with Object-Oriented Design Patterns in C++"
//   by Bruno R. Preiss.
//
//   Copyright (c) 1998 by Bruno R. Preiss, P.Eng.  All rights reserved.
//
//   http://www.pads.uwaterloo.ca/Bruno.Preiss/books/opus4/programs/pgm06_09.cpp
//
void StackAsLinkedList::Push (Object& object)
{
    list.Prepend (&object);
    ++count;
}

Object& StackAsLinkedList::Pop ()
{
    if (count == 0)
throw domain_error ("stack is empty");
    Object& const result = *list.First ();
    list.Extract (&result);
    --count;
    return result;
}

Object& StackAsLinkedList::Top () const
{
    if (count == 0)
throw domain_error ("stack is empty");
    return *list.First ();
}
//
//   This file contains the C++ code from Program 6.10 of
//   "Data Structures and Algorithms
//    with Object-Oriented Design Patterns in C++"
//   by Bruno R. Preiss.
//
//   Copyright (c) 1998 by Bruno R. Preiss, P.Eng.  All rights reserved.
//
//   http://www.pads.uwaterloo.ca/Bruno.Preiss/books/opus4/programs/pgm06_10.cpp
//
void StackAsLinkedList::Accept (Visitor& visitor) const
{
    ListElement<Object*> const* ptr;

    for (ptr = list.Head ();
ptr != 0 && !visitor.IsDone (); ptr = ptr->Next ())
    {
visitor.Visit (*ptr->Datum ());
    }
}
//
//   This file contains the C++ code from Program 6.11 of
//   "Data Structures and Algorithms
//    with Object-Oriented Design Patterns in C++"
//   by Bruno R. Preiss.
//
//   Copyright (c) 1998 by Bruno R. Preiss, P.Eng.  All rights reserved.
//
//   http://www.pads.uwaterloo.ca/Bruno.Preiss/books/opus4/programs/pgm06_11.cpp
//
StackAsLinkedList::Iter::Iter (
    StackAsLinkedList const& _stack) :
    stack (_stack)
    { Reset (); }

bool StackAsLinkedList::Iter::IsDone () const
    { return position == 0; }

Object& StackAsLinkedList::Iter::operator * () const
{
    if (position != 0)
return *position->Datum ();
    else
return NullObject::Instance ();
}

void StackAsLinkedList::Iter::operator ++ ()
{
    if (position != 0)
position = position->Next ();
}

void StackAsLinkedList::Iter::Reset ()
    { position = stack.list.Head (); }
//
//   This file contains the C++ code from Program 6.12 of
//   "Data Structures and Algorithms
//    with Object-Oriented Design Patterns in C++"
//   by Bruno R. Preiss.
//
//   Copyright (c) 1998 by Bruno R. Preiss, P.Eng.  All rights reserved.
//
//   http://www.pads.uwaterloo.ca/Bruno.Preiss/books/opus4/programs/pgm06_12.cpp
//
void RPNCalculator (Stack& stack)
{
    char c;
    while (cin >> c, !cin.eof ())
    {
if (std::isdigit (c))
   stack.Push (*new Int (c - '0'));
else if (c == '+')
{
   Int& arg2 = dynamic_cast<Int&> (stack.Pop ());
   Int& arg1 = dynamic_cast<Int&> (stack.Pop ());
   stack.Push (*new Int (arg1 + arg2));
   delete &arg1;
   delete &arg2;
}
else if (c == '*')
{
   Int& arg2 = dynamic_cast<Int&> (stack.Pop ());
   Int& arg1 = dynamic_cast<Int&> (stack.Pop ());
   stack.Push (*new Int (arg1 * arg2));
   delete &arg1;
   delete &arg2;
}
else if (c == '=')
{
   Int& arg = dynamic_cast<Int&> (stack.Pop ());
   cout << arg << endl;
   delete &arg;
}
    }
}
//
//   This file contains the C++ code from Program 6.13 of
//   "Data Structures and Algorithms
//    with Object-Oriented Design Patterns in C++"
//   by Bruno R. Preiss.
//
//   Copyright (c) 1998 by Bruno R. Preiss, P.Eng.  All rights reserved.
//
//   http://www.pads.uwaterloo.ca/Bruno.Preiss/books/opus4/programs/pgm06_13.cpp
//
class Queue : public virtual Container
{
public:
    virtual Object& Head () const = 0;
    virtual void Enqueue (Object&) = 0;
    virtual Object& Dequeue () = 0;
};
//
//   This file contains the C++ code from Program 6.14 of
//   "Data Structures and Algorithms
//    with Object-Oriented Design Patterns in C++"
//   by Bruno R. Preiss.
//
//   Copyright (c) 1998 by Bruno R. Preiss, P.Eng.  All rights reserved.
//
//   http://www.pads.uwaterloo.ca/Bruno.Preiss/books/opus4/programs/pgm06_14.cpp
//
class QueueAsArray : public virtual Queue
{
protected:
    Array<Object*> array;
    unsigned int head;
    unsigned int tail;
public:
    QueueAsArray (unsigned int);
    ~QueueAsArray ();
    // ...
};
//
//   This file contains the C++ code from Program 6.15 of
//   "Data Structures and Algorithms
//    with Object-Oriented Design Patterns in C++"
//   by Bruno R. Preiss.
//
//   Copyright (c) 1998 by Bruno R. Preiss, P.Eng.  All rights reserved.
//
//   http://www.pads.uwaterloo.ca/Bruno.Preiss/books/opus4/programs/pgm06_15.cpp
//
QueueAsArray::QueueAsArray (unsigned int size) :
    array (size),
    head (0),
    tail (size - 1U)
    {}

void QueueAsArray::Purge ()
{
    if (IsOwner ())
    {
for (unsigned int i = 0; i < count; ++i)
{
   delete array [head];
   if (++head == array.Length ())
head = 0;
}
    }
    count = 0;
}

QueueAsArray::~QueueAsArray ()
    { Purge (); }
//
//   This file contains the C++ code from Program 6.16 of
//   "Data Structures and Algorithms
//    with Object-Oriented Design Patterns in C++"
//   by Bruno R. Preiss.
//
//   Copyright (c) 1998 by Bruno R. Preiss, P.Eng.  All rights reserved.
//
//   http://www.pads.uwaterloo.ca/Bruno.Preiss/books/opus4/programs/pgm06_16.cpp
//
Object& QueueAsArray::Head () const
{
    if (count == 0)
throw domain_error ("queue is empty");
    return *array [head];
}

void QueueAsArray::Enqueue (Object& object)
{
    if (count == array.Length ())
throw domain_error ("queue is full");
    if (++tail == array.Length ())
tail = 0;
    array [tail] = &object;
    ++count;
}

Object& QueueAsArray::Dequeue ()
{
    if (count == 0)
throw domain_error ("queue is empty");
    Object& result = *array [head];
    if (++head == array.Length ())
head = 0;
    --count;
    return result;
}
//
//   This file contains the C++ code from Program 6.17 of
//   "Data Structures and Algorithms
//    with Object-Oriented Design Patterns in C++"
//   by Bruno R. Preiss.
//
//   Copyright (c) 1998 by Bruno R. Preiss, P.Eng.  All rights reserved.
//
//   http://www.pads.uwaterloo.ca/Bruno.Preiss/books/opus4/programs/pgm06_17.cpp
//
class QueueAsLinkedList : public virtual Queue
{
protected:
    LinkedList<Object*> list;
public:
    QueueAsLinkedList ();
    ~QueueAsLinkedList ();
    // ...
};
//
//   This file contains the C++ code from Program 6.18 of
//   "Data Structures and Algorithms
//    with Object-Oriented Design Patterns in C++"
//   by Bruno R. Preiss.
//
//   Copyright (c) 1998 by Bruno R. Preiss, P.Eng.  All rights reserved.
//
//   http://www.pads.uwaterloo.ca/Bruno.Preiss/books/opus4/programs/pgm06_18.cpp
//
QueueAsLinkedList::QueueAsLinkedList () :
    list ()
    {}

void QueueAsLinkedList::Purge ()
{
    if (IsOwner ())
    {
ListElement<Object*> const* ptr;

for (ptr = list.Head (); ptr != 0; ptr = ptr->Next ())
   delete ptr->Datum ();
    }
    list.Purge ();
    count = 0;
}

QueueAsLinkedList::~QueueAsLinkedList ()
    { Purge (); }
//
//   This file contains the C++ code from Program 6.19 of
//   "Data Structures and Algorithms
//    with Object-Oriented Design Patterns in C++"
//   by Bruno R. Preiss.
//
//   Copyright (c) 1998 by Bruno R. Preiss, P.Eng.  All rights reserved.
//
//   http://www.pads.uwaterloo.ca/Bruno.Preiss/books/opus4/programs/pgm06_19.cpp
//
Object& QueueAsLinkedList::Head () const
{
    if (count == 0)
throw domain_error ("queue is empty");
    return *list.First ();
}

void QueueAsLinkedList::Enqueue (Object& object)
{
    list.Append (&object);
    ++count;
}

Object& QueueAsLinkedList::Dequeue ()
{
    if (count == 0)
throw domain_error ("queue is empty");
    Object& result = *list.First ();
    list.Extract (&result);
    --count;
    return result;
}

Comentarii

Postări populare de pe acest blog

WINDOWS 10 COMPUTER FREEZING PROBLEM SOLVED

good news : a BIOS UPDATE can resolve the problem but just for a Windows 7 on 64 bits o.s. and the system is not stable all the time. even after  bios update the system can freeze.
new info : u can try to low the screen brightness and see if this error appear so often after 
news: last info !!! maybe a virus. scann our system now with an antivirus i generate this error using other device ( a tablet pc) connected in the same network and the laptop i have this problem just freeze  http://thehackernews.com/2013/10/backdoor-found-in-chinese-tenda.html

news : if u use a tenda router this make couse all this problems



what i discover so far :
1.the electric company have many failure and affect the main ISP router/switch for building  also the router/switch installed by the ISP may be affected by overheating and will crash after a long utilisation on heat conditions 2.the router/switch of ISP affect any router of the user between this router and pc/laptop of client 3.the router and any other device of t…

program principal cpp

#include "clasa.h" #include <stdio.h> #include <conio.h> #include <stdlib.h> #include <string.h> #define DELAY 9000000 void delay() { for(long i=0;i<DELAY;i++); } //constructor cu initializare de la tastatura BigInt::BigInt() {char x; signed char t[400]; int i; printf("\nNumarul cu semn "); do s=getche(); while((s!='+')&&(s!='-')); n=0; do {x=getche(); t[n]=x-'0'; n++; } while((x>='0')&&(x<='9')); n--; for(i=0;i<n;i++) nr[i]=t[n-i-1]; } //constructor cu initializare prin parametri BigInt::BigInt(char semn,signed char numar[],int dim) {int i; s=semn; n=dim; for(i=0;i<n;i++) nr[i]=numar[n-i-1]; } //transform un int negativ in pozitiv int BigInt::Pozitiv(int x) {int a,vb; a=0; vb=0; while(vb==0) if((x+a)==0) vb=1; else a=a+1; x=a; return x; } //constructor dintr-un nr int obisnuit BigInt::BigInt(int x) {int i; if(x>=0) s='+'…

o aplicatie php localitati romania

//APLICATIA SE REFERA LA BAZA DE DATE SIRUTA

//dragtable.js


/* dragtable v1.0 June 26, 2008 Dan Vanderkam, http://danvk.org/dragtable/ http://code.google.com/p/dragtable/ \Bsortabledraggable\B Instructions: - Download this file - Add <script src="dragtable.js"></script> to your HTML. - Add class="draggable" to any table you might like to reorder. - Drag the headers around to reorder them. This is code was based on: - Stuart Langridge's SortTable (kryogenix.org/code/browser/sorttable) - Mike Hall's draggable class (http://www.brainjar.com/dhtml/drag/) - A discussion of permuting table columns on comp.lang.javascript Licensed under the MIT license. */ // Here's the notice from Mike Hall's draggable script: //***************************************************************************** // Do not remove this notice. // // Copyright 2001 by Mike Hall. // See http…