Main Page | Namespace List | Class Hierarchy | Class List | Directories | File List | Namespace Members | Class Members | File Members | Search for 
Kernel

bmpseq.cpp File Reference

(r1785/r1282)

#include "camtypes.h"
#include "bmpseq.h"
#include "bmpcomp.h"

Go to the source code of this file.

Defines

#define new   CAM_DEBUG_NEW
#define CURRENT_PROCEDURE_NAME   "bmpseq.cpp"
#define ERROR2_CLASS(arg, classname)
#define ERROR3IF_NOT_CLASS(arg, classname)
#define ERROR3IF_NULL_CLASS(arg, classname)

Functions

KernelBitmap * FindBitmap (const List *const pBitmapList, const KernelBitmap *const pStart, const KernelBitmap *const pBitmap)
 Finds the ListItem as the position uOffset items further down the list from pListItem.
const ListItem * FindOffsetItem (const List *pList, const ListItem *pListItem, UINT32 uOffset)
 Finds the ListItem as the position uOffset items further down the list from pListItem. Used by the search FindBitmapSubstring().
KernelBitmap * FindBitmapSubstring (List *pMainList, List *pSubList, const ListItem *pFirstMain, const ListItem *const pFirstSub, const INT32 nSubLength)
 This is used internally by FindBitmapSubstring(...3 arguments...). Call that instead. Notes: Implements some well known string search algorithm whose name I can't remember. Basically, it looks at the end of the search string for a match and moves along in chunks if it can get away with it. Here it is from the STL.
KernelBitmap * FindBitmapSubstring (List *pMainList, List *pSubList, ListItem *pFirstMain)
 Searches for a sequence (string) of bitmaps.
KernelBitmap * FindSimple (List *pMainList, List *pSubList, const ListItem *const pFirstMain)
 Searches for a sequence (string) of bitmaps. This may be faster than the supposedly fast and complicated FindBitmapSubstring(). It was when I profiled it.

Define Documentation

#define CURRENT_PROCEDURE_NAME   "bmpseq.cpp"
 

Definition at line 119 of file bmpseq.cpp.

#define ERROR2_CLASS (  arg,
classname   ) 
 

Value:

ERROR2IF(arg == NULL || !arg->IS_KIND_OF(classname),    \
                                        FALSE, #arg " isn't");

Definition at line 121 of file bmpseq.cpp.

#define ERROR3IF_NOT_CLASS (  arg,
classname   ) 
 

Value:

ERROR3IF(arg != NULL && \
                                                !arg->IS_KIND_OF(classname), \
                                                CURRENT_PROCEDURE_NAME " - " #arg " isn't");

Definition at line 123 of file bmpseq.cpp.

#define ERROR3IF_NULL_CLASS (  arg,
classname   ) 
 

Value:

ERROR3IF(arg == NULL || \
                                                !arg->IS_KIND_OF(classname), \
                                                CURRENT_PROCEDURE_NAME " - " #arg " isn't");

Definition at line 127 of file bmpseq.cpp.

#define new   CAM_DEBUG_NEW
 

Definition at line 115 of file bmpseq.cpp.

Function Documentation

KernelBitmap* FindBitmap (  const List *const   pBitmapList,
const KernelBitmap *const   pStart,
const KernelBitmap *const   pBitmap
) 
 

Finds the ListItem as the position uOffset items further down the list from pListItem.

Author:
Colin_Barfoot (Xara Group Ltd) <camelotdev@xara.com>
Date:
09/07/96
Parameters:
pList - the list in which pListItem is [INPUTS] pListItem - the list item from which we wish to find the offset uOffset - the number of the item further along the list which we wish to retrieve
Returns:
A pointer to the desired list item NULL if gone off the end

Definition at line 216 of file bmpseq.cpp.

00218 {
00219     ERROR3IF_NULL_CLASS(pBitmap, KernelBitmap);
00220 
00221     if (pBitmapList == NULL)
00222     {
00223         return NULL;
00224     }
00225     const ListItem* pItem = pStart;
00226     const OILBitmap* pOILBmp = pBitmap->ActualBitmap;
00227 
00228     while (pItem != NULL)
00229     {
00230         KernelBitmap* pBmp = (KernelBitmap*)pItem;
00231         ERROR3IF_NOT_CLASS(pBmp, KernelBitmap);
00232 
00233         if (pBmp->ActualBitmap == pOILBmp || *pBmp->ActualBitmap == *pOILBmp)
00234         {
00235             return pBmp;
00236         }
00237         pItem = pBitmapList->GetNext(pItem);
00238     }
00239     return NULL;
00240 }

KernelBitmap* FindBitmapSubstring (  List *  pMainList,
List *  pSubList,
ListItem *  pFirstMain
) 
 

Searches for a sequence (string) of bitmaps.

Author:
Colin_Barfoot (Xara Group Ltd) <camelotdev@xara.com>
Date:
09/07/96
Parameters:
pMainList - the KernelBitmap list in which we wish to find pSubList [INPUTS] pSubList - the KernelBitmap list we wish to find pFirstMain - the KernelBitmap in pMainList from which we wish to start searching
Returns:
A pointer to the first KernelBitmap in pMainList where the matched sequence starts. NULL if pSubList wasn't found

Definition at line 467 of file bmpseq.cpp.

00468 {
00469     return (FindBitmapSubstring(pMainList, pSubList, pFirstMain, pSubList->GetHead(), 
00470                                 pSubList->GetCount()));
00471 }

KernelBitmap* FindBitmapSubstring (  List *  pMainList,
List *  pSubList,
const ListItem *  pFirstMain,
const ListItem *const   pFirstSub,
const INT32  nSubLength
) 
 

This is used internally by FindBitmapSubstring(...3 arguments...). Call that instead. Notes: Implements some well known string search algorithm whose name I can't remember. Basically, it looks at the end of the search string for a match and moves along in chunks if it can get away with it. Here it is from the STL.

Author:
Colin_Barfoot (Xara Group Ltd) <camelotdev@xara.com>
Date:
09/07/96
Parameters:
pMainList - the KernelBitmap list in which we wish to find pSubList [INPUTS] pSubList - the KernelBitmap list we wish to find pFirstMain - the KernelBitmap in pMainList from which we wish to start searching pFirstSub - the KernelBitmap in pSubList from which we wish to start matching
template <class chart>=""> size_t basic_string<charT>::find (const basic_string<charT>& str, size_t pos) const _THROW_NONE { return find_str (str.data(), pos, str.length()); }

/*template <class chart>=""> size_t basic_string<charT>::find_str (const charT* s, size_t pos, size_t len) const _THROW_NONE { size_t count = pos; size_t shift; size_t place; if ((length() == 0) || (len == 0)) return NPOS; while (len <= (length()-count)) { for (place = 0; place < len; ++place) { if (baggage_type::ne( *(s+len-1-place), (data()+count+(len-1-place))) ) break; } if (place == len) return count; shift = find(*(s+len-1-place), count+(len-place)); if (shift == NPOS) return NPOS; count = shift-(len-place-1); } return NPOS;

Definition at line 327 of file bmpseq.cpp.

00330 {
00331     ERROR3IF_NOT_CLASS(pMainList, List);
00332     ERROR3IF_NOT_CLASS(pSubList, List);
00333 
00334     if (pFirstMain == NULL || pFirstSub == NULL)
00335         return NULL;
00336 
00337     ERROR3IF_NOT_CLASS(pFirstMain, KernelBitmap);
00338     ERROR3IF_NOT_CLASS(pFirstSub, ImportBitmap);
00339 
00340     if (nSubLength <= 0)
00341     {
00342         ERROR3("FindBitmapSubstring - nSubLength <= 0");
00343         return NULL;
00344     }
00345     const ListItem* pCurrentMain = FindOffsetItem(pMainList, pFirstMain, nSubLength - 1);
00346     const ListItem* pCurrentSub;
00347     const ListItem* pLastSub = pSubList->GetTail();
00348     ERROR3IF(pLastSub == NULL, "FindBitmapSubstring - pLastSub == NULL");
00349 
00350     while (pCurrentMain != NULL)
00351     {
00352         pCurrentSub = pLastSub;
00353         INT32 nCurrentSubLength = 1;        // set as the new length of the substring to check
00354         while (nCurrentSubLength <= nSubLength)
00355         {
00356             KernelBitmap* pMainKernel = (KernelBitmap*)pCurrentMain;
00357             OILBitmap* pExistingOIL = pMainKernel->ActualBitmap;
00358             ERROR3IF_NULL_CLASS(pExistingOIL, OILBitmap);
00359             
00360             KernelBitmap* pSubKernel = ((ImportBitmap*)pCurrentSub)->pBmp;
00361             OILBitmap* pSubOIL = pSubKernel->ActualBitmap;
00362             ERROR3IF_NULL_CLASS(pSubOIL, OILBitmap);
00363 
00364             if (pExistingOIL != pSubOIL && !(*pExistingOIL == *pSubOIL))
00365                 break;
00366 
00367             pCurrentMain = pMainList->GetPrev(pCurrentMain);
00368             pCurrentSub = pSubList->GetPrev(pCurrentSub);
00369             ++nCurrentSubLength;
00370         }
00371 
00372         if (pCurrentSub == pSubList->GetPrev(pFirstSub))        // found the whole sub-list
00373         {
00374             return (KernelBitmap*)pCurrentMain;
00375         }
00376 
00377         // failed to find all the items in SubList so look for the sub-sublist where the
00378         // disparity was, starting at the next item in the main list.
00379         pCurrentMain = FindBitmapSubstring( pMainList, pSubList, 
00380                                 pMainList->GetNext(pCurrentMain), pCurrentSub, 
00381                                 nCurrentSubLength);
00382         if (pCurrentMain == NULL)
00383         {
00384             return NULL;
00385         }
00386         pCurrentMain = pMainList->GetPrev(pCurrentMain);
00387         pLastSub = pSubList->GetPrev(pCurrentSub);
00388     }
00389     return NULL;
00390 }

const ListItem* FindOffsetItem (  const List *  pList,
const ListItem *  pListItem,
UINT32  uOffset
) 
 

Finds the ListItem as the position uOffset items further down the list from pListItem. Used by the search FindBitmapSubstring().

Author:
Colin_Barfoot (Xara Group Ltd) <camelotdev@xara.com>
Date:
09/07/96
Parameters:
pList - the list in which pListItem is [INPUTS] pListItem - the list item from which we wish to find the offset uOffset - the number of the item further along the list which we wish to retrieve
Returns:
A pointer to the desired list item NULL if gone off the end

Definition at line 259 of file bmpseq.cpp.

00260 {
00261     while (uOffset > 0 && pListItem != NULL)
00262     {
00263         pListItem = pList->GetNext(pListItem);
00264         --uOffset;
00265     }
00266     return pListItem;
00267 }

KernelBitmap* FindSimple (  List *  pMainList,
List *  pSubList,
const ListItem *const   pFirstMain
) 
 

Searches for a sequence (string) of bitmaps. This may be faster than the supposedly fast and complicated FindBitmapSubstring(). It was when I profiled it.

Author:
Colin_Barfoot (Xara Group Ltd) <camelotdev@xara.com>
Date:
09/07/96
Parameters:
pMainList - the KernelBitmap list in which we wish to find pSubList [INPUTS] pSubList - the KernelBitmap list we wish to find pFirstMain - the KernelBitmap in pMainList from which we wish to start searching
Returns:
A pointer to the first KernelBitmap in pMainList where the matched sequence starts. NULL if pSubList wasn't found

Definition at line 493 of file bmpseq.cpp.

00494 {
00495     ERROR2IF(pMainList == NULL, NULL, "pMainList == NULL");
00496     ERROR2IF(pSubList == NULL, NULL, "pSubList == NULL");
00497     ERROR2IF(pFirstMain == NULL, NULL, "pFirstMain == NULL");
00498 
00499     // Is the list we're looking for empty or longer than the list we're looking in?
00500     UINT32 uSubListLen = pSubList->GetCount();
00501     if (uSubListLen == 0 || uSubListLen > pMainList->GetCount())
00502     {
00503         return NULL;
00504     }
00505 
00506     // ...No. So go through the main list looking for the first item in our search list
00507     // and each time we find it check subsequent items in the main list for a match with
00508     // those remaining in our search list. If we found them all that's it, otherwise
00509     // continue looking for the first item in the main list.
00510 
00511     const ListItem* pStartMain = pFirstMain;
00512     const ListItem* const pFirstSub = pSubList->GetHead();
00513     for (;;)    // ever
00514     {
00515         // Find the first item of the sublist in the main list
00516         const ListItem* pFound = (ListItem*)FindBitmap(pMainList, (KernelBitmap*)pStartMain, 
00517                                                     ((ImportBitmap*)pFirstSub)->pBmp);
00518         if (pFound == NULL)     // the first search item isn't in the main list at all
00519         {
00520             return NULL;
00521         }
00522 
00523         const ListItem* pCurrentMain = pMainList->GetNext(pFound);
00524         const ListItem* pCurrentSub = pSubList->GetNext(pFirstSub);
00525         while (pCurrentSub != NULL)
00526         {
00527             ERROR3IF(pCurrentMain == NULL, "pCurrentMain == NULL");
00528 
00529             KernelBitmap* pMainKernel = (KernelBitmap*)pCurrentMain;
00530             OILBitmap* pExistingOIL = pMainKernel->ActualBitmap;
00531             ERROR3IF_NULL_CLASS(pExistingOIL, OILBitmap);
00532             
00533             KernelBitmap* pSubKernel = ((ImportBitmap*)pCurrentSub)->pBmp;
00534             OILBitmap* pSubOIL = pSubKernel->ActualBitmap;
00535             ERROR3IF_NULL_CLASS(pSubOIL, OILBitmap);
00536 
00537             if (pExistingOIL != pSubOIL && !(*pExistingOIL == *pSubOIL))
00538                 break;
00539 
00540             pCurrentMain = pMainList->GetNext(pCurrentMain);
00541             pCurrentSub = pSubList->GetNext(pCurrentSub);
00542         }
00543         
00544         if (pCurrentSub == NULL)        // we reached the end of our search list. All done.
00545         {
00546             return (KernelBitmap*)pFound;
00547         }
00548 
00549         // We didn't manage to find the whole search list, so go back looking for the
00550         // first item in the search list starting at the next item in the main list
00551         pStartMain = pMainList->GetNext(pStartMain);
00552     }
00553 }

Generated on Sat Nov 10 03:49:04 2007 for Camelot by  doxygen 1.4.4