collect.cxx

pwlib源码库

    return FALSE;
  RemoveAt(i);
  return TRUE;
}


PObject * PAbstractList::RemoveAt(PINDEX index)
{
  if (!SetCurrent(index)) {
    PAssertAlways(PInvalidArrayIndex);
    return NULL;
  }

  Element * elmt = info->lastElement;

  if (elmt->prev != NULL)
    elmt->prev->next = elmt->next;
  else {
    info->head = elmt->next;
    if (info->head != NULL)
      info->head->prev = NULL;
  }

  if (elmt->next != NULL)
    elmt->next->prev = elmt->prev;
  else {
    info->tail = elmt->prev;
    if (info->tail != NULL)
      info->tail->next = NULL;
  }

  if (elmt->next != NULL)
    info->lastElement = elmt->next;
  else {
    info->lastElement = elmt->prev;
    info->lastIndex--;
  }
  reference->size--;

  PObject * obj = elmt->data;
  if (obj != NULL && reference->deleteObjects) {
    delete obj;
    obj = NULL;
  }
  delete elmt;
  return obj;
}


PObject * PAbstractList::GetAt(PINDEX index) const
{
  return SetCurrent(index) ? info->lastElement->data : (PObject *)NULL;
}


BOOL PAbstractList::SetAt(PINDEX index, PObject * val)
{
  if (!SetCurrent(index))
    return FALSE;
  info->lastElement->data = val;
  return TRUE;
}

BOOL PAbstractList::ReplaceAt(PINDEX index, PObject * val)
{
  if (!SetCurrent(index))
    return FALSE;
  
  if (info->lastElement->data != NULL && reference->deleteObjects) {
    delete info->lastElement->data;
  }

  info->lastElement->data = val;
  return TRUE;
}

PINDEX PAbstractList::GetObjectsIndex(const PObject * obj) const
{
  PINDEX index = 0;
  Element * element = info->head;
  while (element != NULL) {
    if (element->data == obj) {
      info->lastElement = element;
      info->lastIndex = index;
      return index;
    }
    element = element->next;
    index++;
  }

  return P_MAX_INDEX;
}


PINDEX PAbstractList::GetValuesIndex(const PObject & obj) const
{
  PINDEX index = 0;
  Element * element = info->head;
  while (element != NULL) {
    if (*element->data == obj) {
      info->lastElement = element;
      info->lastIndex = index;
      return index;
    }
    element = element->next;
    index++;
  }

  return P_MAX_INDEX;
}


BOOL PAbstractList::SetCurrent(PINDEX index) const
{
  if (index >= GetSize())
    return FALSE;

  if (info->lastElement == NULL || info->lastIndex >= GetSize() || 
      index < info->lastIndex/2 || index > (info->lastIndex+GetSize())/2) {
    if (index < GetSize()/2) {
      info->lastIndex = 0;
      info->lastElement = info->head;
    }
    else {
      info->lastIndex = GetSize()-1;
      info->lastElement = info->tail;
    }
  }

  while (info->lastIndex < index) {
    info->lastElement = info->lastElement->next;
    info->lastIndex++;
  }

  while (info->lastIndex > index) {
    info->lastElement = info->lastElement->prev;
    info->lastIndex--;
  }

  return TRUE;
}


PAbstractList::Element::Element(PObject * theData)
{
  next = prev = NULL;
  data = theData;
}


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

PAbstractSortedList::PAbstractSortedList()
{
  info = new Info;
  PAssert(info != NULL, POutOfMemory);
}


PAbstractSortedList::Info::Info()
{
  root = &nil;
  lastElement = NULL;
  lastIndex = P_MAX_INDEX;
  nil.parent = nil.left = nil.right = &nil;
  nil.subTreeSize = 0;
  nil.colour = Element::Black;
  nil.data = NULL;
}


void PAbstractSortedList::DestroyContents()
{
  RemoveAll();
  delete info;
  info = NULL;
}


void PAbstractSortedList::CopyContents(const PAbstractSortedList & list)
{
  info = list.info;
}


void PAbstractSortedList::CloneContents(const PAbstractSortedList * list)
{
  Info * otherInfo = list->info;

  info = new Info;
  PAssert(info != NULL, POutOfMemory);
  reference->size = 0;

  // Have to do this in this manner rather than just doing a for() loop
  // as "this" and "list" may be the same object and we just changed info in
  // "this" so we need to use the info in "list" saved previously.
  Element * element = otherInfo->OrderSelect(otherInfo->root, 1);
  while (element != &otherInfo->nil) {
    Append(element->data->Clone());
    element = otherInfo->Successor(element);
  }
}


BOOL PAbstractSortedList::SetSize(PINDEX)
{
  return TRUE;
}


PObject::Comparison PAbstractSortedList::Compare(const PObject & obj) const
{
  PAssert(PIsDescendant(&obj, PAbstractSortedList), PInvalidCast);
  Element * elmt1 = info->root;
  while (elmt1->left != &info->nil)
    elmt1 = elmt1->left;

  Element * elmt2 = ((const PAbstractSortedList &)obj).info->root;
  while (elmt2->left != &info->nil)
    elmt2 = elmt2->left;

  while (elmt1 != &info->nil && elmt2 != &info->nil) {
    if (elmt1 == &info->nil)
      return LessThan;
    if (elmt2 == &info->nil)
      return GreaterThan;
    if (*elmt1->data < *elmt2->data)
      return LessThan;
    if (*elmt1->data > *elmt2->data)
      return GreaterThan;
    elmt1 = info->Successor(elmt1);
    elmt2 = info->Successor(elmt2);
  }
  return EqualTo;
}


PINDEX PAbstractSortedList::Append(PObject * obj)
{
  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;
}


BOOL PAbstractSortedList::Remove(const PObject * obj)
{
  if (GetObjectsIndex(obj) == P_MAX_INDEX)
    return FALSE;

  RemoveElement(info->lastElement);
  return TRUE;
}


PObject * PAbstractSortedList::RemoveAt(PINDEX index)
{
  Element * node = info->OrderSelect(info->root, index+1);
  if (node == &info->nil)
    return NULL;

  PObject * data = node->data;
  RemoveElement(node);
  return reference->deleteObjects ? (PObject *)NULL : data;
}


void PAbstractSortedList::RemoveAll()
{
  if (info->root != &info->nil) {
    DeleteSubTrees(info->root, reference->deleteObjects);
    delete info->root;
    info->root = &info->nil;
    reference->size = 0;
  }
}


PINDEX PAbstractSortedList::Insert(const PObject &, PObject * obj)
{
  return Append(obj);
}


PINDEX PAbstractSortedList::InsertAt(PINDEX, PObject * obj)
{
  return Append(obj);
}


BOOL PAbstractSortedList::SetAt(PINDEX, PObject *)
{
  return FALSE;
}


PObject * PAbstractSortedList::GetAt(PINDEX index) const
{
  if (index >= GetSize())
    return NULL;

  if (index != info->lastIndex) {
    if (index == info->lastIndex-1) {
      info->lastIndex--;
      info->lastElement = info->Predecessor(info->lastElement);
    }
    else if (index == info->lastIndex+1 && info->lastElement != NULL) {
      info->lastIndex++;
      info->lastElement = info->Successor(info->lastElement);
    }
    else {
      info->lastIndex = index;
      info->lastElement = info->OrderSelect(info->root, index+1);
    }
  }

  return PAssertNULL(info->lastElement)->data;
}


PINDEX PAbstractSortedList::GetObjectsIndex(const PObject * obj) const
{
  Element * elmt = NULL;
  PINDEX pos = ValueSelect(info->root, *obj, (const Element **)&elmt);
  if (pos == P_MAX_INDEX)
    return P_MAX_INDEX;

  if (elmt->data != obj) {
    PINDEX savePos = pos;
    Element * saveElmt = elmt;
    while (elmt->data != obj &&
            (elmt = info->Predecessor(elmt)) != &info->nil &&
            *obj == *elmt->data)
      pos--;
    if (elmt->data != obj) {
      pos = savePos;
      elmt = saveElmt;
      while (elmt->data != obj &&
              (elmt = info->Successor(elmt)) != &info->nil &&
              *obj == *elmt->data)
        pos++;
      if (elmt->data != obj)
        return P_MAX_INDEX;
    }
  }

  info->lastIndex = pos;
  info->lastElement = elmt;

  return pos;
}


PINDEX PAbstractSortedList::GetValuesIndex(const PObject & obj) const
{
  PINDEX pos = ValueSelect(info->root, obj, (const Element **)&info->lastElement);
  if (pos == P_MAX_INDEX)
    return P_MAX_INDEX;

  info->lastIndex = pos;

  Element * prev;
  while ((prev = info->Predecessor(info->lastElement)) != &info->nil &&
                                  prev->data->Compare(obj) == EqualTo) {
    info->lastElement = prev;
    info->lastIndex--;
  }

  return info->lastIndex;
}


void PAbstractSortedList::RemoveElement(Element * node)
{
  // Don't try an remove one of the special leaf nodes!
  if (PAssertNULL(node) == &info->nil)
    return;

  if (node->data != NULL && reference->deleteObjects)
    delete node->data;

  Element * y = node->left == &info->nil || node->right == &info->nil ? node : info->Successor(node);

  Element * t = y;
  while (t != &info->nil) {
    t->subTreeSize--;
    t = t->parent;
  }

  Element * x = y->left != &info->nil ? y->left : y->right;
  x->parent = y->parent;

  if (y->parent == &info->nil)
    info->root = x;
  else if (y == y->parent->left)
    y->parent->left = x;
  else
    y->parent->right = x;

  if (y != node)
    node->data = y->data;

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

  delete y;

  reference->size--;
  info->lastIndex = P_MAX_INDEX;
  info->lastElement = NULL;
}


void PAbstractSortedList::LeftRotate(Element * node)
{
  Element * pivot = PAssertNULL(node)->right;
  node->right = pivot->left;
  if (pivot->left != &info->nil)
    pivot->left->parent = node;
  pivot->parent = node->parent;
  if (node->parent == &info->nil)
    info->root = pivot;
  else if (node == node->parent->left)
    node->parent->left = pivot;
  else
    node->parent->right = pivot;
  pivot->left = node;
  node->parent = pivot;
  pivot->subTreeSize = node->subTreeSize;
  node->subTreeSize = node->left->subTreeSize + node->right->subTreeSize + 1;
}


void PAbstractSortedList::RightRotate(Element * node)
{
  Element * pivot = PAssertNULL(node)->left;
  node->left = pivot->right;
  if (pivot->right != &info->nil)
    pivot->right->parent = node;
  pivot->parent = node->parent;
  if (node->parent == &info->nil)
    info->root = pivot;
  else if (node == node->parent->right)
    node->parent->right = pivot;
  else
    node->parent->left = pivot;
  pivot->right = node;
  node->parent = pivot;
  pivot->subTreeSize = node->subTreeSize;
  node->subTreeSize = node->left->subTreeSize + node->right->subTreeSize + 1;
}


PAbstractSortedList::Element * PAbstractSortedList::Info ::Successor(const Element * node) const
{
  Element * next;
  if (node->right != &nil) {
    next = node->right;
    while (next->left != &nil)
      next = next->left;
  }
  else {
    next = node->parent;