Treceți la conținutul principal

ALGORITMI CPP CODE 3


//
//   This file contains the C++ code from Program 11.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/pgm11_05.cpp
//
Object& BinaryHeap::FindMin () const
{
    if (count == 0)
throw domain_error ("priority queue is empty");
    return *array [1];
}
//
//   This file contains the C++ code from Program 11.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/pgm11_06.cpp
//
Object& BinaryHeap::DequeueMin ()
{
    if (count == 0)
throw domain_error ("priority queue is empty");
    Object& result = *array [1];
    Object& last = *array [count];
    --count;
    unsigned int i = 1;
    while (2 * i < count + 1)
    {
unsigned int child = 2 * i;
if (child + 1 < count + 1
   && *array [child + 1] < *array [child])
   child += 1;
if (last <= *array [child])
   break;
array [i] = array [child];
i = child;
    }
    array [i] = &last;
    return result;
}
//
//   This file contains the C++ code from Program 11.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/pgm11_07.cpp
//
class LeftistHeap :
    public BinaryTree, public MergeablePriorityQueue
{
    unsigned int nullPathLength;

    void SwapContents (LeftistHeap&);
public:
    LeftistHeap ();
    LeftistHeap (Object&);

    LeftistHeap& Left () const;
    LeftistHeap& Right () const;
    void Merge (MergeablePriorityQueue&);
    // ...
};
//
//   This file contains the C++ code from Program 11.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/pgm11_08.cpp
//
void LeftistHeap::Merge (MergeablePriorityQueue& queue)
{
    LeftistHeap& arg = dynamic_cast<LeftistHeap&> (queue);
    if (IsEmpty ())
SwapContents (arg);
    else if (!arg.IsEmpty ())
    {
if (*key > *arg.key)
   SwapContents (arg);
Right ().Merge (arg);
if (Left ().nullPathLength < Right ().nullPathLength)
   Swap (left, right);
nullPathLength = 1 + Min (Left ().nullPathLength,
   Right ().nullPathLength);
    }
}
//
//   This file contains the C++ code from Program 11.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/pgm11_09.cpp
//
void LeftistHeap::Enqueue (Object& object)
{
    LeftistHeap heap (object);
    Merge (heap);
}
//
//   This file contains the C++ code from Program 11.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/pgm11_10.cpp
//
Object& LeftistHeap::FindMin () const
{
    if (IsEmpty ())
throw domain_error ("priority queue is empty");
    return *key;
}
//
//   This file contains the C++ code from Program 11.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/pgm11_12.cpp
//
class BinomialTree : public GeneralTree
{
    void SwapContents (BinomialTree&);
public:
    BinomialTree (Object&);

    void Add (BinomialTree&);
    BinomialTree& Subtree (unsigned int) const;
};
//
//   This file contains the C++ code from Program 11.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/pgm11_14.cpp
//
class BinomialQueue : public MergeablePriorityQueue
{
    LinkedList<BinomialTree*> list;

    BinomialTree& FindMinTree () const;
    void AddTree (BinomialTree&);
    void RemoveTree (BinomialTree&);

    static BinomialTree* Sum (
BinomialTree*, BinomialTree*, BinomialTree*);
    static BinomialTree* Carry (
BinomialTree*, BinomialTree*, BinomialTree*);
public:
    BinomialQueue ();
    ~BinomialQueue ();
    // ...
};
//
//   This file contains the C++ code from Program 11.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/pgm11_15.cpp
//
void BinomialQueue::AddTree (BinomialTree& tree)
{
    list.Append (&tree);
    count += tree.Count ();
}

void BinomialQueue::RemoveTree (BinomialTree& tree)
{
    list.Extract (&tree);
    count -= tree.Count ();
}
//
//   This file contains the C++ code from Program 11.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/pgm11_17.cpp
//
void BinomialQueue::Merge (MergeablePriorityQueue& queue)
{
    BinomialQueue& arg = dynamic_cast<BinomialQueue&> (queue);
    LinkedList<BinomialTree*> oldList = list;
    list.Purge ();
    count = 0;
    ListElement<BinomialTree*> const* p =
oldList.Head ();
    ListElement<BinomialTree*> const* q =
arg.list.Head();
    BinomialTree* carry = 0;
    for (unsigned int i = 0; p || q || carry; ++i)
    {
BinomialTree* a = 0;
if (p && p->Datum ()->Degree () == i)
   { a = p->Datum (); p = p->Next (); }
BinomialTree* b = 0;
if (q && q->Datum ()->Degree () == i)
   { b = q->Datum (); q = q->Next (); }
BinomialTree* sum = Sum (a, b, carry);
if (sum)
   AddTree (*sum);
carry = Carry (a, b, carry);
    }
    arg.list.Purge ();
    arg.count = 0;
}
//
//   This file contains the C++ code from Program 11.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/pgm11_18.cpp
//
BinomialTree* BinomialQueue::Sum (
    BinomialTree* a, BinomialTree* b, BinomialTree* c)
{
    if (a && !b && !c)
return a;
    else if (!a && b && !c)
return b;
    else if (!a && !b && c)
return c;
    else if (a && b && c)
return c;
    else
return 0;
}

BinomialTree* BinomialQueue::Carry (
    BinomialTree* a, BinomialTree* b, BinomialTree* c)
{
    if (a && b && !c)
{ a->Add (*b); return a; }
    else if (a && !b && c)
{ a->Add (*c); return a; }
    else if (!a && b && c)
{ b->Add (*c); return b; }
    else if (a && b && c)
{ a->Add (*b); return a; }
    else
return 0;
}
//
//   This file contains the C++ code from Program 11.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/pgm11_19.cpp
//
void BinomialQueue::Enqueue (Object& object)
{
    BinomialQueue queue;
    queue.AddTree (*new BinomialTree (object));
    Merge (queue);
}
//
//   This file contains the C++ code from Program 11.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/pgm11_20.cpp
//
Object& BinomialQueue::DequeueMin ()
{
    if (count == 0)
throw domain_error ("priority queue is empty");

    BinomialTree& minTree = FindMinTree ();
    RemoveTree (minTree);

    BinomialQueue queue;
    while (minTree.Degree () > 0)
    {
BinomialTree& child = minTree.Subtree (0);

minTree.DetachSubtree (child);
queue.AddTree (child);
    }
    Merge (queue);

    Object& result = minTree.Key ();
    minTree.RescindOwnership ();
    delete &minTree;

    return result;
}
//
//   This file contains the C++ code from Program 11.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/pgm11_22.cpp
//
void Simulation (PriorityQueue& eventList, time timeLimit)
{
    bool serverBusy = false;
    unsigned int numberInQueue = 0;
    ExponentialRV serviceTime (100.);
    ExponentialRV interArrivalTime (100.);

    eventList.Enqueue (*new Event (Event::arrival, 0));
    while (!eventList.IsEmpty ())
    {
Event& event =
   dynamic_cast<Event&> (eventList.DequeueMin ());
Event::Time& t = event.Key ();
if (t > timeLimit)
{
   delete &event;
   eventList.Purge ();
   break;
}
switch (event.Value ())
{
case Event::arrival:
   if (!serverBusy)
   {
serverBusy = true;
eventList.Enqueue (*new Event (Event::departure,
   t + serviceTime.Sample ()));
   }
   else
++numberInQueue;
   eventList.Enqueue (*new Event (Event::arrival,
t + interArrivalTime.Sample ()));
   break;
case Event::departure:
   if (numberInQueue == 0)
serverBusy = false;
   else
   {
--numberInQueue;
eventList.Enqueue (*new Event (Event::departure,
   t + serviceTime.Sample ()));
   }
   break;
}
delete &event;
    }
}
//
//   This file contains the C++ code from Program 12.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/pgm12_01.cpp
//
class Set : public virtual SearchableContainer
{
protected:
    unsigned int universeSize;

public:
    Set (unsigned int n) : universeSize (n) {}

    typedef Wrapper<unsigned int> Element;
};
//
//   This file contains the C++ code from Program 12.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/pgm12_02.cpp
//
class SetAsArray : public Set
{
    Array<bool> array;
public:
    SetAsArray (unsigned int);
    // ...
    friend SetAsArray operator + (
SetAsArray const&, SetAsArray const&);
    friend SetAsArray operator - (
SetAsArray const&, SetAsArray const&);
    friend SetAsArray operator * (
SetAsArray const&, SetAsArray const&);
    friend bool operator == (
SetAsArray const&, SetAsArray const&);
    friend bool operator <= (
SetAsArray const&, SetAsArray const&);
};
//
//   This file contains the C++ code from Program 12.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/pgm12_03.cpp
//
SetAsArray::SetAsArray (unsigned int n) :
    Set (n),
    array (n)
{
    for (unsigned int item = 0; item < universeSize; ++item)
array [item] = false;
}

void SetAsArray::Insert (Object& object)
{
    unsigned int const item = dynamic_cast<Element&> (object);
    array [item] = true;
}

bool SetAsArray::IsMember (Object const& object) const
{
    unsigned int const item =
dynamic_cast<Element const&> (object);
    return array [item];
}

void SetAsArray::Withdraw (Object& object)
{
    unsigned int const item = dynamic_cast<Element&> (object);
    array [item] = false;
}
//
//   This file contains the C++ code from Program 12.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/pgm12_04.cpp
//
SetAsArray operator + (SetAsArray const& s, SetAsArray const& t)
{
    if (s.universeSize != t.universeSize)
throw invalid_argument ("mismatched sets");
    SetAsArray result (s.universeSize);
    for (unsigned int i = 0; i < s.universeSize; ++i)
result.array [i] = s.array [i] || t.array [i];
    return result;
}

SetAsArray operator * (SetAsArray const& s, SetAsArray const& t)
{
    if (s.universeSize != t.universeSize)
throw invalid_argument ("mismatched sets");
    SetAsArray result (s.universeSize);
    for (unsigned int i = 0; i < s.universeSize; ++i)
result.array [i] = s.array [i] && t.array [i];
    return result;
}

SetAsArray operator - (SetAsArray const& s, SetAsArray const& t)
{
    if (s.universeSize != t.universeSize)
throw invalid_argument ("mismatched sets");
    SetAsArray result (s.universeSize);
    for (unsigned int i = 0; i < s.universeSize; ++i)
result.array [i] = s.array [i] && !t.array [i];
    return result;
}
//
//   This file contains the C++ code from Program 12.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/pgm12_05.cpp
//
bool operator == (SetAsArray const& s, SetAsArray const& t)
{
    if (s.universeSize != t.universeSize)
throw invalid_argument ("mismatched sets");
    for (unsigned int item = 0; item < s.universeSize; ++item)
if (s.array [item] != t.array [item])
   return false;
    return true;
}

bool operator <= (SetAsArray const& s, SetAsArray const& t)
{
    if (s.universeSize != t.universeSize)
throw invalid_argument ("mismatched sets");
    for (unsigned int item = 0; item < s.universeSize; ++item)
if (s.array [item] && !t.array [item])
   return false;
    return true;
}
//
//   This file contains the C++ code from Program 12.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/pgm12_06.cpp
//
class SetAsBitVector : public Set
{
    typedef unsigned int Word;
    enum { wordBits = bitsizeof (Word) };

    Array<Word> vector;
public:
    SetAsBitVector (unsigned int);
    // ...
};
//
//   This file contains the C++ code from Program 12.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/pgm12_07.cpp
//
SetAsBitVector::SetAsBitVector (unsigned int n) :
    Set (n),
    vector ((n + wordBits - 1U) / wordBits)
{
    for (unsigned int i = 0; i < vector.Length (); ++i)
vector [i] = 0;
}

void SetAsBitVector::Insert (Object& object)
{
    unsigned int const item = dynamic_cast<Element&> (object);
    vector [item / wordBits] |= 1 << item % wordBits;
}

void SetAsBitVector::Withdraw (Object& object)
{
    unsigned int const item = dynamic_cast<Element&> (object);
    vector [item / wordBits] &= ~(1 << item % wordBits);
}

bool SetAsBitVector::IsMember (Object const& object) const
{
    unsigned int const item =
dynamic_cast<Element const&> (object);
    return vector [item / wordBits] & (1 << item % wordBits);
}
//
//   This file contains the C++ code from Program 12.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/pgm12_08.cpp
//
SetAsBitVector operator + (
    SetAsBitVector const& s, SetAsBitVector const& t)
{
    if (s.universeSize != t.universeSize)
throw invalid_argument ("mismatched sets");
    SetAsBitVector result (s.universeSize);
    for (unsigned int i = 0; i < s.vector.Length (); ++i)
result.vector [i] = s.vector [i] | t.vector [i];
    return result;
}

SetAsBitVector operator * (
    SetAsBitVector const& s, SetAsBitVector const& t)
{
    if (s.universeSize != t.universeSize)
throw invalid_argument ("mismatched sets");
    SetAsBitVector result (s.universeSize);
    for (unsigned int i = 0; i < s.vector.Length (); ++i)
result.vector [i] = s.vector [i] & t.vector [i];
    return result;
}

SetAsBitVector operator - (
    SetAsBitVector const& s, SetAsBitVector const& t)
{
    if (s.universeSize != t.universeSize)
throw invalid_argument ("mismatched sets");
    SetAsBitVector result (s.universeSize);
    for (unsigned int i = 0; i < s.vector.Length (); ++i)
result.vector [i] = s.vector [i] & ~t.vector [i];
    return result;
}
//
//   This file contains the C++ code from Program 12.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/pgm12_09.cpp
//
class Multiset : public Set
{
public:
    Multiset (unsigned int n) : Set (n) {}
};
//
//   This file contains the C++ code from Program 12.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/pgm12_10.cpp
//
class MultisetAsArray : public Multiset
{
    Array<unsigned int> array;
public:
    MultisetAsArray (unsigned int);
    // ...
};
//
//   This file contains the C++ code from Program 12.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/pgm12_11.cpp
//
MultisetAsArray::MultisetAsArray (unsigned int n) :
    Multiset (n),
    array (n)
{
    for (unsigned int item = 0; item < universeSize; ++item)
array [item] = 0;
}

void MultisetAsArray::Insert (Object& object)
{
    unsigned int const item = dynamic_cast<Element&> (object);
    ++array [item];
}

void MultisetAsArray::Withdraw (Object& object)
{
    unsigned int const item = dynamic_cast<Element&> (object);
    if (array [item] > 0)
--array [item];
}

bool MultisetAsArray::IsMember (Object const& object) const
{
    unsigned int const item =
dynamic_cast<Element const&> (object);
    return array [item] > 0;
}
//
//   This file contains the C++ code from Program 12.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/pgm12_12.cpp
//
MultisetAsArray operator + (
    MultisetAsArray const& s, MultisetAsArray const& t)
{
    if (s.universeSize != t.universeSize)
throw invalid_argument ("mismatched sets");
    MultisetAsArray result (s.universeSize);
    for (unsigned int i = 0; i < s.universeSize; ++i)
result.array [i] = s.array [i] + t.array [i];
    return result;
}

MultisetAsArray operator * (
    MultisetAsArray const& s, MultisetAsArray const& t)
{
    if (s.universeSize != t.universeSize)
throw invalid_argument ("mismatched sets");
    MultisetAsArray result (s.universeSize);
    for (unsigned int i = 0; i < s.universeSize; ++i)
result.array [i] = Min (s.array [i], t.array [i]);
    return result;
}

MultisetAsArray operator - (
    MultisetAsArray const& s, MultisetAsArray const& t)
{
    if (s.universeSize != t.universeSize)
throw invalid_argument ("mismatched sets");
    MultisetAsArray result (s.universeSize);
    for (unsigned int i = 0; i < s.universeSize; ++i)
if (t.array [i] <= s.array [i])
   result.array [i] = s.array [i] - t.array [i];
    return result;
}
//
//   This file contains the C++ code from Program 12.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/pgm12_13.cpp
//
class MultisetAsLinkedList : public Multiset
{
    LinkedList<unsigned int> list;
public:
    MultisetAsLinkedList (unsigned int);
    // ...
};
//
//   This file contains the C++ code from Program 12.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/pgm12_14.cpp
//
MultisetAsLinkedList operator + (
    MultisetAsLinkedList const& s, MultisetAsLinkedList const& t)
{
    if (s.universeSize != t.universeSize)
throw invalid_argument ("mismatched sets");
    MultisetAsLinkedList result (s.universeSize);
    ListElement<unsigned int> const* p = s.list.Head();
    ListElement<unsigned int> const* q = t.list.Head();
    while (p && q)
    {
if (p->Datum () <= q->Datum ())
{
   result.list.Append (p->Datum ());
   p = p->Next ();
}
else
{
   result.list.Append (q->Datum ());
   q = q->Next ();
}
    }
    for ( ; p; p = p->Next ())
result.list.Append (p->Datum ());
    for ( ; q; q = q->Next ())
result.list.Append (q->Datum ());
    return result;
}
//
//   This file contains the C++ code from Program 12.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/pgm12_15.cpp
//
MultisetAsLinkedList operator * (
    MultisetAsLinkedList const& s, MultisetAsLinkedList const& t)
{
    if (s.universeSize != t.universeSize)
throw invalid_argument ("mismatched sets");
    MultisetAsLinkedList result (s.universeSize);
    ListElement<unsigned int> const* p = s.list.Head();
    ListElement<unsigned int> const* q = t.list.Head();
    while (p && q)
    {
int const diff = p->Datum () - q->Datum ();
if (diff == 0)
   result.list.Append (p->Datum ());
if (diff <= 0)
   p = p->Next ();
if (diff >= 0)
   q = q->Next ();
    }
    return result;
}
//
//   This file contains the C++ code from Program 12.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/pgm12_17.cpp
//
class PartitionTree : public Set, public Tree
{
    unsigned int const item;
    PartitionTree* parent;
    unsigned int rank;

    PartitionTree (unsigned int, unsigned int);
    // ...
    friend class PartitionAsForest;
};

class PartitionAsForest : public Partition
{
    Array<PartitionTree*> array;

    void CheckArguments (
PartitionTree const&, PartitionTree const&);
public:
    PartitionAsForest (unsigned int);
    ~PartitionAsForest ();
    // ...
};

//
//   This file contains the C++ code from Program 12.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/pgm12_19.cpp
//
Set& PartitionAsForest::Find (Object const& object) const
{
    unsigned int const item =
dynamic_cast<Set::Element const&> (object);
    PartitionTree* ptr = array [item];
    while (ptr->parent != 0)
ptr = ptr->parent;
    return *ptr;
}
//
//   This file contains the C++ code from Program 12.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/pgm12_21.cpp
//
Set& PartitionAsForest::Find (Object const& object) const
{
    unsigned int const item =
dynamic_cast<Set::Element const&> (object);
    PartitionTree* root = array [item];
    while (root->parent != 0)
root = root->parent;
    PartitionTree* ptr = array [item];
    while (ptr->parent != 0)
    {
PartitionTree* const tmp = ptr->parent;
ptr->parent = root;
ptr = tmp;
    }
    return *root;
}
//
//   This file contains the C++ code from Program 12.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/pgm12_22.cpp
//
void PartitionAsForest::Join (Set& s, Set& t)
{
    PartitionTree& p = dynamic_cast<PartitionTree&> (s);
    PartitionTree& q = dynamic_cast<PartitionTree&> (t);
    CheckArguments (p, q);
    if (p.count > q.count)
    {
q.parent = &p;
p.count += q.count;
    }
    else
    {
p.parent = &q;
q.count += p.count;
    }
    --count;
}
//
//   This file contains the C++ code from Program 12.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/pgm12_24.cpp
//
void EquivalenceClasses ()
{
    unsigned int n;
    cin >> n;
    Partition& p = *new PartitionAsForest (n);

    unsigned int i;
    unsigned int j;
    while (cin >> i >> j, !cin.eof ())
    {
Set& s = p.Find (Set::Element (i)));
Set& t = p.Find (Set::Element (j)));
if (s != t)
   p.Join (s, t);
else
   cout << "redundant pair: "
<< i << ", " << j << endl;
    }
    cout << p << endl;
    delete &p;
}
//
//   This file contains the C++ code from Program 13.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/pgm13_01.cpp
//
class StoragePool
{
public:
    virtual ~StoragePool ();
    virtual void* Acquire (size_t) = 0;
    virtual void Release (void*) = 0;
};
//
//   This file contains the C++ code from Program 13.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/pgm13_02.cpp
//
struct Tag
{
    StoragePool* pool;
};

void* operator new (size_t bytes, StoragePool& p)
{
    Tag* const tag = reinterpret_cast<Tag*> (
p.Acquire (bytes + sizeof (Tag)));
    tag->pool = &p;
    return tag + 1;
}

void* operator new (size_t bytes)
{
    Tag* const tag = reinterpret_cast<Tag*> (
std::malloc (bytes + sizeof (Tag));
    tag->pool = 0;
    return tag + 1;
}

void operator delete (void* arg)
{
    Tag* const tag = reinterpret_cast<Tag*> (arg) - 1U;
    if (tag->pool)
tag->pool->Release (tag);
    else
std::free (tag);
}
//
//   This file contains the C++ code from Program 13.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/pgm13_04.cpp
//
SinglyLinkedPool::SinglyLinkedPool (size_t n) :
    numberOfBlocks ((n + sizeof (Block) - 1U) / sizeof (Block)),
    pool (new Block [numberOfBlocks + 1]),
    sentinel (pool [numberOfBlocks])
{
    Block& head = pool [0];
    head.length = numberOfBlocks;
    head.next = 0;

    sentinel.length = 0;
    sentinel.next = &head;
}

SinglyLinkedPool::~SinglyLinkedPool ()
    { delete [] pool; }
//
//   This file contains the C++ code from Program 13.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/pgm13_05.cpp
//
void* SinglyLinkedPool::Acquire (size_t bytes)
{
    unsigned int const blocks =
(bytes + sizeof (Header) + sizeof (Block) - 1U) /
   sizeof (Block);

    Block* prevPtr = &sentinel;
    Block* ptr = prevPtr->next;
    while (ptr != 0 && ptr->length < blocks)
    {
prevPtr = ptr;
ptr = ptr->next;
    }
    if (ptr == 0)
throw bad_alloc ("out of memory");
    if (ptr->length > blocks)
    {
Block& newBlock = ptr [blocks];
newBlock.length = ptr->length - blocks;
newBlock.next = ptr->next;
ptr->length = blocks;
ptr->next = &newBlock;
    }
    prevPtr->next = ptr->next;
    return ptr->userPart;
}
//
//   This file contains the C++ code from Program 13.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/pgm13_06.cpp
//
void SinglyLinkedPool::Release (void* arg)
{
    Block& block = *reinterpret_cast<Block*> (
reinterpret_cast<Header*> (arg) - 1U);
    
    if (&block < pool || &block >= pool + numberOfBlocks)
throw invalid_argument ("invalid block");

    Block* prevPtr = &sentinel;
    Block* ptr = prevPtr->next;
    while (ptr != 0 && ptr < &block)
    {
prevPtr = ptr;
ptr = ptr->next;
    }
    if (ptr != 0 && &block + block.length == ptr)
    {
block.length += ptr->length;
block.next = ptr->next;
    }
    else
block.next = ptr;
    if (prevPtr + prevPtr->length == &block)
    {
prevPtr->length += block.length;
prevPtr->next = block.next;
    }
    else
prevPtr->next = &block;
}
//
//   This file contains the C++ code from Program 13.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/pgm13_07.cpp
//
class DoublyLinkedPool : public StoragePool
{
public:
    enum Status { free, reserved };
    struct Header
    {
Status status : 1;
unsigned int length : bitsizeof (unsigned int) - 1U;
    };
    struct Block : public Header
    {
enum { size = 16 };
struct Links
{
   Block* next;
   Block* prev;
};
union
{
   Links link;
   char userPart [size - sizeof (Header)];
};
    };
private:
    unsigned int numberOfBlocks;
    Block* pool;
    Block& sentinel;

    static void Unlink (Block&);
    static void InsertAfter (Block&, Block&);
public:
    DoublyLinkedPool (size_t);
    ~DoublyLinkedPool ();

    void* Acquire (size_t);
    void Release (void*);
};
//
//   This file contains the C++ code from Program 13.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/pgm13_09.cpp
//
void DoublyLinkedPool::Release (void* arg)
{
    Block& block = *reinterpret_cast<Block*> (
reinterpret_cast<Header*> (arg) - 1U);

    if (&block < pool || &block >= pool + numberOfBlocks)
throw invalid_argument ("invalid block");
    
    block.status = free;
    InsertAfter (sentinel, block);
}
//
//   This file contains the C++ code from Program 13.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/pgm13_10.cpp
//
void* DoublyLinkedPool::Acquire (size_t bytes)
{
    unsigned int const blocks =
(bytes + sizeof (Header) + sizeof (Block) - 1U) /
   sizeof (Block);

    Block* ptr;
    for (ptr = sentinel.link.next; ptr != &sentinel;
ptr = ptr->link.next)
    {
for (;;)
{
   Block& successor = ptr [ptr->length];
   if (successor.status == reserved)
break;
   Unlink (successor);
   ptr->length += successor.length;
}
if (ptr->length >= blocks)
   break;
    }
    if (ptr == &sentinel)
throw bad_alloc ("out of memory");
    if (ptr->length > blocks)
    {
Block& newBlock = ptr [blocks];
newBlock.status = free;
newBlock.length = ptr->length - blocks;
ptr->length = blocks;
InsertAfter (sentinel, newBlock);
    }
    Unlink (*ptr);
    ptr->status = reserved;
    return ptr->userPart;
}
//
//   This file contains the C++ code from Program 13.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/pgm13_12.cpp
//
BuddyPool::BuddyPool (size_t bytes) :
    m (Log2Ceil (bytes)),
    numberOfBlocks ((1 << m) / sizeof (Block)),
    pool (new Block [numberOfBlocks + m + 1]),
    sentinel (pool + numberOfBlocks)
{
    for (unsigned int i = 0; i <= m; ++i)
    {
sentinel [i].link.next = &sentinel [i];
sentinel [i].link.prev = &sentinel [i];
    }

    Block& head = pool [0];
    head.status = free;
    head.k = m;
    InsertAfter (sentinel [m], head);
}

BuddyPool::~BuddyPool ()
    { delete [] pool; }
//
//   This file contains the C++ code from Program 13.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/pgm13_13.cpp
//
void* BuddyPool::Acquire (size_t bytes)
{
    unsigned int kPrime = Log2Ceil (bytes + sizeof (Header));

    unsigned int i = kPrime;
    while (i <= m && sentinel [i].link.next == &sentinel [i])
++i;
    if (i > m)
throw bad_alloc ("out of memory");

    Block& block = *sentinel [i].link.next;
    Unlink (block);
    while (block.k > kPrime)
    {
block.k -= 1;
Block& buddy = Buddy (block);
buddy.status = free;
buddy.k = block.k;
InsertAfter (sentinel [buddy.k], buddy);
    }
    block.status = reserved;
    return block.userPart;
}
//
//   This file contains the C++ code from Program 13.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/pgm13_14.cpp
//
void BuddyPool::Release (void* arg)
{
    Block& block = *reinterpret_cast<Block*> (
reinterpret_cast<Header*> (arg) - 1U);

    if (&block < pool || &block >= pool + numberOfBlocks)
throw invalid_argument ("invalid pointer");

    block.status = free;
    Block* ptr;
    for (ptr = &block; ptr->k < m; ptr->k += 1)
    {
Block& buddy = Buddy (*ptr);
if (buddy.status == reserved || buddy.k != ptr->k)
   break;
Unlink (buddy);
if (&buddy < ptr)
   ptr = &buddy;
    }
    InsertAfter (sentinel [ptr->k], *ptr);
}
//
//   This file contains the C++ code from Program 13.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/pgm13_16.cpp
//
void StoragePoolTest (StoragePool& pool, time timeLimit)
{
    UniformRV size (100, 2001);
    UniformRV latency (1, 101);
    PriorityQueue& queue = *new LeftistHeap ();

    RandomNumberGenerator::SetSeed (1);
    for (time t = 0; t < timeLimit; ++t)
    {
while (!queue.IsEmpty ())
{
   Event& event = dynamic_cast<Event&> (
queue.FindMin ());
   if (event.Key () > t)
break;
   queue.DequeueMin ();
   pool.Release (event.Value ());
   delete &event;
}
unsigned int const length = size.Sample ();
void* const address = pool.Acquire (length);
unsigned int const releaseTime = t + latency.Sample ();
queue.Enqueue (*new Event (releaseTime, address));
    }
    cout << pool << endl;
    delete &queue;
}
//
//   This file contains the C++ code from Program 14.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/pgm14_01.cpp
//
class Solution : public Object
{
public:
    virtual bool IsFeasible () const = 0;
    virtual bool IsComplete () const = 0;
    virtual int Objective () const = 0;
    virtual int Bound () const = 0;
    virtual Solution& Clone () const = 0;
    virtual Iterator& Successors () const = 0;
};
//
//   This file contains the C++ code from Program 14.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/pgm14_02.cpp
//
class Solver
{
protected:
    Solution* bestSolution;
    int bestObjective;
    void UpdateBest (Solution const&);
    virtual void DoSolve (Solution const&) = 0;
public:
    virtual Solution& Solve (Solution const&);
};
//
//   This file contains the C++ code from Program 14.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/pgm14_04.cpp
//
class DepthFirstSolver : public Solver
{
    void DoSolve (Solution const&);
};
//
//   This file contains the C++ code from Program 14.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/pgm14_05.cpp
//
void DepthFirstSolver::DoSolve (Solution const& solution)
{
    if (solution.IsComplete ())
UpdateBest (solution);
    else
    {
Iterator& i = solution.Successors ();
while (!i.IsDone ()) {
   Solution& successor = dynamic_cast<Solution&> (*i);
   DoSolve (successor);
   delete &successor;
   ++i;
}
delete &i;
    }
}
//
//   This file contains the C++ code from Program 14.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/pgm14_06.cpp
//
class BreadthFirstSolver : public Solver
{
    void DoSolve (Solution const&);
};
//
//   This file contains the C++ code from Program 14.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/pgm14_07.cpp
//
void BreadthFirstSolver::DoSolve (Solution const& initial)
{
    Queue& queue = *new QueueAsLinkedList ();
    queue.Enqueue (initial.Clone ());
    while (!queue.IsEmpty ())
    {
Solution& solution =
   dynamic_cast<Solution&> (queue.Dequeue ());
if (solution.IsComplete ())
   UpdateBest (solution);
else
{
   Iterator& i = solution.Successors ();
   while (!i.IsDone ()) {
Solution& succ = dynamic_cast<Solution&> (*i);
queue.Enqueue (succ);
++i;
   }
   delete &i;
}
delete &solution;
    }
    delete &queue;
}
//
//   This file contains the C++ code from Program 14.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/pgm14_08.cpp
//
void DepthFirstBranchAndBoundSolver::DoSolve (
    Solution const& solution)
{
    if (solution.IsComplete ())
UpdateBest (solution);
    else
    {
Iterator& i = solution.Successors ();
while (!i.IsDone ()) {
   Solution& successor = dynamic_cast<Solution&> (*i);
   if (successor.IsFeasible () &&
   successor.Bound () < bestObjective)
DoSolve (successor);
   delete &successor;
   ++i;
}
delete &i;
    }
}
//
//   This file contains the C++ code from Program 14.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/pgm14_10.cpp
//
unsigned int Fibonacci (unsigned int n)
{
    if (n == 0 || n == 1)
return n;
    else
    {
unsigned int const a = Fibonacci ((n + 1) / 2);
unsigned int const b = Fibonacci ((n + 1) / 2 - 1);
if (n % 2 == 0)
   return a * (a + 2 * b);
else
   return a * a + b * b;
    }
}
//
//   This file contains the C++ code from Program 14.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/pgm14_13.cpp
//
unsigned int Binom (unsigned int n, unsigned int m)
{
    Array<unsigned int> b (n + 1);
    b [0] = 1;
    for (unsigned int i = 1; i <= n; ++i)
    {
b [i] = 1;
for (unsigned int j = i - 1U; j > 0; --j)
   b [j] += b [j - 1U];
    }
    return b [m];
}
//
//   This file contains the C++ code from Program 14.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/pgm14_14.cpp
//
void Typeset (Array<unsigned int> const& l,
    unsigned int D, unsigned int s)
{
    unsigned int const n = l.Length ();
    Array2D<unsigned int> L (n, n);
    for (unsigned int i = 0; i < n; ++i)
    {
L [i][i] = l [i];
for (unsigned int j = i + 1; j < n; ++j)
   L [i][j] = L [i][j - 1U] + l [j];
    }
    Array2D<unsigned int> P (n, n);
    for (unsigned int i = 0; i < n; ++i)
for (unsigned int j = i; j < n; ++j)
{
   if (L [i][j] < D)
P [i][j] = abs (D - L [i][j] - (j - i) * s);
   else
P [i][j] = numeric_limits<unsigned int>::max ();
}
    Array2D<unsigned int> C (n, n);
    for (unsigned int j = 0; j < n; ++j)
    {
C [j][j] = P [j][j];
for (int i = j - 1; i >= 0; --i)
{
   unsigned int min = P [i][j];
   for (unsigned int k = i; k < j; ++k)
   {
unsigned int const tmp = P [i][k] + C [k + 1][j];
if (tmp < min)
   min = tmp;
   }
   C [i][j] = min;
}
    }
}
//
//   This file contains the C++ code from Program 14.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/pgm14_15.cpp
//
class RandomNumberGenerator
{
private:
    static long int seed;
    static long int const a;
    static long int const m;
    static long int const q;
    static long int const r;
public:
    static void SetSeed (long int);
    static double Next ();
};
//
//   This file contains the C++ code from Program 14.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/pgm14_17.cpp
//
class RandomVariable
{
public:
    virtual double Sample () = 0;
};

class SimpleRV : public RandomVariable
{
public:
    double Sample ();
};

class UniformRV : public RandomVariable
{
    double u;
    double v;
public:
    UniformRV (double _u, double _v) : u (_u), v (_v) {}
    double Sample ();
};

class ExponentialRV : public RandomVariable
{
    double mu;
public:
    ExponentialRV (double _mu) : mu (_mu) {}
    double Sample ();
};
//
//   This file contains the C++ code from Program 14.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/pgm14_18.cpp
//
double SimpleRV::Sample ()
    { return RandomNumberGenerator::Next (); }

double UniformRV::Sample ()
    { return u + (v - u) * RandomNumberGenerator::Next (); }

double ExponentialRV::Sample ()
    { return -mu * std::log (RandomNumberGenerator::Next ()); }
//
//   This file contains the C++ code from Program 15.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/pgm15_02.cpp
//
template <class T>
void Sorter<T>::Swap (T& x, T& y)
{
    T const tmp = x;
    x = y;
    y = tmp;
}

template <class T>
void Sorter<T>::Sort (Array<T>& array)
{
    n = array.Length ();
    if (n > 0)
    {
unsigned int const tmp = array.Base ();
array.SetBase (0);
DoSort (array);
array.SetBase (tmp);
    }
}
//
//   This file contains the C++ code from Program 15.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/pgm15_03.cpp
//
template <class T>
class InsertionSorter : public Sorter<T> {};

template <class T>
class ExchangeSorter : public Sorter<T> {};

template <class T>
class SelectionSorter : public Sorter<T> {};

template <class T>
class MergeSorter : public Sorter<T> {};

template <class T>
class DistributionSorter : public Sorter<T> {};
//
//   This file contains the C++ code from Program 15.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/pgm15_04.cpp
//
template <class T>
class StraightInsertionSorter : public InsertionSorter<T>
{
protected:
    void DoSort (Array<T>&);
};

template <class T>
void StraightInsertionSorter<T>::DoSort (Array<T>& array)
{
    for (unsigned int i = 1; i < n; ++i)
for (unsigned int j = i;
j > 0 && array [j - 1U] > array [j]; --j)
   Swap (array [j], array [j - 1U]);
}
//
//   This file contains the C++ code from Program 15.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/pgm15_05.cpp
//
template <class T>
class BinaryInsertionSorter : public InsertionSorter<T>
{
protected:
    void DoSort (Array<T>&);
};

template <class T>
void BinaryInsertionSorter<T>::DoSort (Array<T>& array)
{
    for (unsigned int i = 1; i < n; ++i)
    {
T const& tmp = array [i];
unsigned int left = 0;
unsigned int right = i;
while (left < right)
{
   unsigned int const middle = (left + right) / 2;
   if (tmp >= array [middle])
left = middle + 1;
   else
right = middle;
}
for (unsigned int j = i; j > left; --j)
   Swap (array [j - 1U], array [j]);
    }
}
//
//   This file contains the C++ code from Program 15.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/pgm15_07.cpp
//
template <class T>
class QuickSorter : public ExchangeSorter<T>
{
protected:
    static unsigned int const cutOff;

    virtual unsigned int SelectPivot (
Array<T>&, unsigned int, unsigned int) = 0;
    void DoSort (Array<T>&, unsigned int, unsigned int);
    void DoSort (Array<T>&);
};
//
//   This file contains the C++ code from Program 15.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/pgm15_08.cpp
//
template <class T>
void QuickSorter<T>::DoSort (
    Array<T>& array, unsigned int left, unsigned int right)
{
    if (right - left + 1 > cutOff)
    {
unsigned int const p = SelectPivot (array, left, right);
Swap (array [p], array [right]);
T& pivot = array [right];
unsigned int i = left;
unsigned int j = right - 1U;
for (;;)
{
   while (i < j && array [i] < pivot) ++i;
   while (i < j && array [j] > pivot) --j;
   if (i >= j) break;
   Swap (array [i++], array [j--]);
}
if (array [i] > pivot)
   Swap (array [i], pivot);
if (left < i)
   DoSort (array, left, i - 1U);
if (right > i)
   DoSort (array, i + 1, right);
    }
}
//
//   This file contains the C++ code from Program 15.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/pgm15_09.cpp
//
template <class T>
void QuickSorter<T>::DoSort (Array<T>& array)
{
    DoSort (array, 0, n - 1U);
    StraightInsertionSorter<T> s;
    s.Sort (array);
}
//
//   This file contains the C++ code from Program 15.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/pgm15_10.cpp
//
template <class T>
class MedianOfThreeQuickSorter : public QuickSorter<T>
{
protected:
    unsigned int SelectPivot (
Array<T>&, unsigned int, unsigned int);
};

template <class T>
unsigned int MedianOfThreeQuickSorter<T>::SelectPivot (
    Array<T>& array, unsigned int left, unsigned int right)
{
    unsigned int middle = (left + right) / 2;
    if (array [left] > array [middle])
Swap (left, middle);
    if (array [left] > array [right])
Swap (left, right);
    if (array [middle] > array [right])
Swap (middle, right);
    return middle;
}
//
//   This file contains the C++ code from Program 15.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/pgm15_11.cpp
//
template <class T>
class StraightSelectionSorter : public SelectionSorter<T>
{
protected:
    void DoSort (Array<T>&);
};

template <class T>
void StraightSelectionSorter<T>::DoSort (Array<T>& array)
{
    for (unsigned int i = n; i > 1; --i)
    {
unsigned int max = 0;
for (unsigned int j = 1; j < i; ++j)
   if (array [j] > array [max])
max = j;
Swap (array [i - 1U], array [max]);
    }
}
//
//   This file contains the C++ code from Program 15.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/pgm15_12.cpp
//
template <class T>
class HeapSorter : public SelectionSorter<T>
{
protected:
    void BuildHeap (Array<T>&);
    void PercolateDown (Array<T>&, unsigned int, unsigned int);
    void DoSort (Array<T>&);
};
//
//   This file contains the C++ code from Program 15.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/pgm15_14.cpp
//
template <class T>
void HeapSorter<T>::BuildHeap (Array<T>& array)
{
    for (unsigned int i = n / 2; i > 0; --i)
PercolateDown (array, n, i);
}
//
//   This file contains the C++ code from Program 15.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/pgm15_16.cpp
//
template <class T>
class TwoWayMergeSorter : public MergeSorter<T>
{
protected:
    Array<T>* tempArray;

    void Merge (Array<T>&,
unsigned int, unsigned int, unsigned int);
    void DoSort (Array<T>&, unsigned int, unsigned int);
    void DoSort (Array<T>&);
public:
    TwoWayMergeSorter () : tempArray (0) {}
};
//
//   This file contains the C++ code from Program 15.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/pgm15_17.cpp
//
template <class T>
void TwoWayMergeSorter<T>::Merge (Array<T>& array,
    unsigned int left, unsigned int middle, unsigned int right)
{
    unsigned int i = left;
    unsigned int j = left;
    unsigned int k = middle + 1;
    while (j <= middle && k <= right)
    {
if (array [j] <= array [k])
   (*tempArray) [i++] = array [j++];
else
   (*tempArray) [i++] = array [k++];
    }
    while (j <= middle)
(*tempArray) [i++] = array [j++];
    while (k <= right)
(*tempArray) [i++] = array [k++];
    for (i = left; i <= right; ++i)
array [i] = (*tempArray) [i];
}
//
//   This file contains the C++ code from Program 15.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/pgm15_18.cpp
//
template <class T>
void TwoWayMergeSorter<T>::DoSort (Array<T>& array)
{
    tempArray = new Array<T> (n);
    DoSort (array, 0, n - 1U);
    delete tempArray;
    tempArray = 0;
}

template <class T>
void TwoWayMergeSorter<T>::DoSort (Array<T>& array,
    unsigned int left, unsigned int right)
{
    if (left < right)
    {
unsigned int const middle = (left + right) / 2;
DoSort (array, left, middle);
DoSort (array, middle + 1, right);
Merge (array, left, middle, right);
    }
}
//
//   This file contains the C++ code from Program 15.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/pgm15_20.cpp
//
void BucketSorter::DoSort (Array<unsigned int>& array)
{
    for (unsigned int i = 0; i < m; ++i)
count [i] = 0;
    for (unsigned int j = 0; j < n; ++j)
++count [array [j]];
    for (unsigned int i = 0, j = 0; i < m; ++i)
for ( ; count [i] > 0; --count [i])
   array [j++] = i;
}
//
//   This file contains the C++ code from Program 15.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/pgm15_22.cpp
//
unsigned int const RadixSorter::r = 8;
unsigned int const RadixSorter::R = 1 << r;
unsigned int const RadixSorter::p =
    (bitsizeof (unsigned int) + r - 1U) / r;

void RadixSorter::DoSort (Array<unsigned int>& array)
{
    Array<unsigned int> tempArray (n);
    for (unsigned int i = 0; i < p; ++i)
    {
for (unsigned int j = 0; j < R; ++j)
   count [j] = 0;
for (unsigned int k = 0; k < n; ++k)
{
   ++count [(array [k] >> (r * i)) & (R - 1U)];
   tempArray [k] = array [k];
}
unsigned int pos = 0;
for (unsigned int j = 0; j < R; ++j)
{
   unsigned int const tmp = count [j];
   count [j] = pos;
   pos += tmp;
}
for (unsigned int k = 0; k < n; ++k)
{
   unsigned int j =
(tempArray [k] >> (r * i)) & (R - 1U);
   array [count [j]++] = tempArray [k];
}
    }
}
//
//   This file contains the C++ code from Program 16.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/pgm16_01.cpp
//
class Vertex : public Object
{
public:
    typedef unsigned int Number;
protected:
    Number number;
public:
    Vertex (Number);
    virtual operator Number () const;
    // ...
};
//
//   This file contains the C++ code from Program 16.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/pgm16_02.cpp
//
class Edge : public Object
{
protected:
    Vertex& v0;
    Vertex& v1;
public:
    Edge (Vertex&, Vertex&);
    virtual Vertex& V0 () const;
    virtual Vertex& V1 () const;
    virtual Vertex& Mate (Vertex const&) const;
    // ...
};
//
//   This file contains the C++ code from Program 16.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/pgm16_03.cpp
//
class Graph : public Container
{
protected:
    unsigned int numberOfVertices;
    unsigned int numberOfEdges;

    void DepthFirstTraversal (
PrePostVisitor&, Vertex&, Array<bool>&) const;
public:
    Graph ();

    virtual unsigned int NumberOfEdges () const;
    virtual unsigned int NumberOfVertices () const;
    virtual void AddVertex (Vertex&) = 0;
    virtual Vertex& SelectVertex (Vertex::Number) const = 0;
    virtual Vertex& operator [] (Vertex::Number) const;
    virtual void AddEdge (Edge&) = 0;
    virtual Edge& SelectEdge (
Vertex::Number, Vertex::Number) const = 0;
    virtual bool IsEdge (
Vertex::Number, Vertex::Number) const = 0;
    virtual bool IsConnected () const;
    virtual bool IsCyclic () const;

    virtual Iterator& Vertices () const = 0;
    virtual Iterator& Edges () const = 0;
    virtual Iterator& IncidentEdges (Vertex const&) const = 0;
    virtual Iterator& EmanatingEdges (Vertex const&) const = 0;

    virtual void DepthFirstTraversal (
PrePostVisitor&, Vertex const&) const;
    virtual void BreadthFirstTraversal (
Visitor&, Vertex const&) const;
    // ...
};

class Digraph : public virtual Graph
{
public:
    virtual bool IsConnected () const;
    virtual bool IsCyclic () const;
    virtual void TopologicalOrderTraversal (
Visitor&) const;
};
//
//   This file contains the C++ code from Program 16.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/pgm16_05.cpp
//
class GraphAsLists : public virtual Graph
{
protected:
    Array<Vertex*> vertices;
    Array<LinkedList<Edge*> > adjacencyLists;
public:
    GraphAsLists (unsigned int);
    // ...
};
//
//   This file contains the C++ code from Program 16.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/pgm16_06.cpp
//
class WeightedVertex : public Vertex
{
    Object* weight;
public:
    WeightedVertex (Vertex::Number, Object&);
    virtual Object& Weight () const;
    // ...
};
    
class WeightedEdge : public Edge
{
    Object* weight;
public:
    WeightedEdge (Vertex&, Vertex&, Object&);
    virtual Object& Weight () const;
    // ...
};
//
//   This file contains the C++ code from Program 16.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/pgm16_07.cpp
//
void Graph::DepthFirstTraversal (
    PrePostVisitor& visitor, Vertex const& start) const
{
    Array<bool> visited (numberOfVertices);
    for (Vertex::Number v = 0; v < numberOfVertices; ++v)
visited [v] = false;
    DepthFirstTraversal (
visitor, const_cast<Vertex&> (start), visited);
}

void Graph::DepthFirstTraversal (PrePostVisitor& visitor,
    Vertex& vertex, Array<bool>& visited) const
{
    if (visitor.IsDone ())
return;
    visitor.PreVisit (vertex);
    visited [vertex] = true;
    Iterator& p = EmanatingEdges (vertex);
    while (!p.IsDone ()) {
Edge& edge = dynamic_cast<Edge&> (*p);
Vertex& to = edge.Mate (vertex);
if (!visited [to])
   DepthFirstTraversal (visitor, to, visited);
++p;
    }
    delete &p;
    visitor.PostVisit (vertex);
}
//
//   This file contains the C++ code from Program 16.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/pgm16_08.cpp
//
void Graph::BreadthFirstTraversal (
    Visitor& visitor, Vertex const& start) const
{
    Array<bool> enqueued (numberOfVertices);
    for (Vertex::Number v = 0; v < numberOfVertices; ++v)
enqueued [v] = false;

    Queue& queue = *new QueueAsLinkedList ();
    queue.RescindOwnership ();

    enqueued [start] = true;
    queue.Enqueue (const_cast<Vertex&> (start));
    while (!queue.IsEmpty () && !visitor.IsDone ())
    {
Vertex& vertex =
   dynamic_cast<Vertex&> (queue.Dequeue ());
visitor.Visit (vertex);
Iterator& p = EmanatingEdges (vertex);
while (!p.IsDone ()) {
   Edge& edge = dynamic_cast<Edge&> (*p);
   Vertex& to = edge.Mate (vertex);
   if (!enqueued [to])
   {
enqueued [to] = true;
queue.Enqueue (to);
   }
   ++p;
}
delete &p;
    }
    delete &queue;
}
//
//   This file contains the C++ code from Program 16.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/pgm16_09.cpp
//
void Digraph::TopologicalOrderTraversal (Visitor& visitor) const
{
    Array<unsigned int> inDegree (numberOfVertices);
    for (Vertex::Number v = 0; v < numberOfVertices; ++v)
inDegree [v] = 0;
    Iterator& p = Edges ();
    while (!p.IsDone ()) {
Edge& edge = dynamic_cast<Edge&> (*p);
++inDegree [edge.V1 ()];
++p;
    }
    delete &p;

    Queue& queue = *new QueueAsLinkedList ();
    queue.RescindOwnership ();
    for (Vertex::Number v = 0; v < numberOfVertices; ++v)
if (inDegree [v] == 0)
   queue.Enqueue (SelectVertex (v));
    while (!queue.IsEmpty () && !visitor.IsDone ())
    {
Vertex& vertex =
   dynamic_cast<Vertex&> (queue.Dequeue ());
visitor.Visit (vertex);
Iterator& q = EmanatingEdges (vertex);
while (!q.IsDone ()) {
   Edge& edge = dynamic_cast<Edge&> (*q);
   Vertex& to = edge.V1 ();
   if (--inDegree [to] == 0)
queue.Enqueue (to);
   ++q;
}
delete &q;
    }
    delete &queue;
}
//
//   This file contains the C++ code from Program 16.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/pgm16_10.cpp
//
class CountingVisitor : public Visitor
{
    unsigned int count;
public:
    CountingVisitor () : count (0)
{}
    void Visit (Object&)
{ ++count; }
    unsigned int Count () const
{ return count; }
};

bool Graph::IsConnected () const
{
    CountingVisitor visitor;
    DepthFirstTraversal (PreOrder (visitor), SelectVertex (0));
    return visitor.Count () == numberOfVertices;
}
//
//   This file contains the C++ code from Program 16.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/pgm16_12.cpp
//
bool Digraph::IsCyclic () const
{
    CountingVisitor visitor;
    TopologicalOrderTraversal (visitor);
    return visitor.Count () != numberOfVertices;
}
//
//   This file contains the C++ code from Program 16.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/pgm16_14.cpp
//
Digraph& DijkstrasAlgorithm (Digraph const& g, Vertex const& s)
{
    unsigned int const n = g.NumberOfVertices ();
    Array<TableEntry> table (n);
    PriorityQueue& queue = *new BinaryHeap (g.NumberOfEdges ());
    table [s].distance = 0;
    queue.Enqueue (*new Assoc (0, const_cast<Vertex&> (s)));
    while (!queue.IsEmpty ())
    {
Assoc& assoc =
   dynamic_cast<Assoc&> (queue.DequeueMin ());
Vertex& v0 = dynamic_cast<Vertex&> (assoc.Value ());
if (!table [v0].known)
{
   table [v0].known = true;
   Iterator& p = g.EmanatingEdges (v0);
   while (!p.IsDone ()) {
WeightedEdge& edge =
   dynamic_cast<WeightedEdge&> (*p);
Vertex& v1 = edge.V1 ();
Int& weight =
   dynamic_cast<Int&> (edge.Weight ());
int const d = table [v0].distance + weight;
if (table [v1].distance > d)
{
   table [v1].distance = d;
   table [v1].predecessor = v0;
   queue.Enqueue (*new Assoc (d, v1));
}
++p;
   }
   delete &p;
}
delete &assoc;
    }
    delete &queue;

    Digraph& result = *new DigraphAsLists (n);
    for (Vertex::Number v = 0; v < n; ++v)
result.AddVertex (*new WeightedVertex (
   v, *new Int (table [v].distance)));
    for (Vertex::Number v = 0; v < n; ++v)
if (v != s)
   result.AddEdge (*new Edge (
result [v], result [table [v].predecessor]));
    return result;
}
//
//   This file contains the C++ code from Program 16.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/pgm16_15.cpp
//
Digraph& FloydsAlgorithm (Digraph const& g)
{
    using numeric_limits<unsigned int>::max;

    unsigned int const n = g.NumberOfVertices ();
    Array2D<unsigned int> distance (n, n);
    for (Vertex::Number v = 0; v < n; ++v)
for (Vertex::Number w = 0; w < n; ++w)
   distance [v][w] = max ();
    Iterator& p = g.Edges ();
    while (!p.IsDone ())
    {
WeightedEdge& edge = 
   dynamic_cast<WeightedEdge&> (*p);
Int& weight = dynamic_cast<Int&> (edge.Weight ());
distance [edge.V0 ()][edge.V1 ()] = weight;
++p;
    }
    delete &p;

    for (Vertex::Number i = 0; i < n; ++i)
for (Vertex::Number v = 0; v < n; ++v)
   for (Vertex::Number w = 0; w < n; ++w)
if (distance [v][i] != max () &&
   distance [i][w] != max ())
{
   int const d =
distance [v][i] + distance [i][w];
   if (distance [v][w] > d)
distance [v][w] = d;
}

    Digraph& result = *new DigraphAsMatrix (n);
    for (Vertex::Number v = 0; v < n; ++v)
result.AddVertex (*new Vertex (v));
    for (Vertex::Number v = 0; v < n; ++v)
for (Vertex::Number w = 0; w < n; ++w)
   if (distance [v][w] != max ())
result.AddEdge (*new WeightedEdge (
   result [v], result [w],
   *new Int (distance [v][w])));
    return result;
}
//
//   This file contains the C++ code from Program 16.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/pgm16_16.cpp
//
Graph& PrimsAlgorithm (Graph const& g, Vertex const& s)
{
    unsigned int const n = g.NumberOfVertices ();
    Array<TableEntry> table (n);
    PriorityQueue& queue = *new BinaryHeap (g.NumberOfEdges ());
    table [s].distance = 0;
    queue.Enqueue (*new Assoc (0, const_cast<Vertex&> (s)));
    while (!queue.IsEmpty ())
    {
Assoc& assoc =
   dynamic_cast<Assoc&> (queue.DequeueMin ());
Vertex& v0 = dynamic_cast<Vertex&> (assoc.Value ());
if (!table [v0].known)
{
   table [v0].known = true;
   Iterator& p = g.EmanatingEdges (v0);
   while (!p.IsDone ()) {
WeightedEdge& edge =
   dynamic_cast<WeightedEdge&> (*p);
Vertex& v1 = edge.Mate (v0);
Int& weight =
   dynamic_cast<Int&> (edge.Weight ());
int const d = weight;
if (!table[v1].known && table[v1].distance > d)
{
   table [v1].distance = d;
   table [v1].predecessor = v0;
   queue.Enqueue (*new Assoc (d, v1));
}
++p;
   }
   delete &p;
}
delete &assoc;
    }
    delete &queue;

    Graph& result = *new GraphAsLists (n);
    for (Vertex::Number v = 0; v < n; ++v)
result.AddVertex (*new Vertex (v));

    for (Vertex::Number v = 0; v < n; ++v)
if (v != s)
   result.AddEdge (*new Edge (
result [v], result [table [v].predecessor]));
    return result;
}
//
//   This file contains the C++ code from Program 16.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/pgm16_17.cpp
//
Graph& KruskalsAlgorithm (Graph const& g)
{
    unsigned int const n = g.NumberOfVertices ();

    Graph& result = *new GraphAsLists (n);
    for (Vertex::Number v = 0; v < n; ++v)
result.AddVertex (*new Vertex (v));

    PriorityQueue& queue = *new BinaryHeap (g.NumberOfEdges ());
    Iterator& p = g.Edges ();
    while (!p.IsDone ()) {
WeightedEdge& edge =
   dynamic_cast<WeightedEdge&> (*p);
Int& weight = dynamic_cast<Int&> (edge.Weight ());
queue.Enqueue (*new Assoc (weight, edge));
++p;
    }
    delete &p;

    Partition& partition = *new PartitionAsForest (n);
    while (!queue.IsEmpty () && partition.Count () > 1)
    {
Assoc& assoc =
   dynamic_cast<Assoc&> (queue.DequeueMin ());
Edge& edge = dynamic_cast<Edge&> (assoc.Value ());
Vertex::Number const v0 = edge.V0 ();
Vertex::Number const v1 = edge.V1 ();
Set& s = partition.Find (Set::Element (v0));
Set& t = partition.Find (Set::Element (v1));
if (s != t)
{
   partition.Join (s, t);
   result.AddEdge (*new Edge (result[v0], result[v1]));
}
delete &assoc;
    }
    delete &partition;
    delete &queue;
    return result;
}
//
//   This file contains the C++ code from Program 16.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/pgm16_18.cpp
//
class EarliestTimeVisitor : public Visitor
{
    Graph& graph;
    Array<unsigned int>& earliestTime;
public:
    EarliestTimeVisitor (Graph& g, Array<unsigned int>& e) :
graph (g), earliestTime (e)
{}
    void Visit (Object& object)
    {
Vertex& w = dynamic_cast<Vertex&> (object);
unsigned int max = earliestTime [0];
Iterator& p = graph.IncidentEdges (w);
while (!p.IsDone ()) {
   WeightedEdge& edge =
dynamic_cast<WeightedEdge&> (*p);
   Int& weight =
dynamic_cast<Int&> (edge.Weight ());
   Vertex& v = edge.V0 ();
   unsigned int const t =
earliestTime [v] + weight;
   if (t > max)
max = t;
   ++p;
}
delete &p;
earliestTime [w] = max;
    }
};
//
//   This file contains the C++ code from Program 16.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/pgm16_19.cpp
//
Digraph& CriticalPathAnalysis (Digraph& g)
{
    unsigned int const n = g.NumberOfVertices ();

    Array<unsigned int> earliestTime (n);
    earliestTime [0] = 0;
    g.TopologicalOrderTraversal (
EarliestTimeVisitor (g, earliestTime));

    Array<unsigned int> latestTime (n);
    latestTime [n - 1U] = earliestTime [n - 1U];
    g.DepthFirstTraversal (PostOrder (
LatestTimeVisitor (g, latestTime)), g[0]);

    DigraphAsLists slackGraph (n);
    for (Vertex::Number v = 0; v < n; ++v)
slackGraph.AddVertex (*new Vertex (v));
    Iterator& p = g.Edges ();
    while (!p.IsDone ()) {
WeightedEdge& edge =
   dynamic_cast<WeightedEdge&> (*p);
Int& weight =
   dynamic_cast<Int&> (edge.Weight ());
Vertex& v0 = edge.V0 ();
Vertex& v1 = edge.V1 ();
unsigned int const slack =
   latestTime [v1] - earliestTime [v0] - weight;
slackGraph.AddEdge (*new WeightedEdge (
   slackGraph [v0], slackGraph [v1], *new Int(slack)));
++p;
    }
    delete &p;

    return DijkstrasAlgorithm (slackGraph, slackGraph [0]);
}

Comentarii

Postări populare de pe acest blog

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='+'…

NUMERE PRIME ALGORITM C++

// NUMERE PRIME ALGORITM C++//  reediting from scratch //on this page is just the study for a next algoritm for generating the parime nr series like Fibonnaci or ....if possibile

74111121313417374414124343447 if u know the red part you can generate the orange part
1 0 1 111112222 1 1 23

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…