eavlmmap.h

大型并行量子化学软件；支持密度泛函（DFT）。可以进行各种量子化学计算。支持CHARMM并行计算。非常具有应用价值。

  while (r = uplink(node)) {
      if (node == llink(r)) {
          node = r;
          return;
        }
      node = r;
    }
  node = 0;
}

template <class K, class T>
void
EAVLMMap<K,T>::insert(T* n)
{
  if (!n) {
      return;
    }

  length_++;

  rlink(n) = 0;
  llink(n) = 0;
  balance(n) = 0;

  if (!root_) {
      uplink(n) = 0;
      root_ = n;
      start_ = n;
      return;
    }

  // find an insertion point
  T* p = root_;
  T* prev_p = 0;
  int cmp;
  int have_start = 1;
  while (p) {
      if (p == n) {
          abort();
        }
      prev_p = p;
      cmp = compare(n,p);
      if (cmp < 0) p = llink(p);
      else {
          p = rlink(p);
          have_start = 0;
        }
    }

  // insert the node
  uplink(n) = prev_p;
  if (prev_p) {
      if (cmp < 0) llink(prev_p) = n;
      else rlink(prev_p) = n;
    }

  // maybe update the first node in the map
  if (have_start) start_ = n;

  // adjust the balance factors
  if (prev_p) {
      adjust_balance_insert(prev_p, n);
    }
}

template <class K, class T>
void
EAVLMMap<K,T>::adjust_balance_insert(T* A, T* child)
{
  if (!A) return;
  int adjustment;
  if (llink(A) == child) adjustment = -1;
  else adjustment = 1;
  int bal = balance(A) + adjustment;
  if (bal == 0) {
      balance(A) = 0;
    }
  else if (bal == -1 || bal == 1) {
      balance(A) = bal;
      adjust_balance_insert(uplink(A), A);
    }
  else if (bal == 2) {
      T* B = rlink(A);
      if (balance(B) == 1) {
          balance(B) = 0;
          balance(A) = 0;
          rlink(A) = llink(B);
          llink(B) = A;
          uplink(B) = uplink(A);
          uplink(A) = B;
          if (rlink(A)) uplink(rlink(A)) = A;
          if (llink(B)) uplink(llink(B)) = B;
          if (uplink(B) == 0) root_ = B;
          else {
              if (rlink(uplink(B)) == A) rlink(uplink(B)) = B;
              else llink(uplink(B)) = B;
            }
        }
      else {
          T* X = llink(B);
          rlink(A) = llink(X);
          llink(B) = rlink(X);
          llink(X) = A;
          rlink(X) = B;
          if (balance(X) == 1) {
              balance(A) = -1;
              balance(B) = 0;
            }
          else if (balance(X) == -1) {
              balance(A) = 0;
              balance(B) = 1;
            }
          else {
              balance(A) = 0;
              balance(B) = 0;
            }
          balance(X) = 0;
          uplink(X) = uplink(A);
          uplink(A) = X;
          uplink(B) = X;
          if (rlink(A)) uplink(rlink(A)) = A;
          if (llink(B)) uplink(llink(B)) = B;
          if (uplink(X) == 0) root_ = X;
          else {
              if (rlink(uplink(X)) == A) rlink(uplink(X)) = X;
              else llink(uplink(X)) = X;
            }
        }
    }
  else if (bal == -2) {
      T* B = llink(A);
      if (balance(B) == -1) {
          balance(B) = 0;
          balance(A) = 0;
          llink(A) = rlink(B);
          rlink(B) = A;
          uplink(B) = uplink(A);
          uplink(A) = B;
          if (llink(A)) uplink(llink(A)) = A;
          if (rlink(B)) uplink(rlink(B)) = B;
          if (uplink(B) == 0) root_ = B;
          else {
              if (llink(uplink(B)) == A) llink(uplink(B)) = B;
              else rlink(uplink(B)) = B;
            }
        }
      else {
          T* X = rlink(B);
          llink(A) = rlink(X);
          rlink(B) = llink(X);
          rlink(X) = A;
          llink(X) = B;
          if (balance(X) == -1) {
              balance(A) = 1;
              balance(B) = 0;
            }
          else if (balance(X) == 1) {
              balance(A) = 0;
              balance(B) = -1;
            }
          else {
              balance(A) = 0;
              balance(B) = 0;
            }
          balance(X) = 0;
          uplink(X) = uplink(A);
          uplink(A) = X;
          uplink(B) = X;
          if (llink(A)) uplink(llink(A)) = A;
          if (rlink(B)) uplink(rlink(B)) = B;
          if (uplink(X) == 0) root_ = X;
          else {
              if (llink(uplink(X)) == A) llink(uplink(X)) = X;
              else rlink(uplink(X)) = X;
            }
        }
    }
}

template <class K, class T>
void
EAVLMMap<K,T>::adjust_balance_remove(T* A, T* child)
{
  if (!A) return;
  int adjustment;
  if (llink(A) == child) adjustment = 1;
  else adjustment = -1;
  int bal = balance(A) + adjustment;
  if (bal == 0) {
      balance(A) = 0;
      adjust_balance_remove(uplink(A), A);
    }
  else if (bal == -1 || bal == 1) {
      balance(A) = bal;
    }
  else if (bal == 2) {
      T* B = rlink(A);
      if (balance(B) == 0) {
          balance(B) = -1;
          balance(A) = 1;
          rlink(A) = llink(B);
          llink(B) = A;
          uplink(B) = uplink(A);
          uplink(A) = B;
          if (rlink(A)) uplink(rlink(A)) = A;
          if (llink(B)) uplink(llink(B)) = B;
          if (uplink(B) == 0) root_ = B;
          else {
              if (rlink(uplink(B)) == A) rlink(uplink(B)) = B;
              else llink(uplink(B)) = B;
            }
        }
      else if (balance(B) == 1) {
          balance(B) = 0;
          balance(A) = 0;
          rlink(A) = llink(B);
          llink(B) = A;
          uplink(B) = uplink(A);
          uplink(A) = B;
          if (rlink(A)) uplink(rlink(A)) = A;
          if (llink(B)) uplink(llink(B)) = B;
          if (uplink(B) == 0) root_ = B;
          else {
              if (rlink(uplink(B)) == A) rlink(uplink(B)) = B;
              else llink(uplink(B)) = B;
            }
          adjust_balance_remove(uplink(B), B);
        }
      else {
          T* X = llink(B);
          rlink(A) = llink(X);
          llink(B) = rlink(X);
          llink(X) = A;
          rlink(X) = B;
          if (balance(X) == 0) {
              balance(A) = 0;
              balance(B) = 0;
            }
          else if (balance(X) == 1) {
              balance(A) = -1;
              balance(B) = 0;
            }
          else {
              balance(A) = 0;
              balance(B) = 1;
            }
          balance(X) = 0;
          uplink(X) = uplink(A);
          uplink(A) = X;
          uplink(B) = X;
          if (rlink(A)) uplink(rlink(A)) = A;
          if (llink(B)) uplink(llink(B)) = B;
          if (uplink(X) == 0) root_ = X;
          else {
              if (rlink(uplink(X)) == A) rlink(uplink(X)) = X;
              else llink(uplink(X)) = X;
            }
          adjust_balance_remove(uplink(X), X);
        }
    }
  else if (bal == -2) {
      T* B = llink(A);
      if (balance(B) == 0) {
          balance(B) = 1;
          balance(A) = -1;
          llink(A) = rlink(B);
          rlink(B) = A;
          uplink(B) = uplink(A);
          uplink(A) = B;
          if (llink(A)) uplink(llink(A)) = A;
          if (rlink(B)) uplink(rlink(B)) = B;
          if (uplink(B) == 0) root_ = B;
          else {
              if (llink(uplink(B)) == A) llink(uplink(B)) = B;
              else rlink(uplink(B)) = B;
            }
        }
      else if (balance(B) == -1) {
          balance(B) = 0;
          balance(A) = 0;
          llink(A) = rlink(B);
          rlink(B) = A;
          uplink(B) = uplink(A);
          uplink(A) = B;
          if (llink(A)) uplink(llink(A)) = A;
          if (rlink(B)) uplink(rlink(B)) = B;
          if (uplink(B) == 0) root_ = B;
          else {
              if (llink(uplink(B)) == A) llink(uplink(B)) = B;
              else rlink(uplink(B)) = B;
            }
          adjust_balance_remove(uplink(B), B);
        }
      else {
          T* X = rlink(B);
          llink(A) = rlink(X);
          rlink(B) = llink(X);
          rlink(X) = A;
          llink(X) = B;
          if (balance(X) == 0) {
              balance(A) = 0;
              balance(B) = 0;
            }
          else if (balance(X) == -1) {
              balance(A) = 1;
              balance(B) = 0;
            }
          else {
              balance(A) = 0;
              balance(B) = -1;
            }
          balance(X) = 0;
          uplink(X) = uplink(A);
          uplink(A) = X;
          uplink(B) = X;
          if (llink(A)) uplink(llink(A)) = A;
          if (rlink(B)) uplink(rlink(B)) = B;
          if (uplink(X) == 0) root_ = X;
          else {
              if (llink(uplink(X)) == A) llink(uplink(X)) = X;
              else rlink(uplink(X)) = X;
            }
          adjust_balance_remove(uplink(X), X);
        }
    }
}

template <class K, class T>
inline
EAVLMMap<K,T>::EAVLMMap()
{
  initialize(0);
}

template <class K, class T>
inline
EAVLMMap<K,T>::EAVLMMap(EAVLMMapNode<K,T> T::* node)
{
  initialize(node);
}

template <class K, class T>
inline void
EAVLMMap<K,T>::initialize(EAVLMMapNode<K,T> T::* node)
{
  node_ = node;
  root_ = 0;
  start_ = 0;
  length_ = 0;
}

}

#endif

// ///////////////////////////////////////////////////////////////////////////

// Local Variables:
// mode: c++
// c-file-style: "CLJ"
// End: