home *** CD-ROM | disk | FTP | other *** search
/ Tricks of the Windows Gam…ming Gurus (2nd Edition) / Disc2.iso / msdn_vcb / samples / vc98 / sdk / netds / winsock / dt_dll / nideque.h < prev    next >
C/C++ Source or Header  |  1997-10-08  |  15KB  |  787 lines
  1. /*++
  2.  
  3.   Copyright 1996-1997 Microsoft Corporation.
  4.  
  5.   Copyright (c) 1995 Intel Corp
  6.   
  7.   File Name:
  8.   
  9.     nideque.h
  10.   
  11.   Abstract:
  12.   
  13.     Implements Deque structures.  These are double linked lists  that
  14.     can place and remove data from the beginning and end. This file
  15.     also contains an iterator for Deques.  Important to notice is that
  16.     these are non-intrusive deques.  Meaning the use of these classes
  17.     does not need to insert pointers into there classes to use these.
  18.   
  19. --*/
  20.  
  21. #ifndef _NIDEQUE_H_
  22. #define _NIDEQUE_H_
  23.  
  24. #include "nowarn.h"  /* turn off benign warnings */
  25. #ifndef _WINSOCKAPI_
  26. #define _WINSOCKAPI_   /* Prevent inclusion of winsock.h in windows.h */
  27. #endif
  28. #include <windows.h>
  29. #include "nowarn.h"  /* some warnings may have been turned back on */
  30. #include "huerror.h"
  31.  
  32. template<class T> class NIDeque_c;
  33. template<class T> class NIDequeIter_c;
  34.  
  35. // Class Name:     NILNode_c
  36. // Purpose:  Simply holds data and pointer to form a double linked
  37. // list. 
  38. // Context:  Can be used anywhere.
  39. template<class T> class NILNode_c {
  40.     friend class NIDeque_c<T>;
  41.     friend class NIDequeIter_c<T>;
  42.  
  43.     private:
  44.         T           Data;
  45.         NILNode_c   *Next,
  46.                     *Back;
  47.  
  48.     public:
  49.         NILNode_c();
  50. };
  51.  
  52. template<class T> NILNode_c<T>::NILNode_c()
  53. {
  54.     // Make sure the members are correctly initialized.
  55.     Next = NULL;
  56.     Back = NULL;
  57. } // NILNode_c::NILNode_c
  58.  
  59.  
  60.  
  61. // Class Name:     NIDeque_c   
  62. // Purpose:  Non-intrusize deque                                       
  63. // Context:  Can be used anywhere.
  64. template<class T> class NIDeque_c {
  65.     friend class NIDequeIter_c<T>;
  66.  
  67.     private:
  68.       NILNode_c<T>  *Root,
  69.                     *Tail;   
  70.     public: 
  71.                 NIDeque_c();
  72.             ~NIDeque_c();
  73.         BOOL    RemoveFromFront(T &data);    
  74.         BOOL    RemoveFromBack(T &data);
  75.         BOOL    InsertIntoFront(T data);
  76.         BOOL    InsertIntoBack(T data);
  77.         BOOL    GetFromFront(T &data);
  78.     BOOL    GetFromBack(T &data);
  79.     BOOL    IsEmpty();
  80. };
  81.  
  82.  
  83.  
  84.  
  85. /*++
  86.   
  87.   NIDeque_c::NIDeque_c()
  88.   
  89.   Function Description:
  90.   
  91.       Constructor
  92.   
  93.   Arguments:
  94.   
  95.       None.
  96.   
  97.   Return Value:
  98.   
  99.       None.
  100.   
  101. --*/                                            
  102. template<class T> NIDeque_c<T>::NIDeque_c()
  103. {
  104.     Root = NULL;
  105.     Tail = NULL;
  106. } // End of NINIDeque_c::NIDeque_c 
  107.  
  108.  
  109.  
  110.  
  111.  
  112. /*++
  113.   
  114.   NIDeque_c::~NIDeque_c()
  115.   
  116.   Function Description:
  117.   
  118.       Destructor
  119.   
  120.   Arguments:
  121.   
  122.       None.
  123.   
  124.   Return Value:
  125.   
  126.       None.
  127.   
  128. --*/
  129. template<class T> NIDeque_c<T>::~NIDeque_c()
  130. {                                            
  131.     NILNode_c<T>    *bptr    = NULL,
  132.                     *cptr    = NULL;
  133.  
  134.     for(bptr=NULL,cptr=Root;cptr;bptr=cptr,cptr=cptr->Next){  
  135.         delete bptr;
  136.     }                                           
  137.     delete bptr;
  138. }                
  139.  
  140.  
  141.  
  142.  
  143. /*++
  144.   
  145.   NIDeque_c::InsertIntoFront()
  146.   
  147.   Function Description:
  148.   
  149.       Inserts a piece of data onto the linked list.
  150.   
  151.   Arguments:
  152.   
  153.       Data -- Data to put on the linked list.
  154.   
  155.   Return Value:
  156.   
  157.       None.
  158.   
  159. --*/
  160. template<class T> BOOL NIDeque_c<T>::InsertIntoFront(T Data)
  161. {       
  162.     NILNode_c<T>    *nptr    = NULL;
  163.  
  164.     /*  If the list contains something then move the root pointer down.
  165.     //  Otherwise, put this new object on the root.
  166.     */
  167.     if(!(nptr = new NILNode_c<T>)){
  168.          HUSetLastError(ALLOCERROR);
  169.          return FALSE;
  170.     }                 
  171.  
  172.     nptr->Data = Data;
  173.  
  174.     if(Root){
  175.         nptr->Next = Root;
  176.         Root->Back = nptr;
  177.         Root = nptr;
  178.     }else{    
  179.         Root = nptr;
  180.         Tail = nptr;
  181.     }
  182.     return TRUE;
  183. } // End of NIDeque_c::InsFront
  184.  
  185.  
  186.  
  187.  
  188. /*++
  189.   
  190.   NIDeque_c::RemoveFromFront()
  191.   
  192.   Function Description:
  193.   
  194.       Removes a piece of data from the front of the linked list.
  195.   
  196.   Arguments:
  197.   
  198.       Data -- Data to be taken off of the linked list.
  199.   
  200.   Return Value:
  201.   
  202.       None.
  203.   
  204. --*/
  205. template<class T> BOOL NIDeque_c<T>::RemoveFromFront(T &Data)
  206. {           
  207.     NILNode_c<T>    *nptr    = NULL;   
  208.     
  209.     if(Root){                 
  210.         nptr = Root;
  211.         Root = Root->Next;
  212.         if(Root){
  213.             Root->Back = NULL; 
  214.         }else{
  215.             Tail = NULL;
  216.         }
  217.         nptr->Next = NULL;
  218.         nptr->Back = NULL; 
  219.         Data = nptr->Data;
  220.         delete nptr;
  221.         return TRUE;
  222.     }else{
  223.         Data = NULL;
  224.         return FALSE;
  225.     }
  226. } // End of NIDeque_c::RemFront
  227.  
  228.  
  229.  
  230.                                           
  231. /*++
  232.   
  233.   NIDeque_c::InsertIntoBack()
  234.   
  235.   Function Description:
  236.   
  237.       Inserts a piece of data onto the back of the linked list.
  238.   
  239.   Arguments:
  240.   
  241.       Data -- Data to be taken off of the linked list.
  242.   
  243.   Return Value:
  244.   
  245.       None.
  246.   
  247. --*/
  248. template<class T> BOOL NIDeque_c<T>::InsertIntoBack(T Data)
  249. {       
  250.     NILNode_c<T>    *nptr    = NULL;
  251.     if(!(nptr = new NILNode_c<T>)){
  252.         HUSetLastError(ALLOCERROR);
  253.         return FALSE;
  254.     }    
  255.  
  256.     nptr->Data = Data;
  257.  
  258.     if(Root){
  259.         nptr->Back = Tail;
  260.         Tail->Next = nptr;
  261.         Tail = nptr;
  262.     }else{    
  263.         Root = nptr;
  264.         Tail = nptr;
  265.     }
  266.     return TRUE;
  267. } // End of NIDeque_c::InsBack
  268.  
  269.  
  270.  
  271.  
  272. /*++
  273.   
  274.   NIDeque_c::RemoveFromBack()
  275.   
  276.   Function Description:
  277.   
  278.       Removes a piece of data from the back of the linked list.
  279.   
  280.   Arguments:
  281.   
  282.       Data -- Data to be taken off of the linked list.
  283.   
  284.   Return Value:
  285.   
  286.       None.
  287.   
  288. --*/
  289. template<class T> BOOL NIDeque_c<T>::RemoveFromBack(T &Data)
  290. {
  291.     NILNode_c<T>    *nptr    = NULL;
  292.  
  293.     if(Tail){
  294.         nptr = Tail;
  295.         Tail = Tail->Back;
  296.         if(Tail){
  297.             Tail->Next = NULL;
  298.         }else{
  299.         Root = NULL;
  300.     }
  301.         nptr->Next = NULL;
  302.         nptr->Back = NULL;
  303.         Data = nptr->Data;
  304.         delete nptr;
  305.         return TRUE;
  306.     }else{
  307.         Data = NULL;
  308.         return FALSE;
  309.     }
  310. }
  311.  
  312.  
  313.  
  314.  
  315. /*++
  316.   
  317.   NIDeque_c::GetFromFront()
  318.   
  319.   Function Description:
  320.   
  321.       Gets a piece of data from the front of the linked list.
  322.   
  323.   Arguments:
  324.   
  325.       Data -- Data to be taken off of the linked list.
  326.   
  327.   Return Value:
  328.   
  329.       None.
  330.   
  331. --*/
  332. template<class T> BOOL NIDeque_c<T>::GetFromFront(T &Data)
  333. {           
  334.     NILNode_c<T>    *nptr    = NULL;   
  335.     
  336.     if(Root){                 
  337.         Data = Root->Data;
  338.         return TRUE;
  339.     }else{
  340.         Data = NULL;
  341.         return FALSE;
  342.     }
  343. } // End of NIDeque_c::GetFromFront
  344.  
  345.  
  346.  
  347.  
  348. /*++
  349.   
  350.   NIDeque_c::GetFromBack()
  351.   
  352.   Function Description:
  353.   
  354.       Gets a piece of data from the back of the linked list.
  355.   
  356.   Arguments:
  357.   
  358.       Data -- Data to be taken off of the linked list.
  359.   
  360.   Return Value:
  361.   
  362.       None.
  363.   
  364. --*/
  365. template<class T> BOOL NIDeque_c<T>::GetFromBack(T &Data)
  366. {           
  367.     NILNode_c<T>    *nptr    = NULL;   
  368.     
  369.     if(Tail){                 
  370.         Data = Tail->Data;
  371.         return TRUE;
  372.     }else{
  373.         Data = NULL;
  374.         return FALSE;
  375.     }
  376. } // End of NIDeque_c::RemFront
  377.  
  378.  
  379.  
  380.  
  381. /*++
  382.   
  383.   NIDeque_c::IsEmpty()
  384.   
  385.   Function Description:
  386.   
  387.       Determines whether a deques is empty
  388.   
  389.   Arguments:
  390.   
  391.       None.
  392.   
  393.   Return Value:
  394.   
  395.       None.
  396.   
  397. --*/
  398. template<class T> BOOL NIDeque_c<T>::IsEmpty()
  399. {           
  400.     NILNode_c<T>    *nptr    = NULL;   
  401.     
  402.     if(Root){               
  403.         return FALSE;
  404.     }else{
  405.         return TRUE;
  406.     }
  407. } // End of NIDeque_c::IsEmpty
  408.  
  409.  
  410. // Name:     NIDequeIter_c
  411. // Purpose:  An iterator for the Deque_c class.                        
  412. // Context:  Of course only with Deque_c
  413. template<class T> class NIDequeIter_c {
  414.     private:
  415.         NIDeque_c<T>  *NIDeque;
  416.         NILNode_c<T>  *Current;
  417.  
  418.     private:
  419.         void    RemoveData(NILNode_c<T> *cptr,T &data);
  420.  
  421.     protected: // Derived class interface
  422.     inline NILNode_c<T> *GetCurrent();
  423.     inline NIDeque_c<T> *GetNIDeque();
  424.  
  425.     public: 
  426.                 NIDequeIter_c();
  427.                 NIDequeIter_c(NIDeque_c<T> &ANIDeque);
  428.                 ~NIDequeIter_c();
  429.         BOOL    Initialize(NIDeque_c<T> &ANIDeque);
  430.         BOOL    First(T &data);
  431.         BOOL    Next(T &data);
  432.         BOOL    Last(T &data);
  433.         BOOL    Back(T &data);
  434.         BOOL    Remove(T &data);
  435.         BOOL    Replace(T &src,T chg);
  436. };
  437.  
  438. //
  439. // Private members                                             
  440. //
  441.  
  442.  
  443. /*++
  444.   
  445.   NIDequeIter_c::RemoveData()
  446.   
  447.   Function Description:
  448.   
  449.       To remove all of the data from the linked list.
  450.   
  451.   Arguments:
  452.   
  453.       cptr -- Current pointer in the linked list.
  454.       
  455.       ret_data -- Return the data before deleting.
  456.   
  457.   Return Value:
  458.   
  459.       None.
  460.   
  461. --*/
  462. template<class T> void NIDequeIter_c<T>::RemoveData(NILNode_c<T> *cptr,
  463.                                                     T &ret_data)
  464. {
  465.     NILNode_c<T>  *bptr    = NULL,
  466.                   *nptr    = NULL,
  467.                   *fptr    = NULL;
  468.  
  469.     if(Current == cptr){
  470.         Current = cptr->Next;
  471.     }
  472.     fptr = cptr;
  473.     bptr = cptr->Back;
  474.     nptr = cptr->Next;
  475.     if(bptr != NULL){
  476.         bptr->Next = nptr;
  477.     }                      
  478.     if(nptr != NULL){
  479.         nptr->Back = bptr;
  480.     }
  481.     if(fptr == NIDeque->Root){
  482.         NIDeque->Root = nptr;
  483.     }          
  484.     if(fptr == NIDeque->Tail){
  485.         NIDeque->Tail = bptr;
  486.     }                                             
  487.     if(ret_data){
  488.         ret_data = fptr->Data;
  489.     }
  490.     delete fptr;
  491. } // End of NINIDeque_c::RemoveData
  492.  
  493.  
  494. //
  495. // Public members                                             
  496. //
  497.  
  498.  
  499. /*++
  500.   
  501.   NIDequeIter_c::NIDequeIter_c()
  502.   
  503.   Function Description:
  504.   
  505.       Constructor.
  506.   
  507.   Arguments:
  508.   
  509.       ANIDeque -- The deque to iterate over.
  510.   
  511.   Return Value:
  512.   
  513.       None.
  514.   
  515. --*/
  516. template<class T> NIDequeIter_c<T>::NIDequeIter_c(NIDeque_c<T> &ANIDeque) 
  517. {
  518.     NIDeque = &ANIDeque;
  519.     Current = NULL;
  520. }
  521.  
  522.  
  523.  
  524. template<class T> NIDequeIter_c<T>::NIDequeIter_c() 
  525. {
  526.     NIDeque = NULL;
  527.     Current = NULL;
  528. }
  529.  
  530.  
  531.  
  532.  
  533. /*++
  534.   
  535.   NIDequeIter_c::~NIDequeIter_c()
  536.   
  537.   Function Description:
  538.   
  539.       Destructor.
  540.   
  541.   Arguments:
  542.   
  543.       None.
  544.   
  545.   Return Value:
  546.   
  547.       None.
  548.   
  549. --*/
  550. template<class T> NIDequeIter_c<T>::~NIDequeIter_c()
  551. {
  552. }
  553.  
  554.  
  555.  
  556. /*++
  557.   
  558.   NIDequeIter_c::Initialize()
  559.   
  560.   Function Description:
  561.   
  562.       Initializes the iterator.
  563.   
  564.   Arguments:
  565.   
  566.       ANIDeque -> The deque to iterate over.
  567.   
  568.   Return Value:
  569.   
  570.       None.
  571.   
  572. --*/
  573. template<class T> BOOL NIDequeIter_c<T>::Initialize(NIDeque_c<T> &ANIDeque) 
  574. {
  575.     NIDeque = &ANIDeque;
  576.     Current = NULL;
  577.     return TRUE;
  578. }
  579.  
  580.  
  581.  
  582.  
  583. /*++
  584.   
  585.   NIDequeIter_c::First()
  586.   
  587.   Function Description:
  588.   
  589.       Returns the First data in the linked list.  This primes the
  590.       current pointer so that next time the Next method is used to get
  591.       more linked list data.
  592.   
  593.   Arguments:
  594.   
  595.       data -- The data from the linked list.
  596.   
  597.   Return Value:
  598.   
  599.       TRUE -- If data is valid.
  600.  
  601.       FALSE -- If data is not valid.
  602.   
  603. --*/
  604. template<class T> BOOL NIDequeIter_c<T>::First(T &Data)
  605. {
  606.     Current = NIDeque->Root;
  607.     if(Current != NULL){
  608.         Data = Current->Data;
  609.         return TRUE;
  610.     }else{
  611.         return FALSE;
  612.     }
  613. } // End of NIDeque_c::First
  614.  
  615.  
  616.  
  617.  
  618. /*++
  619.   
  620.   NIDequeIter_c::Next()
  621.   
  622.   Function Description:
  623.   
  624.       Returns the Next data in the linked list.
  625.   
  626.   Arguments:
  627.   
  628.       data -- The data from the linked list.
  629.   
  630.   Return Value:
  631.   
  632.       TRUE -- If data is valid.
  633.  
  634.       FALSE -- If data is not valid.
  635.   
  636. --*/
  637. template<class T> BOOL NIDequeIter_c<T>::Next(T &Data)
  638. {
  639.     if(Current){
  640.         Current = Current->Next;
  641.         if(Current){
  642.             Data = Current->Data;
  643.             return TRUE;
  644.         }
  645.     } 
  646.     Data = NULL;              
  647.     return FALSE;
  648. } // End of NIDeque_c::Next
  649.  
  650.  
  651.  
  652.  
  653. /*++
  654.   
  655.   NIDequeIter_c::Last()
  656.   
  657.   Function Description:
  658.   
  659.       Returns the Last data in the linked list.
  660.   
  661.   Arguments:
  662.   
  663.       data -- The data from the linked list.
  664.   
  665.   Return Value:
  666.   
  667.       TRUE -- If data is valid.
  668.  
  669.       FALSE -- If data is not valid.
  670.   
  671. --*/
  672. template<class T> BOOL NIDequeIter_c<T>::Last(T &Data)
  673. {
  674.     Current = NIDeque->Tail;
  675.     if(Current != NULL){
  676.         Data = Current->Data;
  677.         return TRUE;
  678.     }else{
  679.         return FALSE;
  680.     }
  681. } // End of NIDeque_c::First
  682.  
  683.  
  684.  
  685.  
  686. /*++
  687.   
  688.   NIDequeIter_c::Back()
  689.   
  690.   Function Description:
  691.   
  692.       Returns the previous data in the linked list.
  693.   
  694.   Arguments:
  695.   
  696.       data -- The data from the linked list.
  697.   
  698.   Return Value:
  699.   
  700.       TRUE -- If data is valid.
  701.  
  702.       FALSE -- If data is not valid.
  703.   
  704. --*/
  705. template<class T> BOOL NIDequeIter_c<T>::Back(T &Data)
  706. {
  707.     if(Current && (Current = Current->Back)){
  708.         Data = Current->Data;
  709.         return TRUE;
  710.     }else{ 
  711.         Data = NULL;              
  712.         return FALSE;
  713.     }
  714. } // End of NIDeque_c::Next
  715.  
  716.  
  717.  
  718.  
  719. /*++
  720.   
  721.   NIDequeIter_c::Replace()
  722.   
  723.   Function Description:
  724.   
  725.       Replaces src by chg.
  726.   
  727.   Arguments:
  728.   
  729.       src -- Data to search for.
  730.  
  731.       chg -- The new data.
  732.   
  733.   Return Value:
  734.   
  735.       TRUE -- If data is valid.
  736.  
  737.       FALSE -- If data is not valid.
  738.   
  739. --*/
  740. template<class T> BOOL NIDequeIter_c<T>::Replace(T &src,T chg)
  741. {
  742.     NILNode_c<T> *cptr    = NULL; 
  743.     
  744.     if(Current != NULL){
  745.         src = Current->Data;
  746.         Current->Data = chg;
  747.         return TRUE;
  748.     }                
  749.     return FALSE;
  750. } // End of NIDeque_c::Replace
  751.  
  752.  
  753.  
  754.  
  755. /*++
  756.   
  757.   NIDequeIter_c::Remove()
  758.   
  759.   Function Description:
  760.   
  761.       Removes whatever the current pointer is pointing at.
  762.   
  763.   Arguments:
  764.   
  765.       data -- Data removed.
  766.   
  767.   Return Value:
  768.   
  769.       TRUE -- If data is valid.
  770.  
  771.       FALSE -- If data is not valid.
  772.   
  773. --*/
  774. template<class T> BOOL NIDequeIter_c<T>::Remove(T &data)
  775. {            
  776.     NILNode_c<T>    *cptr   = NULL;
  777.     T               *vdata  = NULL;
  778.                             
  779.     if(Current != NULL){
  780.         RemoveData(Current,data);
  781.         return TRUE;
  782.     }                           
  783.     return FALSE;
  784. } // End of NIDeque_c<T>::Remove
  785.  
  786. #endif
  787.