Sources/CollectionClasses.cp

/*
    File:       CollectionClasses.cp
 
    Contains:   The following collection classes are implemented: TLinkedList, TStack, (TQueue, TDeQueue),
                THashTable.
                CollectionClasses.cp contains the collection class member functions. 
 
    Written by: Kent Sandvik    
 
    Copyright:  Copyright © 1992-1999 by Apple Computer, Inc., All Rights Reserved.
 
                You may incorporate this Apple sample source code into your program(s) without
                restriction. This Apple sample source code has been provided "AS IS" and the
                responsibility for its operation is yours. You are not permitted to redistribute
                this Apple sample source code as "Apple sample source code" after having made
                changes. If you're going to re-distribute the source, we require that you make
                it clear in the source that the code was descended from Apple sample source
                code, but that you've made changes.
 
    Change History (most recent first):
                8/18/1999   Karl Groethe    Updated for Metrowerks Codewarror Pro 2.1
                
 
*/
#ifndef _COLLECTION_
#include "CollectionClasses.h"
#endif
 
 
// _________________________________________________________________________________________________________ //
//  TLINKEDLIST Class definitions.
 
//  CONSTRUCTORS AND DESTRUCTORS
#pragma segment Collections
TLinkedList::TLinkedList(short max)
// Create a Linked list class (max entries pre-defined in a constant in the header file).
{
    fMaxCollectionSize = max;                   // keep track of how many entries we could add to the collection
    fCollectionSize = 0;                        // no entries yet
    // Fix the head and the rest of the pointer hooks.
    fHead = new fNODE;                          // create nodes
    fTail = new fNODE;
    fLastEntry = new fNODE;
    fCurrentNode = new fNODE;
 
    fHead->fNext = fTail;                       // default head points at tail, then we will push in nodes between
    fHead->fPrevious = fHead;                   // bit your own tail
    fTail->fNext = fTail;                       // bite your own tail
    fTail->fPrevious = fHead;                   // hook tail with head (double linked list)
    fTail->fKey = NULL;                         // mark the last entry as NULL
    fHead->fKey = NULL;                         // mark the first entry as NULL
    fLastEntry->fPrevious = fHead;              // hook the ptr node between the head
    fLastEntry->fNext = fTail;                  // Éand the tail
}
 
 
#pragma segment Collections
TLinkedList::~TLinkedList()
// Destruct the structures required for the former linked list.
{
    struct fNODE* temp = fHead;                 // create a temp node
 
    while (temp != fTail)
        // while we have entries, delete them from head to tail
        {
            fHead = temp;                       // copy temp node to the head position
            temp = temp->fNext;                 // and make temp point at the next one
            delete fHead;                       // meanwhile delete the head, and continue copying tmp to head
        }
}
 
 
//  MAIN INTERFACES
 
#pragma segment Collections
Boolean TLinkedList::Append(const TItemtype item)
// Append entry to the linked list (at the end).
{
    if (fCollectionSize < fMaxCollectionSize)
    {
        struct fNODE*        temp = new fNODE;  // create a new node
        temp->fKey = item;
 
        // Hook the temp node between the last entry and the tail       
        if (fCollectionSize == 0)               // first entry?
        {
            fHead->fNext = temp;                // hook it just after the head
            temp->fNext = fTail;                // and before the tail
            fLastEntry = temp;                  // and keep track of it!
        }
        else                                    // OK now we will track of the fCurrentNode
            {
                temp->fNext = fTail;            // stuck it just before the tail
                fLastEntry->fNext = temp;       // and after the current node
                fLastEntry = temp;              // and mark it the current node
            }
 
        fCollectionSize++;                      // keep a count on the size of the linked list
        goto AppendOK;
    }
    ASSERT(fCollectionSize < fMaxCollectionSize, "\pOverflow of the LinkedList");
    return false;
AppendOK:return true;
}
 
 
#pragma segment Collections
Boolean TLinkedList::Remove(const TItemtype item)
// Remove defined entry from the linked list.
{
    // First find the item, if found remove it, connect the links and decrease the collection size count
    this->Reset();                              // get back to the first entry
    struct fNODE*            temp = fHead;      // keep a temp pointer to earlier node passed
 
    do                                          // walk along the list  
    {
        if (fCurrentNode->fKey == item)         // found a hit? 
        {
            // yes!
            temp->fNext = fCurrentNode->fNext;  // short circuit the current node
            delete fCurrentNode;                // delete this node
            fCollectionSize--;                  // decreate the collection count
            goto OK;                            // and jump out 
        }
 
        temp = fCurrentNode;                    // keep track of the just visited node
        fCurrentNode = fCurrentNode->fNext;     // Éand step forward
    } while (fCurrentNode != fTail);            // as long as we are inside the linked list 
 
    return false;                               // nothing happenedÉ
OK: return true;                                // OK, we were able to delete the entry
}
 
 
#pragma segment Collections
Boolean TLinkedList::IsEmpty()
// Check if the collection is empty (head points at tail).
{
    return (fHead->fNext == fTail);             // check if the next pointer is pointing on the tail
}
 
 
#pragma segment Collections
Boolean TLinkedList::Find(const TItemtype item)
// Find if we have the itemtype in the 'queue'.
{
    TItemtype tempVal;
    this->Reset();                              // get back to the first entry
 
    while ((tempVal = this->Next()) != NULL)
        // get all entries one at a time
        {
            if (tempVal == item)                // if we found a one-to-one relationship
                return true;                    // signal OK
        }
    return false;                               // otherwise signal false
}
 
 
#pragma segment Collections
Size TLinkedList::GetSize() const
// Return the internal count of entries in collection.
{
    return fCollectionSize;
}
 
 
// ITERATORS
#pragma segment Collections
TItemtype TLinkedList::First()
// Get the first entry in the collection.
{
    if (fCollectionSize != 0)
        return fHead->fNext->fKey;              // return what FHead->fNext has (the first 'real' node)
    else
        return NULL;
}
 
 
#pragma segment Collections
TItemtype TLinkedList::Next()
// Return next entry in the list.
{
    TItemtype item;
    item = fCurrentNode->fKey;                  // get current item
    fCurrentNode = fCurrentNode->fNext;         // then increase the node to the next entry
 
    return item;                                // return item
}
 
 
#pragma segment Collections
TItemtype TLinkedList::Last()
// Return last entry in the list.
{
    // because we cached the first entry, it's easy to return it
    // we might have problems with a real de-queue later if 
    // we don't revise this scheme (but most likely we will override Last() with new behavior
    return fLastEntry->fKey;                    // the fLastNode is always pointing at the last entry
}
 
 
#pragma segment Collections
void TLinkedList::Reset()
// Make the current node point at the first entry from beginning (reset).
{
    fCurrentNode = fHead->fNext;                // reset the fCurrentNode pointer to the first entry
}
 
 
// _________________________________________________________________________________________________________ //
//  TSTACK Class definitions.
 
//  CONSTRUCTORS AND DESTRUCTORS
#pragma segment Collections
TStack::TStack(short max)
// Create a stack class (max pre-defined in the header files as a constant).
{
    fMaxCollectionSize = max;                   // keep track of how big we could grow the stack into
    fCollectionSize = 0;                        // no entries yet
}
 
 
#pragma segment Collections
TStack::~TStack()
// Default constructor -- not used for the time being.
{
}
 
 
//  MAIN INTERFACES
#pragma segment Collections
Boolean TStack::Push(const TItemtype item)
// Push entry into the stack (beginning).
{
    if (fCollectionSize < fMaxCollectionSize)   // yes, we bail out and don't add more entries
    {
        struct fNODE* temp = new fNODE;         // create temp node
        temp->fKey = item;                      // store value in temp node
        temp->fNext = fHead->fNext;             // make temp point at the real next block 
        fHead->fNext = temp;                    // and make temp suddenly the real head (stack head!)
        fCollectionSize++;                      // increase the stack size
        if (fCollectionSize == 1)               // first entry?
            fLastEntry = temp;                  // store it for fast access later (cache the ptr)
 
        goto PushOK;
    }
    ASSERT(fCollectionSize < fMaxCollectionSize, "\pOverflow of the Stack");// signal about a possible problem
    return false;
PushOK:return true;
}
 
 
#pragma segment Collections
TItemtype TStack::Pop()
// Pop entry from the stack (beginning).
{
    TItemtype item;
    struct fNODE* temp = fHead->fNext;          // create temp node with the header next pointer values
    fHead->fNext = temp->fNext;                 // copy back the following pointer from temp to the head
    item = temp->fKey;                          // get the temp item
 
    delete temp;                                // delete the suddenly non-needed node
    fCollectionSize--;                          // decrease the stack
    return item;                                // return the asked value
}
 
 
#pragma segment Collections
Boolean TStack::Append(const TItemtype item)
// Append entry, same as Push, but we included it.
{
    return (this->Push(item));                  // call the one and only method supported with stack insertion
}
 
 
#pragma segment Collections
Boolean TStack::Remove(const TItemtype          /*item*/)
// Remove is not implemented, but we had to include it because we are subclassing from a TLinkedList.
{
    return false;                               // not supported
}
 
 
// _________________________________________________________________________________________________________ //
//  TQUEUE
//  CONSTRUCTORS AND DESTRUCTORS
#pragma segment Collections
TQueue::TQueue(short max)
// Create a queue class (max pre-defined in the header files as a constant).
{
    fMaxCollectionSize = max;                   // keep track of how big we could grow the stack into
    fCollectionSize = 0;                        // no entries yet
}
 
 
#pragma segment Collections
TQueue::~TQueue()
// Default destructor, not used for the time being.
{
}
 
 
//  MAIN INTERFACE
#pragma segment Collections
Boolean TQueue::Put(const TItemtype item)
// Put entry into the queue (beginning).
{
    if (fCollectionSize < fMaxCollectionSize)   // no problems?
    {
        struct fNODE* temp = new fNODE;         // create a new node
        temp->fKey = item;                      // add value to the node bucket 
 
        // place it in the beginning of the queue
        temp->fNext = fHead->fNext;             // push it into the queue
        fHead->fNext = temp;                    // now it's there
 
        // update the tail pointer
        if (fCollectionSize == 0)               // first entry?
        {
            fTail->fPrevious = temp;            // hook fTail to the entry
        }
        temp->fPrevious = fHead;                // and hook it back to head
        fLastEntry->fPrevious = temp;           // and as well as to the current first entry
        fLastEntry = temp;                      // and mark it as the current first entry   
 
        fCollectionSize++;                      // increase the collection count
        goto QueueOK;
    }
    ASSERT(fCollectionSize < fMaxCollectionSize, "\pOverflow of TQueue");
    return false;
QueueOK:return true;
}
 
 
#pragma segment Collections
Boolean TQueue::Append(const TItemtype item)
// Append is the same as Put.
{
    return (this->Put(item));                   // call TQueue.Put
}
 
 
#pragma segment Collections
TItemtype TQueue::Get()
// Get entry from the end of the list (queue).
{
    TItemtype item;
 
    // get the node and the value       
    struct fNODE* temp = fTail->fPrevious;      // get the last before fTail
    item = temp->fKey;                          // get the item 
 
 
    // change the pointers
    fTail->fPrevious = temp->fPrevious;         // hook fTail to the previous entry
    temp->fPrevious->fNext = fTail;             // hook the node to tail as well    
 
    delete temp;                                // delete the entry 
 
    fCollectionSize--;                          // decrease the collection count    
    return item;                                // return the item
}
 
 
#pragma segment Collections
TItemtype TQueue::Last()
// Get last entry from queue.
{
    return fTail->fPrevious->fKey;              // get the last entry
}
 
 
#pragma segment Collections
Boolean TQueue::Remove(const TItemtype          /*item*/)
// Remove is not supported, but we needed to include this because TQueue is subclassed from TLinkedList
{
    return false;                               // not supported
}
 
 
 
// _________________________________________________________________________________________________________ //
// TDEQUE
 
//  CONSTRUCTORS AND DESTRUCTORS
#pragma segment Collections
TDeque::TDeque(short max)
// Create dequeue class (max pre-defined in the header files as a constant).
{
    fMaxCollectionSize = max;                   // keep track of how big we could grow the stack into
    fCollectionSize = 0;                        // no entries yet
}
 
 
#pragma segment Collections
TDeque::~TDeque()
// Default destructor, not used for the time being.
{
}
 
#pragma segment Collections
Boolean TDeque::Push(const TItemtype item)
// Push entry into queue (beginning).
{
    return (TQueue::Put(item));                 // call inherited Put
}
 
 
#pragma segment Collections
Boolean TDeque::PutAtEnd(const TItemtype item)
// Place entry at end of the deque.
{
    if (fCollectionSize < fMaxCollectionSize)   // bail out if we reach the limit
    {
        struct fNODE*     temp = new fNODE;     // create temp node
        temp->fKey = item;                      // store the value
        temp->fNext = fTail;                    // point at tail
        temp->fPrevious = fTail->fPrevious;     // make the backwards ptr hooked to the new entry
        fTail->fPrevious->fNext = temp;         // and hook the old last one into this one 
        fTail->fPrevious = temp;                // make the tail point at the new entry
 
        fCollectionSize++;                      // increase the counter
        goto PutAtEndOK;
    }
    ASSERT(fCollectionSize < fMaxCollectionSize, "\pOverflow of the TDeque");
    return false;
PutAtEndOK:return true;
}
 
 
TItemtype TDeque::Pop()
// Pop entry from the queue end.
{
    TItemtype item;
    struct fNODE* temp = fHead->fNext;          // hook to the beginning of the deque
    fHead->fNext = temp->fNext;                 // hook head to the following node
    temp->fNext->fPrevious = fHead;             // and the next one should point back at the head
 
    item = temp->fKey;                          // get the stored value
    delete temp;                                // remove node
    fCollectionSize--;                          // decrease the counter
 
    return item;                                // and return the item
}
 
 
// _________________________________________________________________________________________________________ //
// THASHTABLE 
 
//  CONSTRUCTORS AND DESTRUCTORS
THashTable::THashTable()
// Create a hash table class.
{
    // Clear the array bucket.
    for (long i = 0; i < NBUCKETS; i++)
        fBucket[i] = 0;
}
 
 
THashTable::~THashTable()
// Delete any memory structures required for the hashtable class.
{
    // Delete the entries in the array bucket.  
    for (long i = 0; i < NBUCKETS; i++)
    {
        THashEntryPtr p = fBucket[i];           // get a ptr to the entry
        while (p)
            // while a valid ptr
            {
                fBucket[i] = p->fNext;          // install next entry in array
                delete p;                       // delete the current node
                p = fBucket[i];                 // ptr back to the new value
            }
    }
}
 
 
//  MAIN INTERFACE
#pragma segment Collections
Boolean THashTable::Add(THashKey key,
                        TItemtype value)
// Add entries to the hash table.
{
    THashEntryPtr p;
    THashKey whichItem = this->Hash(key);       // hash out the real value
 
    cout << " whichItem = " << whichItem << "\n";
 
    p = FindInBucket(fBucket[whichItem], key);
    if (p)                                      // have already an entry?
        goto problem;                           // signal the failure
 
    p = this->AddElement(key);                  // add our entry
    p->fValue = value;                          // add the item value to the entry
    return true;
 
problem:return false;
}
 
 
#pragma segment Collections
Boolean THashTable::Remove(THashKey key)
// Remove entries from the hash table.
{
    THashKey whichItem = this->Hash(key);       // hash out the real value
    THashEntryPtr p = FindInBucket(fBucket[whichItem], key);
    if (!p)                                     // no valid ptr?
        goto problem;
 
    if (fBucket[whichItem] == p)
        fBucket[whichItem] = p->fNext;          // connect to next node
 
    delete p;                                   // delete current node
    return true;
 
problem:return false;
}
 
 
 
#pragma segment Collections
TItemtype THashTable::Find(THashKey key)
// Find entries in the hash table.
{
    THashKey whichItem = this->Hash(key);       // hash out the real value
    THashEntryPtr p = this->FindInBucket(fBucket[whichItem], key);
    if (!p)
        return 0;                               // return 0
    else
        return p->fValue;                       // return valid value
}
 
 
void THashTable::MapCar(MapFun function)
// Run a function on each entry in the hash table.
{
    for (long i = 0; i < NBUCKETS; i++)         // iterate through all the entries
    {
        THashEntryPtr p = fBucket[i];           // get the ptr to the entry
 
        while (p)
            // while we have a nice value
            {
                function(p);                    // call the function on p
                p = p->fNext;                   // get the next ptr
            }
    }
}
 
 
// PRIVATE INTERNAL FUNCTIONS
THashEntryPtr THashTable::AddElement(THashKey key)
// Add an element to the internal structure.
{
    THashKey whichItem = this->Hash(key);
    THashEntryPtr p = new THashEntry(key);
 
    p->fNext = fBucket[whichItem];              // get ptr to next entry
    if (fBucket[whichItem])                     // OK?
        fBucket[whichItem]->fPrevious = p;      // establish ptrs backwards
 
    fBucket[whichItem] = p;                     // as well as the current one
 
    return p;
}
 
 
THashKey THashTable::Hash(THashKey key)
// Hash out a key to be used with the buckets. Override for your own preferences.
{
    key &= kResourceIDMask;
    return ((THashKey)(0x7FF & (key ^ (key >> 11))) % NBUCKETS);
    // Note: if you write your own hash function, don't forget modula NBUCKETS to get
    // down the size of the key so it hooks to the buckets.
}
 
 
THashEntryPtr THashTable::FindInBucket(THashEntryPtr p,
                                       THashKey key)
// Find bucket where entry is located.
{
    while (p)
        // valid pointer?
        {
            if (p->fKey == key)                 // hit?
                break;                          // found it!
            p = p->fNext;                       // nope, continue cycling the list
        }
    return p;                                   // return found (not found) ptr
}
 
 
// _________________________________________________________________________________________________________ //
 
 
/*  Change History (most recent last):
  No        Init.   Date        Comment
  1         khs     11/7/92     New file
  2         khs     11/28/92    Added TLinkedList
  3         khs     11/29/92    Added TQueue and TDeque
  4         khs     1/14/93     Cleanup
*/


Copyright © 2003 Apple Computer, Inc. All Rights Reserved. Terms of Use | Privacy Policy | Updated: 2003-01-14