Optimized splay tree implementation

splay.cpp

template<class T> struct splnode {
  typedef splnode<T> node_t;

  splnode() : P(NULL) {
    C[0] = C[1] = NULL;
    pull();
  }

  /* Add extra state here. */

  node_t* P;
  node_t* C[2];

  /* Pull state changes up the tree (e.g. pull subtree sums).  Also here is
   * where we fix parent pointers.  pull() should not adjust for any range
   * aggregates (i.e. pull() shouldn't do anything different if you called
   * push() on the parent first). */
  void pull() {
    if(C[0]) C[0]->P = this;
    if(C[1]) C[1]->P = this;
  }

  /* Push state changes down the tree (e.g. push range updates).  A call to
   * pull() is requried after push() to update node state. */
  void push() {
  }

  /* Return the direction of this relative its parent. */
  int up() {
    return !P ? -1 : (P->C[0] == this ? 0 : 1);
  }

  /* Simple zig step in the 'c' direction. */
  void zig(int c) {
    node_t* X = C[c];
    if(X->P = P) P->C[up()] = X;
    C[c] = X->C[1 - c];
    X->C[1 - c] = this;
    pull(); X->pull();
    if(P) P->pull();
  }

  /* Splay this up to the root. */
  node_t* splay(splnode<T>* rt = NULL) {
    for(push(); P != rt; ) {
      if(P->P != rt) P->P->push();
      P->push();
      push();

      int c1 = up();
      if(P->P == rt) {
        P->zig(c1);
      } else {
        int c2 = P->up();
        if(c1 == c2) {
          P->P->zig(c2);
          P->zig(c1);
        } else {
          P->zig(c1);
          P->zig(c2);
        }
      }
    }
    return this;
  }

  /* Return the max element of the subtree rooted at this. */
  node_t* last(splnode<T>* rt = NULL) {
    for(node_t* r = this; ; r = r->C[1]) if(!r->C[1]) return r->splay(rt);
  }

  /* Return the min element of the subtree rooted at this. */
  node_t* first(splnode<T>* rt = NULL) {
    for(node_t* r = this; ; r = r->C[0]) if(!r->C[0]) return r->splay(rt);
  }
};