Treceți la conținutul principal

ALGORITMI CPP CODE 2


//
//   This file contains the C++ code from Program 6.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/pgm06_20.cpp
//
void BreadthFirstTraversal (NaryTree& tree)
{
    Queue& queue = *new QueueAsLinkedList ();
    queue.Enqueue (tree);
    while (!queue.IsEmpty ())
    {
NaryTree& t =
   dynamic_cast<NaryTree&> (queue.Dequeue ());
cout << t.Key () << endl;
for (unsigned int i = 0; i < t.Degree (); ++i)
{
   NaryTree& subTree = t.Subtree (i);
   queue.Enqueue (subTree);
}
    }
    delete &queue;
}
//
//   This file contains the C++ code from Program 6.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/pgm06_21.cpp
//
class Deque : public virtual Queue
{
public:
    virtual Object& Head () const = 0;
    virtual Object& Tail () const = 0;
    virtual void Enqueue (Object&);
    virtual void EnqueueHead (Object&) = 0;
    virtual void EnqueueTail (Object&) = 0;
    virtual Object& Dequeue ();
    virtual Object& DequeueHead () = 0;
    virtual Object& DequeueTail () = 0;
};
//
//   This file contains the C++ code from Program 6.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/pgm06_22.cpp
//
void Deque::Enqueue (Object& object)
    { EnqueueTail (object); }

Object& Deque::Dequeue ()
    { return DequeueHead (); }
//
//   This file contains the C++ code from Program 6.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/pgm06_23.cpp
//
class DequeAsArray : public Deque, public QueueAsArray
{
public:
    DequeAsArray (unsigned int);
    // ...
};
//
//   This file contains the C++ code from Program 6.24 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_24.cpp
//
Object& DequeAsArray::Head () const
    { return QueueAsArray::Head (); }

void DequeAsArray::EnqueueTail (Object& object)
    { QueueAsArray::Enqueue (object); }

Object& DequeAsArray::DequeueHead ()
    { return QueueAsArray::Dequeue (); }
//
//   This file contains the C++ code from Program 6.25 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_25.cpp
//
Object& DequeAsArray::Tail () const
{
    if (count == 0)
throw domain_error ("deque is empty");
    return *array [tail];
}

void DequeAsArray::EnqueueHead (Object& object)
{
    if (count == array.Length ())
throw domain_error ("deque is full");
    if (head-- == 0)
head = array.Length () - 1U;
    array [head] = &object;
    ++count;
}


Object& DequeAsArray::DequeueTail ()
{
    if (count == 0)
throw domain_error ("deque is empty");
    Object& result = *array [tail];
    if (tail-- == 0)
tail = array.Length () - 1U;
    --count;
    return result;
}
//
//   This file contains the C++ code from Program 6.26 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_26.cpp
//
class DequeAsLinkedList : public Deque, public QueueAsLinkedList
{
public:
    DequeAsLinkedList ();
    // ...
};
//
//   This file contains the C++ code from Program 6.27 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_27.cpp
//
Object& DequeAsLinkedList::Head () const
    { return QueueAsLinkedList::Head (); }

void DequeAsLinkedList::EnqueueTail (Object& object)
    { QueueAsLinkedList::Enqueue (object); }

Object& DequeAsLinkedList::DequeueHead ()
    { return QueueAsLinkedList::Dequeue (); }
//
//   This file contains the C++ code from Program 6.28 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_28.cpp
//
Object& DequeAsLinkedList::Tail () const
{
    if (count == 0)
throw domain_error ("deque is empty");
    return *list.Last ();
}

void DequeAsLinkedList::EnqueueHead (Object& object)
{
    list.Prepend (&object);
    ++count;
}

Object& DequeAsLinkedList::DequeueTail ()
{
    if (count == 0)
throw domain_error ("deque is empty");
    Object& result = *list.Last ();
    list.Extract (&result);
    --count;
    return result;
}
//
//   This file contains the C++ code from Program 7.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/pgm07_01.cpp
//
class Position : public Iterator
{
};

class List : public virtual SearchableContainer
{
public:
    virtual Object& operator [] (unsigned int) const = 0;
    virtual Object& operator [] (Position const&) const = 0;
    virtual Position& FindPosition (Object const&) const = 0;
    virtual void Withdraw (Position const&) = 0;
};

class OrderedList : public virtual List
{
public:
    virtual void InsertAfter (Position const&, Object&) = 0;
    virtual void InsertBefore (Position const&, Object&) = 0;
};
//
//   This file contains the C++ code from Program 7.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/pgm07_02.cpp
//
class ListAsArray : public virtual OrderedList
{
protected:
    Array<Object*> array;

    class Pos;
public:
    ListAsArray (unsigned int);
    // ...
    friend class Pos;
};
//
//   This file contains the C++ code from Program 7.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/pgm07_03.cpp
//
ListAsArray::ListAsArray (unsigned int size) :
    array (size)
    {}

void ListAsArray::Insert (Object& object)
{
    if (count == array.Length ())
throw domain_error ("list is full");
    array [count] = &object;
    ++count;
}

Object& ListAsArray::operator [] (unsigned int offset) const
{
    if (offset >= count)
throw out_of_range ("invalid offset");
    return *array [offset];
}
//
//   This file contains the C++ code from Program 7.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/pgm07_04.cpp
//
bool ListAsArray::IsMember (Object const& object) const
{
    for (unsigned int i = 0; i < count; ++i)
if (array [i] == &object)
   return true;
    return false;
}

Object& ListAsArray::Find (Object const& object) const
{
    for (unsigned int i = 0; i < count; ++i)
if (*array [i] == object)
   return *array [i];
    return NullObject::Instance ();
}
//
//   This file contains the C++ code from Program 7.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/pgm07_05.cpp
//
void ListAsArray::Withdraw (Object& object)
{
    if (count == 0)
throw domain_error ("list is empty");
    unsigned int i = 0;
    while (i < count && array [i] != &object)
++i;
    if (i == count)
throw invalid_argument ("object not found");

    for ( ; i < count - 1U; ++i)
array [i] = array [i + 1];
    --count;
}
//
//   This file contains the C++ code from Program 7.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/pgm07_06.cpp
//
class ListAsArray::Pos : public Position
{
protected:
    ListAsArray const& list;
    unsigned int offset;
public:
    // ...
    friend class ListAsArray;
    friend class SortedListAsArray;
};
//
//   This file contains the C++ code from Program 7.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/pgm07_07.cpp
//
Position& ListAsArray::FindPosition (Object const& object) const
{
    unsigned int i = 0;
    while (i < count && *array [i] != object)
++i;
    return *new Pos (*this, i);
}

Object& ListAsArray::operator [] (Position const& arg) const
{
    Pos const& position = dynamic_cast<Pos const&> (arg);

    if (&position.list != this || position.offset >= count)
throw invalid_argument ("invalid position");
    return *array [position.offset];
}
//
//   This file contains the C++ code from Program 7.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/pgm07_08.cpp
//
void ListAsArray::InsertAfter (
    Position const& arg, Object& object)
{
    Pos const& position = dynamic_cast<Pos const&> (arg);

    if (count == array.Length ())
throw domain_error ("list is full");
    if (&position.list != this || position.offset >= count)
throw invalid_argument ("invalid position");

    unsigned int const insertPosition = position.offset + 1;

    for (unsigned int i = count; i > insertPosition; --i)
array [i] = array [i - 1U];
    array [insertPosition] = &object;
    ++count;
}
//
//   This file contains the C++ code from Program 7.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/pgm07_09.cpp
//
void ListAsArray::Withdraw (Position const& arg)
{
    Pos const& position = dynamic_cast<Pos const&> (arg);

    if (count == 0)
throw domain_error ("list is empty");
    if (&position.list != this || position.offset >= count)
throw invalid_argument ("invalid position");
    for (unsigned int i = position.offset; i < count-1U; ++i)
array [i] = array [i + 1];
    --count;
}
//
//   This file contains the C++ code from Program 7.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/pgm07_10.cpp
//
class ListAsLinkedList : public virtual OrderedList
{
protected:
    LinkedList<Object*> linkedList;

    class Pos;
public:
    ListAsLinkedList ();
    // ...
    friend class Pos;
};
//
//   This file contains the C++ code from Program 7.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/pgm07_11.cpp
//
ListAsLinkedList::ListAsLinkedList () :
    linkedList ()
    {}

void ListAsLinkedList::Insert (Object& object)
{
    linkedList.Append (&object);
    ++count;
}

Object& ListAsLinkedList::operator [] (unsigned int offset) const
{
    if (offset >= count)
throw out_of_range ("invalid offset");

    unsigned int i = 0;
    ListElement<Object*> const* ptr =
linkedList.Head ();
    while (i < offset && ptr != 0)
    {
ptr = ptr->Next ();
++i;
    }
    if (ptr == 0)
throw logic_error ("should never happen");
    return *ptr->Datum ();
}
//
//   This file contains the C++ code from Program 7.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/pgm07_12.cpp
//
bool ListAsLinkedList::IsMember (Object const& object) const
{
    ListElement<Object*> const* ptr;

    for (ptr = linkedList.Head (); ptr != 0; ptr = ptr->Next ())
if (ptr->Datum () == &object)
   return true;
    return false;
}

Object& ListAsLinkedList::Find (Object const& object) const
{
    ListElement<Object*> const* ptr;

    for (ptr = linkedList.Head (); ptr != 0; ptr = ptr->Next ())
if (*ptr->Datum () == object)
   return *ptr->Datum ();
    return NullObject::Instance ();
}
//
//   This file contains the C++ code from Program 7.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/pgm07_13.cpp
//
void ListAsLinkedList::Withdraw (Object& object)
{
    if (count == 0)
throw domain_error ("list is empty");
    linkedList.Extract (&object);
    --count;
}
//
//   This file contains the C++ code from Program 7.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/pgm07_14.cpp
//
class ListAsLinkedList::Pos : public Position
{
    ListAsLinkedList const& list;
    ListElement<Object*> const* element;
public:
    // ...
    friend class ListAsLinkedList;
};
//
//   This file contains the C++ code from Program 7.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/pgm07_16.cpp
//
void ListAsLinkedList::InsertAfter (
    Position const& arg, Object& object)
{
    Pos const& position = dynamic_cast<Pos const&> (arg);

    if (&position.list != this || position.element == 0)
throw invalid_argument ("invalid position");
    linkedList.InsertAfter (position.element, &object);
    ++count;
}
//
//   This file contains the C++ code from Program 7.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/pgm07_18.cpp
//
class Term : public Object
{
    double coefficient;
    unsigned int exponent;
public:
    Term (double, unsigned int);
    // ...
    int CompareTo (Object const&) const;
    void Differentiate ();
};

Term::Term (double _coefficient, unsigned int _exponent) :
    coefficient (_coefficient),
    exponent (_exponent)
    {}

int Term::CompareTo (Object const& object) const
{
    Term const& term = dynamic_cast<Term const&> (object);
    if (exponent == term.exponent)
return ::Compare (coefficient, term.coefficient);
    else
return exponent - term.exponent;
}

void Term::Differentiate ()
{
    if (exponent > 0)
    {
coefficient *= exponent;
exponent -= 1;
    }
    else
coefficient = 0;
}
//
//   This file contains the C++ code from Program 7.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/pgm07_19.cpp
//
class Polynomial : public ListAsLinkedList
{
public:
    void Differentiate ();
};

class DifferentiatingVisitor : public Visitor
{
public:
    void Visit (Object& object)
    {
Term& term = dynamic_cast<Term&> (object);
term.Differentiate ();
    }
};

void Polynomial::Differentiate ()
{
    DifferentiatingVisitor visitor;
    Accept (visitor);
    Object& zeroTerm = Find (Term (0, 0));
    if (!zeroTerm.IsNull ())
    {
Withdraw (zeroTerm);
delete &zeroTerm;
    }
}
//
//   This file contains the C++ code from Program 7.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/pgm07_20.cpp
//
class SortedList : public virtual List
{
};
//
//   This file contains the C++ code from Program 7.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/pgm07_21.cpp
//
class SortedListAsArray :
    public virtual SortedList, public virtual ListAsArray
{
    unsigned int FindOffset (Object const&) const;
public:
    SortedListAsArray (unsigned int);
    // ...
};
//
//   This file contains the C++ code from Program 7.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/pgm07_22.cpp
//
void SortedListAsArray::Insert (Object& object)
{
    if (count == array.Length ())
throw domain_error ("list is full");
    unsigned int i = count;
    while (i > 0 && *array [i - 1U] > object)
    {
array [i] = array [i - 1U];
--i;
    }
    array [i] = &object;
    ++count;
}
//
//   This file contains the C++ code from Program 7.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/pgm07_23.cpp
//
unsigned int SortedListAsArray::FindOffset (
    Object const& object) const
{
    int left = 0;
    int right = count - 1;

    while (left <= right)
    {
int const middle = (left + right) / 2;

if (object > *array [middle])
   left = middle + 1;
else if (object < *array [middle])
   right = middle - 1;
else
   return middle;
    }
    return count;
}
//
//   This file contains the C++ code from Program 7.24 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/pgm07_24.cpp
//
Object& SortedListAsArray::Find (Object const& object) const
{
    unsigned int const offset = FindOffset (object);

    if (offset < count)
return *array [offset];
    else
return NullObject::Instance ();
}

Position& SortedListAsArray::FindPosition (
    Object const& object) const
{
    Pos& result = *new Pos (*this);
    result.offset = FindOffset (object);
    return result;
}
//
//   This file contains the C++ code from Program 7.25 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/pgm07_25.cpp
//
void SortedListAsArray::Withdraw (Object& object)
{
    if (count == 0)
throw domain_error ("list is empty");

    unsigned int const offset = FindOffset (object);

    if (offset == count)
throw invalid_argument ("object not found");

    for (unsigned int i = offset; i < count - 1U; ++i)
array [i] = array [i + 1];
    --count;
}
//
//   This file contains the C++ code from Program 7.26 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/pgm07_26.cpp
//
class SortedListAsLinkedList :
    public virtual SortedList, public virtual ListAsLinkedList
{
public:
    SortedListAsLinkedList ();
    // ...
};
//
//   This file contains the C++ code from Program 7.27 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/pgm07_27.cpp
//
void SortedListAsLinkedList::Insert (Object& object)
{
    ListElement<Object*> const* prevPtr = 0;
    ListElement<Object*> const* ptr =
linkedList.Head ();
    while (ptr != 0 && *ptr->Datum () < object)
    {
prevPtr = ptr;
ptr = ptr->Next ();
    }
    if (prevPtr == 0)
linkedList.Prepend (&object);
    else
linkedList.InsertAfter (prevPtr, &object);
    ++count;
}
//
//   This file contains the C++ code from Program 7.28 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/pgm07_28.cpp
//
class Term : public Object
{
    double coefficient;
    unsigned int exponent;
public:
    // ...
    double Coefficient () const;
    unsigned int Exponent () const;
    friend Term operator + (Term const&, Term const&);
};

double Term::Coefficient () const
    { return coefficient; }

unsigned int Term::Exponent () const
    { return exponent; }

Term operator + (Term const& arg1, Term const& arg2)
{
    if (arg1.exponent != arg2.exponent)
throw domain_error ("unequal exponents");
    return Term (arg1.coefficient + arg2.coefficient,
arg1.exponent);
}
//
//   This file contains the C++ code from Program 7.29 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/pgm07_29.cpp
//
class Polynomial : public SortedListAsLinkedList
{
public:
    // ...
    friend Polynomial operator + (
Polynomial const&, Polynomial const&);
};
//
//   This file contains the C++ code from Program 7.30 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/pgm07_30.cpp
//
Polynomial operator + (
    Polynomial const& arg1, Polynomial const& arg2)
{
    Polynomial result;
    Iterator& pos1 = arg1.NewIterator ();
    Iterator& pos2 = arg2.NewIterator ();
    while (!pos1.IsDone () && !pos2.IsDone ())
    {
Term const& term1 = dynamic_cast<Term const&> (*pos1);
Term const& term2 = dynamic_cast<Term const&> (*pos2);
if (term1.Exponent () < term2.Exponent ())
{
   result.Insert (*new Term (term1));
   ++pos1;
}
else if (term1.Exponent () > term2.Exponent ())
{
   result.Insert (*new Term (term2));
   ++pos2;
}
else
{
   Term sum = term1 + term2;
   if (sum.Coefficient () != 0)
result.Insert (*new Term (sum));
   ++pos1;
   ++pos2;
}
    }
    while (!pos1.IsDone ())
    {
Term const& term1 = dynamic_cast<Term const&> (*pos1);
result.Insert (*new Term (term1));
++pos1;
    }
    while (!pos2.IsDone ())
    {
Term const& term2 = dynamic_cast<Term const&> (*pos2);
result.Insert (*new Term (term2));
++pos2;
    }
    delete &pos1;
    delete &pos2;
    return result;
}
//
//   This file contains the C++ code from Program 8.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/pgm08_01.cpp
//
typedef unsigned int HashValue;

HashValue Hash (char c)
    { return abs (c); }

HashValue Hash (int i)
    { return abs (i); }
//
//   This file contains the C++ code from Program 8.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/pgm08_02.cpp
//
HashValue Hash (double d)
{
    if (d == 0)
return 0;
    else
    {
int exponent;
double mantissa = std::frexp (d, &exponent);
return (2 * fabs (mantissa) - 1) * ~0U;
    }
}
//
//   This file contains the C++ code from Program 8.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/pgm08_03.cpp
//
unsigned int const shift = 6;
HashValue const mask = ~0U << (bitsizeof (HashValue) - shift);

HashValue Hash (std::string const& s)
{
    HashValue result = 0;
    for (unsigned int i = 0; s [i] != 0; ++i)
result = (result & mask) ^ (result << shift) ^ s [i];
    return result;
}



//
//   This file contains the C++ code from Program 8.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/pgm08_04.cpp
//
template <class T>
HashValue Wrapper<T>::Hash () const
    { return ::Hash (datum); }
//
//   This file contains the C++ code from Program 8.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/pgm08_05.cpp
//
class HashingVisitor : public Visitor
{
    HashValue value;
public:
    HashingVisitor (HashValue _value) : value (_value)
{}
    void Visit (Object& object)
{ value += object.Hash (); }
    HashValue Value () const
{ return value; }
};

HashValue Container::Hash () const
{
    HashingVisitor visitor (::Hash (typeid (*this).name ()));
    Accept (visitor);
    return visitor.Value ();
}
//
//   This file contains the C++ code from Program 8.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/pgm08_06.cpp
//
HashValue Association::Hash () const
    { return key->Hash (); }
//
//   This file contains the C++ code from Program 8.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/pgm08_07.cpp
//
class HashTable : public virtual SearchableContainer
{
protected:
    unsigned int length;
public:
    HashTable (unsigned int);
    virtual unsigned int H (Object const&) const;
};
//
//   This file contains the C++ code from Program 8.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/pgm08_08.cpp
//
HashTable::HashTable (unsigned int _length) :
    length (_length)
    {}

unsigned int HashTable::H (Object const& object) const
    { return object.Hash () % length; }
//
//   This file contains the C++ code from Program 8.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/pgm08_09.cpp
//
class ChainedHashTable : public HashTable
{
    Array<LinkedList<Object*> > array;
public:
    ChainedHashTable (unsigned int);
    // ...
};
//
//   This file contains the C++ code from Program 8.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/pgm08_10.cpp
//
ChainedHashTable::ChainedHashTable (unsigned int _length) :
    HashTable (_length),
    array (_length)
    {}

void ChainedHashTable::Purge ()
{
    for (unsigned int i = 0; i < length; ++i)
    {
if (IsOwner ())
{
   ListElement<Object*> const* ptr;

   for (ptr = array [i].Head ();
   ptr != 0; ptr = ptr->Next ())
delete ptr->Datum ();
}
array [i].Purge ();
    }
    count = 0;
}

ChainedHashTable::~ChainedHashTable ()
    { Purge (); }
//
//   This file contains the C++ code from Program 8.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/pgm08_11.cpp
//
void ChainedHashTable::Insert (Object& object)
{
    array [H (object)].Append (&object);
    ++count;
}

void ChainedHashTable::Withdraw (Object& object)
{
    array [H (object)].Extract (&object);
    --count;
}
//
//   This file contains the C++ code from Program 8.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/pgm08_12.cpp
//
Object& ChainedHashTable::Find (Object const& object) const
{
    ListElement<Object*> const* ptr;

    for (ptr = array [H (object)].Head ();
ptr != 0; ptr = ptr->Next())
    {
if (object == *ptr->Datum ())
   return *ptr->Datum ();
    }
    return NullObject::Instance ();
}
//
//   This file contains the C++ code from Program 8.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/pgm08_13.cpp
//
class ChainedScatterTable : public HashTable
{
    class Entry
    {
    public:
enum { null = ~0U };
Object* object;
unsigned int next;

Entry ();
    };

    Array<Entry> array;
public:
    ChainedScatterTable (unsigned int);
    // ...
};
//
//   This file contains the C++ code from Program 8.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/pgm08_14.cpp
//
ChainedScatterTable::Entry::Entry () :
    object (0),
    next (null)
    {}

ChainedScatterTable::ChainedScatterTable (unsigned int _length) :
    HashTable (_length),
    array (_length)
    {}

void ChainedScatterTable::Purge ()
{
    for (unsigned int i = 0; i < length; ++i)
    {
if (array [i].object != 0)
{
   if (IsOwner ())
delete array [i].object;
   array [i] = Entry ();
}
    }
    count = 0;
}

ChainedScatterTable::~ChainedScatterTable ()
    { Purge (); }
//
//   This file contains the C++ code from Program 8.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/pgm08_15.cpp
//
void ChainedScatterTable::Insert (Object& object)
{
    if (count == length)
throw domain_error ("scatter table is full");
    unsigned int probe = H (object);
    if (array [probe].object != 0)
    {
while (array [probe].next != Entry::null)
   probe = array [probe].next;
unsigned int const tail = probe;
probe = (probe + 1) % length;
while (array [probe].object != 0)
   probe = (probe + 1) % length;
array [tail].next = probe;
    }
    array [probe].object = &object;
    array [probe].next = Entry::null;
    ++count;
}

Object& ChainedScatterTable::Find (Object const& object) const
{
    for (unsigned int probe = H (object);
probe != Entry::null; probe = array [probe].next)
    {
if (object == *array [probe].object)
   return *array [probe].object;
    }
    return NullObject::Instance ();
}
//
//   This file contains the C++ code from Program 8.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/pgm08_16.cpp
//
void ChainedScatterTable::Withdraw (Object& object)
{
    if (count == 0)
throw domain_error ("scatter table is empty");
    unsigned int i = H (object);
    while (i != Entry::null && array [i].object != &object)
i = array [i].next;
    if (i == Entry::null)
throw invalid_argument ("object not found");
    for (;;)
    {
unsigned int j;
for (j = array [i].next;
   j != Entry::null; j = array [j].next)
{
   unsigned int const h = H (*array [j].object);
   bool contained = false;
   for (unsigned int k = array [i].next;
k != array [j].next && !contained;
k = array [k].next)
   {
if (k == h)
   contained = true;
   }
   if (!contained)
break;
}
if (j == Entry::null)
   break;
array [i].object = array [j].object;
i = j;
    }
    array [i].object = 0;
    array [i].next = Entry::null;
    for (unsigned int j = (i + length - 1U) % length;
j != i; j = (j + length - 1U) % length)
    {
if (array [j].next == i)
{
   array [j].next = Entry::null;
   break;
}
    }
    --count;
}
//
//   This file contains the C++ code from Program 8.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/pgm08_17.cpp
//
class OpenScatterTable : public HashTable
{
    class Entry
    {
    public:
enum State { empty, occupied, deleted };
State state;
Object* object;

Entry ();
    };

    Array<Entry> array;

    unsigned int C (unsigned int) const;
    unsigned int FindMatch (Object const&) const;
    unsigned int FindInstance (Object const&) const;
    unsigned int FindUnoccupied (Object const&) const;
public:
    OpenScatterTable (unsigned int);
    // ...
};
//
//   This file contains the C++ code from Program 8.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/pgm08_18.cpp
//
OpenScatterTable::Entry::Entry () :
    state (empty),
    object (0)
    {}

OpenScatterTable::OpenScatterTable (unsigned int _length) :
    HashTable (_length),
    array (_length)
    {}

void OpenScatterTable::Purge ()
{
    for (unsigned int i = 0; i < length; ++i)
    {
if (array [i].state == Entry::occupied)
{
   if (IsOwner ())
delete array [i].object;
   array [i] = Entry ();
}
    }
    count = 0;
}

OpenScatterTable::~OpenScatterTable ()
    { Purge (); }
//
//   This file contains the C++ code from Program 8.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/pgm08_19.cpp
//
unsigned int OpenScatterTable::C (unsigned int i) const
    { return i; }

unsigned int OpenScatterTable::FindUnoccupied (
    Object const& object) const
{
    unsigned int const hash = H (object);
    for (unsigned int i = 0; i < count + 1; ++i)
    {
unsigned int const probe = (hash + C (i)) % length;
if (array [probe].state != Entry::occupied)
   return probe;
    }
    return length;
}

void OpenScatterTable::Insert (Object& object)
{
    if (count == length)
throw domain_error ("scatter table is full");
    unsigned int const offset = FindUnoccupied (object);
    array [offset].state = Entry::occupied;
    array [offset].object = &object;
    ++count;
}
//
//   This file contains the C++ code from Program 8.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/pgm08_20.cpp
//
unsigned int OpenScatterTable::FindMatch (
    Object const& object) const
{
    unsigned int const hash = H (object);
    for (unsigned int i = 0; i < length; ++i)
    {
unsigned int const probe = (hash + C (i)) % length;
if (array [probe].state == Entry::empty)
   break;
if (array [probe].state == Entry::occupied
   && object == *array [probe].object)
   return probe;
    }
    return length;
}

Object& OpenScatterTable::Find (Object const& object) const
{
    unsigned int const offset = FindMatch (object);
    if (offset < length)
return *array [offset].object;
    else
return NullObject::Instance ();
}
//
//   This file contains the C++ code from Program 8.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/pgm08_21.cpp
//
void OpenScatterTable::Withdraw (Object& object)
{
    if (count == 0)
throw domain_error ("scatter table is empty");
    unsigned int const offset = FindInstance (object);
    if (offset == length)
throw invalid_argument ("object not found");
    array [offset].state = Entry::deleted;
    array [offset].object = 0;
    --count;
}
//
//   This file contains the C++ code from Program 8.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/pgm08_22.cpp
//
void OpenScatterTable::Withdraw (Object& object)
{
    if (count == 0)
throw domain_error ("scatter table is empty");
    unsigned int i = FindInstance (object);
    if (i == length)
throw invalid_argument ("object not found");
    for (;;)
    {
unsigned int j;
for (j = (i + 1) % length;
   array [j].state == Entry::occupied;
   j = (j + 1) % length)
{
   unsigned int const h = H (*array [j].object);
   if ((h <= i && i < j) || (i < j && j < h) ||
(j < h && h <= i))
break;
}
if (array [j].state == Entry::empty)
   break;
array [i] = array [j];
i = j;
    }
    array [i].state = Entry::empty;
    array [i].object = 0;
    --count;
}
//
//   This file contains the C++ code from Program 8.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/pgm08_23.cpp
//
class Counter : public Int
{
public:
    Counter (int i) : Int (i)
{}
    void operator ++ ()
{ ++datum; }
};

void CountWords (HashTable& table)
{
    std::string word; 
    while (cin >> word, !cin.eof ())
    {
Object& obj =
   table.Find (Association (*new String (word)));
if (obj.IsNull ())
   table.Insert (*new Association (
*new String (word), *new Counter (1)));
else
{
   Association& assoc =
dynamic_cast<Association&> (obj);
   Counter& i =
dynamic_cast<Counter&> (assoc.Value ());
   ++i;
}
    }
    cout << table << endl;
}
//
//   This file contains the C++ code from Program 9.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/pgm09_01.cpp
//
class Tree : public virtual Container
{
    class Iter;
public:
    virtual Object& Key () const = 0;
    virtual Tree& Subtree (unsigned int) const = 0;
    virtual bool IsEmpty () const = 0;
    virtual bool IsLeaf () const = 0;
    virtual unsigned int Degree () const = 0;
    virtual int Height () const;
    virtual void DepthFirstTraversal (PrePostVisitor&) const;
    virtual void BreadthFirstTraversal (Visitor&) const;
    void Accept (Visitor&) const;
};
//
//   This file contains the C++ code from Program 9.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/pgm09_02.cpp
//
void Tree::DepthFirstTraversal (
    PrePostVisitor& visitor) const
{
    if (visitor.IsDone ())
return;
    if (!IsEmpty ())
    {
visitor.PreVisit (Key ());
for (unsigned int i = 0; i < Degree (); ++i)
   Subtree (i).DepthFirstTraversal (visitor);
visitor.PostVisit (Key ());
    }
}
//
//   This file contains the C++ code from Program 9.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/pgm09_03.cpp
//
class PrePostVisitor : public Visitor
{
public:
    virtual void PreVisit (Object&) {}
    virtual void Visit (Object&) {}
    virtual void PostVisit (Object&) {}
};

class PreOrder : public PrePostVisitor
{
    Visitor& visitor;
public:
    PreOrder (Visitor& v) : visitor (v)
{}
    void PreVisit (Object& object)
{ visitor.Visit (object); }
};

class InOrder : public PrePostVisitor
{
    Visitor& visitor;
public:
    InOrder (Visitor& v) : visitor (v)
{}
    void Visit (Object& object)
{ visitor.Visit (object); }
};

class PostOrder : public PrePostVisitor
{
    Visitor& visitor;
public:
    PostOrder (Visitor& v) : visitor (v)
{}
    void PostVisit (Object& object)
{ visitor.Visit (object); }
};
//
//   This file contains the C++ code from Program 9.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/pgm09_04.cpp
//
void Tree::BreadthFirstTraversal (Visitor& visitor) const
{
    Queue& queue = *new QueueAsLinkedList ();
    queue.RescindOwnership ();

    if (!IsEmpty ())
queue.Enqueue (const_cast<Tree&> (*this));
    while (!queue.IsEmpty () && !visitor.IsDone ())
    {
Tree const& head =
   dynamic_cast<Tree const &> (queue.Dequeue ());

visitor.Visit (head.Key ());
for (unsigned int i = 0; i < head.Degree (); ++i)
{
   Tree& child = head.Subtree (i);
   if (!child.IsEmpty ())
queue.Enqueue (child);
}
    }
    delete &queue;
}
//
//   This file contains the C++ code from Program 9.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/pgm09_05.cpp
//
void Tree::Accept (Visitor& visitor) const
    { DepthFirstTraversal (PreOrder (visitor)); }
//
//   This file contains the C++ code from Program 9.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/pgm09_06.cpp
//
class Tree::Iter : public Iterator
{
    Tree const& tree;
    Stack& stack;
public:
    Iter (Tree const&);
    ~Iter ();
    void Reset ();
    bool IsDone () const;
    Object& operator * () const;
    void operator ++ ();
};
//
//   This file contains the C++ code from Program 9.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/pgm09_07.cpp
//
Tree::Iter::Iter (Tree const& _tree) :
    tree (_tree),
    stack (*new StackAsLinkedList ())
{
    stack.RescindOwnership ();
    Reset ();
}

Tree::Iter::~Iter ()
    { delete &stack; }

void Tree::Iter::Reset ()
{
    stack.Purge ();
    if (!tree.IsEmpty ())
stack.Push (const_cast<Tree&> (tree));
}
//
//   This file contains the C++ code from Program 9.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/pgm09_09.cpp
//
class GeneralTree : public Tree
{
protected:
    Object* key;
    unsigned int degree;
    LinkedList<GeneralTree*> list;
public:
    GeneralTree (Object&);
    ~GeneralTree ();

    Object& Key () const;
    GeneralTree& Subtree (unsigned int) const;
    virtual void AttachSubtree (GeneralTree&);
    virtual GeneralTree& DetachSubtree (GeneralTree&);
    // ...
};
//
//   This file contains the C++ code from Program 9.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/pgm09_10.cpp
//
GeneralTree::GeneralTree (Object& _key) :
    key (&_key),
    degree (0),
    list ()
    {}

void GeneralTree::Purge ()
{
    ListElement<GeneralTree*> const* ptr;

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

GeneralTree::~GeneralTree ()
    { Purge (); }
//
//   This file contains the C++ code from Program 9.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/pgm09_11.cpp
//
Object& GeneralTree::Key () const
    { return *key; }

GeneralTree& GeneralTree::Subtree (unsigned int i) const
{
    if (i >= degree)
throw out_of_range ("invalid subtree index");

    unsigned int j = 0;
    ListElement<GeneralTree*> const* ptr =
list.Head ();
    while (j < i && ptr != 0)
    {
++j;
ptr = ptr->Next ();
    }
    if (ptr == 0)
throw logic_error ("should never happen");
    return *ptr->Datum ();
}

void GeneralTree::AttachSubtree (GeneralTree& t)
{
    list.Append (&t);
    ++degree;
}

GeneralTree& GeneralTree::DetachSubtree (GeneralTree& t)
{
    list.Extract (&t);
    --degree;
    return t;
}
//
//   This file contains the C++ code from Program 9.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/pgm09_13.cpp
//
NaryTree::NaryTree (unsigned int _degree) :
    key (0),
    degree (_degree),
    subtree (0)
    {}

NaryTree::NaryTree (unsigned int _degree, Object& _key):
    key (&_key),
    degree (_degree),
    subtree (_degree)
{
    for (unsigned int i = 0; i < degree; ++i)
subtree [i] = new NaryTree (degree);
}
//
//   This file contains the C++ code from Program 9.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/pgm09_14.cpp
//
bool NaryTree::IsEmpty () const
    { return key == 0; }

Object& NaryTree::Key () const
{
    if (IsEmpty ())
throw domain_error ("invalid operation");
    return *key;
}

void NaryTree::AttachKey (Object& object)
{
    if (!IsEmpty ())
throw domain_error ("invalid operation");
    key = &object;
    subtree.SetLength (degree);
    for (unsigned int i = 0; i < degree; ++i)
subtree [i] = new NaryTree (degree);
}

Object& NaryTree::DetachKey ()
{
    if (!IsLeaf ())
throw domain_error ("invalid operation");
    Object& result = *key;
    key = 0;
    for (unsigned int i = 0; i < degree; ++i)
delete subtree [i];
    subtree.SetLength (0);
    return result;
}
//
//   This file contains the C++ code from Program 9.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/pgm09_15.cpp
//
NaryTree& NaryTree::Subtree (unsigned int i) const
{
    if (IsEmpty ())
throw domain_error ("invalid operation");
    return *subtree [i];
}

void NaryTree::AttachSubtree (unsigned int i, NaryTree& t)
{
    if (IsEmpty ())
throw domain_error ("invalid operation");
    if (!subtree [i]->IsEmpty ())
throw domain_error ("non-empty subtree present");
    delete subtree [i];
    subtree [i] = &t;
}

NaryTree& NaryTree::DetachSubtree (unsigned int i)
{
    if (IsEmpty ())
throw domain_error ("invalid operation");
    NaryTree& result = *subtree [i];
    subtree [i] = new NaryTree (degree);
    return result;
}
//
//   This file contains the C++ code from Program 9.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/pgm09_16.cpp
//
class BinaryTree : public virtual Tree
{
protected:
    Object* key;
    BinaryTree* left;
    BinaryTree* right;
public:
    BinaryTree ();
    BinaryTree (Object&);
    ~BinaryTree ();

    Object& Key () const;
    virtual void AttachKey (Object&);
    virtual Object& DetachKey ();
    virtual BinaryTree& Left () const;
    virtual BinaryTree& Right () const;
    virtual void AttachLeft (BinaryTree&);
    virtual void AttachRight (BinaryTree&);
    virtual BinaryTree& DetachLeft ();
    virtual BinaryTree& DetachRight ();
    // ...
};
//
//   This file contains the C++ code from Program 9.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/pgm09_17.cpp
//
BinaryTree::BinaryTree () :
    key (0),
    left (0),
    right (0)
    {}

BinaryTree::BinaryTree (Object& _key) :
    key (&_key),
    left (new BinaryTree ()),
    right (new BinaryTree ())
    {}
//
//   This file contains the C++ code from Program 9.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/pgm09_18.cpp
//
void BinaryTree::Purge ()
{
    if (!IsEmpty ())
    {
if (IsOwner ())
   delete key;
delete left;
delete right;
key = 0;
left = 0;
right = 0;
    }
}

BinaryTree::~BinaryTree ()
    { Purge (); }
//
//   This file contains the C++ code from Program 9.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/pgm09_19.cpp
//
void BinaryTree::DepthFirstTraversal (
    PrePostVisitor& visitor) const
{
    if (visitor.IsDone ())
return;
    if (!IsEmpty ())
    {
visitor.PreVisit (*key);
left->DepthFirstTraversal (visitor);
visitor.Visit (*key);
right->DepthFirstTraversal (visitor);
visitor.PostVisit (*key);
    }
}



//
//   This file contains the C++ code from Program 9.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/pgm09_20.cpp
//
int BinaryTree::CompareTo (Object const& object) const
{
    BinaryTree const& arg = 
dynamic_cast<BinaryTree const&> (object);
    if (IsEmpty ())
return arg.IsEmpty () ? 0 : -1;
    else if (arg.IsEmpty ())
return 1;
    else
    {
int result = Key ().Compare (arg.Key ());
if (result == 0)
   result = Left ().CompareTo (arg.Left ());
if (result == 0)
   result = Right ().CompareTo (arg.Right ());
return result;
    }
}
//
//   This file contains the C++ code from Program 9.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/pgm09_21.cpp
//
class ExpressionTree : public BinaryTree
{
public:
    ExpressionTree (char c) :
BinaryTree (*new Char (c)) {}
};

void PostfixToInfix ()
{
    char c;
    Stack& stack = *new StackAsLinkedList ();

    while (cin >> c, !cin.eof ())
    {
if (std::isdigit (c) || std::isalpha (c))
   stack.Push (*new ExpressionTree (c));
else if (c == '+' || c == '-' || c == '*' || c == '/')
{
   ExpressionTree& result = *new ExpressionTree (c);
   result.AttachRight (
dynamic_cast<ExpressionTree&> (stack.Pop ()));
   result.AttachLeft (
dynamic_cast<ExpressionTree&> (stack.Pop ()));
   stack.Push (result);
}
    }
    ExpressionTree& result =
dynamic_cast<ExpressionTree&> (stack.Pop ());
    InfixVisitor visitor;
    result.DepthFirstTraversal (visitor);
    delete &result;
    delete &stack;
}
//
//   This file contains the C++ code from Program 9.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/pgm09_22.cpp
//
class InfixVisitor : public PrePostVisitor
{
public:
    void PreVisit (Object&)
{ cout << "("; }
    void Visit (Object& object)
{ cout << object; }
    void PostVisit (Object&)
{ cout << ")"; }
};
//
//   This file contains the C++ code from Program A.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/pgm0A_01.cpp
//
void Two (int x)
{
    x = 2;
    cout << x << endl;
}

void One ()
{
    int y = 1;
    Two (y);
    cout << y << endl;
}
//
//   This file contains the C++ code from Program A.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/pgm0A_02.cpp
//
void Two (int& x)
{
    x = 2;
    cout << x << endl;
}

void One ()
{
    int y = 1;
    Two (y);
    cout << y << endl;
}
//
//   This file contains the C++ code from Program A.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/pgm0A_03.cpp
//
class Complex
{
    double real;
    double imag;
public:
    Complex ();
    Complex (double);
    Complex (double, double);
    Complex (Complex const&);
    ~Complex ();

    double Real () const;
    double Imag () const;
    double R () const;
    double Theta () const;
    void Put (ostream&) const;

    void SetReal (double);
    void SetImag (double);
    Complex& operator = (Complex  const&);
};
//
//   This file contains the C++ code from Program A.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/pgm0A_05.cpp
//
double Complex::Real () const
    { return real; }

double Complex::Imag () const
    { return imag; }

double Complex::R () const
    { return std::sqrt (real * real + imag * imag); }

double Complex::Theta () const
    { return atan2 (imag, real); }

void Complex::Put (ostream& s) const
    { s << real << "+" << imag << "i"; }
//
//   This file contains the C++ code from Program A.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/pgm0A_06.cpp
//
void Complex::SetReal (double x)
    { real = x; }

void Complex::SetImag (double y)
    { imag = y; }

Complex& Complex::operator = (Complex  const& c)
{
    real = c.real;
    imag = c.imag;
    return *this;
}
//
//   This file contains the C++ code from Program A.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/pgm0A_07.cpp
//
class Person
{
public:
    enum Sex { male, female };
protected:
    std::string name;
    Sex sex;
public:
    std::string Name () const
{ return name; }
    void Put (ostream& s) const
{ s << name; }
    // ...
};

class Parent : public Person
{
protected:
    unsigned int numberOfChildren;
    Person* child;
public:
    Person& Child (unsigned int i) const
    {
if (i >= numberOfChildren)
   throw out_of_range ("invalid child number");
return child [i];
    }
    void Put (ostream& s)
    {
// ...
    }
    // ...
};
//
//   This file contains the C++ code from Program A.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/pgm0A_08.cpp
//
class Point
{
    int x;
    int y;
public:
    Point (int, int);
    // ...
};

class GraphicalObject
{
protected:
    Point center;

    GraphicalObject (Point const& p) :
center (p) {}
public:
    virtual ~GraphicalObject ();
    virtual void Draw () const = 0;
    virtual void Erase () const;
    virtual void MoveTo (Point const&);
};
//
//   This file contains the C++ code from Program A.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/pgm0A_09.cpp
//
void GraphicalObject::Erase () const
{
    SetPenColour (backgroundColour);
    Draw ();
    SetPenColour (foregroundColour);
}

void GraphicalObject::MoveTo (Point const& p)
{
    Erase ();
    center = p;
    Draw ();
}
//
//   This file contains the C++ code from Program A.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/pgm0A_10.cpp
//
class Circle : public GraphicalObject
{
    int radius;
public:
    Circle (Point const& p, int r) :
GraphicalObject (p), radius (r) {}

    void Draw () const;
};

class Rectangle : public GraphicalObject
{
    int height;
    int width;
public:
    Rectangle (Point const& p, int ht, int wid) :
GraphicalObject (p), height (ht), width (wid) {}

    void Draw () const;
};

class Square : public Rectangle
{
public:
    Square (Point const& p, int wid) :
Rectangle (p, wid, wid) {}
};
//
//   This file contains the C++ code from Program 10.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/pgm10_01.cpp
//
class SearchTree :
    public virtual Tree, public virtual SearchableContainer
{
public:
    virtual Object& FindMin () const = 0;
    virtual Object& FindMax () const = 0;
};
//
//   This file contains the C++ code from Program 10.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/pgm10_02.cpp
//
class BST : public BinaryTree, public SearchTree
{
protected:
    virtual void AttachKey (Object&);
    virtual Object& DetachKey ();
    virtual void Balance ();
public:
    BST& Left () const;
    BST& Right () const;
    // ...
};
//
//   This file contains the C++ code from Program 10.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/pgm10_04.cpp
//
Object& BST::Find (Object const& object) const
{
    if (IsEmpty ())
return NullObject::Instance ();
    int const diff = object.Compare (*key);
    if (diff == 0)
return *key;
    else if (diff < 0)
return Left ().Find (object);
    else
return Right ().Find (object);
}

Object& BST::FindMin () const
{
    if (IsEmpty ())
return NullObject::Instance ();
    else if (Left ().IsEmpty ())
return *key;
    else
return Left ().FindMin();
}
//
//   This file contains the C++ code from Program 10.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/pgm10_05.cpp
//
void BST::Insert (Object& object)
{
    if (IsEmpty ())
AttachKey (object);
    else
    {
int const diff = object.Compare (*key);
if (diff == 0)
   throw invalid_argument ("duplicate key");
if (diff < 0)
   Left ().Insert (object);
else
   Right ().Insert (object);
    }
    Balance ();
}

void BST::AttachKey (Object& object)
{
    if (!IsEmpty ())
throw domain_error ("invalid operation");
    key = &object;
    left = new BST ();
    right = new BST ();
}

void BST::Balance ()
    {}
//
//   This file contains the C++ code from Program 10.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/pgm10_06.cpp
//
void BST::Withdraw (Object& object)
{
    if (IsEmpty ())
throw invalid_argument ("object not found");
    int const diff = object.Compare (*key);
    if (diff == 0)
    {
if (!Left ().IsEmpty ())
{
   Object& max = Left ().FindMax ();
   key = &max;
   Left ().Withdraw (max);
}
else if (!Right ().IsEmpty ())
{
   Object& min = Right ().FindMin ();
   key = &min;
   Right ().Withdraw (min);
}
else
   DetachKey ();
    }
    else if (diff < 0)
Left ().Withdraw (object);
    else
Right ().Withdraw (object);
    Balance ();
}

Object& BST::DetachKey ()
{
    if (!IsLeaf ())
throw domain_error ("invalid operation");
    Object& result = *key;
    delete left;
    delete right;
    key = 0;
    left = 0;
    right = 0;
    return result;
}
//
//   This file contains the C++ code from Program 10.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/pgm10_07.cpp
//
class AVLTree : public BST
{
protected:
    int height;

    int BalanceFactor () const;
    void AdjustHeight ();
    void LLRotation ();
    void LRRotation ();
    void RRRotation ();
    void RLRotation ();
    void AttachKey (Object&);
    Object& DetachKey ();
    void Balance ();
public:
    AVLTree ();

    int Height () const;
    AVLTree& Left () const;
    AVLTree& Right () const;
};
//
//   This file contains the C++ code from Program 10.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/pgm10_08.cpp
//
AVLTree::AVLTree () :
    BST (),
    height (-1)
    {}

int AVLTree::Height () const
    { return height; }

void AVLTree::AdjustHeight ()
{
    if (IsEmpty ())
height = -1;
    else
height = Max (left->Height (), right->Height ()) + 1;
}

int AVLTree::BalanceFactor () const
{
    if (IsEmpty ())
return 0;
    else
return left->Height () - right->Height ();
}
//
//   This file contains the C++ code from Program 10.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/pgm10_09.cpp
//
void AVLTree::LLRotation ()
{
    if (IsEmpty ())
throw domain_error ("invalid rotation");
    BinaryTree* const tmp = right;
    right = left;
    left = Right ().left;
    Right ().left = Right ().right;
    Right ().right = tmp;

    Object* const tmpObj = key;
    key = Right ().key;
    Right ().key = tmpObj;

    Right ().AdjustHeight ();
    AdjustHeight ();
}
//
//   This file contains the C++ code from Program 10.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/pgm10_11.cpp
//
void AVLTree::Balance ()
{
    AdjustHeight ();
    if (abs (BalanceFactor ()) > 1)
    {
if (BalanceFactor () > 0)
{
   if (Left ().BalanceFactor () > 0)
LLRotation ();
   else
LRRotation ();
}
else
{
   if (Right ().BalanceFactor () < 0)
RRRotation ();
   else
RLRotation ();
}
    }
}
//
//   This file contains the C++ code from Program 10.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/pgm10_13.cpp
//
class MWayTree : public SearchTree
{
protected:
    unsigned int const m;
    unsigned int numberOfKeys;
    Array<Object*> key;
    Array<MWayTree*> subtree;

    unsigned int FindIndex (Object const&) const;
public:
    MWayTree (unsigned int);
    ~MWayTree ();

    Object& Key (unsigned int) const;
    MWayTree& Subtree (unsigned int) const;
    // ...
};
//
//   This file contains the C++ code from Program 10.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/pgm10_14.cpp
//
void MWayTree::DepthFirstTraversal (
    PrePostVisitor& visitor) const
{
    if (!IsEmpty ())
    {
for (int i = 0; i <= numberOfKeys + 1; ++i)
{
   if (i >= 2)
visitor.PostVisit (*key [i - 1]);
   if (i >= 1 && i <= numberOfKeys)
visitor.Visit (*key [i]);
   if (i <= numberOfKeys - 1)
visitor.PreVisit (*key [i + 1]);
   if (i <= count)
subtree [i]->DepthFirstTraversal (visitor);
}
    }
}
//
//   This file contains the C++ code from Program 10.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/pgm10_16.cpp
//
unsigned int MWayTree::FindIndex (Object const& object) const
{
    if (IsEmpty ())
throw domain_error ("invalid operation");
    if (object < *key [1])
return 0;
    unsigned int left = 1;
    unsigned int right = numberOfKeys;
    while (left < right)
    {
int const middle = (left + right + 1) / 2;
if (object >= *key [middle])
   left = middle;
else
   right = middle - 1U;
    }
    return left;
}

Object& MWayTree::Find (Object const& object) const
{
    if (IsEmpty ())
return NullObject::Instance ();
    unsigned int const index = FindIndex (object);
    if (index != 0 && object == *key [index])
return *key [index];
    else
return subtree [index]->Find (object);
}
//
//   This file contains the C++ code from Program 10.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/pgm10_17.cpp
//
void MWayTree::Insert (Object& object)
{
    if (IsEmpty ())
    {
subtree [0] = new MWayTree (m);
key [1] = &object;
subtree [1] = new MWayTree (m);
numberOfKeys = 1;
    }
    else
    {
unsigned int const index = FindIndex (object);
if (index != 0 && object == *key [index])
   throw invalid_argument ("duplicate key");
if (numberOfKeys < m - 1U)
{
   for(unsigned int i = numberOfKeys; i > index; --i)
   {
key [i + 1] = key [i];
subtree [i + 1] = subtree [i];
   }
   key [index + 1] = &object;
   subtree [index + 1] = new MWayTree (m);
   ++numberOfKeys;
}
else
   subtree [index]->Insert (object);
    }
}
//
//   This file contains the C++ code from Program 10.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/pgm10_18.cpp
//
void MWayTree::Withdraw (Object& object)
{
    if (IsEmpty ())
throw invalid_argument ("object not found");
    unsigned int const index = FindIndex (object);
    if (index != 0 && object == *key [index])
    {
if (!subtree [index - 1U]->IsEmpty ())
{
   Object& max = subtree [index - 1U]->FindMax ();
   key [index] = &max;
   subtree [index - 1U]->Withdraw (max);
}
else if (!subtree [index]->IsEmpty ())
{
   Object& min = subtree [index]->FindMin ();
   key [index] = &min;
   subtree [index]->Withdraw (min);
}
else
{
   --numberOfKeys;
   delete subtree [index];
   for(unsigned int i = index; i <= numberOfKeys; ++i)
   {
key [i] = key [i + 1];
subtree [i] = subtree [i + 1];
   }
   if (numberOfKeys == 0)
delete subtree [0];
}
    }
    else
subtree [index]->Withdraw (object);
}
//
//   This file contains the C++ code from Program 10.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/pgm10_19.cpp
//
class BTree : public MWayTree
{
    BTree* parent;

    void InsertPair (Object&, BTree&);
    void AttachKey (unsigned int, Object&);
    void AttachSubtree (unsigned int, MWayTree&);
    Object& InsertKey (unsigned int, Object&);
    BTree& InsertSubtree (unsigned int, BTree&);
    void AttachLeftHalfOf (BTree const&);
    void AttachRightHalfOf (BTree const&, Object&, BTree&);
public:
    BTree (unsigned int);
    BTree (unsigned int, BTree&);

    void Insert (Object&);
    void Withdraw (Object&);
};
//
//   This file contains the C++ code from Program 10.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/pgm10_20.cpp
//
void BTree::Insert (Object& object)
{
    if (IsEmpty ())
    {
if (parent == 0)
{
   AttachSubtree (0, *new BTree (m, *this));
   AttachKey (1, object);
   AttachSubtree (1, *new BTree (m, *this));
   numberOfKeys = 1;
}
else
   parent->InsertPair (object, *new BTree (m, *parent));
    }
    else
    {
unsigned int const index = FindIndex (object);
if (index != 0 && object == *key [index])
   throw invalid_argument ("duplicate key");
subtree [index]->Insert (object);
    }
}
//
//   This file contains the C++ code from Program 10.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/pgm10_21.cpp
//
void BTree::InsertPair (Object& object, BTree& child)
{
    unsigned int const index = FindIndex (object);
    BTree& extraTree = InsertSubtree (index + 1, child);
    Object& extraKey = InsertKey (index + 1, object);

    if (++numberOfKeys == m)
    {
if (parent == 0)
{
   BTree& left = *new BTree (m, *this);
   BTree& right = *new BTree (m, *this);
   left.AttachLeftHalfOf (*this);
   right.AttachRightHalfOf (*this, extraKey, extraTree);
   AttachSubtree (0, left);
   AttachKey (1, *key [(m + 1)/2]);
   AttachSubtree (1, right);
   numberOfKeys = 1;
}
else
{
   numberOfKeys = (m + 1)/2 - 1;
   BTree& right = *new BTree (m, *parent);
   right.AttachRightHalfOf (*this, extraKey, extraTree);
   parent->InsertPair (*key [(m + 1)/2], right);
}
    }
}
//
//   This file contains the C++ code from Program 11.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/pgm11_03.cpp
//
BinaryHeap::BinaryHeap (unsigned int length) :
    array (length, 1)
    {}

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

BinaryHeap::~BinaryHeap ()
    { Purge (); }
//
//   This file contains the C++ code from Program 11.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/pgm11_04.cpp
//
void BinaryHeap::Enqueue (Object& object)
{
    if (count == array.Length ())
throw domain_error ("priority queue is full");
    ++count;
    unsigned int i = count;
    while (i > 1 && *array [i / 2] > object)
    {
array [i] = array [i / 2];
i /= 2;
    }
    array [i] = &object;
}

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…