list.cpp

来自「A*算法 A*算法 A*算法 A*算法A*算法A*算法」· C++ 代码 · 共 765 行 · 第 1/2 页

wxNodeBase *wxListBase::DetachNode(wxNodeBase *node)
{
    wxCHECK_MSG( node, NULL, wxT("detaching NULL wxNodeBase") );
    wxCHECK_MSG( node->m_list == this, NULL,
                 wxT("detaching node which is not from this list") );

    // update the list
    wxNodeBase **prevNext = node->GetPrevious() ? &node->GetPrevious()->m_next
                                                : &m_nodeFirst;
    wxNodeBase **nextPrev = node->GetNext() ? &node->GetNext()->m_previous
                                            : &m_nodeLast;

    *prevNext = node->GetNext();
    *nextPrev = node->GetPrevious();

    m_count--;

    // mark the node as not belonging to this list any more
    node->m_list = NULL;

    return node;
}

bool wxListBase::DeleteNode(wxNodeBase *node)
{
    if ( !DetachNode(node) )
        return false;

    DoDeleteNode(node);

    return true;
}

bool wxListBase::DeleteObject(void *object)
{
    for ( wxNodeBase *current = GetFirst(); current; current = current->GetNext() )
    {
        if ( current->GetData() == object )
        {
            DeleteNode(current);
            return true;
        }
    }

    // not found
    return false;
}

void wxListBase::Clear()
{
    wxNodeBase *current = m_nodeFirst;
    while ( current )
    {
        wxNodeBase *next = current->GetNext();
        DoDeleteNode(current);
        current = next;
    }

    m_nodeFirst =
    m_nodeLast = (wxNodeBase *)NULL;

    m_count = 0;
}

void wxListBase::ForEach(wxListIterateFunction F)
{
    for ( wxNodeBase *current = GetFirst(); current; current = current->GetNext() )
    {
        (*F)(current->GetData());
    }
}

void *wxListBase::FirstThat(wxListIterateFunction F)
{
    for ( wxNodeBase *current = GetFirst(); current; current = current->GetNext() )
    {
        if ( (*F)(current->GetData()) )
            return current->GetData();
    }

    return (wxNodeBase *)NULL;
}

void *wxListBase::LastThat(wxListIterateFunction F)
{
    for ( wxNodeBase *current = GetLast(); current; current = current->GetPrevious() )
    {
        if ( (*F)(current->GetData()) )
            return current->GetData();
    }

    return (wxNodeBase *)NULL;
}

// ([e-mail])
//
// function for sorting lists. the concept is borrowed from 'qsort'.
// by giving a sort function, arbitrary lists can be sorted.
// method:
// - put wxObject pointers into an array
// - sort the array with qsort
// - put back the sorted wxObject pointers into the list
//
// CAVE: the sort function receives pointers to wxObject pointers (wxObject **),
//       so dereference right!
// EXAMPLE:
//   int listcompare(const void *arg1, const void *arg2)
//   {
//      return(compare(**(wxString **)arg1,
//                     **(wxString **)arg2));
//   }
//
//   void main()
//   {
//     wxListBase list;
//
//     list.Append(new wxString("DEF"));
//     list.Append(new wxString("GHI"));
//     list.Append(new wxString("ABC"));
//     list.Sort(listcompare);
//   }

void wxListBase::Sort(const wxSortCompareFunction compfunc)
{
    // allocate an array for the wxObject pointers of the list
    const size_t num = GetCount();
    void **objArray = new void *[num];
    void **objPtr = objArray;

    // go through the list and put the pointers into the array
    wxNodeBase *node;
    for ( node = GetFirst(); node; node = node->GetNext() )
    {
        *objPtr++ = node->GetData();
    }

    // sort the array
    qsort((void *)objArray,num,sizeof(wxObject *),
#ifdef __WXWINCE__
        (int (__cdecl *)(const void *,const void *))
#endif
        compfunc);

    // put the sorted pointers back into the list
    objPtr = objArray;
    for ( node = GetFirst(); node; node = node->GetNext() )
    {
        node->SetData(*objPtr++);
    }

    // free the array
    delete[] objArray;
}

void wxListBase::Reverse()
{
    wxNodeBase* node = m_nodeFirst;
    wxNodeBase* tmp;

    while (node)
    {
        // swap prev and next pointers
        tmp = node->m_next;
        node->m_next = node->m_previous;
        node->m_previous = tmp;

        // this is the node that was next before swapping
        node = tmp;
    }

    // swap first and last node
    tmp = m_nodeFirst; m_nodeFirst = m_nodeLast; m_nodeLast = tmp;
}

void wxListBase::DeleteNodes(wxNodeBase* first, wxNodeBase* last)
{
    wxNodeBase* node = first;

    while (node != last)
    {
        wxNodeBase* next = node->GetNext();
        DeleteNode(node);
        node = next;
    }
}

// ============================================================================
// compatibility section from now on
// ============================================================================

#ifdef wxLIST_COMPATIBILITY

// -----------------------------------------------------------------------------
// wxList (a.k.a. wxObjectList)
// -----------------------------------------------------------------------------

IMPLEMENT_DYNAMIC_CLASS(wxList, wxObject)

wxList::wxList( int key_type )
    : wxObjectList( (wxKeyType)key_type )
{
}

void wxObjectListNode::DeleteData()
{
    delete (wxObject *)GetData();
}

// ----------------------------------------------------------------------------
// wxStringList
// ----------------------------------------------------------------------------

static inline wxChar* MYcopystring(const wxChar* s)
{
    wxChar* copy = new wxChar[wxStrlen(s) + 1];
    return wxStrcpy(copy, s);
}

IMPLEMENT_DYNAMIC_CLASS(wxStringList, wxObject)

// instead of WX_DEFINE_LIST(wxStringListBase) we define this function
// ourselves
void wxStringListNode::DeleteData()
{
    delete [] (char *)GetData();
}

bool wxStringList::Delete(const wxChar *s)
{
    wxStringListNode *current;

    for ( current = GetFirst(); current; current = current->GetNext() )
    {
        if ( wxStrcmp(current->GetData(), s) == 0 )
        {
            DeleteNode(current);
            return true;
        }
    }

    // not found
    return false;
}

void wxStringList::DoCopy(const wxStringList& other)
{
    wxASSERT( GetCount() == 0 );    // this list must be empty before copying!

    size_t count = other.GetCount();
    for ( size_t n = 0; n < count; n++ )
    {
        Add(other.Item(n)->GetData());
    }
}

wxStringList::wxStringList()
{
    DeleteContents(true);
}

// Variable argument list, terminated by a zero
// Makes new storage for the strings
wxStringList::wxStringList (const wxChar *first, ...)
{
  DeleteContents(true);
  if ( !first )
    return;

  va_list ap;
  va_start(ap, first);

  const wxChar *s = first;
  for (;;)
  {
      Add(s);

      s = va_arg(ap, const wxChar *);
      //    if (s == NULL)
#ifdef __WXMSW__
      if ((int)(long) s == 0)
#else
      if ((long) s == 0)
#endif
          break;
  }

  va_end(ap);
}

// Only makes new strings if arg is true
wxChar **wxStringList::ListToArray(bool new_copies) const
{
    wxChar **string_array = new wxChar *[GetCount()];
    wxStringListNode *node = GetFirst();
    for (size_t i = 0; i < GetCount(); i++)
    {
        wxChar *s = node->GetData();
        if ( new_copies )
            string_array[i] = MYcopystring(s);
        else
            string_array[i] = s;
        node = node->GetNext();
    }

    return string_array;
}

// Checks whether s is a member of the list
bool wxStringList::Member(const wxChar *s) const
{
    for ( wxStringListNode *node = GetFirst(); node; node = node->GetNext() )
    {
        const wxChar *s1 = node->GetData();
        if (s == s1 || wxStrcmp (s, s1) == 0)
            return true;
    }

    return false;
}

#ifdef __WXWINCE__
extern "C" int __cdecl
#else
extern "C" int LINKAGEMODE
#endif

wx_comparestrings(const void *arg1, const void *arg2)
{
  wxChar **s1 = (wxChar **) arg1;
  wxChar **s2 = (wxChar **) arg2;

  return wxStrcmp (*s1, *s2);
}

// Sort a list of strings - deallocates old nodes, allocates new
void wxStringList::Sort()
{
    size_t N = GetCount();
    wxChar **array = new wxChar *[N];
    wxStringListNode *node;

    size_t i = 0;
    for ( node = GetFirst(); node; node = node->GetNext() )
    {
        array[i++] = node->GetData();
    }

    qsort (array, N, sizeof (wxChar *), wx_comparestrings);

    i = 0;
    for ( node = GetFirst(); node; node = node->GetNext() )
        node->SetData( array[i++] );

    delete [] array;
}

wxNode *wxStringList::Add(const wxChar *s)
{
    return (wxNode *)wxStringListBase::Append(MYcopystring(s));
}

wxNode *wxStringList::Prepend(const wxChar *s)
{
    return (wxNode *)wxStringListBase::Insert(MYcopystring(s));
}

#endif // wxLIST_COMPATIBILITY

#else // wxUSE_STL = 1

    #include "wx/listimpl.cpp"
    WX_DEFINE_LIST(wxObjectList);

// with wxUSE_STL wxStringList contains wxString objects, not pointers
void wxStringListBase::DeleteFunction( _WX_DELETEFUNCTIONCONST wxString WXUNUSED(X) )
{
}

#endif // !wxUSE_STL