/*

    File:       CollectionClasses.h

    Contains:   The following collection classes are implemented: TLinkedList, TStack, (TQueue, TDeQueue),

                THashTable.

                CollectionClasses.h contains the collection class definitions. 

    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

*/

// Declare label for this header file

#ifndef _COLLECTION__

#define _COLLECTION__

#ifndef _DTSCPLUSLIBRARY_

#include "DTSCPlusLibrary.h"

#endif

//  GLOBAL CONSTRUCTS

typedef unsigned long TItemtype;

//typedef void* TItemtype;

// Note that we need to define this for the collecion items --

// when we have tempates this will be moot!

// Note that void* is the most practical one concerning storing

// data structure pointers in lists, queues and stacks (typedef void * TItemtype)

const kCollectionSize = 200;                    // tune this concerning performance

// _________________________________________________________________________________________________________ //

//  TLinkedList Class Interface.

class TLinkedList

{

public:

    //  CONSTRUCTORS AND DESTRUCTORS

    TLinkedList(short max = kCollectionSize);

    virtual~ TLinkedList();

    // MAIN INTERFACES

    virtual Boolean Append(const TItemtype item);// add an entry to the linked list

    virtual Boolean Remove(const TItemtype item);// remove defined item from the linked list

    virtual Boolean IsEmpty();                  // check if the collection has zero entries

    virtual Boolean Find(const TItemtype item); // find out if a special item type is in the list

    virtual Size GetSize() const;               // get amount of entries in collection

    // ITERATORS

    virtual TItemtype First();                  // return first entry

    virtual TItemtype Next();                   // return next entry

    virtual TItemtype Last();                   // return last entry

    virtual void Reset();                       // move iterator to first entry     

    //  FIELDS

protected:

    short fMaxCollectionSize;                   // max entries in the collection

    short fCollectionSize;                      // current amount of entries in the collection

    struct fNODE                                // our pointer list structure

    {

        TItemtype fKey;

        struct fNODE *fNext;

        struct fNODE *fPrevious;                // for future use

    };

    struct fNODE *fHead, * fTail, * fLastEntry, * fCurrentNode;

    // linked list pointers: forward, backward, last entry, current

};

// _________________________________________________________________________________________________________ //

//  TStack Class Interface.

class TStack : public TLinkedList

{

public:

    // CONSTRUCTORS AND DESTRUCTORS

    TStack(short max = kCollectionSize);

    virtual~ TStack();

    // MAIN INTERFACES

    virtual Boolean Push(const TItemtype item); // push on the 'stack'

    virtual Boolean Append(const TItemtype item);// will just call push anyway

    virtual TItemtype Pop();                    // pop from the 'stack'

    virtual Boolean Remove(const TItemtype item);// not supported, will return false

};

class TQueue : public TLinkedList

{

public:

    // CONSTRUCTORS AND DESTRUCTORS

    TQueue(short max = kCollectionSize);

    ~TQueue();

    // MAIN INTERFACE

    virtual Boolean Put(const TItemtype item);  // put at the beginning of the queue

    virtual Boolean Append(const TItemtype item);// will just call put anyway

    virtual TItemtype Get();                    // get from the end of the queue

    virtual TItemtype Last();                   // get the one at the end

    virtual Boolean Remove(const TItemtype item);// not supported, will return false

};

class TDeque : public TQueue

{

public:

    // CONSTRUCTORS AND DESTRUCTORS

    TDeque(short max = kCollectionSize);

    virtual~ TDeque();

    // MAIN INTERFACE

    virtual Boolean Push(const TItemtype item); // will call Put anyway

    virtual Boolean PutAtEnd(const TItemtype item);// add entry to the end of the dequeue

    virtual TItemtype Pop();                    // remove from beginning of deque

};

// _________________________________________________________________________________________________________ //

//  THashEntry Class Interface.

// globals, constants, enums and typedefs

const unsigned long kResourceIDMask = 0xFFFFF;

const NBUCKETS = 256;                           // amount of buckets in our hash entry array    

typedef unsigned long THashKey;                 // define our hash key type

typedef void(* MapFun)(void*);                  // our MapCar function definition

// Our Hash Bucket entry data structure

class THashEntry                                // embedded bucket for hash ptrs and values

{

public:

    THashKey fKey;                              // hash key

    TItemtype fValue;                           // value in bucket

    THashEntry* fNext, * fPrevious;             // pointers to other buckets

    THashEntry(THashKey key)                    // constructor for this mini class

    {

        fKey = key;

        fNext = NULL;

        fPrevious = NULL;

    }

    ~THashEntry()

    {

        if (fNext)

            fNext->fPrevious = fPrevious;

        if (fPrevious)

            fPrevious->fNext = fNext;

    }

};

typedef THashEntry* THashEntryPtr;              // we are using a ptr quite a lot in the THashTable implementation

// The THashTable class definition

class THashTable

{

public:

    // CONSTRUCTORS AND DESTRUCTORS

    THashTable();

    virtual~ THashTable();

    // MAIN INTERFACE

    virtual Boolean Add(THashKey key,

                        TItemtype value);       // add to hash table

    virtual Boolean Remove(THashKey key);       // remove from hash table

    virtual TItemtype Find(THashKey key);       // find entry in hash table

    virtual void MapCar(MapFun function);       // iterate with a function over hash table entries

    // PRIVATE INTERNAL FUNCTIONS

protected:

    THashEntryPtr AddElement(THashKey key);     // add an element to the hash table

    virtual THashKey Hash(THashKey key);        // create the hash value

    virtual THashEntryPtr FindInBucket(THashEntryPtr p,

                                       // find inside the bucket the element

                                       THashKey key);

    // FIELDS

protected:

    THashEntryPtr fBucket[NBUCKETS];            // our internal class bucket with entries

};

#endif

// _________________________________________________________________________________________________________ //

/*  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

*/