home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / cpp_libs / cool / ge_cool.lha / GE_COOL2.1 / src / Queue / Queue.C < prev    next >
Encoding:
C/C++ Source or Header  |  1992-06-29  |  12.8 KB  |  421 lines
  1. //
  2. // Copyright (C) 1991 Texas Instruments Incorporated.
  3. //
  4. // Permission is granted to any individual or institution to use, copy, modify,
  5. // and distribute this software, provided that this complete copyright and
  6. // permission notice is maintained, intact, in all copies and supporting
  7. // documentation.
  8. //
  9. // Texas Instruments Incorporated provides this software "as is" without
  10. // express or implied warranty.
  11. //
  12.  
  13. #include <cool/Queue.h>
  14.  
  15. // CoolQueue<Type> () -- Empty constructor for the CoolQueue class
  16. // Input:            None
  17. // Output:           None
  18.  
  19. template<class Type> 
  20. CoolQueue<Type>::CoolQueue<Type> () {
  21.   this->data = NULL;                // Intialize data
  22.   if (this->compare_s == NULL)            // If no compare function
  23.     this->compare_s = &Type##_CoolQueue_is_data_equal;    // Default
  24. }
  25.  
  26.  
  27. // CoolQueue<Type> (long) -- constructor that specifies number of elements
  28. // Input:                Integer number of elements
  29. // Output:               None
  30.  
  31. template<class Type> 
  32. CoolQueue<Type>::CoolQueue<Type> (unsigned long n)
  33.  : CoolQueue(n)
  34. {
  35.   this->data = (Type*) new Type[n];        // Allocate memory
  36.   if (this->compare_s == NULL)            // If no compare function
  37.     this->compare_s = &Type##_CoolQueue_is_data_equal;    // Default
  38. }
  39.  
  40.  
  41. // CoolQueue<Type> (void*, long) -- constructor that specifies user-defined storage
  42. //                              and number of elements
  43. // Input:                       Integer number of elements
  44. // Output:                      None
  45.  
  46. template<class Type> 
  47. CoolQueue<Type>::CoolQueue<Type> (void* s, unsigned long n)
  48.  : CoolQueue(n)
  49. {
  50.   this->data = (Type*) s;            // Pointer to storage
  51.   this->alloc_size = INVALID;            // Indicate this is static size
  52.   if (this->compare_s == NULL)            // If no compare function
  53.     this->compare_s = &Type##_CoolQueue_is_data_equal;    // Default
  54. }
  55.  
  56.  
  57. // CoolQueue<Type> (CoolQueue<Type>&) -- Copy constructor
  58. // Input:                        CoolQueue reference
  59. // Output:                       None
  60.  
  61. template<class Type> 
  62. CoolQueue<Type>::CoolQueue<Type> (const CoolQueue<Type>& s)
  63.  : CoolQueue(s)
  64. {
  65.   this->data = (Type*) new Type[s.limit];    // New memory allocation
  66.   for (long i = 0; i < s.limit; i++)        // For each element
  67.     this->data[i] = s.data[i];            // Copy data into this
  68. }
  69.  
  70.  
  71. // ~CoolQueue<Type> -- Destructor for CoolQueue class that frees up storage
  72. // Input:          None
  73. // Output:         None
  74.  
  75. template<class Type> 
  76. CoolQueue<Type>::~CoolQueue<Type> () {
  77.   if (this->limit != 0 &&
  78.       this->alloc_size != INVALID)        // If not static-size object
  79.     delete [] this->data;            // Free up the memory
  80. }
  81.  
  82.  
  83.  
  84. // Type& get () -- Get and remove first-in item in this CoolQueue
  85. // Input:          None
  86. // Output:         Reference to first-in Type value
  87.  
  88. template<class Type> 
  89. Type& CoolQueue<Type>::get () {
  90. #if ERROR_CHECKING
  91.   if (in == out) {                // If no elements in CoolQueue
  92.     printf ("CoolQueue<%s>::get(): No elements in queue.\n", #Type);
  93.     abort ();
  94.   }
  95. #endif
  96.   long result = out;                // Get data
  97.   if (++out >= limit) out = 0;            // increment and wrap
  98.   return data[result];
  99. }
  100.  
  101. // Boolean get (Type& result) -- Get and remove first-in item in this CoolQueue
  102. // Input:          None
  103. // Output:         Reference to first-in Type value
  104.  
  105. template<class Type>
  106. Boolean CoolQueue<Type>::get (Type& result) {
  107.   if (in == out) return FALSE;
  108.   result = this->data[out];        // Get data
  109.   if (++out >= limit) out = 0;        // Increment and wrap
  110.   return TRUE;
  111. }
  112.  
  113. // Boolean unget (Type&) -- Return TRUE if able to put a Type value on the
  114. //                          front-end of this CoolQueue
  115. // Input:                   Reference to a Type value
  116. // Output:                  TRUE or FALSE
  117.  
  118. template<class Type> 
  119. Boolean CoolQueue<Type>::unget (const Type& value) {
  120.   long save = out;
  121.   if (--out < 0) out = limit - 1;    // decrement and wrap
  122.   if (in == out) {            // Check for full
  123.     out = save;
  124.     if (!this->grow()) return FALSE;
  125.     if (--out < 0) out = limit - 1;    // decrement and wrap
  126.   }
  127.   data[out] = value;            // Stuff data
  128.   return TRUE;
  129. }
  130.  
  131. // Boolean put (Type&) -- Put a new last-in item on this CoolQueue; return TRUE
  132. ///                       if successful
  133. // Input:                 Reference to a Type value
  134. // Output:                TRUE or FALSE
  135.  
  136. template<class Type> 
  137. Boolean CoolQueue<Type>::put (const Type& value) {
  138.   long save = in;
  139.   if (++in >= limit) in = 0;        // Increment and Wrap
  140.   if (in == out) {            // Check for full
  141.     in = save;
  142.     if (!this->grow()) return FALSE;
  143.     save = in;
  144.     if (++in >= limit) in = 0;        // Increment and Wrap
  145.   }
  146.   data[save] = value;            // Store
  147.   curpos = in;                // Invalidate curpos
  148.   return TRUE;
  149. }
  150.  
  151. // Type& unput () -- Remove and return last-in item of this CoolQueue
  152. // Input:            None
  153. // Output:           Reference to the Type value of the last-in item
  154.  
  155. template<class Type> 
  156. Type& CoolQueue<Type>::unput () {
  157. #if ERROR_CHECKING
  158.   if (in == out) {                // If no elements in queue
  159.     printf ("CoolQueue<%s>::unput(): No elements in queue.\n", #Type);
  160.     abort ();
  161.   }
  162. #endif
  163.   if (--in < 0) in = limit - 1;            // decrement and wrap
  164.   curpos = in;                    // Invalidate curpos
  165.   return data[in];
  166. }
  167.  
  168. template<class Type>
  169. Boolean CoolQueue<Type>::unput (Type& result) {
  170.   if (in == out) return FALSE;            // If no elements in queue
  171.   if (--in < 0) in = limit - 1;            // decrement and wrap
  172.   curpos = in;                    // Invalidate curpos
  173.   result = this->data[in];                // Get data
  174.   return TRUE;
  175. }
  176.  
  177. // Boolean find (Type&) -- Return TRUE if value is found in this CoolQueue
  178. // Input:                  Reference to a Type value
  179. // Output:                 TRUE or FALSE
  180.  
  181. template<class Type> 
  182. Boolean CoolQueue<Type>::find (const Type& value) {
  183.   long i;
  184.   if (in == out)                // Nothing is in CoolQueue
  185.     return FALSE;                // Return failure
  186.   if (in > out) {
  187.     for (i = out; i < in; i++)            // check from out to in-1
  188.       if ((*(this->compare_s))(this->data[i], value)) { // If found
  189.         this->curpos = i;            // Set curpos to index 
  190.         return TRUE;                // Return success
  191.       }
  192.   }
  193.   else {
  194.     for (i = out; i < limit; i++)        // check from out to limit-1
  195.       if ((*(this->compare_s))(this->data[i], value)) { // If found
  196.         this->curpos = i;            // Set curpos to index 
  197.         return TRUE;                // Return success
  198.       }
  199.     for (i = 0; i < in; i++)            // check from first to in-1
  200.       if ((*(this->compare_s))(this->data[i], value)) { // If found
  201.         this->curpos = i;            // Set curpos to index 
  202.         return TRUE;                // Return success
  203.       }
  204.   }
  205.   return FALSE;                    // Return failure
  206. }
  207.  
  208. template<class Type> 
  209. Boolean CoolQueue<Type>::grow () {
  210.   long new_size;
  211.   if (this->alloc_size == INVALID) return FALSE;
  212.   if (growth_ratio_s > 0.0)
  213.      new_size = (long)(limit * (1.0 + growth_ratio_s)); // New size?
  214.   else
  215.     new_size = limit + alloc_size;
  216.   resize(new_size);
  217.   return TRUE;
  218. }
  219.   
  220.  
  221. // void resize (long)-- Adjust the memory size of a CoolQueue to accomodate some
  222. //                      new size
  223. // Input:               Number of elements to hold
  224. // Output:              None
  225.  
  226. template<class Type> 
  227. void CoolQueue<Type>::resize (long s) {
  228. #if ERROR_CHECKING
  229.   if (this->alloc_size == INVALID) {        // If not allowed to grow
  230.     this->resize_error (#Type);            // Raise exception
  231. #endif
  232.     return;                    // Return
  233.   }
  234.   Type* temp;                    // Temporary variable
  235.   Type* tp;
  236.   long len = this->length();
  237.   long i;
  238.   tp = temp = (Type*) new Type[s];        // Allocate storage
  239.   if (in > out) {
  240.     for (i = out; i < in; i++)            // copy from out to in-1
  241.       *tp++ = data[i];                // Copy value
  242.   }
  243.   if (in < out) {
  244.     for (i = out; i < limit; i++)        // copy from out to limit-1
  245.       *tp++ = data[i];                // Copy value
  246.     for (i = 0; i < in; i++)            // copy from first to in-1
  247.       *tp++ = data[i];                // Copy value
  248.   }
  249.   if (this->limit != 0)
  250.     delete [] this->data;            // Free up old memory
  251.   this->data = temp;                // Assign new memory block
  252.   this->limit = s;                // Save new size value
  253.   curpos = len;
  254.   in = len;
  255.   out = 0;
  256. }
  257.  
  258.  
  259. // Boolean remove () -- Destructively remove item at current position; return
  260. //                      TRUE if successful
  261. // Input:               None
  262. // Output:              TRUE or FALSE
  263. template<class Type> 
  264. Boolean CoolQueue<Type>::remove () {
  265.   long i;
  266.   if (in == out) return FALSE;            // Fail if nothing in queue
  267.   if (in > out) {                // Data is between out and in-1
  268.     if (curpos < out || curpos >= in)        // Fail if invalid curpos
  269.       return FALSE;
  270.     in--;
  271.     for (i = curpos; i < in; i++)
  272.       data[i] = data[i+1];
  273.   }                           
  274.   else {
  275.     if (curpos >= out) {               // Data is between out and limit
  276.       if (curpos >= limit)               // fail if invalid curpos
  277.     return FALSE;
  278.       out--;
  279.       for (i = curpos; i >= out; i--)
  280.     data[i] = data[i - 1];
  281.     }
  282.     else {                        // data is between 0 and in-1
  283.       if (curpos >= in)                   // fail if invalid curpos
  284.     return FALSE;
  285.       in--;
  286.       for (i = curpos; i < in; i++)
  287.     data[i] = data[i+1];
  288.     }
  289.   }
  290.   return TRUE;                    // Report success
  291. }
  292.  
  293.  
  294. // Boolean remove (Type&) -- Destructively remove the first occurence of an 
  295. //                           element, starting from front of this CoolQueue; return
  296. //                           TRUE if element is found and removed
  297. // Input:                    Reference to Type value
  298. // Output:                   TRUE or FALSE
  299.  
  300. template<class Type> 
  301. Boolean CoolQueue<Type>::remove (const Type& value) {
  302.  return find(value) && remove();    // find it, Remove it & return status
  303. }
  304.  
  305.  
  306. // CoolQueue<Type>& operator= (CoolQueue<Type>&) -- Assignment
  307. // Input:  Reference to a CoolQueue
  308. // Output: Reference to modified this
  309.  
  310. template<class Type> 
  311. CoolQueue<Type>& CoolQueue<Type>::operator= (const CoolQueue<Type>& s) {
  312.   if (this != &s) {
  313.     long len = s.length();
  314.     long i;
  315.     if (this->limit < len) {            // if not enough memory
  316. #if ERROR_CHECKING
  317.       if (this->alloc_size == INVALID)        // If static size queue
  318.     this->assign_error (#Type);        // Raise exception
  319. #endif
  320.       if (this->limit != 0)
  321.     delete [] this->data;                    // Free it up
  322.       this->limit = s.limit;            // New CoolQueue size
  323.       this->data = (Type*) new Type[s.limit];    // Allocate bigger memory
  324.     }
  325.     out = 0;
  326.     in = len;
  327.     curpos = len;
  328.     register Type* dp = this->data;
  329.     if (s.in >= s.out)
  330.       for (i = s.out; i < s.in; i++)        // copy from s.out to s.in-1
  331.     *dp++ = s.data[i];            // Copy value
  332.     else {
  333.       for (i = s.out; i < s.limit; i++)        // copy from s.out to s.limit-1
  334.     *dp++ = s.data[i];            // Copy value
  335.       for (i = 0; i < s.in; i++)        // copy from first to s.in-1
  336.     *dp++ = s.data[i];            // Copy value
  337.     }}
  338.   return *this;                    // Return reference
  339. }
  340.  
  341.  
  342. // Boolean operator== (CoolQueue<Type>&) -- Compare this CoolQueue with another
  343. //                                      CoolQueue;
  344. // Input:  Reference to a CoolQueue
  345. // Output: TRUE or FALSE if equal/non equal.
  346.  
  347. template<class Type> 
  348. Boolean CoolQueue<Type>::operator== (const CoolQueue<Type>& q) const {
  349.   if (this->length() != q.length())        // If not same number
  350.     return FALSE;                // Then not equal
  351.   long tp = this->out;
  352.   long qp = q.out;
  353.       while (tp != this->in) {
  354.     if (!(*this->compare_s)(this->data[tp], q.data[qp]))
  355.       return FALSE;                // Return failure if no match
  356.     if (++tp >= this->limit) tp = 0;        // increment and wrap
  357.     if (++qp >= q.limit) tp = 0;        // increment and wrap
  358.   }
  359.   return TRUE;
  360. }
  361.  
  362.  
  363. // Boolean is_data_equal -- Default data comparison function if user has not
  364. //                          provided another one.
  365. // Input:                   Two Type references
  366. // Output:                  TRUE or FALSE
  367.  
  368. template<class Type> CoolQueue {
  369.   Boolean Type##_CoolQueue_is_data_equal (const Type& t1, const Type& t2) {
  370.     return (t1 == t2);
  371.   }
  372. }
  373.  
  374.  
  375. // void set_compare(Type##_CoolQueue_Compare) -- Set this CoolQueue's compare function
  376. // Input:  Pointer to a compare function
  377. // Output: None
  378.  
  379. template<class Type> 
  380. void CoolQueue<Type>::set_compare (Type##_CoolQueue_Compare cf) {
  381.   if (cf == NULL)
  382.     this->compare_s = &Type##_CoolQueue_is_data_equal; // Default equality function
  383.   else
  384.     this->compare_s = cf;            // Else set to user function
  385. }
  386.  
  387.  
  388. // operator<< -- Overload the output operator for CoolQueue
  389. // Input:        ostream reference, queue reference
  390. // Output:       CoolQueue data is output to ostream
  391.  
  392. template<class Type> CoolQueue {
  393. ostream& operator<< (ostream& os, const CoolQueue<Type>& q) {
  394.   return q.qprint(os);
  395. }
  396. }
  397.  
  398.  
  399. // This is a method because Glockenspiel's Cfront 1.2 doesn't let 
  400. // friend functions access the protected data members of our base class
  401. template<class Type>
  402. ostream& CoolQueue<Type>::qprint(ostream& os) const {
  403.   if (in == out)                // If no elements
  404.     os << " Empty ";                // Report empty status
  405.   else {
  406.     long i;
  407.     os << "[ ";
  408.     if (in >= out)
  409.       for (i = out; i < in; i++)        // copy from out to in-1
  410.     os << data[i] << " ";
  411.     else {
  412.       for (i = out; i < limit; i++)        // copy from out to limit-1
  413.     os << data[i] << " ";
  414.       for (i = 0; i < in; i++)            // copy from first to in-1
  415.     os << data[i] << " ";
  416.     }
  417.     os << "]";
  418.   }
  419.   return os;                    // Return stream reference
  420. }
  421.