[comctl32]

[reactos.git] / reactos / dll / win32 / comctl32 / listview.c

/*
 * Listview control
 *
 * Copyright 1998, 1999 Eric Kohl
 * Copyright 1999 Luc Tourangeau
 * Copyright 2000 Jason Mawdsley
 * Copyright 2001 CodeWeavers Inc.
 * Copyright 2002 Dimitrie O. Paun
 * Copyright 2009-2011 Nikolay Sivov
 * Copyright 2009 Owen Rudge for CodeWeavers
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2.1 of the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA
 *
 * NOTES
 *
 * This code was audited for completeness against the documented features
 * of Comctl32.dll version 6.0 on May. 20, 2005, by James Hawkins.
 * 
 * Unless otherwise noted, we believe this code to be complete, as per
 * the specification mentioned above.
 * If you discover missing features, or bugs, please note them below.
 * 
 * TODO:
 *
 * Default Message Processing
 *   -- WM_CREATE: create the icon and small icon image lists at this point only if
 *      the LVS_SHAREIMAGELISTS style is not specified.
 *   -- WM_WINDOWPOSCHANGED: arrange the list items if the current view is icon
 *      or small icon and the LVS_AUTOARRANGE style is specified.
 *   -- WM_TIMER
 *   -- WM_WININICHANGE
 *
 * Features
 *   -- Hot item handling, mouse hovering
 *   -- Workareas support
 *   -- Tilemode support
 *   -- Groups support
 *
 * Bugs
 *   -- Expand large item in ICON mode when the cursor is flying over the icon or text.
 *   -- Support CustomDraw options for _WIN32_IE >= 0x560 (see NMLVCUSTOMDRAW docs).
 *   -- LVA_SNAPTOGRID not implemented
 *   -- LISTVIEW_ApproximateViewRect partially implemented
 *   -- LISTVIEW_SetColumnWidth ignores header images & bitmap
 *   -- LISTVIEW_SetIconSpacing is incomplete
 *   -- LISTVIEW_StyleChanged doesn't handle some changes too well
 *
 * Speedups
 *   -- LISTVIEW_GetNextItem needs to be rewritten. It is currently
 *      linear in the number of items in the list, and this is
 *      unacceptable for large lists.
 *   -- if list is sorted by item text LISTVIEW_InsertItemT could use
 *      binary search to calculate item index (e.g. DPA_Search()).
 *      This requires sorted state to be reliably tracked in item modifiers.
 *   -- we should keep an ordered array of coordinates in iconic mode
 *      this would allow to frame items (iterator_frameditems),
 *      and find nearest item (LVFI_NEARESTXY) a lot more efficiently
 *
 * Flags
 *   -- LVIF_COLUMNS
 *   -- LVIF_GROUPID
 *
 * States
 *   -- LVIS_ACTIVATING (not currently supported by comctl32.dll version 6.0)
 *   -- LVIS_DROPHILITED
 *   -- LVIS_OVERLAYMASK
 *
 * Styles
 *   -- LVS_NOLABELWRAP
 *   -- LVS_NOSCROLL (see Q137520)
 *   -- LVS_ALIGNTOP
 *
 * Extended Styles
 *   -- LVS_EX_BORDERSELECT
 *   -- LVS_EX_FLATSB
 *   -- LVS_EX_INFOTIP
 *   -- LVS_EX_LABELTIP
 *   -- LVS_EX_MULTIWORKAREAS
 *   -- LVS_EX_REGIONAL
 *   -- LVS_EX_SIMPLESELECT
 *   -- LVS_EX_TWOCLICKACTIVATE
 *   -- LVS_EX_UNDERLINECOLD
 *   -- LVS_EX_UNDERLINEHOT
 *   
 * Notifications:
 *   -- LVN_BEGINSCROLL, LVN_ENDSCROLL
 *   -- LVN_GETINFOTIP
 *   -- LVN_HOTTRACK
 *   -- LVN_SETDISPINFO
 *   -- LVN_BEGINRDRAG
 *
 * Messages:
 *   -- LVM_ENABLEGROUPVIEW
 *   -- LVM_GETBKIMAGE, LVM_SETBKIMAGE
 *   -- LVM_GETGROUPINFO, LVM_SETGROUPINFO
 *   -- LVM_GETGROUPMETRICS, LVM_SETGROUPMETRICS
 *   -- LVM_GETINSERTMARK, LVM_SETINSERTMARK
 *   -- LVM_GETINSERTMARKCOLOR, LVM_SETINSERTMARKCOLOR
 *   -- LVM_GETINSERTMARKRECT
 *   -- LVM_GETNUMBEROFWORKAREAS
 *   -- LVM_GETOUTLINECOLOR, LVM_SETOUTLINECOLOR
 *   -- LVM_GETSELECTEDCOLUMN, LVM_SETSELECTEDCOLUMN
 *   -- LVM_GETISEARCHSTRINGW, LVM_GETISEARCHSTRINGA
 *   -- LVM_GETTILEINFO, LVM_SETTILEINFO
 *   -- LVM_GETTILEVIEWINFO, LVM_SETTILEVIEWINFO
 *   -- LVM_GETWORKAREAS, LVM_SETWORKAREAS
 *   -- LVM_HASGROUP, LVM_INSERTGROUP, LVM_REMOVEGROUP, LVM_REMOVEALLGROUPS
 *   -- LVM_INSERTGROUPSORTED
 *   -- LVM_INSERTMARKHITTEST
 *   -- LVM_ISGROUPVIEWENABLED
 *   -- LVM_MOVEGROUP
 *   -- LVM_MOVEITEMTOGROUP
 *   -- LVM_SETINFOTIP
 *   -- LVM_SETTILEWIDTH
 *   -- LVM_SORTGROUPS
 *
 * Macros:
 *   -- ListView_GetHoverTime, ListView_SetHoverTime
 *   -- ListView_GetISearchString
 *   -- ListView_GetNumberOfWorkAreas
 *   -- ListView_GetWorkAreas, ListView_SetWorkAreas
 *
 * Functions:
 *   -- LVGroupComparE
 *
 * Known differences in message stream from native control (not known if
 * these differences cause problems):
 *   LVM_INSERTITEM issues LVM_SETITEMSTATE and LVM_SETITEM in certain cases.
 *   LVM_SETITEM does not always issue LVN_ITEMCHANGING/LVN_ITEMCHANGED.
 *   WM_CREATE does not issue WM_QUERYUISTATE and associated registry
 *     processing for "USEDOUBLECLICKTIME".
 */

#include "config.h"
#include "wine/port.h"

#include <assert.h>
#include <ctype.h>
#include <string.h>
#include <stdlib.h>
#include <stdarg.h>
#include <stdio.h>

#include "windef.h"
#include "winbase.h"
#include "winnt.h"
#include "wingdi.h"
#include "winuser.h"
#include "winnls.h"
#include "commctrl.h"
#include "comctl32.h"
#include "uxtheme.h"

#include "wine/debug.h"
#include "wine/unicode.h"

WINE_DEFAULT_DEBUG_CHANNEL(listview);

typedef struct tagCOLUMN_INFO
{
  RECT rcHeader;        /* tracks the header's rectangle */
  INT fmt;              /* same as LVCOLUMN.fmt */
  INT cxMin;
} COLUMN_INFO;

typedef struct tagITEMHDR
{
  LPWSTR pszText;
  INT iImage;
} ITEMHDR, *LPITEMHDR;

typedef struct tagSUBITEM_INFO
{
  ITEMHDR hdr;
  INT iSubItem;
} SUBITEM_INFO;

typedef struct tagITEM_ID ITEM_ID;

typedef struct tagITEM_INFO
{
  ITEMHDR hdr;
  UINT state;
  LPARAM lParam;
  INT iIndent;
  ITEM_ID *id;
} ITEM_INFO;

struct tagITEM_ID
{
  UINT id;   /* item id */
  HDPA item; /* link to item data */
};

typedef struct tagRANGE
{
  INT lower;
  INT upper;
} RANGE;

typedef struct tagRANGES
{
  HDPA hdpa;
} *RANGES;

typedef struct tagITERATOR
{
  INT nItem;
  INT nSpecial;
  RANGE range;
  RANGES ranges;
  INT index;
} ITERATOR;

typedef struct tagDELAYED_ITEM_EDIT
{
  BOOL fEnabled;
  INT iItem;
} DELAYED_ITEM_EDIT;

typedef struct tagLISTVIEW_INFO
{
  /* control window */
  HWND hwndSelf;
  RECT rcList;                 /* This rectangle is really the window
                                * client rectangle possibly reduced by the 
                                * horizontal scroll bar and/or header - see 
                                * LISTVIEW_UpdateSize. This rectangle offset
                                * by the LISTVIEW_GetOrigin value is in
                                * client coordinates   */

  /* notification window */
  SHORT notifyFormat;
  HWND hwndNotify;
  BOOL bDoChangeNotify;         /* send change notification messages? */
  UINT uCallbackMask;

  /* tooltips */
  HWND hwndToolTip;

  /* items */
  INT nItemCount;               /* the number of items in the list */
  HDPA hdpaItems;               /* array ITEM_INFO pointers */
  HDPA hdpaItemIds;             /* array of ITEM_ID pointers */
  HDPA hdpaPosX;                /* maintains the (X, Y) coordinates of the */
  HDPA hdpaPosY;                /* items in LVS_ICON, and LVS_SMALLICON modes */
  RANGES selectionRanges;
  INT nSelectionMark;           /* item to start next multiselection from */
  INT nHotItem;
  BOOL bAutoarrange;            /* Autoarrange flag when NOT in LVS_AUTOARRANGE */

  /* columns */
  HDPA hdpaColumns;             /* array of COLUMN_INFO pointers */
  BOOL colRectsDirty;           /* trigger column rectangles requery from header */

  /* item metrics */
  BOOL bNoItemMetrics;          /* flags if item metrics are not yet computed */
  INT nItemHeight;
  INT nItemWidth;

  /* sorting */
  PFNLVCOMPARE pfnCompare;      /* sorting callback pointer */
  LPARAM lParamSort;

  /* style */
  DWORD dwStyle;                /* the cached window GWL_STYLE */
  DWORD dwLvExStyle;            /* extended listview style */
  DWORD uView;                  /* current view available through LVM_[G,S]ETVIEW */

  /* edit item */
  HWND hwndEdit;
  WNDPROC EditWndProc;
  INT nEditLabelItem;
  DELAYED_ITEM_EDIT itemEdit;   /* Pointer to this structure will be the timer ID */

  /* icons */
  HIMAGELIST himlNormal;
  HIMAGELIST himlSmall;
  HIMAGELIST himlState;
  SIZE iconSize;
  SIZE iconSpacing;
  SIZE iconStateSize;
  POINT currIconPos;        /* this is the position next icon will be placed */

  /* header */
  HWND hwndHeader;
  INT xTrackLine;           /* The x coefficient of the track line or -1 if none */

  /* marquee selection */
  BOOL bMarqueeSelect;      /* marquee selection/highlight underway */
  BOOL bScrolling;
  RECT marqueeRect;         /* absolute coordinates of marquee selection */
  RECT marqueeDrawRect;     /* relative coordinates for drawing marquee */
  POINT marqueeOrigin;      /* absolute coordinates of marquee click origin */

  /* focus drawing */
  BOOL bFocus;              /* control has focus */
  INT nFocusedItem;
  RECT rcFocus;             /* focus bounds */

  /* colors */
  HBRUSH hBkBrush;
  COLORREF clrBk;
  COLORREF clrText;
  COLORREF clrTextBk;
  BOOL bDefaultBkColor;

  /* font */
  HFONT hDefaultFont;
  HFONT hFont;
  INT ntmHeight;            /* Some cached metrics of the font used */
  INT ntmMaxCharWidth;      /* by the listview to draw items */
  INT nEllipsisWidth;

  /* mouse operation */
  BOOL bLButtonDown;
  BOOL bRButtonDown;
  BOOL bDragging;
  POINT ptClickPos;         /* point where the user clicked */
  INT nLButtonDownItem;     /* tracks item to reset multiselection on WM_LBUTTONUP */
  DWORD dwHoverTime;
  HCURSOR hHotCursor;

  /* keyboard operation */
  DWORD lastKeyPressTimestamp;
  WPARAM charCode;
  INT nSearchParamLength;
  WCHAR szSearchParam[ MAX_PATH ];

  /* painting */
  DWORD cditemmode;        /* Keep the custom draw flags for an item/row */
  BOOL bIsDrawing;         /* Drawing in progress */
  INT nMeasureItemHeight;  /* WM_MEASUREITEM result */
  BOOL bRedraw;            /* WM_SETREDRAW switch */

  /* misc */
  DWORD iVersion;          /* CCM_[G,S]ETVERSION */
} LISTVIEW_INFO;

/*
 * constants
 */
/* How many we debug buffer to allocate */
#define DEBUG_BUFFERS 20
/* The size of a single debug buffer */
#define DEBUG_BUFFER_SIZE 256

/* Internal interface to LISTVIEW_HScroll and LISTVIEW_VScroll */
#define SB_INTERNAL      -1

/* maximum size of a label */
#define DISP_TEXT_SIZE 260

/* padding for items in list and small icon display modes */
#define WIDTH_PADDING 12

/* padding for items in list, report and small icon display modes */
#define HEIGHT_PADDING 1

/* offset of items in report display mode */
#define REPORT_MARGINX 2

/* padding for icon in large icon display mode
 *   ICON_TOP_PADDING_NOTHITABLE - space between top of box and area
 *                                 that HITTEST will see.
 *   ICON_TOP_PADDING_HITABLE - spacing between above and icon.
 *   ICON_TOP_PADDING - sum of the two above.
 *   ICON_BOTTOM_PADDING - between bottom of icon and top of text
 *   LABEL_HOR_PADDING - between text and sides of box
 *   LABEL_VERT_PADDING - between bottom of text and end of box
 *
 *   ICON_LR_PADDING - additional width above icon size.
 *   ICON_LR_HALF - half of the above value
 */
#define ICON_TOP_PADDING_NOTHITABLE  2
#define ICON_TOP_PADDING_HITABLE     2
#define ICON_TOP_PADDING (ICON_TOP_PADDING_NOTHITABLE + ICON_TOP_PADDING_HITABLE)
#define ICON_BOTTOM_PADDING          4
#define LABEL_HOR_PADDING            5
#define LABEL_VERT_PADDING           7
#define ICON_LR_PADDING              16
#define ICON_LR_HALF                 (ICON_LR_PADDING/2)

/* default label width for items in list and small icon display modes */
#define DEFAULT_LABEL_WIDTH 40
/* maximum select rectangle width for empty text item in LV_VIEW_DETAILS */
#define MAX_EMPTYTEXT_SELECT_WIDTH 80

/* default column width for items in list display mode */
#define DEFAULT_COLUMN_WIDTH 128

/* Size of "line" scroll for V & H scrolls */
#define LISTVIEW_SCROLL_ICON_LINE_SIZE 37

/* Padding between image and label */
#define IMAGE_PADDING  2

/* Padding behind the label */
#define TRAILING_LABEL_PADDING  12
#define TRAILING_HEADER_PADDING  11

/* Border for the icon caption */
#define CAPTION_BORDER  2

/* Standard DrawText flags */
#define LV_ML_DT_FLAGS  (DT_TOP | DT_NOPREFIX | DT_EDITCONTROL | DT_CENTER | DT_WORDBREAK | DT_WORD_ELLIPSIS | DT_END_ELLIPSIS)
#define LV_FL_DT_FLAGS  (DT_TOP | DT_NOPREFIX | DT_EDITCONTROL | DT_CENTER | DT_WORDBREAK | DT_NOCLIP)
#define LV_SL_DT_FLAGS  (DT_VCENTER | DT_NOPREFIX | DT_EDITCONTROL | DT_SINGLELINE | DT_WORD_ELLIPSIS | DT_END_ELLIPSIS)

/* Image index from state */
#define STATEIMAGEINDEX(x) (((x) & LVIS_STATEIMAGEMASK) >> 12)

/* The time in milliseconds to reset the search in the list */
#define KEY_DELAY       450

/* Dump the LISTVIEW_INFO structure to the debug channel */
#define LISTVIEW_DUMP(iP) do { \
  TRACE("hwndSelf=%p, clrBk=0x%06x, clrText=0x%06x, clrTextBk=0x%06x, ItemHeight=%d, ItemWidth=%d, Style=0x%08x\n", \
        iP->hwndSelf, iP->clrBk, iP->clrText, iP->clrTextBk, \
        iP->nItemHeight, iP->nItemWidth, iP->dwStyle); \
  TRACE("hwndSelf=%p, himlNor=%p, himlSml=%p, himlState=%p, Focused=%d, Hot=%d, exStyle=0x%08x, Focus=%d\n", \
        iP->hwndSelf, iP->himlNormal, iP->himlSmall, iP->himlState, \
        iP->nFocusedItem, iP->nHotItem, iP->dwLvExStyle, iP->bFocus ); \
  TRACE("hwndSelf=%p, ntmH=%d, icSz.cx=%d, icSz.cy=%d, icSp.cx=%d, icSp.cy=%d, notifyFmt=%d\n", \
        iP->hwndSelf, iP->ntmHeight, iP->iconSize.cx, iP->iconSize.cy, \
        iP->iconSpacing.cx, iP->iconSpacing.cy, iP->notifyFormat); \
  TRACE("hwndSelf=%p, rcList=%s\n", iP->hwndSelf, wine_dbgstr_rect(&iP->rcList)); \
} while(0)

static const WCHAR themeClass[] = {'L','i','s','t','V','i','e','w',0};

/*
 * forward declarations
 */
static BOOL LISTVIEW_GetItemT(const LISTVIEW_INFO *, LPLVITEMW, BOOL);
static void LISTVIEW_GetItemBox(const LISTVIEW_INFO *, INT, LPRECT);
static void LISTVIEW_GetItemOrigin(const LISTVIEW_INFO *, INT, LPPOINT);
static BOOL LISTVIEW_GetItemPosition(const LISTVIEW_INFO *, INT, LPPOINT);
static BOOL LISTVIEW_GetItemRect(const LISTVIEW_INFO *, INT, LPRECT);
static void LISTVIEW_GetOrigin(const LISTVIEW_INFO *, LPPOINT);
static BOOL LISTVIEW_GetViewRect(const LISTVIEW_INFO *, LPRECT);
static void LISTVIEW_UpdateSize(LISTVIEW_INFO *);
static LRESULT LISTVIEW_Command(LISTVIEW_INFO *, WPARAM, LPARAM);
static INT LISTVIEW_GetStringWidthT(const LISTVIEW_INFO *, LPCWSTR, BOOL);
static BOOL LISTVIEW_KeySelection(LISTVIEW_INFO *, INT, BOOL);
static UINT LISTVIEW_GetItemState(const LISTVIEW_INFO *, INT, UINT);
static BOOL LISTVIEW_SetItemState(LISTVIEW_INFO *, INT, const LVITEMW *);
static LRESULT LISTVIEW_VScroll(LISTVIEW_INFO *, INT, INT);
static LRESULT LISTVIEW_HScroll(LISTVIEW_INFO *, INT, INT);
static BOOL LISTVIEW_EnsureVisible(LISTVIEW_INFO *, INT, BOOL);
static HIMAGELIST LISTVIEW_SetImageList(LISTVIEW_INFO *, INT, HIMAGELIST);
static INT LISTVIEW_HitTest(const LISTVIEW_INFO *, LPLVHITTESTINFO, BOOL, BOOL);
static BOOL LISTVIEW_EndEditLabelT(LISTVIEW_INFO *, BOOL, BOOL);
static BOOL LISTVIEW_Scroll(LISTVIEW_INFO *, INT, INT);

/******** Text handling functions *************************************/

/* A text pointer is either NULL, LPSTR_TEXTCALLBACK, or points to a
 * text string. The string may be ANSI or Unicode, in which case
 * the boolean isW tells us the type of the string.
 *
 * The name of the function tell what type of strings it expects:
 *   W: Unicode, T: ANSI/Unicode - function of isW
 */

static inline BOOL is_text(LPCWSTR text)
{
    return text != NULL && text != LPSTR_TEXTCALLBACKW;
}

static inline int textlenT(LPCWSTR text, BOOL isW)
{
    return !is_text(text) ? 0 :
           isW ? lstrlenW(text) : lstrlenA((LPCSTR)text);
}

static inline void textcpynT(LPWSTR dest, BOOL isDestW, LPCWSTR src, BOOL isSrcW, INT max)
{
    if (isDestW)
        if (isSrcW) lstrcpynW(dest, src, max);
        else MultiByteToWideChar(CP_ACP, 0, (LPCSTR)src, -1, dest, max);
    else
        if (isSrcW) WideCharToMultiByte(CP_ACP, 0, src, -1, (LPSTR)dest, max, NULL, NULL);
        else lstrcpynA((LPSTR)dest, (LPCSTR)src, max);
}

static inline LPWSTR textdupTtoW(LPCWSTR text, BOOL isW)
{
    LPWSTR wstr = (LPWSTR)text;

    if (!isW && is_text(text))
    {
        INT len = MultiByteToWideChar(CP_ACP, 0, (LPCSTR)text, -1, NULL, 0);
        wstr = Alloc(len * sizeof(WCHAR));
        if (wstr) MultiByteToWideChar(CP_ACP, 0, (LPCSTR)text, -1, wstr, len);
    }
    TRACE("   wstr=%s\n", text == LPSTR_TEXTCALLBACKW ?  "(callback)" : debugstr_w(wstr));
    return wstr;
}

static inline void textfreeT(LPWSTR wstr, BOOL isW)
{
    if (!isW && is_text(wstr)) Free (wstr);
}

/*
 * dest is a pointer to a Unicode string
 * src is a pointer to a string (Unicode if isW, ANSI if !isW)
 */
static BOOL textsetptrT(LPWSTR *dest, LPCWSTR src, BOOL isW)
{
    BOOL bResult = TRUE;
    
    if (src == LPSTR_TEXTCALLBACKW)
    {
        if (is_text(*dest)) Free(*dest);
        *dest = LPSTR_TEXTCALLBACKW;
    }
    else
    {
        LPWSTR pszText = textdupTtoW(src, isW);
        if (*dest == LPSTR_TEXTCALLBACKW) *dest = NULL;
        bResult = Str_SetPtrW(dest, pszText);
        textfreeT(pszText, isW);
    }
    return bResult;
}

/*
 * compares a Unicode to a Unicode/ANSI text string
 */
static inline int textcmpWT(LPCWSTR aw, LPCWSTR bt, BOOL isW)
{
    if (!aw) return bt ? -1 : 0;
    if (!bt) return 1;
    if (aw == LPSTR_TEXTCALLBACKW)
        return bt == LPSTR_TEXTCALLBACKW ? 1 : -1;
    if (bt != LPSTR_TEXTCALLBACKW)
    {
        LPWSTR bw = textdupTtoW(bt, isW);
        int r = bw ? lstrcmpW(aw, bw) : 1;
        textfreeT(bw, isW);
        return r;
    }       
            
    return 1;
}
    
static inline int lstrncmpiW(LPCWSTR s1, LPCWSTR s2, int n)
{
    int res;

    n = min(min(n, lstrlenW(s1)), lstrlenW(s2));
    res = CompareStringW(LOCALE_USER_DEFAULT, NORM_IGNORECASE, s1, n, s2, n);
    return res ? res - sizeof(WCHAR) : res;
}

/******** Debugging functions *****************************************/

static inline LPCSTR debugtext_t(LPCWSTR text, BOOL isW)
{
    if (text == LPSTR_TEXTCALLBACKW) return "(callback)";
    return isW ? debugstr_w(text) : debugstr_a((LPCSTR)text);
}

static inline LPCSTR debugtext_tn(LPCWSTR text, BOOL isW, INT n)
{
    if (text == LPSTR_TEXTCALLBACKW) return "(callback)";
    n = min(textlenT(text, isW), n);
    return isW ? debugstr_wn(text, n) : debugstr_an((LPCSTR)text, n);
}

static char* debug_getbuf(void)
{
    static int index = 0;
    static char buffers[DEBUG_BUFFERS][DEBUG_BUFFER_SIZE];
    return buffers[index++ % DEBUG_BUFFERS];
}

static inline const char* debugrange(const RANGE *lprng)
{
    if (!lprng) return "(null)";
    return wine_dbg_sprintf("[%d, %d]", lprng->lower, lprng->upper);
}

static const char* debugscrollinfo(const SCROLLINFO *pScrollInfo)
{
    char* buf = debug_getbuf(), *text = buf;
    int len, size = DEBUG_BUFFER_SIZE;

    if (pScrollInfo == NULL) return "(null)";
    len = snprintf(buf, size, "{cbSize=%d, ", pScrollInfo->cbSize);
    if (len == -1) goto end; buf += len; size -= len;
    if (pScrollInfo->fMask & SIF_RANGE)
        len = snprintf(buf, size, "nMin=%d, nMax=%d, ", pScrollInfo->nMin, pScrollInfo->nMax);
    else len = 0;
    if (len == -1) goto end; buf += len; size -= len;
    if (pScrollInfo->fMask & SIF_PAGE)
        len = snprintf(buf, size, "nPage=%u, ", pScrollInfo->nPage);
    else len = 0;
    if (len == -1) goto end; buf += len; size -= len;
    if (pScrollInfo->fMask & SIF_POS)
        len = snprintf(buf, size, "nPos=%d, ", pScrollInfo->nPos);
    else len = 0;
    if (len == -1) goto end; buf += len; size -= len;
    if (pScrollInfo->fMask & SIF_TRACKPOS)
        len = snprintf(buf, size, "nTrackPos=%d, ", pScrollInfo->nTrackPos);
    else len = 0;
    if (len == -1) goto end; buf += len;
    goto undo;
end:
    buf = text + strlen(text);
undo:
    if (buf - text > 2) { buf[-2] = '}'; buf[-1] = 0; }
    return text;
} 

static const char* debugnmlistview(const NMLISTVIEW *plvnm)
{
    if (!plvnm) return "(null)";
    return wine_dbg_sprintf("iItem=%d, iSubItem=%d, uNewState=0x%x,"
                 " uOldState=0x%x, uChanged=0x%x, ptAction=%s, lParam=%ld",
                 plvnm->iItem, plvnm->iSubItem, plvnm->uNewState, plvnm->uOldState,
                 plvnm->uChanged, wine_dbgstr_point(&plvnm->ptAction), plvnm->lParam);
}

static const char* debuglvitem_t(const LVITEMW *lpLVItem, BOOL isW)
{
    char* buf = debug_getbuf(), *text = buf;
    int len, size = DEBUG_BUFFER_SIZE;
    
    if (lpLVItem == NULL) return "(null)";
    len = snprintf(buf, size, "{iItem=%d, iSubItem=%d, ", lpLVItem->iItem, lpLVItem->iSubItem);
    if (len == -1) goto end; buf += len; size -= len;
    if (lpLVItem->mask & LVIF_STATE)
        len = snprintf(buf, size, "state=%x, stateMask=%x, ", lpLVItem->state, lpLVItem->stateMask);
    else len = 0;
    if (len == -1) goto end; buf += len; size -= len;
    if (lpLVItem->mask & LVIF_TEXT)
        len = snprintf(buf, size, "pszText=%s, cchTextMax=%d, ", debugtext_tn(lpLVItem->pszText, isW, 80), lpLVItem->cchTextMax);
    else len = 0;
    if (len == -1) goto end; buf += len; size -= len;
    if (lpLVItem->mask & LVIF_IMAGE)
        len = snprintf(buf, size, "iImage=%d, ", lpLVItem->iImage);
    else len = 0;
    if (len == -1) goto end; buf += len; size -= len;
    if (lpLVItem->mask & LVIF_PARAM)
        len = snprintf(buf, size, "lParam=%lx, ", lpLVItem->lParam);
    else len = 0;
    if (len == -1) goto end; buf += len; size -= len;
    if (lpLVItem->mask & LVIF_INDENT)
        len = snprintf(buf, size, "iIndent=%d, ", lpLVItem->iIndent);
    else len = 0;
    if (len == -1) goto end; buf += len;
    goto undo;
end:
    buf = text + strlen(text);
undo:
    if (buf - text > 2) { buf[-2] = '}'; buf[-1] = 0; }
    return text;
}

static const char* debuglvcolumn_t(const LVCOLUMNW *lpColumn, BOOL isW)
{
    char* buf = debug_getbuf(), *text = buf;
    int len, size = DEBUG_BUFFER_SIZE;
    
    if (lpColumn == NULL) return "(null)";
    len = snprintf(buf, size, "{");
    if (len == -1) goto end; buf += len; size -= len;
    if (lpColumn->mask & LVCF_SUBITEM)
        len = snprintf(buf, size, "iSubItem=%d, ",  lpColumn->iSubItem);
    else len = 0;
    if (len == -1) goto end; buf += len; size -= len;
    if (lpColumn->mask & LVCF_FMT)
        len = snprintf(buf, size, "fmt=%x, ", lpColumn->fmt);
    else len = 0;
    if (len == -1) goto end; buf += len; size -= len;
    if (lpColumn->mask & LVCF_WIDTH)
        len = snprintf(buf, size, "cx=%d, ", lpColumn->cx);
    else len = 0;
    if (len == -1) goto end; buf += len; size -= len;
    if (lpColumn->mask & LVCF_TEXT)
        len = snprintf(buf, size, "pszText=%s, cchTextMax=%d, ", debugtext_tn(lpColumn->pszText, isW, 80), lpColumn->cchTextMax);
    else len = 0;
    if (len == -1) goto end; buf += len; size -= len;
    if (lpColumn->mask & LVCF_IMAGE)
        len = snprintf(buf, size, "iImage=%d, ", lpColumn->iImage);
    else len = 0;
    if (len == -1) goto end; buf += len; size -= len;
    if (lpColumn->mask & LVCF_ORDER)
        len = snprintf(buf, size, "iOrder=%d, ", lpColumn->iOrder);
    else len = 0;
    if (len == -1) goto end; buf += len;
    goto undo;
end:
    buf = text + strlen(text);
undo:
    if (buf - text > 2) { buf[-2] = '}'; buf[-1] = 0; }
    return text;
}

static const char* debuglvhittestinfo(const LVHITTESTINFO *lpht)
{
    if (!lpht) return "(null)";

    return wine_dbg_sprintf("{pt=%s, flags=0x%x, iItem=%d, iSubItem=%d}",
                 wine_dbgstr_point(&lpht->pt), lpht->flags, lpht->iItem, lpht->iSubItem);
}

/* Return the corresponding text for a given scroll value */
static inline LPCSTR debugscrollcode(int nScrollCode)
{
  switch(nScrollCode)
  {
  case SB_LINELEFT: return "SB_LINELEFT";
  case SB_LINERIGHT: return "SB_LINERIGHT";
  case SB_PAGELEFT: return "SB_PAGELEFT";
  case SB_PAGERIGHT: return "SB_PAGERIGHT";
  case SB_THUMBPOSITION: return "SB_THUMBPOSITION";
  case SB_THUMBTRACK: return "SB_THUMBTRACK";
  case SB_ENDSCROLL: return "SB_ENDSCROLL";
  case SB_INTERNAL: return "SB_INTERNAL";
  default: return "unknown";
  }
}


/******** Notification functions ************************************/

static int get_ansi_notification(UINT unicodeNotificationCode)
{
    switch (unicodeNotificationCode)
    {
    case LVN_BEGINLABELEDITA:
    case LVN_BEGINLABELEDITW: return LVN_BEGINLABELEDITA;
    case LVN_ENDLABELEDITA:
    case LVN_ENDLABELEDITW: return LVN_ENDLABELEDITA;
    case LVN_GETDISPINFOA:
    case LVN_GETDISPINFOW: return LVN_GETDISPINFOA;
    case LVN_SETDISPINFOA:
    case LVN_SETDISPINFOW: return LVN_SETDISPINFOA;
    case LVN_ODFINDITEMA:
    case LVN_ODFINDITEMW: return LVN_ODFINDITEMA;
    case LVN_GETINFOTIPA:
    case LVN_GETINFOTIPW: return LVN_GETINFOTIPA;
    /* header forwards */
    case HDN_TRACKA:
    case HDN_TRACKW: return HDN_TRACKA;
    case HDN_ENDTRACKA:
    case HDN_ENDTRACKW: return HDN_ENDTRACKA;
    case HDN_BEGINDRAG: return HDN_BEGINDRAG;
    case HDN_ENDDRAG: return HDN_ENDDRAG;
    case HDN_ITEMCHANGINGA:
    case HDN_ITEMCHANGINGW: return HDN_ITEMCHANGINGA;
    case HDN_ITEMCHANGEDA:
    case HDN_ITEMCHANGEDW: return HDN_ITEMCHANGEDA;
    case HDN_ITEMCLICKA:
    case HDN_ITEMCLICKW: return HDN_ITEMCLICKA;
    case HDN_DIVIDERDBLCLICKA:
    case HDN_DIVIDERDBLCLICKW: return HDN_DIVIDERDBLCLICKA;
    default: break;
    }
    FIXME("unknown notification %x\n", unicodeNotificationCode);
    return unicodeNotificationCode;
}

/* forwards header notifications to listview parent */
static LRESULT notify_forward_header(const LISTVIEW_INFO *infoPtr, const NMHEADERW *lpnmh)
{
    NMHEADERA nmhA;
    HDITEMA hditema;
    HD_TEXTFILTERA textfilter;
    LPSTR text = NULL, filter = NULL;
    LRESULT ret;

    /* on unicode format exit earlier */
    if (infoPtr->notifyFormat == NFR_UNICODE)
        return SendMessageW(infoPtr->hwndNotify, WM_NOTIFY, lpnmh->hdr.idFrom,
                            (LPARAM)lpnmh);

    /* header always supplies unicode notifications,
       all we have to do is to convert strings to ANSI */
    nmhA = *(const NMHEADERA*)lpnmh;
    if (lpnmh->pitem)
    {
        hditema = *(HDITEMA*)lpnmh->pitem;
        nmhA.pitem = &hditema;
        /* convert item text */
        if (lpnmh->pitem->mask & HDI_TEXT)
        {
            hditema.pszText = NULL;
            Str_SetPtrWtoA(&hditema.pszText, lpnmh->pitem->pszText);
            text = hditema.pszText;
        }
        /* convert filter text */
        if ((lpnmh->pitem->mask & HDI_FILTER) && (lpnmh->pitem->type == HDFT_ISSTRING) &&
             lpnmh->pitem->pvFilter)
        {
            hditema.pvFilter = &textfilter;
            textfilter = *(HD_TEXTFILTERA*)(lpnmh->pitem->pvFilter);
            textfilter.pszText = NULL;
            Str_SetPtrWtoA(&textfilter.pszText, ((HD_TEXTFILTERW*)lpnmh->pitem->pvFilter)->pszText);
            filter = textfilter.pszText;
        }
    }
    nmhA.hdr.code = get_ansi_notification(lpnmh->hdr.code);

    ret = SendMessageW(infoPtr->hwndNotify, WM_NOTIFY, nmhA.hdr.idFrom,
                       (LPARAM)&nmhA);

    /* cleanup */
    Free(text);
    Free(filter);

    return ret;
}

static LRESULT notify_hdr(const LISTVIEW_INFO *infoPtr, INT code, LPNMHDR pnmh)
{
    LRESULT result;
    
    TRACE("(code=%d)\n", code);

    pnmh->hwndFrom = infoPtr->hwndSelf;
    pnmh->idFrom = GetWindowLongPtrW(infoPtr->hwndSelf, GWLP_ID);
    pnmh->code = code;
    result = SendMessageW(infoPtr->hwndNotify, WM_NOTIFY, pnmh->idFrom, (LPARAM)pnmh);

    TRACE("  <= %ld\n", result);

    return result;
}

static inline BOOL notify(const LISTVIEW_INFO *infoPtr, INT code)
{
    NMHDR nmh;
    HWND hwnd = infoPtr->hwndSelf;
    notify_hdr(infoPtr, code, &nmh);
    return IsWindow(hwnd);
}

static inline void notify_itemactivate(const LISTVIEW_INFO *infoPtr, const LVHITTESTINFO *htInfo)
{
    NMITEMACTIVATE nmia;
    LVITEMW item;

    if (htInfo) {
      nmia.uNewState = 0;
      nmia.uOldState = 0;
      nmia.uChanged  = 0;
      nmia.uKeyFlags = 0;
      
      item.mask = LVIF_PARAM|LVIF_STATE;
      item.iItem = htInfo->iItem;
      item.iSubItem = 0;
      item.stateMask = (UINT)-1;
      if (LISTVIEW_GetItemT(infoPtr, &item, TRUE)) {
          nmia.lParam = item.lParam;
          nmia.uOldState = item.state;
          nmia.uNewState = item.state | LVIS_ACTIVATING;
          nmia.uChanged  = LVIF_STATE;
      }
      
      nmia.iItem = htInfo->iItem;
      nmia.iSubItem = htInfo->iSubItem;
      nmia.ptAction = htInfo->pt;     
      
      if (GetKeyState(VK_SHIFT) & 0x8000) nmia.uKeyFlags |= LVKF_SHIFT;
      if (GetKeyState(VK_CONTROL) & 0x8000) nmia.uKeyFlags |= LVKF_CONTROL;
      if (GetKeyState(VK_MENU) & 0x8000) nmia.uKeyFlags |= LVKF_ALT;
    }
    notify_hdr(infoPtr, LVN_ITEMACTIVATE, (LPNMHDR)&nmia);
}

static inline LRESULT notify_listview(const LISTVIEW_INFO *infoPtr, INT code, LPNMLISTVIEW plvnm)
{
    TRACE("(code=%d, plvnm=%s)\n", code, debugnmlistview(plvnm));
    return notify_hdr(infoPtr, code, (LPNMHDR)plvnm);
}

static BOOL notify_click(const LISTVIEW_INFO *infoPtr, INT code, const LVHITTESTINFO *lvht)
{
    NMITEMACTIVATE nmia;
    LVITEMW item;
    HWND hwnd = infoPtr->hwndSelf;

    TRACE("code=%d, lvht=%s\n", code, debuglvhittestinfo(lvht)); 
    ZeroMemory(&nmia, sizeof(nmia));
    nmia.iItem = lvht->iItem;
    nmia.iSubItem = lvht->iSubItem;
    nmia.ptAction = lvht->pt;
    item.mask = LVIF_PARAM;
    item.iItem = lvht->iItem;
    item.iSubItem = 0;
    if (LISTVIEW_GetItemT(infoPtr, &item, TRUE)) nmia.lParam = item.lParam;
    notify_hdr(infoPtr, code, (LPNMHDR)&nmia);
    return IsWindow(hwnd);
}

static BOOL notify_deleteitem(const LISTVIEW_INFO *infoPtr, INT nItem)
{
    NMLISTVIEW nmlv;
    LVITEMW item;
    HWND hwnd = infoPtr->hwndSelf;

    ZeroMemory(&nmlv, sizeof (NMLISTVIEW));
    nmlv.iItem = nItem;
    item.mask = LVIF_PARAM;
    item.iItem = nItem;
    item.iSubItem = 0;
    if (LISTVIEW_GetItemT(infoPtr, &item, TRUE)) nmlv.lParam = item.lParam;
    notify_listview(infoPtr, LVN_DELETEITEM, &nmlv);
    return IsWindow(hwnd);
}

/*
  Send notification. depends on dispinfoW having same
  structure as dispinfoA.
  infoPtr : listview struct
  code : *Unicode* notification code
  pdi : dispinfo structure (can be unicode or ansi)
  isW : TRUE if dispinfo is Unicode
*/
static BOOL notify_dispinfoT(const LISTVIEW_INFO *infoPtr, UINT code, LPNMLVDISPINFOW pdi, BOOL isW)
{
    INT length = 0, ret_length;
    LPWSTR buffer = NULL, ret_text;
    BOOL return_ansi = FALSE;
    BOOL return_unicode = FALSE;
    BOOL ret;

    if ((pdi->item.mask & LVIF_TEXT) && is_text(pdi->item.pszText))
    {
        return_unicode = ( isW && infoPtr->notifyFormat == NFR_ANSI);
        return_ansi    = (!isW && infoPtr->notifyFormat == NFR_UNICODE);
    }

    ret_length = pdi->item.cchTextMax;
    ret_text = pdi->item.pszText;

    if (return_unicode || return_ansi)
    {
        if (code != LVN_GETDISPINFOW)
        {
            length = return_ansi ?
                MultiByteToWideChar(CP_ACP, 0, (LPCSTR)pdi->item.pszText, -1, NULL, 0):
                WideCharToMultiByte(CP_ACP, 0, pdi->item.pszText, -1, NULL, 0, NULL, NULL);
        }
        else
        {
            length = pdi->item.cchTextMax;
            *pdi->item.pszText = 0; /* make sure we don't process garbage */
        }

        buffer = Alloc( (return_ansi ? sizeof(WCHAR) : sizeof(CHAR)) * length);
        if (!buffer) return FALSE;

        if (return_ansi)
            MultiByteToWideChar(CP_ACP, 0, (LPCSTR)pdi->item.pszText, -1,
                                buffer, length);
        else
            WideCharToMultiByte(CP_ACP, 0, pdi->item.pszText, -1, (LPSTR) buffer,
                                length, NULL, NULL);

        pdi->item.pszText = buffer;
        pdi->item.cchTextMax = length;
    }

    if (infoPtr->notifyFormat == NFR_ANSI)
        code = get_ansi_notification(code);

    TRACE(" pdi->item=%s\n", debuglvitem_t(&pdi->item, infoPtr->notifyFormat != NFR_ANSI));
    ret = notify_hdr(infoPtr, code, &pdi->hdr);
    TRACE(" resulting code=%d\n", pdi->hdr.code);

    if (return_ansi || return_unicode)
    {
        if (return_ansi && (pdi->hdr.code == LVN_GETDISPINFOA))
        {
            strcpy((char*)ret_text, (char*)pdi->item.pszText);
        }
        else if (return_unicode && (pdi->hdr.code == LVN_GETDISPINFOW))
        {
            strcpyW(ret_text, pdi->item.pszText);
        }
        else if (return_ansi) /* note : pointer can be changed by app ! */
        {
            WideCharToMultiByte(CP_ACP, 0, pdi->item.pszText, -1, (LPSTR) ret_text,
                ret_length, NULL, NULL);
        }
        else
            MultiByteToWideChar(CP_ACP, 0, (LPSTR) pdi->item.pszText, -1,
                ret_text, ret_length);

        pdi->item.pszText = ret_text; /* restores our buffer */
        pdi->item.cchTextMax = ret_length;

        Free(buffer);
        return ret;
    }

    /* if dipsinfo holder changed notification code then convert */
    if (!isW && (pdi->hdr.code == LVN_GETDISPINFOW) && (pdi->item.mask & LVIF_TEXT))
    {
        length = WideCharToMultiByte(CP_ACP, 0, pdi->item.pszText, -1, NULL, 0, NULL, NULL);

        buffer = Alloc(length * sizeof(CHAR));
        if (!buffer) return FALSE;

        WideCharToMultiByte(CP_ACP, 0, pdi->item.pszText, -1, (LPSTR) buffer,
                ret_length, NULL, NULL);

        strcpy((LPSTR)pdi->item.pszText, (LPSTR)buffer);
        Free(buffer);
    }

    return ret;
}

static void customdraw_fill(NMLVCUSTOMDRAW *lpnmlvcd, const LISTVIEW_INFO *infoPtr, HDC hdc,
                            const RECT *rcBounds, const LVITEMW *lplvItem)
{
    ZeroMemory(lpnmlvcd, sizeof(NMLVCUSTOMDRAW));
    lpnmlvcd->nmcd.hdc = hdc;
    lpnmlvcd->nmcd.rc = *rcBounds;
    lpnmlvcd->clrTextBk = infoPtr->clrTextBk;
    lpnmlvcd->clrText   = infoPtr->clrText;
    if (!lplvItem) return;
    lpnmlvcd->nmcd.dwItemSpec = lplvItem->iItem + 1;
    lpnmlvcd->iSubItem = lplvItem->iSubItem;
    if (lplvItem->state & LVIS_SELECTED) lpnmlvcd->nmcd.uItemState |= CDIS_SELECTED;
    if (lplvItem->state & LVIS_FOCUSED) lpnmlvcd->nmcd.uItemState |= CDIS_FOCUS;
    if (lplvItem->iItem == infoPtr->nHotItem) lpnmlvcd->nmcd.uItemState |= CDIS_HOT;
    lpnmlvcd->nmcd.lItemlParam = lplvItem->lParam;
}

static inline DWORD notify_customdraw (const LISTVIEW_INFO *infoPtr, DWORD dwDrawStage, NMLVCUSTOMDRAW *lpnmlvcd)
{
    BOOL isForItem = (lpnmlvcd->nmcd.dwItemSpec != 0);
    DWORD result;

    lpnmlvcd->nmcd.dwDrawStage = dwDrawStage;
    if (isForItem) lpnmlvcd->nmcd.dwDrawStage |= CDDS_ITEM; 
    if (lpnmlvcd->iSubItem) lpnmlvcd->nmcd.dwDrawStage |= CDDS_SUBITEM;
    if (isForItem) lpnmlvcd->nmcd.dwItemSpec--;
    result = notify_hdr(infoPtr, NM_CUSTOMDRAW, &lpnmlvcd->nmcd.hdr);
    if (isForItem) lpnmlvcd->nmcd.dwItemSpec++;
    return result;
}

static void prepaint_setup (const LISTVIEW_INFO *infoPtr, HDC hdc, NMLVCUSTOMDRAW *lpnmlvcd, BOOL SubItem)
{
    if (lpnmlvcd->clrTextBk == CLR_DEFAULT)
        lpnmlvcd->clrTextBk = comctl32_color.clrWindow;
    if (lpnmlvcd->clrText == CLR_DEFAULT)
        lpnmlvcd->clrText = comctl32_color.clrWindowText;

    /* apparently, for selected items, we have to override the returned values */
    if (!SubItem)
    {
        if (lpnmlvcd->nmcd.uItemState & CDIS_SELECTED)
        {
            if (infoPtr->bFocus)
            {
                lpnmlvcd->clrTextBk = comctl32_color.clrHighlight;
                lpnmlvcd->clrText   = comctl32_color.clrHighlightText;
            }
            else if (infoPtr->dwStyle & LVS_SHOWSELALWAYS)
            {
                lpnmlvcd->clrTextBk = comctl32_color.clr3dFace;
                lpnmlvcd->clrText   = comctl32_color.clrBtnText;
            }
        }
    }

    /* Set the text attributes */
    if (lpnmlvcd->clrTextBk != CLR_NONE)
    {
        SetBkMode(hdc, OPAQUE);
        SetBkColor(hdc,lpnmlvcd->clrTextBk);
    }
    else
        SetBkMode(hdc, TRANSPARENT);
    SetTextColor(hdc, lpnmlvcd->clrText);
}

static inline DWORD notify_postpaint (const LISTVIEW_INFO *infoPtr, NMLVCUSTOMDRAW *lpnmlvcd)
{
    return notify_customdraw(infoPtr, CDDS_POSTPAINT, lpnmlvcd);
}

/* returns TRUE when repaint needed, FALSE otherwise */
static BOOL notify_measureitem(LISTVIEW_INFO *infoPtr)
{
    MEASUREITEMSTRUCT mis;
    mis.CtlType = ODT_LISTVIEW;
    mis.CtlID = GetWindowLongPtrW(infoPtr->hwndSelf, GWLP_ID);
    mis.itemID = -1;
    mis.itemWidth = 0;
    mis.itemData = 0;
    mis.itemHeight= infoPtr->nItemHeight;
    SendMessageW(infoPtr->hwndNotify, WM_MEASUREITEM, mis.CtlID, (LPARAM)&mis);
    if (infoPtr->nItemHeight != max(mis.itemHeight, 1))
    {
        infoPtr->nMeasureItemHeight = infoPtr->nItemHeight = max(mis.itemHeight, 1);
        return TRUE;
    }
    return FALSE;
}

/******** Item iterator functions **********************************/

static RANGES ranges_create(int count);
static void ranges_destroy(RANGES ranges);
static BOOL ranges_add(RANGES ranges, RANGE range);
static BOOL ranges_del(RANGES ranges, RANGE range);
static void ranges_dump(RANGES ranges);

static inline BOOL ranges_additem(RANGES ranges, INT nItem)
{
    RANGE range = { nItem, nItem + 1 };

    return ranges_add(ranges, range);
}

static inline BOOL ranges_delitem(RANGES ranges, INT nItem)
{
    RANGE range = { nItem, nItem + 1 };

    return ranges_del(ranges, range);
}

/***
 * ITERATOR DOCUMENTATION
 *
 * The iterator functions allow for easy, and convenient iteration
 * over items of interest in the list. Typically, you create a
 * iterator, use it, and destroy it, as such:
 *   ITERATOR i;
 *
 *   iterator_xxxitems(&i, ...);
 *   while (iterator_{prev,next}(&i)
 *   {
 *       //code which uses i.nItem
 *   }
 *   iterator_destroy(&i);
 *
 *   where xxx is either: framed, or visible.
 * Note that it is important that the code destroys the iterator
 * after it's done with it, as the creation of the iterator may
 * allocate memory, which thus needs to be freed.
 * 
 * You can iterate both forwards, and backwards through the list,
 * by using iterator_next or iterator_prev respectively.
 * 
 * Lower numbered items are draw on top of higher number items in
 * LVS_ICON, and LVS_SMALLICON (which are the only modes where
 * items may overlap). So, to test items, you should use
 *    iterator_next
 * which lists the items top to bottom (in Z-order).
 * For drawing items, you should use
 *    iterator_prev
 * which lists the items bottom to top (in Z-order).
 * If you keep iterating over the items after the end-of-items
 * marker (-1) is returned, the iterator will start from the
 * beginning. Typically, you don't need to test for -1,
 * because iterator_{next,prev} will return TRUE if more items
 * are to be iterated over, or FALSE otherwise.
 *
 * Note: the iterator is defined to be bidirectional. That is,
 *       any number of prev followed by any number of next, or
 *       five versa, should leave the iterator at the same item:
 *           prev * n, next * n = next * n, prev * n
 *
 * The iterator has a notion of an out-of-order, special item,
 * which sits at the start of the list. This is used in
 * LVS_ICON, and LVS_SMALLICON mode to handle the focused item,
 * which needs to be first, as it may overlap other items.
 *           
 * The code is a bit messy because we have:
 *   - a special item to deal with
 *   - simple range, or composite range
 *   - empty range.
 * If you find bugs, or want to add features, please make sure you
 * always check/modify *both* iterator_prev, and iterator_next.
 */

/****
 * This function iterates through the items in increasing order,
 * but prefixed by the special item, then -1. That is:
 *    special, 1, 2, 3, ..., n, -1.
 * Each item is listed only once.
 */
static inline BOOL iterator_next(ITERATOR* i)
{
    if (i->nItem == -1)
    {
        i->nItem = i->nSpecial;
        if (i->nItem != -1) return TRUE;
    }
    if (i->nItem == i->nSpecial)
    {
        if (i->ranges) i->index = 0;
        goto pickarange;
    }

    i->nItem++;
testitem:
    if (i->nItem == i->nSpecial) i->nItem++;
    if (i->nItem < i->range.upper) return TRUE;

pickarange:
    if (i->ranges)
    {
        if (i->index < DPA_GetPtrCount(i->ranges->hdpa))
            i->range = *(RANGE*)DPA_GetPtr(i->ranges->hdpa, i->index++);
        else goto end;
    }
    else if (i->nItem >= i->range.upper) goto end;

    i->nItem = i->range.lower;
    if (i->nItem >= 0) goto testitem;
end:
    i->nItem = -1;
    return FALSE;
}

/****
 * This function iterates through the items in decreasing order,
 * followed by the special item, then -1. That is:
 *    n, n-1, ..., 3, 2, 1, special, -1.
 * Each item is listed only once.
 */
static inline BOOL iterator_prev(ITERATOR* i)
{
    BOOL start = FALSE;

    if (i->nItem == -1)
    {
        start = TRUE;
        if (i->ranges) i->index = DPA_GetPtrCount(i->ranges->hdpa);
        goto pickarange;
    }
    if (i->nItem == i->nSpecial)
    {
        i->nItem = -1;
        return FALSE;
    }

testitem:
    i->nItem--;
    if (i->nItem == i->nSpecial) i->nItem--;
    if (i->nItem >= i->range.lower) return TRUE;

pickarange:
    if (i->ranges)
    {
        if (i->index > 0)
            i->range = *(RANGE*)DPA_GetPtr(i->ranges->hdpa, --i->index);
        else goto end;
    }
    else if (!start && i->nItem < i->range.lower) goto end;

    i->nItem = i->range.upper;
    if (i->nItem > 0) goto testitem;
end:
    return (i->nItem = i->nSpecial) != -1;
}

static RANGE iterator_range(const ITERATOR *i)
{
    RANGE range;

    if (!i->ranges) return i->range;

    if (DPA_GetPtrCount(i->ranges->hdpa) > 0)
    {
        range.lower = (*(RANGE*)DPA_GetPtr(i->ranges->hdpa, 0)).lower;
        range.upper = (*(RANGE*)DPA_GetPtr(i->ranges->hdpa, DPA_GetPtrCount(i->ranges->hdpa) - 1)).upper;
    }
    else range.lower = range.upper = 0;

    return range;
}

/***
 * Releases resources associated with this ierator.
 */
static inline void iterator_destroy(const ITERATOR *i)
{
    ranges_destroy(i->ranges);
}

/***
 * Create an empty iterator.
 */
static inline BOOL iterator_empty(ITERATOR* i)
{
    ZeroMemory(i, sizeof(*i));
    i->nItem = i->nSpecial = i->range.lower = i->range.upper = -1;
    return TRUE;
}

/***
 * Create an iterator over a range.
 */
static inline BOOL iterator_rangeitems(ITERATOR* i, RANGE range)
{
    iterator_empty(i);
    i->range = range;
    return TRUE;
}

/***
 * Create an iterator over a bunch of ranges.
 * Please note that the iterator will take ownership of the ranges,
 * and will free them upon destruction.
 */
static inline BOOL iterator_rangesitems(ITERATOR* i, RANGES ranges)
{
    iterator_empty(i);
    i->ranges = ranges;
    return TRUE;
}

/***
 * Creates an iterator over the items which intersect frame.
 * Uses absolute coordinates rather than compensating for the current offset.
 */
static BOOL iterator_frameditems_absolute(ITERATOR* i, const LISTVIEW_INFO* infoPtr, const RECT *frame)
{
    RECT rcItem, rcTemp;
    
    /* in case we fail, we want to return an empty iterator */
    if (!iterator_empty(i)) return FALSE;

    TRACE("(frame=%s)\n", wine_dbgstr_rect(frame));

    if (infoPtr->uView == LV_VIEW_ICON || infoPtr->uView == LV_VIEW_SMALLICON)
    {
        INT nItem;
        
        if (infoPtr->uView == LV_VIEW_ICON && infoPtr->nFocusedItem != -1)
        {
            LISTVIEW_GetItemBox(infoPtr, infoPtr->nFocusedItem, &rcItem);
            if (IntersectRect(&rcTemp, &rcItem, frame))
                i->nSpecial = infoPtr->nFocusedItem;
        }
        if (!(iterator_rangesitems(i, ranges_create(50)))) return FALSE;
        /* to do better here, we need to have PosX, and PosY sorted */
        TRACE("building icon ranges:\n");
        for (nItem = 0; nItem < infoPtr->nItemCount; nItem++)
        {
            rcItem.left = (LONG_PTR)DPA_GetPtr(infoPtr->hdpaPosX, nItem);
            rcItem.top = (LONG_PTR)DPA_GetPtr(infoPtr->hdpaPosY, nItem);
            rcItem.right = rcItem.left + infoPtr->nItemWidth;
            rcItem.bottom = rcItem.top + infoPtr->nItemHeight;
            if (IntersectRect(&rcTemp, &rcItem, frame))
                ranges_additem(i->ranges, nItem);
        }
        return TRUE;
    }
    else if (infoPtr->uView == LV_VIEW_DETAILS)
    {
        RANGE range;
        
        if (frame->left >= infoPtr->nItemWidth) return TRUE;
        if (frame->top >= infoPtr->nItemHeight * infoPtr->nItemCount) return TRUE;
        
        range.lower = max(frame->top / infoPtr->nItemHeight, 0);
        range.upper = min((frame->bottom - 1) / infoPtr->nItemHeight, infoPtr->nItemCount - 1) + 1;
        if (range.upper <= range.lower) return TRUE;
        if (!iterator_rangeitems(i, range)) return FALSE;
        TRACE("    report=%s\n", debugrange(&i->range));
    }
    else
    {
        INT nPerCol = max((infoPtr->rcList.bottom - infoPtr->rcList.top) / infoPtr->nItemHeight, 1);
        INT nFirstRow = max(frame->top / infoPtr->nItemHeight, 0);
        INT nLastRow = min((frame->bottom - 1) / infoPtr->nItemHeight, nPerCol - 1);
        INT nFirstCol;
        INT nLastCol;
        INT lower;
        RANGE item_range;
        INT nCol;

        if (infoPtr->nItemWidth)
        {
            nFirstCol = max(frame->left / infoPtr->nItemWidth, 0);
            nLastCol  = min((frame->right - 1) / infoPtr->nItemWidth, (infoPtr->nItemCount + nPerCol - 1) / nPerCol);
        }
        else
        {
            nFirstCol = max(frame->left, 0);
            nLastCol  = min(frame->right - 1, (infoPtr->nItemCount + nPerCol - 1) / nPerCol);
        }

        lower = nFirstCol * nPerCol + nFirstRow;

        TRACE("nPerCol=%d, nFirstRow=%d, nLastRow=%d, nFirstCol=%d, nLastCol=%d, lower=%d\n",
              nPerCol, nFirstRow, nLastRow, nFirstCol, nLastCol, lower);
        
        if (nLastCol < nFirstCol || nLastRow < nFirstRow) return TRUE;

        if (!(iterator_rangesitems(i, ranges_create(nLastCol - nFirstCol + 1)))) return FALSE;
        TRACE("building list ranges:\n");
        for (nCol = nFirstCol; nCol <= nLastCol; nCol++)
        {
            item_range.lower = nCol * nPerCol + nFirstRow;
            if(item_range.lower >= infoPtr->nItemCount) break;
            item_range.upper = min(nCol * nPerCol + nLastRow + 1, infoPtr->nItemCount);
            TRACE("   list=%s\n", debugrange(&item_range));
            ranges_add(i->ranges, item_range);
        }
    }

    return TRUE;
}

/***
 * Creates an iterator over the items which intersect lprc.
 */
static BOOL iterator_frameditems(ITERATOR* i, const LISTVIEW_INFO* infoPtr, const RECT *lprc)
{
    RECT frame = *lprc;
    POINT Origin;

    TRACE("(lprc=%s)\n", wine_dbgstr_rect(lprc));

    LISTVIEW_GetOrigin(infoPtr, &Origin);
    OffsetRect(&frame, -Origin.x, -Origin.y);

    return iterator_frameditems_absolute(i, infoPtr, &frame);
}

/***
 * Creates an iterator over the items which intersect the visible region of hdc.
 */
static BOOL iterator_visibleitems(ITERATOR *i, const LISTVIEW_INFO *infoPtr, HDC  hdc)
{
    POINT Origin, Position;
    RECT rcItem, rcClip;
    INT rgntype;
    
    rgntype = GetClipBox(hdc, &rcClip);
    if (rgntype == NULLREGION) return iterator_empty(i);
    if (!iterator_frameditems(i, infoPtr, &rcClip)) return FALSE;
    if (rgntype == SIMPLEREGION) return TRUE;

    /* first deal with the special item */
    if (i->nSpecial != -1)
    {
        LISTVIEW_GetItemBox(infoPtr, i->nSpecial, &rcItem);
        if (!RectVisible(hdc, &rcItem)) i->nSpecial = -1;
    }
    
    /* if we can't deal with the region, we'll just go with the simple range */
    LISTVIEW_GetOrigin(infoPtr, &Origin);
    TRACE("building visible range:\n");
    if (!i->ranges && i->range.lower < i->range.upper)
    {
        if (!(i->ranges = ranges_create(50))) return TRUE;
        if (!ranges_add(i->ranges, i->range))
        {
            ranges_destroy(i->ranges);
            i->ranges = 0;
            return TRUE;
        }
    }

    /* now delete the invisible items from the list */
    while(iterator_next(i))
    {
        LISTVIEW_GetItemOrigin(infoPtr, i->nItem, &Position);
        rcItem.left = (infoPtr->uView == LV_VIEW_DETAILS) ? Origin.x : Position.x + Origin.x;
        rcItem.top = Position.y + Origin.y;
        rcItem.right = rcItem.left + infoPtr->nItemWidth;
        rcItem.bottom = rcItem.top + infoPtr->nItemHeight;
        if (!RectVisible(hdc, &rcItem))
            ranges_delitem(i->ranges, i->nItem);
    }
    /* the iterator should restart on the next iterator_next */
    TRACE("done\n");
    
    return TRUE;
}

/******** Misc helper functions ************************************/

static inline LRESULT CallWindowProcT(WNDPROC proc, HWND hwnd, UINT uMsg,
                                      WPARAM wParam, LPARAM lParam, BOOL isW)
{
    if (isW) return CallWindowProcW(proc, hwnd, uMsg, wParam, lParam);
    else return CallWindowProcA(proc, hwnd, uMsg, wParam, lParam);
}

static inline BOOL is_autoarrange(const LISTVIEW_INFO *infoPtr)
{
    return ((infoPtr->dwStyle & LVS_AUTOARRANGE) || infoPtr->bAutoarrange) &&
           (infoPtr->uView == LV_VIEW_ICON || infoPtr->uView == LV_VIEW_SMALLICON);
}

static void toggle_checkbox_state(LISTVIEW_INFO *infoPtr, INT nItem)
{
    DWORD state = STATEIMAGEINDEX(LISTVIEW_GetItemState(infoPtr, nItem, LVIS_STATEIMAGEMASK));
    if(state == 1 || state == 2)
    {
        LVITEMW lvitem;
        state ^= 3;
        lvitem.state = INDEXTOSTATEIMAGEMASK(state);
        lvitem.stateMask = LVIS_STATEIMAGEMASK;
        LISTVIEW_SetItemState(infoPtr, nItem, &lvitem);
    }
}

/* this should be called after window style got updated,
   it used to reset view state to match current window style */
static inline void map_style_view(LISTVIEW_INFO *infoPtr)
{
    switch (infoPtr->dwStyle & LVS_TYPEMASK)
    {
    case LVS_ICON:
        infoPtr->uView = LV_VIEW_ICON;
        break;
    case LVS_REPORT:
        infoPtr->uView = LV_VIEW_DETAILS;
        break;
    case LVS_SMALLICON:
        infoPtr->uView = LV_VIEW_SMALLICON;
        break;
    case LVS_LIST:
        infoPtr->uView = LV_VIEW_LIST;
    }
}

/* computes next item id value */
static DWORD get_next_itemid(const LISTVIEW_INFO *infoPtr)
{
    INT count = DPA_GetPtrCount(infoPtr->hdpaItemIds);

    if (count > 0)
    {
        ITEM_ID *lpID = DPA_GetPtr(infoPtr->hdpaItemIds, count - 1);
        return lpID->id + 1;
    }
    return 0;
}

/******** Internal API functions ************************************/

static inline COLUMN_INFO * LISTVIEW_GetColumnInfo(const LISTVIEW_INFO *infoPtr, INT nSubItem)
{
    static COLUMN_INFO mainItem;

    if (nSubItem == 0 && DPA_GetPtrCount(infoPtr->hdpaColumns) == 0) return &mainItem;
    assert (nSubItem >= 0 && nSubItem < DPA_GetPtrCount(infoPtr->hdpaColumns));

    /* update cached column rectangles */
    if (infoPtr->colRectsDirty)
    {
        COLUMN_INFO *info;
        LISTVIEW_INFO *Ptr = (LISTVIEW_INFO*)infoPtr;
        INT i;

        for (i = 0; i < DPA_GetPtrCount(infoPtr->hdpaColumns); i++) {
            info = DPA_GetPtr(infoPtr->hdpaColumns, i);
            SendMessageW(infoPtr->hwndHeader, HDM_GETITEMRECT, i, (LPARAM)&info->rcHeader);
        }
        Ptr->colRectsDirty = FALSE;
    }

    return DPA_GetPtr(infoPtr->hdpaColumns, nSubItem);
}

static INT LISTVIEW_CreateHeader(LISTVIEW_INFO *infoPtr)
{
    DWORD dFlags = WS_CHILD | HDS_HORZ | HDS_FULLDRAG | HDS_DRAGDROP;
    HINSTANCE hInst;

    if (infoPtr->hwndHeader) return 0;

    TRACE("Creating header for list %p\n", infoPtr->hwndSelf);

    /* setup creation flags */
    dFlags |= (LVS_NOSORTHEADER & infoPtr->dwStyle) ? 0 : HDS_BUTTONS;
    dFlags |= (LVS_NOCOLUMNHEADER & infoPtr->dwStyle) ? HDS_HIDDEN : 0;

    hInst = (HINSTANCE)GetWindowLongPtrW(infoPtr->hwndSelf, GWLP_HINSTANCE);

    /* create header */
    infoPtr->hwndHeader = CreateWindowW(WC_HEADERW, NULL, dFlags,
      0, 0, 0, 0, infoPtr->hwndSelf, NULL, hInst, NULL);
    if (!infoPtr->hwndHeader) return -1;

    /* set header unicode format */
    SendMessageW(infoPtr->hwndHeader, HDM_SETUNICODEFORMAT, TRUE, 0);

    /* set header font */
    SendMessageW(infoPtr->hwndHeader, WM_SETFONT, (WPARAM)infoPtr->hFont, TRUE);

    LISTVIEW_UpdateSize(infoPtr);

    return 0;
}

static inline void LISTVIEW_GetHeaderRect(const LISTVIEW_INFO *infoPtr, INT nSubItem, LPRECT lprc)
{
    *lprc = LISTVIEW_GetColumnInfo(infoPtr, nSubItem)->rcHeader;
}

static inline BOOL LISTVIEW_IsHeaderEnabled(const LISTVIEW_INFO *infoPtr)
{
    return (infoPtr->uView == LV_VIEW_DETAILS ||
            infoPtr->dwLvExStyle & LVS_EX_HEADERINALLVIEWS) &&
          !(infoPtr->dwStyle & LVS_NOCOLUMNHEADER);
}
        
static inline BOOL LISTVIEW_GetItemW(const LISTVIEW_INFO *infoPtr, LPLVITEMW lpLVItem)
{
    return LISTVIEW_GetItemT(infoPtr, lpLVItem, TRUE);
}

/* used to handle collapse main item column case */
static inline BOOL LISTVIEW_DrawFocusRect(const LISTVIEW_INFO *infoPtr, HDC hdc)
{
    BOOL Ret = FALSE;

    if (infoPtr->rcFocus.left < infoPtr->rcFocus.right)
    {
        DWORD dwOldBkColor, dwOldTextColor;

        dwOldBkColor = SetBkColor(hdc, RGB(255, 255, 255));
        dwOldTextColor = SetBkColor(hdc, RGB(0, 0, 0));
        Ret = DrawFocusRect(hdc, &infoPtr->rcFocus);
        SetBkColor(hdc, dwOldBkColor);
        SetBkColor(hdc, dwOldTextColor);
    }
    return Ret;
}

/* Listview invalidation functions: use _only_ these functions to invalidate */

static inline BOOL is_redrawing(const LISTVIEW_INFO *infoPtr)
{
    return infoPtr->bRedraw;
}

static inline void LISTVIEW_InvalidateRect(const LISTVIEW_INFO *infoPtr, const RECT* rect)
{
    if(!is_redrawing(infoPtr)) return; 
    TRACE(" invalidating rect=%s\n", wine_dbgstr_rect(rect));
    InvalidateRect(infoPtr->hwndSelf, rect, TRUE);
}

static inline void LISTVIEW_InvalidateItem(const LISTVIEW_INFO *infoPtr, INT nItem)
{
    RECT rcBox;

    if(!is_redrawing(infoPtr)) return; 
    LISTVIEW_GetItemBox(infoPtr, nItem, &rcBox);
    LISTVIEW_InvalidateRect(infoPtr, &rcBox);
}

static inline void LISTVIEW_InvalidateSubItem(const LISTVIEW_INFO *infoPtr, INT nItem, INT nSubItem)
{
    POINT Origin, Position;
    RECT rcBox;
    
    if(!is_redrawing(infoPtr)) return; 
    assert (infoPtr->uView == LV_VIEW_DETAILS);
    LISTVIEW_GetOrigin(infoPtr, &Origin);
    LISTVIEW_GetItemOrigin(infoPtr, nItem, &Position);
    LISTVIEW_GetHeaderRect(infoPtr, nSubItem, &rcBox);
    rcBox.top = 0;
    rcBox.bottom = infoPtr->nItemHeight;
    OffsetRect(&rcBox, Origin.x + Position.x, Origin.y + Position.y);
    LISTVIEW_InvalidateRect(infoPtr, &rcBox);
}

static inline void LISTVIEW_InvalidateList(const LISTVIEW_INFO *infoPtr)
{
    LISTVIEW_InvalidateRect(infoPtr, NULL);
}

static inline void LISTVIEW_InvalidateColumn(const LISTVIEW_INFO *infoPtr, INT nColumn)
{
    RECT rcCol;
    
    if(!is_redrawing(infoPtr)) return; 
    LISTVIEW_GetHeaderRect(infoPtr, nColumn, &rcCol);
    rcCol.top = infoPtr->rcList.top;
    rcCol.bottom = infoPtr->rcList.bottom;
    LISTVIEW_InvalidateRect(infoPtr, &rcCol);
}

/***
 * DESCRIPTION:
 * Retrieves the number of items that can fit vertically in the client area.
 *
 * PARAMETER(S):
 * [I] infoPtr : valid pointer to the listview structure
 *
 * RETURN:
 * Number of items per row.
 */
static inline INT LISTVIEW_GetCountPerRow(const LISTVIEW_INFO *infoPtr)
{
    INT nListWidth = infoPtr->rcList.right - infoPtr->rcList.left;

    return max(nListWidth/(infoPtr->nItemWidth ? infoPtr->nItemWidth : 1), 1);
}

/***
 * DESCRIPTION:
 * Retrieves the number of items that can fit horizontally in the client
 * area.
 *
 * PARAMETER(S):
 * [I] infoPtr : valid pointer to the listview structure
 *
 * RETURN:
 * Number of items per column.
 */
static inline INT LISTVIEW_GetCountPerColumn(const LISTVIEW_INFO *infoPtr)
{
    INT nListHeight = infoPtr->rcList.bottom - infoPtr->rcList.top;

    return max(nListHeight / infoPtr->nItemHeight, 1);
}


/*************************************************************************
 *              LISTVIEW_ProcessLetterKeys
 *
 *  Processes keyboard messages generated by pressing the letter keys
 *  on the keyboard.
 *  What this does is perform a case insensitive search from the
 *  current position with the following quirks:
 *  - If two chars or more are pressed in quick succession we search
 *    for the corresponding string (e.g. 'abc').
 *  - If there is a delay we wipe away the current search string and
 *    restart with just that char.
 *  - If the user keeps pressing the same character, whether slowly or
 *    fast, so that the search string is entirely composed of this
 *    character ('aaaaa' for instance), then we search for first item
 *    that starting with that character.
 *  - If the user types the above character in quick succession, then
 *    we must also search for the corresponding string ('aaaaa'), and
 *    go to that string if there is a match.
 *
 * PARAMETERS
 *   [I] hwnd : handle to the window
 *   [I] charCode : the character code, the actual character
 *   [I] keyData : key data
 *
 * RETURNS
 *
 *  Zero.
 *
 * BUGS
 *
 *  - The current implementation has a list of characters it will
 *    accept and it ignores everything else. In particular it will
 *    ignore accentuated characters which seems to match what
 *    Windows does. But I'm not sure it makes sense to follow
 *    Windows there.
 *  - We don't sound a beep when the search fails.
 *
 * SEE ALSO
 *
 *  TREEVIEW_ProcessLetterKeys
 */
static INT LISTVIEW_ProcessLetterKeys(LISTVIEW_INFO *infoPtr, WPARAM charCode, LPARAM keyData)
{
    WCHAR buffer[MAX_PATH];
    INT endidx, startidx;
    DWORD prevTime;
    LVITEMW item;
    INT nItem;
    INT diff;

    /* simple parameter checking */
    if (!charCode || !keyData || infoPtr->nItemCount == 0) return 0;

    /* only allow the valid WM_CHARs through */
    if (!isalnumW(charCode) &&
        charCode != '.' && charCode != '`' && charCode != '!' &&
        charCode != '@' && charCode != '#' && charCode != '$' &&
        charCode != '%' && charCode != '^' && charCode != '&' &&
        charCode != '*' && charCode != '(' && charCode != ')' &&
        charCode != '-' && charCode != '_' && charCode != '+' &&
        charCode != '=' && charCode != '\\'&& charCode != ']' &&
        charCode != '}' && charCode != '[' && charCode != '{' &&
        charCode != '/' && charCode != '?' && charCode != '>' &&
        charCode != '<' && charCode != ',' && charCode != '~')
        return 0;

    /* update the search parameters */
    prevTime = infoPtr->lastKeyPressTimestamp;
    infoPtr->lastKeyPressTimestamp = GetTickCount();
    diff = infoPtr->lastKeyPressTimestamp - prevTime;

    if (diff >= 0 && diff < KEY_DELAY)
    {
        if (infoPtr->nSearchParamLength < MAX_PATH - 1)
            infoPtr->szSearchParam[infoPtr->nSearchParamLength++] = charCode;

        if (infoPtr->charCode != charCode)
            infoPtr->charCode = charCode = 0;
    }
    else
    {
        infoPtr->charCode = charCode;
        infoPtr->szSearchParam[0] = charCode;
        infoPtr->nSearchParamLength = 1;
    }

    /* and search from the current position */
    nItem = -1;
    endidx = infoPtr->nItemCount;

    /* should start from next after focused item, so next item that matches
       will be selected, if there isn't any and focused matches it will be selected
       on second search stage from beginning of the list */
    if (infoPtr->nFocusedItem >= 0 && infoPtr->nItemCount > 1)
        startidx = infoPtr->nFocusedItem + 1;
    else
        startidx = 0;

    /* let application handle this for virtual listview */
    if (infoPtr->dwStyle & LVS_OWNERDATA)
    {
        NMLVFINDITEMW nmlv;

        memset(&nmlv.lvfi, 0, sizeof(nmlv.lvfi));
        nmlv.lvfi.flags = (LVFI_WRAP | LVFI_PARTIAL);
        nmlv.lvfi.psz = infoPtr->szSearchParam;
        nmlv.iStart = startidx;

        infoPtr->szSearchParam[infoPtr->nSearchParamLength] = 0;

        nItem = notify_hdr(infoPtr, LVN_ODFINDITEMW, (LPNMHDR)&nmlv.hdr);
    }
    else
    {
        INT i = startidx;

        /* first search in [startidx, endidx), on failure continue in [0, startidx) */
        while (1)
        {
            /* start from first item if not found with >= startidx */
            if (i == infoPtr->nItemCount && startidx > 0)
            {
                endidx = startidx;
                startidx = 0;
            }

            for (i = startidx; i < endidx; i++)
            {
                /* retrieve text */
                item.mask = LVIF_TEXT;
                item.iItem = i;
                item.iSubItem = 0;
                item.pszText = buffer;
                item.cchTextMax = MAX_PATH;
                if (!LISTVIEW_GetItemW(infoPtr, &item)) return 0;

                if (lstrncmpiW(item.pszText, infoPtr->szSearchParam, infoPtr->nSearchParamLength) == 0)
                {
                    nItem = i;
                    break;
                }
                else if (nItem == -1 && lstrncmpiW(item.pszText, infoPtr->szSearchParam, 1) == 0)
                {
                    /* this would work but we must keep looking for a longer match */
                    nItem = i;
                }
            }

            if ( nItem != -1 || /* found something */
                 endidx != infoPtr->nItemCount || /* second search done */
                (startidx == 0 && endidx == infoPtr->nItemCount) /* full range for first search */ )
                break;
        };
    }

    if (nItem != -1)
        LISTVIEW_KeySelection(infoPtr, nItem, FALSE);

    return 0;
}

/*************************************************************************
 * LISTVIEW_UpdateHeaderSize [Internal]
 *
 * Function to resize the header control
 *
 * PARAMS
 * [I]  hwnd : handle to a window
 * [I]  nNewScrollPos : scroll pos to set
 *
 * RETURNS
 * None.
 */
static void LISTVIEW_UpdateHeaderSize(const LISTVIEW_INFO *infoPtr, INT nNewScrollPos)
{
    RECT winRect;
    POINT point[2];

    TRACE("nNewScrollPos=%d\n", nNewScrollPos);

    if (!infoPtr->hwndHeader)  return;

    GetWindowRect(infoPtr->hwndHeader, &winRect);
    point[0].x = winRect.left;
    point[0].y = winRect.top;
    point[1].x = winRect.right;
    point[1].y = winRect.bottom;

    MapWindowPoints(HWND_DESKTOP, infoPtr->hwndSelf, point, 2);
    point[0].x = -nNewScrollPos;
    point[1].x += nNewScrollPos;

    SetWindowPos(infoPtr->hwndHeader,0,
        point[0].x,point[0].y,point[1].x,point[1].y,
        (infoPtr->dwStyle & LVS_NOCOLUMNHEADER) ? SWP_HIDEWINDOW : SWP_SHOWWINDOW |
        SWP_NOZORDER | SWP_NOACTIVATE);
}

/***
 * DESCRIPTION:
 * Update the scrollbars. This functions should be called whenever
 * the content, size or view changes.
 *
 * PARAMETER(S):
 * [I] infoPtr : valid pointer to the listview structure
 *
 * RETURN:
 * None
 */
static void LISTVIEW_UpdateScroll(const LISTVIEW_INFO *infoPtr)
{
    SCROLLINFO horzInfo, vertInfo;
    INT dx, dy;

    if ((infoPtr->dwStyle & LVS_NOSCROLL) || !is_redrawing(infoPtr)) return;

    ZeroMemory(&horzInfo, sizeof(SCROLLINFO));
    horzInfo.cbSize = sizeof(SCROLLINFO);
    horzInfo.nPage = infoPtr->rcList.right - infoPtr->rcList.left;

    /* for now, we'll set info.nMax to the _count_, and adjust it later */
    if (infoPtr->uView == LV_VIEW_LIST)
    {
        INT nPerCol = LISTVIEW_GetCountPerColumn(infoPtr);
        horzInfo.nMax = (infoPtr->nItemCount + nPerCol - 1) / nPerCol;

        /* scroll by at least one column per page */
        if(horzInfo.nPage < infoPtr->nItemWidth)
                horzInfo.nPage = infoPtr->nItemWidth;

        if (infoPtr->nItemWidth)
            horzInfo.nPage /= infoPtr->nItemWidth;
    }
    else if (infoPtr->uView == LV_VIEW_DETAILS)
    {
        horzInfo.nMax = infoPtr->nItemWidth;
    }
    else /* LV_VIEW_ICON, or LV_VIEW_SMALLICON */
    {
        RECT rcView;

        if (LISTVIEW_GetViewRect(infoPtr, &rcView)) horzInfo.nMax = rcView.right - rcView.left;
    }

    if (LISTVIEW_IsHeaderEnabled(infoPtr))
    {
        if (DPA_GetPtrCount(infoPtr->hdpaColumns))
        {
            RECT rcHeader;
            INT index;

            index = SendMessageW(infoPtr->hwndHeader, HDM_ORDERTOINDEX,
                                 DPA_GetPtrCount(infoPtr->hdpaColumns) - 1, 0);

            LISTVIEW_GetHeaderRect(infoPtr, index, &rcHeader);
            horzInfo.nMax = rcHeader.right;
            TRACE("horzInfo.nMax=%d\n", horzInfo.nMax);
        }
    }

    horzInfo.fMask = SIF_RANGE | SIF_PAGE;
    horzInfo.nMax = max(horzInfo.nMax - 1, 0);
    dx = GetScrollPos(infoPtr->hwndSelf, SB_HORZ);
    dx -= SetScrollInfo(infoPtr->hwndSelf, SB_HORZ, &horzInfo, TRUE);
    TRACE("horzInfo=%s\n", debugscrollinfo(&horzInfo));

    /* Setting the horizontal scroll can change the listview size
     * (and potentially everything else) so we need to recompute
     * everything again for the vertical scroll
     */

    ZeroMemory(&vertInfo, sizeof(SCROLLINFO));
    vertInfo.cbSize = sizeof(SCROLLINFO);
    vertInfo.nPage = infoPtr->rcList.bottom - infoPtr->rcList.top;

    if (infoPtr->uView == LV_VIEW_DETAILS)
    {
        vertInfo.nMax = infoPtr->nItemCount;
        
        /* scroll by at least one page */
        if(vertInfo.nPage < infoPtr->nItemHeight)
          vertInfo.nPage = infoPtr->nItemHeight;

        if (infoPtr->nItemHeight > 0)
            vertInfo.nPage /= infoPtr->nItemHeight;
    }
    else if (infoPtr->uView != LV_VIEW_LIST) /* LV_VIEW_ICON, or LV_VIEW_SMALLICON */
    {
        RECT rcView;

        if (LISTVIEW_GetViewRect(infoPtr, &rcView)) vertInfo.nMax = rcView.bottom - rcView.top;
    }

    vertInfo.fMask = SIF_RANGE | SIF_PAGE;
    vertInfo.nMax = max(vertInfo.nMax - 1, 0);
    dy = GetScrollPos(infoPtr->hwndSelf, SB_VERT);
    dy -= SetScrollInfo(infoPtr->hwndSelf, SB_VERT, &vertInfo, TRUE);
    TRACE("vertInfo=%s\n", debugscrollinfo(&vertInfo));

    /* Change of the range may have changed the scroll pos. If so move the content */
    if (dx != 0 || dy != 0)
    {
        RECT listRect;
        listRect = infoPtr->rcList;
        ScrollWindowEx(infoPtr->hwndSelf, dx, dy, &listRect, &listRect, 0, 0,
            SW_ERASE | SW_INVALIDATE);
    }

    /* Update the Header Control */
    if (infoPtr->hwndHeader)
    {
        horzInfo.fMask = SIF_POS;
        GetScrollInfo(infoPtr->hwndSelf, SB_HORZ, &horzInfo);
        LISTVIEW_UpdateHeaderSize(infoPtr, horzInfo.nPos);
    }
}


/***
 * DESCRIPTION:
 * Shows/hides the focus rectangle. 
 *
 * PARAMETER(S):
 * [I] infoPtr : valid pointer to the listview structure
 * [I] fShow : TRUE to show the focus, FALSE to hide it.
 *
 * RETURN:
 * None
 */
static void LISTVIEW_ShowFocusRect(const LISTVIEW_INFO *infoPtr, BOOL fShow)
{
    HDC hdc;

    TRACE("fShow=%d, nItem=%d\n", fShow, infoPtr->nFocusedItem);

    if (infoPtr->nFocusedItem < 0) return;

    /* we need some gymnastics in ICON mode to handle large items */
    if (infoPtr->uView == LV_VIEW_ICON)
    {
        RECT rcBox;

        LISTVIEW_GetItemBox(infoPtr, infoPtr->nFocusedItem, &rcBox); 
        if ((rcBox.bottom - rcBox.top) > infoPtr->nItemHeight)
        {
            LISTVIEW_InvalidateRect(infoPtr, &rcBox);
            return;
        }
    }

    if (!(hdc = GetDC(infoPtr->hwndSelf))) return;

    /* for some reason, owner draw should work only in report mode */
    if ((infoPtr->dwStyle & LVS_OWNERDRAWFIXED) && (infoPtr->uView == LV_VIEW_DETAILS))
    {
        DRAWITEMSTRUCT dis;
        LVITEMW item;

        HFONT hFont = infoPtr->hFont ? infoPtr->hFont : infoPtr->hDefaultFont;
        HFONT hOldFont = SelectObject(hdc, hFont);

        item.iItem = infoPtr->nFocusedItem;
        item.iSubItem = 0;
        item.mask = LVIF_PARAM;
        if (!LISTVIEW_GetItemW(infoPtr, &item)) goto done;
           
        ZeroMemory(&dis, sizeof(dis)); 
        dis.CtlType = ODT_LISTVIEW;
        dis.CtlID = (UINT)GetWindowLongPtrW(infoPtr->hwndSelf, GWLP_ID);
        dis.itemID = item.iItem;
        dis.itemAction = ODA_FOCUS;
        if (fShow) dis.itemState |= ODS_FOCUS;
        dis.hwndItem = infoPtr->hwndSelf;
        dis.hDC = hdc;
        LISTVIEW_GetItemBox(infoPtr, dis.itemID, &dis.rcItem);
        dis.itemData = item.lParam;

        SendMessageW(infoPtr->hwndNotify, WM_DRAWITEM, dis.CtlID, (LPARAM)&dis);

        SelectObject(hdc, hOldFont);
    }
    else
    {
        LISTVIEW_DrawFocusRect(infoPtr, hdc);
    }
done:
    ReleaseDC(infoPtr->hwndSelf, hdc);
}

/***
 * Invalidates all visible selected items.
 */
static void LISTVIEW_InvalidateSelectedItems(const LISTVIEW_INFO *infoPtr)
{
    ITERATOR i; 
   
    iterator_frameditems(&i, infoPtr, &infoPtr->rcList); 
    while(iterator_next(&i))
    {
        if (LISTVIEW_GetItemState(infoPtr, i.nItem, LVIS_SELECTED))
            LISTVIEW_InvalidateItem(infoPtr, i.nItem);
    }
    iterator_destroy(&i);
}

            
/***
 * DESCRIPTION:            [INTERNAL]
 * Computes an item's (left,top) corner, relative to rcView.
 * That is, the position has NOT been made relative to the Origin.
 * This is deliberate, to avoid computing the Origin over, and
 * over again, when this function is called in a loop. Instead,
 * one can factor the computation of the Origin before the loop,
 * and offset the value returned by this function, on every iteration.
 * 
 * PARAMETER(S):
 * [I] infoPtr : valid pointer to the listview structure
 * [I] nItem  : item number
 * [O] lpptOrig : item top, left corner
 *
 * RETURN:
 *   None.
 */
static void LISTVIEW_GetItemOrigin(const LISTVIEW_INFO *infoPtr, INT nItem, LPPOINT lpptPosition)
{
    assert(nItem >= 0 && nItem < infoPtr->nItemCount);

    if ((infoPtr->uView == LV_VIEW_SMALLICON) || (infoPtr->uView == LV_VIEW_ICON))
    {
        lpptPosition->x = (LONG_PTR)DPA_GetPtr(infoPtr->hdpaPosX, nItem);
        lpptPosition->y = (LONG_PTR)DPA_GetPtr(infoPtr->hdpaPosY, nItem);
    }
    else if (infoPtr->uView == LV_VIEW_LIST)
    {
        INT nCountPerColumn = LISTVIEW_GetCountPerColumn(infoPtr);
        lpptPosition->x = nItem / nCountPerColumn * infoPtr->nItemWidth;
        lpptPosition->y = nItem % nCountPerColumn * infoPtr->nItemHeight;
    }
    else /* LV_VIEW_DETAILS */
    {
        lpptPosition->x = REPORT_MARGINX;
        /* item is always at zero indexed column */
        if (DPA_GetPtrCount(infoPtr->hdpaColumns) > 0)
            lpptPosition->x += LISTVIEW_GetColumnInfo(infoPtr, 0)->rcHeader.left;
        lpptPosition->y = nItem * infoPtr->nItemHeight;
    }
}
    
/***
 * DESCRIPTION:            [INTERNAL]
 * Compute the rectangles of an item.  This is to localize all
 * the computations in one place. If you are not interested in some
 * of these values, simply pass in a NULL -- the function is smart
 * enough to compute only what's necessary. The function computes
 * the standard rectangles (BOUNDS, ICON, LABEL) plus a non-standard
 * one, the BOX rectangle. This rectangle is very cheap to compute,
 * and is guaranteed to contain all the other rectangles. Computing
 * the ICON rect is also cheap, but all the others are potentially
 * expensive. This gives an easy and effective optimization when
 * searching (like point inclusion, or rectangle intersection):
 * first test against the BOX, and if TRUE, test against the desired
 * rectangle.
 * If the function does not have all the necessary information
 * to computed the requested rectangles, will crash with a
 * failed assertion. This is done so we catch all programming
 * errors, given that the function is called only from our code.
 *
 * We have the following 'special' meanings for a few fields:
 *   * If LVIS_FOCUSED is set, we assume the item has the focus
 *     This is important in ICON mode, where it might get a larger
 *     then usual rectangle
 *
 * Please note that subitem support works only in REPORT mode.
 *
 * PARAMETER(S):
 * [I] infoPtr : valid pointer to the listview structure
 * [I] lpLVItem : item to compute the measures for
 * [O] lprcBox : ptr to Box rectangle
 *                Same as LVM_GETITEMRECT with LVIR_BOUNDS
 * [0] lprcSelectBox : ptr to select box rectangle
 *                Same as LVM_GETITEMRECT with LVIR_SELECTEDBOUNDS
 * [O] lprcIcon : ptr to Icon rectangle
 *                Same as LVM_GETITEMRECT with LVIR_ICON
 * [O] lprcStateIcon: ptr to State Icon rectangle
 * [O] lprcLabel : ptr to Label rectangle
 *                Same as LVM_GETITEMRECT with LVIR_LABEL
 *
 * RETURN:
 *   None.
 */
static void LISTVIEW_GetItemMetrics(const LISTVIEW_INFO *infoPtr, const LVITEMW *lpLVItem,
                                    LPRECT lprcBox, LPRECT lprcSelectBox,
                                    LPRECT lprcIcon, LPRECT lprcStateIcon, LPRECT lprcLabel)
{
    BOOL doSelectBox = FALSE, doIcon = FALSE, doLabel = FALSE, oversizedBox = FALSE;
    RECT Box, SelectBox, Icon, Label;
    COLUMN_INFO *lpColumnInfo = NULL;
    SIZE labelSize = { 0, 0 };

    TRACE("(lpLVItem=%s)\n", debuglvitem_t(lpLVItem, TRUE));

    /* Be smart and try to figure out the minimum we have to do */
    if (lpLVItem->iSubItem) assert(infoPtr->uView == LV_VIEW_DETAILS);
    if (infoPtr->uView == LV_VIEW_ICON && (lprcBox || lprcLabel))
    {
        assert((lpLVItem->mask & LVIF_STATE) && (lpLVItem->stateMask & LVIS_FOCUSED));
        if (lpLVItem->state & LVIS_FOCUSED) oversizedBox = doLabel = TRUE;
    }
    if (lprcSelectBox) doSelectBox = TRUE;
    if (lprcLabel) doLabel = TRUE;
    if (doLabel || lprcIcon || lprcStateIcon) doIcon = TRUE;
    if (doSelectBox)
    {
        doIcon = TRUE;
        doLabel = TRUE;
    }

    /************************************************************/
    /* compute the box rectangle (it should be cheap to do)     */
    /************************************************************/
    if (lpLVItem->iSubItem || infoPtr->uView == LV_VIEW_DETAILS)
        lpColumnInfo = LISTVIEW_GetColumnInfo(infoPtr, lpLVItem->iSubItem);

    if (lpLVItem->iSubItem)    
    {
        Box = lpColumnInfo->rcHeader;
    }
    else
    {
        Box.left = 0;
        Box.right = infoPtr->nItemWidth;
    }
    Box.top = 0;
    Box.bottom = infoPtr->nItemHeight;

    /******************************************************************/
    /* compute ICON bounding box (ala LVM_GETITEMRECT) and STATEICON  */
    /******************************************************************/
    if (doIcon)
    {
        LONG state_width = 0;

        if (infoPtr->himlState && lpLVItem->iSubItem == 0)
            state_width = infoPtr->iconStateSize.cx;

        if (infoPtr->uView == LV_VIEW_ICON)
        {
            Icon.left   = Box.left + state_width;
            if (infoPtr->himlNormal)
                Icon.left += (infoPtr->nItemWidth - infoPtr->iconSize.cx - state_width) / 2;
            Icon.top    = Box.top + ICON_TOP_PADDING;
            Icon.right  = Icon.left;
            Icon.bottom = Icon.top;
            if (infoPtr->himlNormal)
            {
                Icon.right  += infoPtr->iconSize.cx;
                Icon.bottom += infoPtr->iconSize.cy;
            }
        }
        else /* LV_VIEW_SMALLICON, LV_VIEW_LIST or LV_VIEW_DETAILS */
        {
            Icon.left   = Box.left + state_width;

            if (infoPtr->uView == LV_VIEW_DETAILS && lpLVItem->iSubItem == 0)
            {
                /* we need the indent in report mode */
                assert(lpLVItem->mask & LVIF_INDENT);
                Icon.left += infoPtr->iconSize.cx * lpLVItem->iIndent + REPORT_MARGINX;
            }

            Icon.top    = Box.top;
            Icon.right  = Icon.left;
            if (infoPtr->himlSmall &&
                (!lpColumnInfo || lpLVItem->iSubItem == 0 || (lpColumnInfo->fmt & LVCFMT_IMAGE) ||
                 ((infoPtr->dwLvExStyle & LVS_EX_SUBITEMIMAGES) && lpLVItem->iImage != I_IMAGECALLBACK)))
                Icon.right += infoPtr->iconSize.cx;
            Icon.bottom = Icon.top + infoPtr->iconSize.cy;
        }
        if(lprcIcon) *lprcIcon = Icon;
        TRACE("    - icon=%s\n", wine_dbgstr_rect(&Icon));

        /* TODO: is this correct? */
        if (lprcStateIcon)
        {
            lprcStateIcon->left = Icon.left - state_width;
            lprcStateIcon->right = Icon.left;
            lprcStateIcon->top = Icon.top;
            lprcStateIcon->bottom = lprcStateIcon->top + infoPtr->iconSize.cy;
            TRACE("    - state icon=%s\n", wine_dbgstr_rect(lprcStateIcon));
        }
     }
     else Icon.right = 0;

    /************************************************************/
    /* compute LABEL bounding box (ala LVM_GETITEMRECT)         */
    /************************************************************/
    if (doLabel)
    {
        /* calculate how far to the right can the label stretch */
        Label.right = Box.right;
        if (infoPtr->uView == LV_VIEW_DETAILS)
        {
            if (lpLVItem->iSubItem == 0)
            {
                /* we need a zero based rect here */
                Label = lpColumnInfo->rcHeader;
                OffsetRect(&Label, -Label.left, 0);
            }
        }

        if (lpLVItem->iSubItem || ((infoPtr->dwStyle & LVS_OWNERDRAWFIXED) && infoPtr->uView == LV_VIEW_DETAILS))
        {
           labelSize.cx = infoPtr->nItemWidth;
           labelSize.cy = infoPtr->nItemHeight;
           goto calc_label;
        }
        
        /* we need the text in non owner draw mode */
        assert(lpLVItem->mask & LVIF_TEXT);
        if (is_text(lpLVItem->pszText))
        {
            HFONT hFont = infoPtr->hFont ? infoPtr->hFont : infoPtr->hDefaultFont;
            HDC hdc = GetDC(infoPtr->hwndSelf);
            HFONT hOldFont = SelectObject(hdc, hFont);
            UINT uFormat;
            RECT rcText;

            /* compute rough rectangle where the label will go */
            SetRectEmpty(&rcText);
            rcText.right = infoPtr->nItemWidth - TRAILING_LABEL_PADDING;
            rcText.bottom = infoPtr->nItemHeight;
            if (infoPtr->uView == LV_VIEW_ICON)
                rcText.bottom -= ICON_TOP_PADDING + infoPtr->iconSize.cy + ICON_BOTTOM_PADDING;

            /* now figure out the flags */
            if (infoPtr->uView == LV_VIEW_ICON)
                uFormat = oversizedBox ? LV_FL_DT_FLAGS : LV_ML_DT_FLAGS;
            else
                uFormat = LV_SL_DT_FLAGS;
            
            DrawTextW (hdc, lpLVItem->pszText, -1, &rcText, uFormat | DT_CALCRECT);

            if (rcText.right != rcText.left)
                labelSize.cx = min(rcText.right - rcText.left + TRAILING_LABEL_PADDING, infoPtr->nItemWidth);

            labelSize.cy = rcText.bottom - rcText.top;

            SelectObject(hdc, hOldFont);
            ReleaseDC(infoPtr->hwndSelf, hdc);
        }

calc_label:
        if (infoPtr->uView == LV_VIEW_ICON)
        {
            Label.left = Box.left + (infoPtr->nItemWidth - labelSize.cx) / 2;
            Label.top  = Box.top + ICON_TOP_PADDING_HITABLE +
                         infoPtr->iconSize.cy + ICON_BOTTOM_PADDING;
            Label.right = Label.left + labelSize.cx;
            Label.bottom = Label.top + infoPtr->nItemHeight;
            if (!oversizedBox && labelSize.cy > infoPtr->ntmHeight)
            {
                labelSize.cy = min(Box.bottom - Label.top, labelSize.cy);
                labelSize.cy /= infoPtr->ntmHeight;
                labelSize.cy = max(labelSize.cy, 1);
                labelSize.cy *= infoPtr->ntmHeight;
             }
             Label.bottom = Label.top + labelSize.cy + HEIGHT_PADDING;
        }
        else if (infoPtr->uView == LV_VIEW_DETAILS)
        {
            Label.left = Icon.right;
            Label.top = Box.top;
            Label.right = lpLVItem->iSubItem ? lpColumnInfo->rcHeader.right :
                          lpColumnInfo->rcHeader.right - lpColumnInfo->rcHeader.left;
            Label.bottom = Label.top + infoPtr->nItemHeight;
        }
        else /* LV_VIEW_SMALLICON or LV_VIEW_LIST */
        {
            Label.left = Icon.right;
            Label.top = Box.top;
            Label.right = min(Label.left + labelSize.cx, Label.right);
            Label.bottom = Label.top + infoPtr->nItemHeight;
        }
  
        if (lprcLabel) *lprcLabel = Label;
        TRACE("    - label=%s\n", wine_dbgstr_rect(&Label));
    }

    /************************************************************/
    /* compute SELECT bounding box                              */
    /************************************************************/
    if (doSelectBox)
    {
        if (infoPtr->uView == LV_VIEW_DETAILS)
        {
            SelectBox.left = Icon.left;
            SelectBox.top = Box.top;
            SelectBox.bottom = Box.bottom;

            if (labelSize.cx)
                SelectBox.right = min(Label.left + labelSize.cx, Label.right);
            else
                SelectBox.right = min(Label.left + MAX_EMPTYTEXT_SELECT_WIDTH, Label.right);
        }
        else
        {
            UnionRect(&SelectBox, &Icon, &Label);
        }
        if (lprcSelectBox) *lprcSelectBox = SelectBox;
        TRACE("    - select box=%s\n", wine_dbgstr_rect(&SelectBox));
    }

    /* Fix the Box if necessary */
    if (lprcBox)
    {
        if (oversizedBox) UnionRect(lprcBox, &Box, &Label);
        else *lprcBox = Box;
    }
    TRACE("    - box=%s\n", wine_dbgstr_rect(&Box));
}

/***
 * DESCRIPTION:            [INTERNAL]
 *
 * PARAMETER(S):
 * [I] infoPtr : valid pointer to the listview structure
 * [I] nItem : item number
 * [O] lprcBox : ptr to Box rectangle
 *
 * RETURN:
 *   None.
 */
static void LISTVIEW_GetItemBox(const LISTVIEW_INFO *infoPtr, INT nItem, LPRECT lprcBox)
{
    WCHAR szDispText[DISP_TEXT_SIZE] = { '\0' };
    POINT Position, Origin;
    LVITEMW lvItem;

    LISTVIEW_GetOrigin(infoPtr, &Origin);
    LISTVIEW_GetItemOrigin(infoPtr, nItem, &Position);

    /* Be smart and try to figure out the minimum we have to do */
    lvItem.mask = 0;
    if (infoPtr->uView == LV_VIEW_ICON && infoPtr->bFocus && LISTVIEW_GetItemState(infoPtr, nItem, LVIS_FOCUSED))
        lvItem.mask |= LVIF_TEXT;
    lvItem.iItem = nItem;
    lvItem.iSubItem = 0;
    lvItem.pszText = szDispText;
    lvItem.cchTextMax = DISP_TEXT_SIZE;
    if (lvItem.mask) LISTVIEW_GetItemW(infoPtr, &lvItem);
    if (infoPtr->uView == LV_VIEW_ICON)
    {
        lvItem.mask |= LVIF_STATE;
        lvItem.stateMask = LVIS_FOCUSED;
        lvItem.state = (lvItem.mask & LVIF_TEXT ? LVIS_FOCUSED : 0);
    }
    LISTVIEW_GetItemMetrics(infoPtr, &lvItem, lprcBox, 0, 0, 0, 0);

    if (infoPtr->uView == LV_VIEW_DETAILS && infoPtr->dwLvExStyle & LVS_EX_FULLROWSELECT &&
        SendMessageW(infoPtr->hwndHeader, HDM_ORDERTOINDEX, 0, 0))
    {
        OffsetRect(lprcBox, Origin.x, Position.y + Origin.y);
    }
    else
        OffsetRect(lprcBox, Position.x + Origin.x, Position.y + Origin.y);
}

/* LISTVIEW_MapIdToIndex helper */
static INT CALLBACK MapIdSearchCompare(LPVOID p1, LPVOID p2, LPARAM lParam)
{
    ITEM_ID *id1 = (ITEM_ID*)p1;
    ITEM_ID *id2 = (ITEM_ID*)p2;

    if (id1->id == id2->id) return 0;

    return (id1->id < id2->id) ? -1 : 1;
}

/***
 * DESCRIPTION:
 * Returns the item index for id specified.
 *
 * PARAMETER(S):
 * [I] infoPtr : valid pointer to the listview structure
 * [I] iID : item id to get index for
 *
 * RETURN:
 * Item index, or -1 on failure.
 */
static INT LISTVIEW_MapIdToIndex(const LISTVIEW_INFO *infoPtr, UINT iID)
{
    ITEM_ID ID;
    INT index;

    TRACE("iID=%d\n", iID);

    if (infoPtr->dwStyle & LVS_OWNERDATA) return -1;
    if (infoPtr->nItemCount == 0) return -1;

    ID.id = iID;
    index = DPA_Search(infoPtr->hdpaItemIds, &ID, -1, &MapIdSearchCompare, 0, DPAS_SORTED);

    if (index != -1)
    {
        ITEM_ID *lpID = DPA_GetPtr(infoPtr->hdpaItemIds, index);
        return DPA_GetPtrIndex(infoPtr->hdpaItems, lpID->item);
    }

    return -1;
}

/***
 * DESCRIPTION:
 * Returns the item id for index given.
 *
 * PARAMETER(S):
 * [I] infoPtr : valid pointer to the listview structure
 * [I] iItem : item index to get id for
 *
 * RETURN:
 * Item id.
 */
static DWORD LISTVIEW_MapIndexToId(const LISTVIEW_INFO *infoPtr, INT iItem)
{
    ITEM_INFO *lpItem;
    HDPA hdpaSubItems;

    TRACE("iItem=%d\n", iItem);

    if (infoPtr->dwStyle & LVS_OWNERDATA) return -1;
    if (iItem < 0 || iItem >= infoPtr->nItemCount) return -1;

    hdpaSubItems = DPA_GetPtr(infoPtr->hdpaItems, iItem);
    lpItem = DPA_GetPtr(hdpaSubItems, 0);

    return lpItem->id->id;
}

/***
 * DESCRIPTION:
 * Returns the current icon position, and advances it along the top.
 * The returned position is not offset by Origin.
 *
 * PARAMETER(S):
 * [I] infoPtr : valid pointer to the listview structure
 * [O] lpPos : will get the current icon position
 *
 * RETURN:
 * None
 */
static void LISTVIEW_NextIconPosTop(LISTVIEW_INFO *infoPtr, LPPOINT lpPos)
{
    INT nListWidth = infoPtr->rcList.right - infoPtr->rcList.left;
    
    *lpPos = infoPtr->currIconPos;
    
    infoPtr->currIconPos.x += infoPtr->nItemWidth;
    if (infoPtr->currIconPos.x + infoPtr->nItemWidth <= nListWidth) return;

    infoPtr->currIconPos.x  = 0;
    infoPtr->currIconPos.y += infoPtr->nItemHeight;
}

    
/***
 * DESCRIPTION:
 * Returns the current icon position, and advances it down the left edge.
 * The returned position is not offset by Origin.
 *
 * PARAMETER(S):
 * [I] infoPtr : valid pointer to the listview structure
 * [O] lpPos : will get the current icon position
 *
 * RETURN:
 * None
 */
static void LISTVIEW_NextIconPosLeft(LISTVIEW_INFO *infoPtr, LPPOINT lpPos)
{
    INT nListHeight = infoPtr->rcList.bottom - infoPtr->rcList.top;
    
    *lpPos = infoPtr->currIconPos;
    
    infoPtr->currIconPos.y += infoPtr->nItemHeight;
    if (infoPtr->currIconPos.y + infoPtr->nItemHeight <= nListHeight) return;

    infoPtr->currIconPos.x += infoPtr->nItemWidth;
    infoPtr->currIconPos.y  = 0;
}

    
/***
 * DESCRIPTION:
 * Moves an icon to the specified position.
 * It takes care of invalidating the item, etc.
 *
 * PARAMETER(S):
 * [I] infoPtr : valid pointer to the listview structure
 * [I] nItem : the item to move
 * [I] lpPos : the new icon position
 * [I] isNew : flags the item as being new
 *
 * RETURN:
 *   Success: TRUE
 *   Failure: FALSE
 */
static BOOL LISTVIEW_MoveIconTo(const LISTVIEW_INFO *infoPtr, INT nItem, const POINT *lppt, BOOL isNew)
{
    POINT old;
    
    if (!isNew)
    { 
        old.x = (LONG_PTR)DPA_GetPtr(infoPtr->hdpaPosX, nItem);
        old.y = (LONG_PTR)DPA_GetPtr(infoPtr->hdpaPosY, nItem);
    
        if (lppt->x == old.x && lppt->y == old.y) return TRUE;
        LISTVIEW_InvalidateItem(infoPtr, nItem);
    }

    /* Allocating a POINTER for every item is too resource intensive,
     * so we'll keep the (x,y) in different arrays */
    if (!DPA_SetPtr(infoPtr->hdpaPosX, nItem, (void *)(LONG_PTR)lppt->x)) return FALSE;
    if (!DPA_SetPtr(infoPtr->hdpaPosY, nItem, (void *)(LONG_PTR)lppt->y)) return FALSE;

    LISTVIEW_InvalidateItem(infoPtr, nItem);

    return TRUE;
}

/***
 * DESCRIPTION:
 * Arranges listview items in icon display mode.
 *
 * PARAMETER(S):
 * [I] infoPtr : valid pointer to the listview structure
 * [I] nAlignCode : alignment code
 *
 * RETURN:
 *   SUCCESS : TRUE
 *   FAILURE : FALSE
 */
static BOOL LISTVIEW_Arrange(LISTVIEW_INFO *infoPtr, INT nAlignCode)
{
    void (*next_pos)(LISTVIEW_INFO *, LPPOINT);
    POINT pos;
    INT i;

    if (infoPtr->uView != LV_VIEW_ICON && infoPtr->uView != LV_VIEW_SMALLICON) return FALSE;
  
    TRACE("nAlignCode=%d\n", nAlignCode);

    if (nAlignCode == LVA_DEFAULT)
    {
        if (infoPtr->dwStyle & LVS_ALIGNLEFT) nAlignCode = LVA_ALIGNLEFT;
        else nAlignCode = LVA_ALIGNTOP;
    }
   
    switch (nAlignCode)
    {
    case LVA_ALIGNLEFT:  next_pos = LISTVIEW_NextIconPosLeft; break;
    case LVA_ALIGNTOP:   next_pos = LISTVIEW_NextIconPosTop;  break;
    case LVA_SNAPTOGRID: next_pos = LISTVIEW_NextIconPosTop;  break; /* FIXME */
    default: return FALSE;
    }
    
    infoPtr->bAutoarrange = TRUE;
    infoPtr->currIconPos.x = infoPtr->currIconPos.y = 0;
    for (i = 0; i < infoPtr->nItemCount; i++)
    {
        next_pos(infoPtr, &pos);
        LISTVIEW_MoveIconTo(infoPtr, i, &pos, FALSE);
    }

    return TRUE;
}
  
/***
 * DESCRIPTION:
 * Retrieves the bounding rectangle of all the items, not offset by Origin.
 * For LVS_REPORT always returns empty rectangle.
 *
 * PARAMETER(S):
 * [I] infoPtr : valid pointer to the listview structure
 * [O] lprcView : bounding rectangle
 *
 * RETURN:
 *   SUCCESS : TRUE
 *   FAILURE : FALSE
 */
static void LISTVIEW_GetAreaRect(const LISTVIEW_INFO *infoPtr, LPRECT lprcView)
{
    INT i, x, y;

    SetRectEmpty(lprcView);

    switch (infoPtr->uView)
    {
    case LV_VIEW_ICON:
    case LV_VIEW_SMALLICON:
        for (i = 0; i < infoPtr->nItemCount; i++)
        {
            x = (LONG_PTR)DPA_GetPtr(infoPtr->hdpaPosX, i);
            y = (LONG_PTR)DPA_GetPtr(infoPtr->hdpaPosY, i);
            lprcView->right = max(lprcView->right, x);
            lprcView->bottom = max(lprcView->bottom, y);
        }
        if (infoPtr->nItemCount > 0)
        {
            lprcView->right += infoPtr->nItemWidth;
            lprcView->bottom += infoPtr->nItemHeight;
        }
        break;

    case LV_VIEW_LIST:
        y = LISTVIEW_GetCountPerColumn(infoPtr);
        x = infoPtr->nItemCount / y;
        if (infoPtr->nItemCount % y) x++;
        lprcView->right = x * infoPtr->nItemWidth;
        lprcView->bottom = y * infoPtr->nItemHeight;
        break;
    }
}

/***
 * DESCRIPTION:
 * Retrieves the bounding rectangle of all the items.
 *
 * PARAMETER(S):
 * [I] infoPtr : valid pointer to the listview structure
 * [O] lprcView : bounding rectangle
 *
 * RETURN:
 *   SUCCESS : TRUE
 *   FAILURE : FALSE
 */
static BOOL LISTVIEW_GetViewRect(const LISTVIEW_INFO *infoPtr, LPRECT lprcView)
{
    POINT ptOrigin;

    TRACE("(lprcView=%p)\n", lprcView);

    if (!lprcView) return FALSE;

    LISTVIEW_GetAreaRect(infoPtr, lprcView);

    if (infoPtr->uView != LV_VIEW_DETAILS)
    {
        LISTVIEW_GetOrigin(infoPtr, &ptOrigin);
        OffsetRect(lprcView, ptOrigin.x, ptOrigin.y);
    }

    TRACE("lprcView=%s\n", wine_dbgstr_rect(lprcView));

    return TRUE;
}

/***
 * DESCRIPTION:
 * Retrieves the subitem pointer associated with the subitem index.
 *
 * PARAMETER(S):
 * [I] hdpaSubItems : DPA handle for a specific item
 * [I] nSubItem : index of subitem
 *
 * RETURN:
 *   SUCCESS : subitem pointer
 *   FAILURE : NULL
 */
static SUBITEM_INFO* LISTVIEW_GetSubItemPtr(HDPA hdpaSubItems, INT nSubItem)
{
    SUBITEM_INFO *lpSubItem;
    INT i;

    /* we should binary search here if need be */
    for (i = 1; i < DPA_GetPtrCount(hdpaSubItems); i++)
    {
        lpSubItem = DPA_GetPtr(hdpaSubItems, i);
        if (lpSubItem->iSubItem == nSubItem)
            return lpSubItem;
    }

    return NULL;
}


/***
 * DESCRIPTION:
 * Calculates the desired item width.
 *
 * PARAMETER(S):
 * [I] infoPtr : valid pointer to the listview structure
 *
 * RETURN:
 *  The desired item width.
 */
static INT LISTVIEW_CalculateItemWidth(const LISTVIEW_INFO *infoPtr)
{
    INT nItemWidth = 0;

    TRACE("uView=%d\n", infoPtr->uView);

    if (infoPtr->uView == LV_VIEW_ICON)
        nItemWidth = infoPtr->iconSpacing.cx;
    else if (infoPtr->uView == LV_VIEW_DETAILS)
    {
        if (DPA_GetPtrCount(infoPtr->hdpaColumns) > 0)
        {
            RECT rcHeader;
            INT index;

            index = SendMessageW(infoPtr->hwndHeader, HDM_ORDERTOINDEX,
                                 DPA_GetPtrCount(infoPtr->hdpaColumns) - 1, 0);

            LISTVIEW_GetHeaderRect(infoPtr, index, &rcHeader);
            nItemWidth = rcHeader.right;
        }
    }
    else /* LV_VIEW_SMALLICON, or LV_VIEW_LIST */
    {
        WCHAR szDispText[DISP_TEXT_SIZE] = { '\0' };
        LVITEMW lvItem;
        INT i;

        lvItem.mask = LVIF_TEXT;
        lvItem.iSubItem = 0;

        for (i = 0; i < infoPtr->nItemCount; i++)
        {
            lvItem.iItem = i;
            lvItem.pszText = szDispText;
            lvItem.cchTextMax = DISP_TEXT_SIZE;
            if (LISTVIEW_GetItemW(infoPtr, &lvItem))
                nItemWidth = max(LISTVIEW_GetStringWidthT(infoPtr, lvItem.pszText, TRUE),
                                 nItemWidth);
        }

        if (infoPtr->himlSmall) nItemWidth += infoPtr->iconSize.cx; 
        if (infoPtr->himlState) nItemWidth += infoPtr->iconStateSize.cx;

        nItemWidth = max(DEFAULT_COLUMN_WIDTH, nItemWidth + WIDTH_PADDING);
    }

    return nItemWidth;
}

/***
 * DESCRIPTION:
 * Calculates the desired item height.
 *
 * PARAMETER(S):
 * [I] infoPtr : valid pointer to the listview structure
 *
 * RETURN:
 *  The desired item height.
 */
static INT LISTVIEW_CalculateItemHeight(const LISTVIEW_INFO *infoPtr)
{
    INT nItemHeight;

    TRACE("uView=%d\n", infoPtr->uView);

    if (infoPtr->uView == LV_VIEW_ICON)
        nItemHeight = infoPtr->iconSpacing.cy;
    else
    {
        nItemHeight = infoPtr->ntmHeight; 
        if (infoPtr->uView == LV_VIEW_DETAILS && infoPtr->dwLvExStyle & LVS_EX_GRIDLINES)
            nItemHeight++;
        if (infoPtr->himlState)
            nItemHeight = max(nItemHeight, infoPtr->iconStateSize.cy);
        if (infoPtr->himlSmall)
            nItemHeight = max(nItemHeight, infoPtr->iconSize.cy);
        if (infoPtr->himlState || infoPtr->himlSmall)
            nItemHeight += HEIGHT_PADDING;
    if (infoPtr->nMeasureItemHeight > 0)
        nItemHeight = infoPtr->nMeasureItemHeight;
    }

    return max(nItemHeight, 1);
}

/***
 * DESCRIPTION:
 * Updates the width, and height of an item.
 *
 * PARAMETER(S):
 * [I] infoPtr : valid pointer to the listview structure
 *
 * RETURN:
 *  None.
 */
static inline void LISTVIEW_UpdateItemSize(LISTVIEW_INFO *infoPtr)
{
    infoPtr->nItemWidth = LISTVIEW_CalculateItemWidth(infoPtr);
    infoPtr->nItemHeight = LISTVIEW_CalculateItemHeight(infoPtr);
}


/***
 * DESCRIPTION:
 * Retrieves and saves important text metrics info for the current
 * Listview font.
 *
 * PARAMETER(S):
 * [I] infoPtr : valid pointer to the listview structure
 *
 */
static void LISTVIEW_SaveTextMetrics(LISTVIEW_INFO *infoPtr)
{
    HDC hdc = GetDC(infoPtr->hwndSelf);
    HFONT hFont = infoPtr->hFont ? infoPtr->hFont : infoPtr->hDefaultFont;
    HFONT hOldFont = SelectObject(hdc, hFont);
    TEXTMETRICW tm;
    SIZE sz;

    if (GetTextMetricsW(hdc, &tm))
    {
        infoPtr->ntmHeight = tm.tmHeight;
        infoPtr->ntmMaxCharWidth = tm.tmMaxCharWidth;
    }

    if (GetTextExtentPoint32A(hdc, "...", 3, &sz))
        infoPtr->nEllipsisWidth = sz.cx;
        
    SelectObject(hdc, hOldFont);
    ReleaseDC(infoPtr->hwndSelf, hdc);
    
    TRACE("tmHeight=%d\n", infoPtr->ntmHeight);
}

/***
 * DESCRIPTION:
 * A compare function for ranges
 *
 * PARAMETER(S)
 * [I] range1 : pointer to range 1;
 * [I] range2 : pointer to range 2;
 * [I] flags : flags
 *
 * RETURNS:
 * > 0 : if range 1 > range 2
 * < 0 : if range 2 > range 1
 * = 0 : if range intersects range 2
 */
static INT CALLBACK ranges_cmp(LPVOID range1, LPVOID range2, LPARAM flags)
{
    INT cmp;
    
    if (((RANGE*)range1)->upper <= ((RANGE*)range2)->lower) 
        cmp = -1;
    else if (((RANGE*)range2)->upper <= ((RANGE*)range1)->lower) 
        cmp = 1;
    else 
        cmp = 0;

    TRACE("range1=%s, range2=%s, cmp=%d\n", debugrange(range1), debugrange(range2), cmp);

    return cmp;
}

#define ranges_check(ranges, desc) if (TRACE_ON(listview)) ranges_assert(ranges, desc, __FUNCTION__, __LINE__)

static void ranges_assert(RANGES ranges, LPCSTR desc, const char *func, int line)
{
    INT i;
    RANGE *prev, *curr;
    
    TRACE("*** Checking %s:%d:%s ***\n", func, line, desc);
    assert (ranges);
    assert (DPA_GetPtrCount(ranges->hdpa) >= 0);
    ranges_dump(ranges);
    if (DPA_GetPtrCount(ranges->hdpa) > 0)
    {
        prev = DPA_GetPtr(ranges->hdpa, 0);
        assert (prev->lower >= 0 && prev->lower < prev->upper);
        for (i = 1; i < DPA_GetPtrCount(ranges->hdpa); i++)
        {
            curr = DPA_GetPtr(ranges->hdpa, i);
            assert (prev->upper <= curr->lower);
            assert (curr->lower < curr->upper);
            prev = curr;
        }
    }
    TRACE("--- Done checking---\n");
}

static RANGES ranges_create(int count)
{
    RANGES ranges = Alloc(sizeof(struct tagRANGES));
    if (!ranges) return NULL;
    ranges->hdpa = DPA_Create(count);
    if (ranges->hdpa) return ranges;
    Free(ranges);
    return NULL;
}

static void ranges_clear(RANGES ranges)
{
    INT i;
        
    for(i = 0; i < DPA_GetPtrCount(ranges->hdpa); i++)
        Free(DPA_GetPtr(ranges->hdpa, i));
    DPA_DeleteAllPtrs(ranges->hdpa);
}


static void ranges_destroy(RANGES ranges)
{
    if (!ranges) return;
    ranges_clear(ranges);
    DPA_Destroy(ranges->hdpa);
    Free(ranges);
}

static RANGES ranges_clone(RANGES ranges)
{
    RANGES clone;
    INT i;
           
    if (!(clone = ranges_create(DPA_GetPtrCount(ranges->hdpa)))) goto fail;

    for (i = 0; i < DPA_GetPtrCount(ranges->hdpa); i++)
    {
        RANGE *newrng = Alloc(sizeof(RANGE));
        if (!newrng) goto fail;
        *newrng = *((RANGE*)DPA_GetPtr(ranges->hdpa, i));
        DPA_SetPtr(clone->hdpa, i, newrng);
    }
    return clone;
    
fail:
    TRACE ("clone failed\n");
    ranges_destroy(clone);
    return NULL;
}

static RANGES ranges_diff(RANGES ranges, RANGES sub)
{
    INT i;

    for (i = 0; i < DPA_GetPtrCount(sub->hdpa); i++)
        ranges_del(ranges, *((RANGE *)DPA_GetPtr(sub->hdpa, i)));

    return ranges;
}

static void ranges_dump(RANGES ranges)
{
    INT i;

    for (i = 0; i < DPA_GetPtrCount(ranges->hdpa); i++)
        TRACE("   %s\n", debugrange