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

uSequence.h

//                              -*- Mode: C++ -*- 
// 
// Copyright (C) Glen Ditchfield 1994
// 
// uSequence.h -- 
// 
// Author           : Glen Ditchfield
// Created On       : Sun Feb 13 19:56:07 1994
// Last Modified By : Peter A. Buhr
// Last Modified On : Mon Jul 19 23:09:16 2004
// Update Count     : 110
//
// 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_SEQUENCE_H__
#define __U_SEQUENCE_H__


#include "uCollection.h"

// Class that sequence elements derive from.

class uSeqable : public uColable {
    friend class uSFriend;

    uSeqable* back;                             // Pointer to previous node in the list.
  public:
    uSeqable() {
      back = 0;
    }
    uSeqable *getback() {
      return back;
    }
};


// uSFriend and its descendents have access to uSeqable::back.
 
class uSFriend {
  protected:
    uSeqable*& uBack(uSeqable* sp) const {
      return sp->back;
    };
};


// A uSequence<T> is a uCollection<T> where the elements form a sequence.  It is
// possible to move back and forth along the sequence, and to insert and remove
// elements in the sequence.  uHead() returns a pointer to the first element of
// the sequence.  T must be a public descendant of uSeqable.

// Sequences are organized as circular doubly-linked lists.  root points at
// the first element of the sequence.

template<class T> class uSequence: public uCollection<T>, protected uSFriend {
  protected:
    using uCollection<T>::root;

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

    uSequence() : uCollection<T>() {};                // post: uEmpty().
    // Return a pointer to the last sequence element, without removing it.
    T *uTail() const {
      return root ? (T *)uBack(root) : 0;
    }                                     // post: uEmpty() & uTail() == 0 | !uEmpty() & uTail() in *this
    // Return a pointer to the element after *n, or 0 if there isn't one.
    T *uSucc(T *n) const {                      // pre: *n in *this
#ifdef __U_DEBUG__
      if ( ! n->uListed() ) uAbort( "(uSequence &)0x%p.uSucc( 0x%p ) node is not on a list.", this, n );
#endif // __U_DEBUG__
      return (uNext(n) == root) ? 0 : (T *)uNext(n);
    }                                     // post: n == uTail() & uSucc(n) == 0 | n != uTail() & *uSucc(n) in *this
    // Return a pointer to the element before *n, or 0 if there isn't one.
    T *uPred(T *n) const {                      // pre: *n in *this
#ifdef __U_DEBUG__
      if ( ! n->uListed() ) uAbort( "(uSequence &)0x%p.uPred( 0x%p ) node is not on a list.", this, n );
#endif // __U_DEBUG__
      return (n == root) ? 0 : (T *)uBack(n);
    }                                     // post: n == uHead() & uHead(n) == 0 | n != uHead() & *uPred(n) in *this
    // Insert *n into the sequence before *bef, or at the end if bef == 0.
    void uInsertBef(T *n, T *bef) {             // pre: !n->uListed() & *bef in *this
#ifdef __U_DEBUG__
      if ( n->uListed() ) uAbort( "(uSequence &)0x%p.uInsertBef( 0x%p, 0x%p ) node is already on another list.", this, n, bef );
#endif // __U_DEBUG__
      if (bef == root) {
          if (root) {
            uNext(n) = root;
            uBack(n) = uBack(root);
            uNext(uBack(n)) = n;
            uBack(root) = n;
          }
          else {
            uNext(n) = n;
            uBack(n) = n;
          };
          root = n;
      } else {
          if (!bef) bef = root;
          uNext(n) = bef;
          uBack(n) = uBack(bef);
          uNext(uBack(n)) = n;
          uBack(bef) = n;
      }
    }                                     // post: n->uListed() & *n in *this & uSucc(n) == bef
    // Insert *n into the sequence after *aft, or at the beginning if aft == 0.
    void uInsertAft(T *aft, T *n) {             // pre: !n->uListed() & *aft in *this
#ifdef __U_DEBUG__
      if ( n->uListed() ) uAbort( "(uSequence &)0x%p.uInsertAft( 0x%p, 0x%p ) node is already on another list.", this, aft, n );
#endif // __U_DEBUG__
      if (!aft) {
          if (root) {
            uNext(n) = root;
            uBack(n) = uBack(root);
            uNext(uBack(n)) = n;
            uBack(root) = n;
          }
          else {
            uNext(n) = n;
            uBack(n) = n;
          };
          root = n;
      }
      else {
          uNext(n) = uNext(aft);
          uBack(n) = aft;
          uBack((T *)uNext(n)) = n;
          uNext(aft) = n;
      }
    }                                     // post: n->uListed() & *n in *this & uSucc(n) == bef
    void uRemove(T *n) {                        // O(1)
#ifdef __U_DEBUG__
      if ( ! n->uListed() ) uAbort( "(uSequence &)0x%p.uRemove( 0x%p ) node is not on a list.", this, n );
#endif // __U_DEBUG__
      if (n == root) {
          if (uNext(root) == root) root = 0;
          else root = (T *)uNext(root);
      };
      uBack((T *)uNext(n)) = uBack(n);
      uNext(uBack(n)) = uNext(n);
      uNext(n) = uBack(n) = 0;
    }                                     // post: !n->uListed().
    // Add an element to the head of the sequence.
    inline void uAddHead(T* n) {                // pre: !n->uListed(); post: n->uListed() & uHead() == n
      uInsertAft( 0, n );
    }
    // Add an element to the tail of the sequence.
    inline void uAddTail(T* n) {                // pre: !n->uListed(); post: n->uListed() & uHead() == n
      uInsertBef( n, 0 );
    }
    // Add an element to the tail of the sequence.
    inline void uAdd(T* n) {                    // pre: !n->uListed(); post: n->uListed() & uHead() == n
      uAddTail( n );
    }
    // Remove and return the head element in the sequence.
    T *uDropHead() {
      T *n = uHead();
      return n ? uRemove( n ), n : 0;
    }
    // Remove and return the head element in the sequence.
    inline T *uDrop() {
      return uDropHead();
    }
    // Remove and return the tail element in the sequence.
    T *uDropTail() {
      T *n = uTail();
      return n ? uRemove( n ), n : 0;
    }
};


// uSeqGen<T> is used to iterate over a uSequence<T> in head-to-tail order.


template<class T> class uSeqGen: public uColGen<T>, protected uSFriend {
  protected:
    using uColGen<T>::curr;

    const uSequence<T> *seq;
  public:
    uSeqGen() : uColGen<T>() {
      seq = 0;
    } // post: elts = null.
    // Create a generator active in sequence s
    uSeqGen(const uSequence<T> &s) {      
      curr = s.uHead();
      seq = &s;
    }                                     // post: elts = {e in s}.
    // Make the generator active in sequence s.
    void uOver(const uSequence<T> &s) {
      curr = s.uHead();
      seq = &s;
    }                                     // post: elts = {e in s}.
    bool operator>>(T *&tp) {
      if (curr) {
          tp = curr;
          T *n = seq->uSucc(curr);
          curr = (n == seq->uHead()) ? 0 : n;
      }
      else tp = 0;
      return tp != 0;
    }
};


// A uSeqGenRev<T> is used to iterate over a uSequence<T> in tail-to-head order.

template<class T> class uSeqGenRev: public uColGen<T>, protected uSFriend {
  protected:
    using uColGen<T>::curr;

    const uSequence<T> *seq;
  public:
    uSeqGenRev() : uColGen<T>() {
      seq = 0;
    }                                     // post: elts = null.
    // Create a generator active in sequence s.
    uSeqGenRev(const uSequence<T> &s) {
      seq = &s;
      curr = s.uTail();
    }                                     // post: elts = {e in s}.
    // Make the generator active in sequence s.
    void uOver(const uSequence<T> &s) {
      seq = &s;
      curr = s.uTail();
    }                                     // post: elts = {e in s}.
    bool operator>>(T *&tp) {
      if (curr) {
          tp = curr;
          T *n = seq->uPred(curr);
          curr = (n == seq->uTail()) ? 0 : n;
      }
      else tp = 0;
      return tp != 0;
    }
};


#endif // __U_SEQUENCE_H__


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

Generated by  Doxygen 1.6.0   Back to index