Logo Search packages:      
Sourcecode: pwlib version File versions  Download package

PINDEX PAbstractSortedList::Append ( PObject obj ) [virtual]

Add a new object to the collection. The object is always placed in the correct ordinal position in the list. It is not placed at the "end".

Returns:
index of the newly added object.

Implements PCollection.

Definition at line 853 of file collect.cxx.

{
  if (PAssertNULL(obj) == NULL)
    return P_MAX_INDEX;

  Element * z = new Element;
  z->parent = z->left = z->right = &info->nil;
  z->colour = Element::Black;
  z->subTreeSize = 1;
  z->data = obj;

  Element * x = info->root;
  Element * y = &info->nil;
  while (x != &info->nil) {
    x->subTreeSize++;
    y = x;
    x = *z->data < *x->data ? x->left : x->right;
  }
  z->parent = y;
  if (y == &info->nil)
    info->root = z;
  else if (*z->data < *y->data)
    y->left = z;
  else
    y->right = z;

  info->lastElement = x = z;

  x->colour = Element::Red;
  while (x != info->root && x->parent->colour == Element::Red) {
    if (x->parent == x->parent->parent->left) {
      y = x->parent->parent->right;
      if (y->colour == Element::Red) {
        x->parent->colour = Element::Black;
        y->colour = Element::Black;
        x->parent->parent->colour = Element::Red;
        x = x->parent->parent;
      }
      else {
        if (x == x->parent->right) {
          x = x->parent;
          LeftRotate(x);
        }
        x->parent->colour = Element::Black;
        x->parent->parent->colour = Element::Red;
        RightRotate(x->parent->parent);
      }
    }
    else {
      y = x->parent->parent->left;
      if (y->colour == Element::Red) {
        x->parent->colour = Element::Black;
        y->colour = Element::Black;
        x->parent->parent->colour = Element::Red;
        x = x->parent->parent;
      }
      else {
        if (x == x->parent->left) {
          x = x->parent;
          RightRotate(x);
        }
        x->parent->colour = Element::Black;
        x->parent->parent->colour = Element::Red;
        LeftRotate(x->parent->parent);
      }
    }
  }

  info->root->colour = Element::Black;

  x = info->lastElement;
  info->lastIndex = x->left->subTreeSize;
  while (x != info->root) {
    if (x != x->parent->left)
      info->lastIndex += x->parent->left->subTreeSize+1;
    x = x->parent;
  }

  reference->size++;
  return info->lastIndex;
}

Generated by  Doxygen 1.6.0   Back to index