collect.cxx

opal的ptlib c++源程序 可以从官方网站上下载

        return node->left->subTreeSize;
    }
  }

  return P_MAX_INDEX;
}


void PAbstractSortedList::DeleteSubTrees(Element * node, PBoolean deleteObject)
{
  if (node->left != &info->nil) {
    DeleteSubTrees(node->left, deleteObject);
    delete node->left;
    node->left = &info->nil;
  }
  if (node->right != &info->nil) {
    DeleteSubTrees(node->right, deleteObject);
    delete node->right;
    node->right = &info->nil;
  }
  if (deleteObject) {
    delete node->data;
    node->data = NULL;
  }
}


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

PObject * POrdinalKey::Clone() const
{
  return new POrdinalKey(theKey);
}


PObject::Comparison POrdinalKey::Compare(const PObject & obj) const
{
  PAssert(PIsDescendant(&obj, POrdinalKey), PInvalidCast);
  const POrdinalKey & other = (const POrdinalKey &)obj;
  
  if (theKey < other.theKey)
    return LessThan;

  if (theKey > other.theKey)
    return GreaterThan;

  return EqualTo;
}


PINDEX POrdinalKey::HashFunction() const
{
  return PABSINDEX(theKey)%23;
}


void POrdinalKey::PrintOn(ostream & strm) const
{
  strm << theKey;
}


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

void PHashTableInfo::DestroyContents()
{
  for (PINDEX i = 0; i < GetSize(); i++) {
    Element * list = GetAt(i);
    if (list != NULL) {
      Element * elmt = list;
      do {
        Element * nextElmt = elmt->next;
        if (elmt->data != NULL && reference->deleteObjects)
          delete elmt->data;
        if (deleteKeys)
          delete elmt->key;
        delete elmt;
        elmt = nextElmt;
      } while (elmt != list);
    }
  }
  PAbstractArray::DestroyContents();
}


PINDEX PHashTableInfo::AppendElement(PObject * key, PObject * data)
{
  PINDEX bucket = PAssertNULL(key)->HashFunction();
  Element * list = GetAt(bucket);
  Element * element = new Element;
  PAssert(element != NULL, POutOfMemory);
  element->key = key;
  element->data = data;
  if (list == NULL) {
    element->next = element->prev = element;
    SetAt(bucket, element);
  }
  else if (list == list->prev) {
    list->next = list->prev = element;
    element->next = element->prev = list;
  }
  else {
    element->next = list;
    element->prev = list->prev;
    list->prev->next = element;
    list->prev = element;
  }
  return bucket;
}


PObject * PHashTableInfo::RemoveElement(const PObject & key)
{
  PObject * obj = NULL;
  Element * lastElement = GetElementAt(key);
  if (lastElement != NULL) {
    if (lastElement == lastElement->prev)
      SetAt(key.HashFunction(), NULL);
    else {
      lastElement->prev->next = lastElement->next;
      lastElement->next->prev = lastElement->prev;
      SetAt(key.HashFunction(), lastElement->next);
    }
    obj = lastElement->data;
    if (deleteKeys)
      delete lastElement->key;
    delete lastElement;
  }
  return obj;
}


PBoolean PHashTableInfo::SetLastElementAt(PINDEX index, PHashTableElement * & lastElement)
{
  PINDEX lastBucket = 0;
  while ((lastElement = GetAt(lastBucket)) == NULL) {
    if (lastBucket >= GetSize())
      return FALSE;
    lastBucket++;
  }

  PINDEX lastIndex = 0;

  if (lastIndex < index) {
    while (lastIndex != index) {
      if (lastElement->next != operator[](lastBucket))
        lastElement = lastElement->next;
      else {
        do {
          if (++lastBucket >= GetSize())
            return PFalse;
        } while ((lastElement = operator[](lastBucket)) == NULL);
      }
      lastIndex++;
    }
  }
  else {
    while (lastIndex != index) {
      if (lastElement != operator[](lastBucket))
        lastElement = lastElement->prev;
      else {
        do {
          if (lastBucket-- == 0)
            return PFalse;
        } while ((lastElement = operator[](lastBucket)) == NULL);
        lastElement = lastElement->prev;
      }
      lastIndex--;
    }
  }

  return PTrue;
}


PHashTableElement * PHashTableInfo::GetElementAt(const PObject & key)
{
  Element * list = GetAt(key.HashFunction());
  if (list != NULL) {
    Element * element = list;
    do {
      if (*element->key == key) 
        return element;
      element = element->next;
    } while (element != list);
  }
  return NULL;
}


PINDEX PHashTableInfo::GetElementsIndex(
                           const PObject * obj, PBoolean byValue, PBoolean keys) const
{
  PINDEX index = 0;
  for (PINDEX i = 0; i < GetSize(); i++) {
    Element * list = operator[](i);
    if (list != NULL) {
      Element * element = list;
      do {
        PObject * keydata = keys ? element->key : element->data;
        if (byValue ? (*keydata == *obj) : (keydata == obj))
          return index;
        element = element->next;
        index++;
      } while (element != list);
    }
  }
  return P_MAX_INDEX;
}


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

PHashTable::PHashTable()
  : hashTable(new PHashTable::Table)
{
  PAssert(hashTable != NULL, POutOfMemory);
}


void PHashTable::DestroyContents()
{
  if (hashTable != NULL) {
    hashTable->reference->deleteObjects = reference->deleteObjects;
    delete hashTable;
    hashTable = NULL;
  }
}


void PHashTable::CopyContents(const PHashTable & hash)
{
  hashTable = hash.hashTable;
}

  
void PHashTable::CloneContents(const PHashTable * hash)
{
  PINDEX sz = PAssertNULL(hash)->GetSize();
  PHashTable::Table * original = PAssertNULL(hash->hashTable);

  hashTable = new PHashTable::Table(original->GetSize());
  PAssert(hashTable != NULL, POutOfMemory);

  for (PINDEX i = 0; i < sz; i++) {
    Element * lastElement = NULL;
    original->SetLastElementAt(i, lastElement);
    PObject * data = lastElement->data;
    if (data != NULL)
      data = data->Clone();
    hashTable->AppendElement(lastElement->key->Clone(), data);
  }
}


PObject::Comparison PHashTable::Compare(const PObject & obj) const
{
  PAssert(PIsDescendant(&obj, PHashTable), PInvalidCast);
  return reference != ((const PHashTable &)obj).reference
                                                      ? GreaterThan : EqualTo;
}


PBoolean PHashTable::SetSize(PINDEX)
{
  return PTrue;
}


PObject & PHashTable::AbstractGetDataAt(PINDEX index) const
{
  Element * lastElement;
  PAssert(hashTable->SetLastElementAt(index, lastElement), PInvalidArrayIndex);
  return *lastElement->data;
}


const PObject & PHashTable::AbstractGetKeyAt(PINDEX index) const
{
  Element * lastElement;
  PAssert(hashTable->SetLastElementAt(index, lastElement), PInvalidArrayIndex);
  return *lastElement->key;
}


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

void PAbstractSet::DestroyContents()
{
  hashTable->deleteKeys = reference->deleteObjects;
  PHashTable::DestroyContents();
}


void PAbstractSet::CopyContents(const PAbstractSet & )
{
}

  
void PAbstractSet::CloneContents(const PAbstractSet * )
{
}


PINDEX PAbstractSet::Append(PObject * obj)
{
  if (AbstractContains(*obj)) {
    if (reference->deleteObjects)
      delete obj;
    return P_MAX_INDEX;
  }

  reference->size++;
  return hashTable->AppendElement(obj, NULL);
}


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


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


PBoolean PAbstractSet::Remove(const PObject * obj)
{
  if (PAssertNULL(obj) == NULL)
    return PFalse;

  if (hashTable->GetElementAt(*obj) == NULL)
    return PFalse;

  hashTable->deleteKeys = hashTable->reference->deleteObjects = reference->deleteObjects;
  hashTable->RemoveElement(*obj);
  reference->size--;
  return PTrue;
}


PObject * PAbstractSet::RemoveAt(PINDEX index)
{
  Element * lastElement;
  if (!hashTable->SetLastElementAt(index, lastElement))
    return NULL;

  PObject * obj = lastElement->key;
  hashTable->deleteKeys = hashTable->reference->deleteObjects = reference->deleteObjects;
  hashTable->RemoveElement(*obj);
  reference->size--;
  return obj;
}


PINDEX PAbstractSet::GetObjectsIndex(const PObject * obj) const
{
  return hashTable->GetElementsIndex(obj, PFalse, PTrue);
}


PINDEX PAbstractSet::GetValuesIndex(const PObject & obj) const
{
  return hashTable->GetElementsIndex(&obj, PTrue, PTrue);
}


PObject * PAbstractSet::GetAt(PINDEX index) const
{
  return (PObject *)&AbstractGetKeyAt(index);
}


PBoolean PAbstractSet::SetAt(PINDEX, PObject * obj)
{
  return Append(obj);
}


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

PINDEX PAbstractDictionary::Append(PObject *)
{
  PAssertAlways(PUnimplementedFunction);
  return 0;
}


PINDEX PAbstractDictionary::Insert(const PObject & before, PObject * obj)
{
  AbstractSetAt(before, obj);
  return 0;
}


PINDEX PAbstractDictionary::InsertAt(PINDEX index, PObject * obj)
{
  AbstractSetAt(AbstractGetKeyAt(index), obj);
  return index;
}
 
 
PBoolean PAbstractDictionary::Remove(const PObject * obj)
{
  PINDEX idx = GetObjectsIndex(obj);
  if (idx == P_MAX_INDEX)
    return PFalse;

  RemoveAt(idx);
  return PTrue;
}


PObject * PAbstractDictionary::RemoveAt(PINDEX index)
{
  PObject & obj = AbstractGetDataAt(index);
  AbstractSetAt(AbstractGetKeyAt(index), NULL);
  return &obj;
}


PINDEX PAbstractDictionary::GetObjectsIndex(const PObject * obj) const
{
  return hashTable->GetElementsIndex(obj, PFalse, PFalse);
}


PINDEX PAbstractDictionary::GetValuesIndex(const PObject & obj) const
{
  return hashTable->GetElementsIndex(&obj, PTrue, PFalse);
}


PBoolean PAbstractDictionary::SetAt(PINDEX index, PObject * val)
{
  return AbstractSetAt(AbstractGetKeyAt(index), val);
}


PObject * PAbstractDictionary::GetAt(PINDEX index) const
{
  Element * lastElement;
  PAssert(hashTable->SetLastElementAt(index, lastElement), PInvalidArrayIndex);
  return lastElement->data;
}
 
 
PBoolean PAbstractDictionary::SetDataAt(PINDEX index, PObject * val)
{
  return AbstractSetAt(AbstractGetKeyAt(index), val);
}


PBoolean PAbstractDictionary::AbstractSetAt(const PObject & key, PObject * obj)
{
  if (obj == NULL) {
    obj = hashTable->RemoveElement(key);
    if (obj != NULL) {
      if (reference->deleteObjects)
        delete obj;
      reference->size--;
    }
  }
  else {
    Element * element = hashTable->GetElementAt(key);
    if (element == NULL) {
      hashTable->AppendElement(key.Clone(), obj);
      reference->size++;
    }
    else {
      if (reference->deleteObjects) 
    		delete element->data;
      element->data = obj;
    }
  }
  return PTrue;
}


PObject * PAbstractDictionary::AbstractGetAt(const PObject & key) const
{
  Element * element = hashTable->GetElementAt(key);
  return element != NULL ? element->data : (PObject *)NULL;
}


PObject & PAbstractDictionary::GetRefAt(const PObject & key) const
{
  Element * element = hashTable->GetElementAt(key);
  return *PAssertNULL(element)->data;
}


void PAbstractDictionary::PrintOn(ostream &strm) const
{
  char separator = strm.fill();
  if (separator == ' ')
    separator = '\n';

  for (PINDEX i = 0; i < GetSize(); i++) {
    if (i > 0)
      strm << separator;
    strm << AbstractGetKeyAt(i) << '=' << AbstractGetDataAt(i);
  }

  if (separator == '\n')
    strm << separator;
}


// End Of File ///////////////////////////////////////////////////////////////