Logo Search packages:      
Sourcecode: u++ version File versions

uQueue.h

//                              -*- Mode: C++ -*- 
// 
// Copyright (C) Glen Ditchfield 1994
// 
// uQueue.h -- 
// 
// Author           : Glen Ditchfield
// Created On       : Sun Feb 13 17:35:59 1994
// Last Modified By : Peter A. Buhr
// Last Modified On : Mon Jul 19 23:08:41 2004
// Update Count     : 67
//
// This  library is free  software; you  can redistribute  it and/or  modify it
// under the terms of the GNU Lesser General Public License as published by the
// Free Software  Foundation; either  version 2.1 of  the License, or  (at your
// option) any later version.
// 
// This library is distributed in the  hope that it will be useful, but WITHOUT
// ANY  WARRANTY;  without even  the  implied  warranty  of MERCHANTABILITY  or
// FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public License
// for more details.
// 
// You should  have received a  copy of the  GNU Lesser General  Public License
// along  with this library.
// 


#ifndef __U_QUEUE_H__
#define __U_QUEUE_H__


#include "uCollection.h"

// A uQueue<T> is a uCollection<T> that defines an ordering among the elements:
// they are returned by uDrop() in the same order that they are added by uAdd().

// The implementation is a typical singly-linked list, except that uQueue
// maintains uColable's invariant by having the next field of the last element
// of the list point to itself instead of being null.

template<class T> class uQueue : public uCollection<T> {
  protected:
    using uCollection<T>::root;

    T *last;                                    // last element, or 0 if queue is empty.

    uQueue(const uQueue &);                     // no copy
    uQueue &operator=(const uQueue &);                // no assignment
  public:
    using uCollection<T>::uHead;
    using uCollection<T>::uNext;

    inline uQueue() {                           // post: isEmpty().
      last = 0;
    }
    inline T *uTail() const {
      return last;
    }
    void uAddHead(T *n) {
#ifdef __U_DEBUG__
      if ( n->uListed() ) uAbort( "(uQueue &)0x%p.uAddHead( 0x%p ) node is already on another list.", this, n );
#endif // __U_DEBUG__
      if (last) {
          uNext(n) = root;
          root = n;
      } else {
          last = root = n;
          uNext(n) = n;                   // last node points to itself
      }
    }
    void uAddTail(T *n) {
#ifdef __U_DEBUG__
      if ( n->uListed() ) uAbort( "(uQueue &)0x%p.uAddTail( 0x%p ) node is already on another list.", this, n );
#endif // __U_DEBUG__
      if (last) uNext(last) = n;
      else root = n;
      last = n;
      uNext(n) = n;                             // last node points to itself
    }
    inline void uAdd(T *n) {
      uAddTail( n );
    }
    T *uDropHead() {
      T *t = uHead();
      if (root) {
          root = (T *)uNext(root);
          if (root == t) {
            root = last = 0;              // only one element
          }
          uNext(t) = 0;
      }
      return t;
    }
    inline T *uDrop() {
      return uDropHead();
    }
    inline T *uDropTail() {                     // O(n)
      T *n = uTail();
      return n ? uRemove( n ), n : 0;
    }
    void uRemove(T *n) {                        // O(n)
#ifdef __U_DEBUG__
      if ( ! n->uListed() ) uAbort( "(uQueue &)0x%p.uRemove( 0x%p ) node is not on a list.", this, n );
#endif // __U_DEBUG__
      T *prev = 0;
      T *curr = root;
      for ( ;; ) {
          if (n == curr) {                      // found => remove
            if (root == n) {
                uDropHead();
            } else if (last == n) {
                last = prev;
                uNext(last) = last;
            } else {
                uNext(prev) = uNext(curr);
            }
            uNext(n) = 0;
            break;
          }
#ifdef __U_DEBUG__
          // not found => error
          if (curr == last) uAbort( "(uQueue &)0x%p.uRemove( 0x%p ) node is not in list.", this, n );
#endif // __U_DEBUG__
          prev = curr;
          curr = (T *)uNext(curr);
      }
    }                                     // post: !n->uListed().
    static void transfer(uQueue<T> &to, uQueue<T> &from) {
      if (!from.last) return;                   // "from" list empty ?
      if (to.last) {                            // "to" list not empty ?
          to.uNext(to.last) = from.root;
      } else {                            // "to" list empty
          to.root = from.root;
      }
      to.last = from.last;
      from.root = from.last = 0;
    }
};


// A uQueueGen<T> is a subclass of uColGen<T> that generates the elements of a
// uQueue<T>.  It returns the elements in the order that they would be returned
// by uDrop().

template<class T> class uQueueGen : public uColGen<T> {
  protected:
    using uColGen<T>::curr;
  public:
    uQueueGen():uColGen<T>() {}                       // post: elts = null.
    // Create an generator active in queue q.
    inline uQueueGen(const uQueue<T> &q) {            // post: elts = {e in q}.
      curr = q.uHead();
    }
    // Make the generator active in queue q.
    inline void uOver(const uQueue<T> &q) {           // post: elts = {e in q}.
      curr = q.uHead();
    }
    bool operator>>(T *&tp) {
      if (curr) {
          tp = curr;
          T *n = (T *)uNext(curr);
          curr = (n == curr) ? 0 : n;
      } else tp = 0;
      return tp != 0;
    }
};


#endif // __U_QUEUE_H__


// Local Variables: //
// compile-command: "gmake install" //
// End: //

Generated by  Doxygen 1.6.0   Back to index