listview.c

Go to the documentation of this file.

/*
 * 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-2015 Nikolay Sivov
 * Copyright 2009 Owen Rudge for CodeWeavers
 * Copyright 2012-2013 Daniel Jelinski
 *
 * 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
 *
 * 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_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 framing items (iterator_frameditems),
 *      and finding the 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
 *
 * 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
 *
 * 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
 */

#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;

  /* 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;
  BOOL autoSpacing;
  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;
#ifdef __REACTOS__
  BOOL bDefaultBkColor;
#endif

  /* 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 bDragging;
  POINT ptClickPos;         /* point where the user clicked */
  INT nLButtonDownItem;     /* tracks item to reset multiselection on WM_LBUTTONUP */
  DWORD dwHoverTime;
  HCURSOR hHotCursor;
  INT cWheelRemainder;

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

  /* painting */
  BOOL bIsDrawing;         /* Drawing in progress */
  INT nMeasureItemHeight;  /* WM_MEASUREITEM result */
  BOOL redraw;             /* 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)
{
    n = min(min(n, lstrlenW(s1)), lstrlenW(s2));
    return CompareStringW(LOCALE_USER_DEFAULT, NORM_IGNORECASE, s1, n, s2, n) - CSTR_EQUAL;
}

/******** 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=%u, ", 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, NMHEADERW *lpnmhW)
{
    LPCWSTR text = NULL, filter = NULL;
    LRESULT ret;
    NMHEADERA *lpnmh = (NMHEADERA*) lpnmhW;

    /* 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 */
    if (lpnmh->pitem)
    {
        /* convert item text */
        if (lpnmh->pitem->mask & HDI_TEXT)
        {
            text = (LPCWSTR)lpnmh->pitem->pszText;
            lpnmh->pitem->pszText = NULL;
            Str_SetPtrWtoA(&lpnmh->pitem->pszText, text);
        }
        /* convert filter text */
        if ((lpnmh->pitem->mask & HDI_FILTER) && (lpnmh->pitem->type == HDFT_ISSTRING) &&
             lpnmh->pitem->pvFilter)
        {
            filter = (LPCWSTR)((HD_TEXTFILTERA*)lpnmh->pitem->pvFilter)->pszText;
            ((HD_TEXTFILTERA*)lpnmh->pitem->pvFilter)->pszText = NULL;
            Str_SetPtrWtoA(&((HD_TEXTFILTERA*)lpnmh->pitem->pvFilter)->pszText, filter);
        }
    }
    lpnmh->hdr.code = get_ansi_notification(lpnmh->hdr.code);

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

    /* cleanup */
    if(text)
    {
        Free(lpnmh->pitem->pszText);
        lpnmh->pitem->pszText = (LPSTR)text;
    }
    if(filter)
    {
        Free(((HD_TEXTFILTERA*)lpnmh->pitem->pvFilter)->pszText);
        ((HD_TEXTFILTERA*)lpnmh->pitem->pvFilter)->pszText = (LPSTR)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;

    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);
}

/* Handles NM_DBLCLK, NM_CLICK, NM_RDBLCLK, NM_RCLICK. Only NM_RCLICK return value is used. */
static BOOL notify_click(const LISTVIEW_INFO *infoPtr, INT code, const LVHITTESTINFO *lvht)
{
    NMITEMACTIVATE nmia;
    LVITEMW item;
    HWND hwnd = infoPtr->hwndSelf;
    LRESULT ret;

    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;
    ret = notify_hdr(infoPtr, code, (NMHDR*)&nmia);
    return IsWindow(hwnd) && (code == NM_RCLICK ? !ret : TRUE);
}

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 dispinfo 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)
{
    COLORREF backcolor, textcolor;

    /* apparently, for selected items, we have to override the returned values */
    if (!SubItem || (infoPtr->dwLvExStyle & LVS_EX_FULLROWSELECT))
    {
        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;
            }
        }
    }

    backcolor = lpnmlvcd->clrTextBk;
    textcolor = lpnmlvcd->clrText;

    if (backcolor == CLR_DEFAULT)
        backcolor = comctl32_color.clrWindow;
    if (textcolor == CLR_DEFAULT)
        textcolor = comctl32_color.clrWindowText;

    /* Set the text attributes */
    if (backcolor != CLR_NONE)
    {
    SetBkMode(hdc, OPAQUE);
    SetBkColor(hdc, backcolor);
    }
    else
    SetBkMode(hdc, TRANSPARENT);
    SetTextColor(hdc, textcolor);
}

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 an
 * 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 iterator.
 */
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;
}

/* Remove common elements from two iterators */
/* Passed iterators have to point on the first elements */
static BOOL iterator_remove_common_items(ITERATOR *iter1, ITERATOR *iter2)
{
    if(!iter1->ranges || !iter2->ranges) {
        int lower, upper;

        if(iter1->ranges || iter2->ranges ||
                (iter1->range.lower<iter2->range.lower && iter1->range.upper>iter2->range.upper) ||
                (iter1->range.lower>iter2->range.lower && iter1->range.upper<iter2->range.upper)) {
            ERR("result is not a one range iterator\n");
            return FALSE;
        }

        if(iter1->range.lower==-1 || iter2->range.lower==-1)
            return TRUE;

        lower = iter1->range.lower;
        upper = iter1->range.upper;

        if(lower < iter2->range.lower)
            iter1->range.upper = iter2->range.lower;
        else if(upper > iter2->range.upper)
            iter1->range.lower = iter2->range.upper;
        else
            iter1->range.lower = iter1->range.upper = -1;

        if(iter2->range.lower < lower)
            iter2->range.upper = lower;
        else if(iter2->range.upper > upper)
            iter2->range.lower = upper;
        else
            iter2->range.lower = iter2->range.upper = -1;

        return TRUE;
    }

    iterator_next(iter1);
    iterator_next(iter2);

    while(1) {
        if(iter1->nItem==-1 || iter2->nItem==-1)
            break;

        if(iter1->nItem == iter2->nItem) {
            int delete = iter1->nItem;

            iterator_prev(iter1);
            iterator_prev(iter2);
            ranges_delitem(iter1->ranges, delete);
            ranges_delitem(iter2->ranges, delete);
            iterator_next(iter1);
            iterator_next(iter2);
        } else if(iter1->nItem > iter2->nItem)
            iterator_next(iter2);
        else
            iterator_next(iter1);
    }

    iter1->nItem = iter1->range.lower = iter1->range.upper = -1;
    iter2->nItem = iter2->range.lower = iter2->range.upper = -1;
    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->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);

    /* set header image list */
    if (infoPtr->himlSmall)
        SendMessageW(infoPtr->hwndHeader, HDM_SETIMAGELIST, 0, (LPARAM)infoPtr->himlSmall);

    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)
{
#ifdef __REACTOS__
    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;
#else
    return (infoPtr->rcFocus.left < infoPtr->rcFocus.right) ?
            DrawFocusRect(hdc, &infoPtr->rcFocus) : FALSE;
#endif
}

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

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

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];
    DWORD prevTime;
    LVITEMW item;
    int startidx;
    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;
    }

    /* 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)
    {
        /* with some accumulated search data available start with current focus, otherwise
           it's excluded from search */
        startidx = infoPtr->nSearchParamLength > 1 ? infoPtr->nFocusedItem : infoPtr->nFocusedItem + 1;
        if (startidx == infoPtr->nItemCount) startidx = 0;
    }
    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, endidx;

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

        /* 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))
                {
                    nItem = i;
                    break;
                }
                /* this is used to find first char match when search string is not available yet,
                   otherwise every WM_CHAR will search to next item by first char, ignoring that we're
                   already waiting for user to complete a string */
                else if (nItem == -1 && infoPtr->nSearchParamLength == 1 && !lstrncmpiW(item.pszText, infoPtr->szSearchParam, 1))
                {
                    /* 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);
}

static INT LISTVIEW_UpdateHScroll(LISTVIEW_INFO *infoPtr)
{
    SCROLLINFO horzInfo;
    INT dx;

    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));

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

    LISTVIEW_UpdateSize(infoPtr);
    return dx;
}

static INT LISTVIEW_UpdateVScroll(LISTVIEW_INFO *infoPtr)
{
    SCROLLINFO vertInfo;
    INT dy;

    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));

    LISTVIEW_UpdateSize(infoPtr);
    return dy;
}

/***
 * DESCRIPTION:
 * Update the scrollbars. This function 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(LISTVIEW_INFO *infoPtr)
{
    INT dx, dy, pass;

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

    /* Setting the horizontal scroll can change the listview size
     * (and potentially everything else) so we need to recompute
     * everything again for the vertical scroll and vice-versa
     */
    for (dx = 0, dy = 0, pass = 0; pass <= 1; pass++)
    {
        dx += LISTVIEW_UpdateHScroll(infoPtr);
        dy += LISTVIEW_UpdateVScroll(infoPtr);
    }

    /* 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);
    }
}


/***
 * 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_InvalidateItem(infoPtr, infoPtr->nFocusedItem);

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 ||
                 ((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->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->himlState)
        nItemHeight = max(nItemHeight, infoPtr->iconStateSize.cy);
    if (infoPtr->himlSmall)
        nItemHeight = max(nItemHeight, infoPtr->iconSize.cy);
    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, __FILE__, __LINE__)

static void ranges_assert(RANGES ranges, LPCSTR desc, const char *file, int line)
{
    INT i;
    RANGE *prev, *curr;
    
    TRACE("*** Checking %s:%d:%s ***\n", file, 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));
        if (!DPA_SetPtr(clone->hdpa, i, newrng))
        {
            Free(newrng);
            goto fail;
        }
    }
    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(DPA_GetPtr(ranges->hdpa, i)));
}

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

    TRACE("(nItem=%d)\n", nItem);
    ranges_check(ranges, "before contain");
    return DPA_Search(ranges->hdpa, &srchrng, 0, ranges_cmp, 0, DPAS_SORTED) != -1;
}

static INT ranges_itemcount(RANGES ranges)
{
    INT i, count = 0;
    
    for (i = 0; i < DPA_GetPtrCount(ranges->hdpa); i++)
    {
    RANGE *sel = DPA_GetPtr(ranges->hdpa, i);
    count += sel->upper - sel->lower;
    }

    return count;
}

static BOOL ranges_shift(RANGES ranges, INT nItem, INT delta, INT nUpper)
{
    RANGE srchrng = { nItem, nItem + 1 }, *chkrng;
    INT index;

    index = DPA_Search(ranges->hdpa, &srchrng, 0, ranges_cmp, 0, DPAS_SORTED | DPAS_INSERTAFTER);
    if (index == -1) return TRUE;

    for (; index < DPA_GetPtrCount(ranges->hdpa); index++)
    {
    chkrng = DPA_GetPtr(ranges->hdpa, index);
        if (chkrng->lower >= nItem)
        chkrng->lower = max(min(chkrng->lower + delta, nUpper - 1), 0);
        if (chkrng->upper > nItem)
        chkrng->upper = max(min(chkrng->upper + delta, nUpper), 0);
    }
    return TRUE;
}

static BOOL ranges_add(RANGES ranges, RANGE range)
{
    RANGE srchrgn;
    INT index;

    TRACE("(%s)\n", debugrange(&range));
    ranges_check(ranges, "before add");

    /* try find overlapping regions first */
    srchrgn.lower = range.lower - 1;
    srchrgn.upper = range.upper + 1;
    index = DPA_Search(ranges->hdpa, &srchrgn, 0, ranges_cmp, 0, DPAS_SORTED);
   
    if (index == -1)
    {
    RANGE *newrgn;

    TRACE("Adding new range\n");

    /* create the brand new range to insert */  
        newrgn = Alloc(sizeof(RANGE));
    if(!newrgn) goto fail;
    *newrgn = range;
    
    /* figure out where to insert it */
    index = DPA_Search(ranges->hdpa, newrgn, 0, ranges_cmp, 0, DPAS_SORTED | DPAS_INSERTAFTER);
    TRACE("index=%d\n", index);
    if (index == -1) index = 0;
    
    /* and get it over with */
    if (DPA_InsertPtr(ranges->hdpa, index, newrgn) == -1)
    {
        Free(newrgn);
        goto fail;
    }
    }
    else
    {
    RANGE *chkrgn, *mrgrgn;
    INT fromindex, mergeindex;

    chkrgn = DPA_GetPtr(ranges->hdpa, index);
    TRACE("Merge with %s @%d\n", debugrange(chkrgn), index);

    chkrgn->lower = min(range.lower, chkrgn->lower);
    chkrgn->upper = max(range.upper, chkrgn->upper);
    
    TRACE("New range %s @%d\n", debugrange(chkrgn), index);

        /* merge now common ranges */
    fromindex = 0;
    srchrgn.lower = chkrgn->lower - 1;
    srchrgn.upper = chkrgn->upper + 1;
        
    do
    {
        mergeindex = DPA_Search(ranges->hdpa, &srchrgn, fromindex, ranges_cmp, 0, 0);
        if (mergeindex == -1) break;
        if (mergeindex == index) 
        {
        fromindex = index + 1;
        continue;
        }
      
        TRACE("Merge with index %i\n", mergeindex);
        
        mrgrgn = DPA_GetPtr(ranges->hdpa, mergeindex);
        chkrgn->lower = min(chkrgn->lower, mrgrgn->lower);
        chkrgn->upper = max(chkrgn->upper, mrgrgn->upper);
        Free(mrgrgn);
        DPA_DeletePtr(ranges->hdpa, mergeindex);
        if (mergeindex < index) index --;
    } while(1);
    }

    ranges_check(ranges, "after add");
    return TRUE;
    
fail:
    ranges_check(ranges, "failed add");
    return FALSE;
}

static BOOL ranges_del(RANGES ranges, RANGE range)
{
    RANGE *chkrgn;
    INT index;

    TRACE("(%s)\n", debugrange(&range));
    ranges_check(ranges, "before del");

    /* we don't use DPAS_SORTED here, since we need *
     * to find the first overlapping range          */
    index = DPA_Search(ranges->hdpa, &range, 0, ranges_cmp, 0, 0);
    while(index != -1)
    {
    chkrgn = DPA_GetPtr(ranges->hdpa, index);

    TRACE("Matches range %s @%d\n", debugrange(chkrgn), index);

    /* case 1: Same range */
    if ( (chkrgn->upper == range.upper) &&
         (chkrgn->lower == range.lower) )
    {
        DPA_DeletePtr(ranges->hdpa, index);
        Free(chkrgn);
        break;
    }
    /* case 2: engulf */
    else if ( (chkrgn->upper <= range.upper) &&
          (chkrgn->lower >= range.lower) )
    {
        DPA_DeletePtr(ranges->hdpa, index);
        Free(chkrgn);
    }
    /* case 3: overlap upper */
    else if ( (chkrgn->upper <= range.upper) &&
          (chkrgn->lower < range.lower) )
    {
        chkrgn->upper = range.lower;
    }
    /* case 4: overlap lower */
    else if ( (chkrgn->upper > range.upper) &&
          (chkrgn->lower >= range.lower) )
    {
        chkrgn->lower = range.upper;
        break;
    }
    /* case 5: fully internal */
    else
    {
        RANGE *newrgn;

        if (!(newrgn = Alloc(sizeof(RANGE)))) goto fail;
        newrgn->lower = chkrgn->lower;
        newrgn->upper = range.lower;
        chkrgn->lower = range.upper;
        if (DPA_InsertPtr(ranges->hdpa, index, newrgn) == -1)
        {
        Free(newrgn);
        goto fail;
        }
        break;
    }

    index = DPA_Search(ranges->hdpa, &range, index, ranges_cmp, 0, 0);
    }

    ranges_check(ranges, "after del");
    return TRUE;

fail:
    ranges_check(ranges, "failed del");
    return FALSE;
}

/***
* DESCRIPTION:
* Removes all selection ranges
*
* Parameters(s):
* [I] infoPtr : valid pointer to the listview structure
* [I] toSkip : item range to skip removing the selection
*
* RETURNS:
*   SUCCESS : TRUE
*   FAILURE : FALSE
*/
static BOOL LISTVIEW_DeselectAllSkipItems(LISTVIEW_INFO *infoPtr, RANGES toSkip)
{
    LVITEMW lvItem;
    ITERATOR i;
    RANGES clone;

    TRACE("()\n");

    lvItem.state = 0;
    lvItem.stateMask = LVIS_SELECTED;
    
    /* need to clone the DPA because callbacks can change it */
    if (!(clone = ranges_clone(infoPtr->selectionRanges))) return FALSE;
    iterator_rangesitems(&i, ranges_diff(clone, toSkip));
    while(iterator_next(&i))
    LISTVIEW_SetItemState(infoPtr, i.nItem, &lvItem);
    /* note that the iterator destructor will free the cloned range */
    iterator_destroy(&i);

    return TRUE;
}

static inline BOOL LISTVIEW_DeselectAllSkipItem(LISTVIEW_INFO *infoPtr, INT nItem)
{
    RANGES toSkip;
   
    if (!(toSkip = ranges_create(1))) return FALSE;
    if (nItem != -1) ranges_additem(toSkip, nItem);
    LISTVIEW_DeselectAllSkipItems(infoPtr, toSkip);
    ranges_destroy(toSkip);
    return TRUE;
}

static inline BOOL LISTVIEW_DeselectAll(LISTVIEW_INFO *infoPtr)
{
    return LISTVIEW_DeselectAllSkipItem(infoPtr, -1);
}

/***
 * DESCRIPTION:
 * Retrieves the number of items that are marked as selected.
 *
 * PARAMETER(S):
 * [I] infoPtr : valid pointer to the listview structure
 *
 * RETURN:
 * Number of items selected.
 */
static INT LISTVIEW_GetSelectedCount(const LISTVIEW_INFO *infoPtr)
{
    INT nSelectedCount = 0;

    if (infoPtr->uCallbackMask & LVIS_SELECTED)
    {
        INT i;
    for (i = 0; i < infoPtr->nItemCount; i++)
    {
        if (LISTVIEW_GetItemState(infoPtr, i, LVIS_SELECTED))
        nSelectedCount++;
    }
    }
    else
    nSelectedCount = ranges_itemcount(infoPtr->selectionRanges);

    TRACE("nSelectedCount=%d\n", nSelectedCount);
    return nSelectedCount;
}

/***
 * DESCRIPTION:
 * Manages the item focus.
 *
 * PARAMETER(S):
 * [I] infoPtr : valid pointer to the listview structure
 * [I] nItem : item index
 *
 * RETURN:
 *   TRUE : focused item changed
 *   FALSE : focused item has NOT changed
 */
static inline BOOL LISTVIEW_SetItemFocus(LISTVIEW_INFO *infoPtr, INT nItem)
{
    INT oldFocus = infoPtr->nFocusedItem;
    LVITEMW lvItem;

    if (nItem == infoPtr->nFocusedItem) return FALSE;
    
    lvItem.state =  nItem == -1 ? 0 : LVIS_FOCUSED;
    lvItem.stateMask = LVIS_FOCUSED;
    LISTVIEW_SetItemState(infoPtr, nItem == -1 ? infoPtr->nFocusedItem : nItem, &lvItem);

    return oldFocus != infoPtr->nFocusedItem;
}

static INT shift_item(const LISTVIEW_INFO *infoPtr, INT nShiftItem, INT nItem, INT direction)
{
    if (nShiftItem < nItem) return nShiftItem;

    if (nShiftItem > nItem) return nShiftItem + direction;

    if (direction > 0) return nShiftItem + direction;

    return min(nShiftItem, infoPtr->nItemCount - 1);
}

/* This function updates focus index.

Parameters:
   focus : current focus index
   item : index of item to be added/removed
   direction : add/remove flag
*/
static void LISTVIEW_ShiftFocus(LISTVIEW_INFO *infoPtr, INT focus, INT item, INT direction)
{
    BOOL old_change = infoPtr->bDoChangeNotify;

    infoPtr->bDoChangeNotify = FALSE;
    focus = shift_item(infoPtr, focus, item, direction);
    if (focus != infoPtr->nFocusedItem)
        LISTVIEW_SetItemFocus(infoPtr, focus);
    infoPtr->bDoChangeNotify = old_change;
}

static void LISTVIEW_ShiftIndices(LISTVIEW_INFO *infoPtr, INT nItem, INT direction)
{
    TRACE("Shifting %i, %i steps\n", nItem, direction);

    ranges_shift(infoPtr->selectionRanges, nItem, direction, infoPtr->nItemCount);
    assert(abs(direction) == 1);
    infoPtr->nSelectionMark = shift_item(infoPtr, infoPtr->nSelectionMark, nItem, direction);

    /* But we are not supposed to modify nHotItem! */
}

static BOOL LISTVIEW_AddGroupSelection(LISTVIEW_INFO *infoPtr, INT nItem)
{
    INT nFirst = min(infoPtr->nSelectionMark, nItem);
    INT nLast = max(infoPtr->nSelectionMark, nItem);
    HWND hwndSelf = infoPtr->hwndSelf;
    NMLVODSTATECHANGE nmlv;
    LVITEMW item;
    BOOL bOldChange;
    INT i;

    /* Temporarily disable change notification
     * If the control is LVS_OWNERDATA, we need to send
     * only one LVN_ODSTATECHANGED notification.
     * See MSDN documentation for LVN_ITEMCHANGED.
     */
    bOldChange = infoPtr->bDoChangeNotify;
    if (infoPtr->dwStyle & LVS_OWNERDATA) infoPtr->bDoChangeNotify = FALSE;

    if (nFirst == -1) nFirst = nItem;

    item.state = LVIS_SELECTED;
    item.stateMask = LVIS_SELECTED;

    for (i = nFirst; i <= nLast; i++)
    LISTVIEW_SetItemState(infoPtr,i,&item);

    ZeroMemory(&nmlv, sizeof(nmlv));
    nmlv.iFrom = nFirst;
    nmlv.iTo = nLast;
    nmlv.uOldState = 0;
    nmlv.uNewState = item.state;

    notify_hdr(infoPtr, LVN_ODSTATECHANGED, (LPNMHDR)&nmlv);
    if (!IsWindow(hwndSelf))
        return FALSE;
    infoPtr->bDoChangeNotify = bOldChange;
    return TRUE;
}


/***
 * DESCRIPTION:
 * Sets a single group selection.
 *
 * PARAMETER(S):
 * [I] infoPtr : valid pointer to the listview structure
 * [I] nItem : item index
 *
 * RETURN:
 * None
 */
static void LISTVIEW_SetGroupSelection(LISTVIEW_INFO *infoPtr, INT nItem)
{
    RANGES selection;
    LVITEMW item;
    ITERATOR i;
    BOOL bOldChange;

    if (!(selection = ranges_create(100))) return;

    item.state = LVIS_SELECTED; 
    item.stateMask = LVIS_SELECTED;

    if ((infoPtr->uView == LV_VIEW_LIST) || (infoPtr->uView == LV_VIEW_DETAILS))
    {
    if (infoPtr->nSelectionMark == -1)
    {
        infoPtr->nSelectionMark = nItem;
        ranges_additem(selection, nItem);
    }
    else
    {
        RANGE sel;
        
        sel.lower = min(infoPtr->nSelectionMark, nItem);
        sel.upper = max(infoPtr->nSelectionMark, nItem) + 1;
        ranges_add(selection, sel);
    }
    }
    else
    {
    RECT rcItem, rcSel, rcSelMark;
    POINT ptItem;
    
    rcItem.left = LVIR_BOUNDS;
    if (!LISTVIEW_GetItemRect(infoPtr, nItem, &rcItem)) {
         ranges_destroy (selection);
         return;
    }
    rcSelMark.left = LVIR_BOUNDS;
    if (!LISTVIEW_GetItemRect(infoPtr, infoPtr->nSelectionMark, &rcSelMark)) {
         ranges_destroy (selection);
         return;
    }
    UnionRect(&rcSel, &rcItem, &rcSelMark);
    iterator_frameditems(&i, infoPtr, &rcSel);
    while(iterator_next(&i))
    {
        LISTVIEW_GetItemPosition(infoPtr, i.nItem, &ptItem);
        if (PtInRect(&rcSel, ptItem)) ranges_additem(selection, i.nItem);
    }
    iterator_destroy(&i);
    }

    /* disable per item notifications on LVS_OWNERDATA style
       FIXME: single LVN_ODSTATECHANGED should be used */
    bOldChange = infoPtr->bDoChangeNotify;
    if (infoPtr->dwStyle & LVS_OWNERDATA) infoPtr->bDoChangeNotify = FALSE;

    LISTVIEW_DeselectAllSkipItems(infoPtr, selection);


    iterator_rangesitems(&i, selection);
    while(iterator_next(&i))
    LISTVIEW_SetItemState(infoPtr, i.nItem, &item);
    /* this will also destroy the selection */
    iterator_destroy(&i);

    infoPtr->bDoChangeNotify = bOldChange;
    
    LISTVIEW_SetItemFocus(infoPtr, nItem);
}

/***
 * DESCRIPTION:
 * Sets a single selection.
 *
 * PARAMETER(S):
 * [I] infoPtr : valid pointer to the listview structure
 * [I] nItem : item index
 *
 * RETURN:
 * None
 */
static void LISTVIEW_SetSelection(LISTVIEW_INFO *infoPtr, INT nItem)
{
    LVITEMW lvItem;

    TRACE("nItem=%d\n", nItem);
    
    LISTVIEW_DeselectAllSkipItem(infoPtr, nItem);

    lvItem.state = LVIS_FOCUSED | LVIS_SELECTED;
    lvItem.stateMask = LVIS_FOCUSED | LVIS_SELECTED;
    LISTVIEW_SetItemState(infoPtr, nItem, &lvItem);

    infoPtr->nSelectionMark = nItem;
}

/***
 * DESCRIPTION:
 * Set selection(s) with keyboard.
 *
 * PARAMETER(S):
 * [I] infoPtr : valid pointer to the listview structure
 * [I] nItem : item index
 * [I] space : VK_SPACE code sent
 *
 * RETURN:
 *   SUCCESS : TRUE (needs to be repainted)
 *   FAILURE : FALSE (nothing has changed)
 */
static BOOL LISTVIEW_KeySelection(LISTVIEW_INFO *infoPtr, INT nItem, BOOL space)
{
  /* FIXME: pass in the state */
  WORD wShift = GetKeyState(VK_SHIFT) & 0x8000;
  WORD wCtrl = GetKeyState(VK_CONTROL) & 0x8000;
  BOOL bResult = FALSE;

  TRACE("nItem=%d, wShift=%d, wCtrl=%d\n", nItem, wShift, wCtrl);
  if ((nItem >= 0) && (nItem < infoPtr->nItemCount))
  {
    bResult = TRUE;

    if (infoPtr->dwStyle & LVS_SINGLESEL || (wShift == 0 && wCtrl == 0))
      LISTVIEW_SetSelection(infoPtr, nItem);
    else
    {
      if (wShift)
        LISTVIEW_SetGroupSelection(infoPtr, nItem);
      else if (wCtrl)
      {
        LVITEMW lvItem;
        lvItem.state = ~LISTVIEW_GetItemState(infoPtr, nItem, LVIS_SELECTED);
        lvItem.stateMask = LVIS_SELECTED;
        if (space)
        {
            LISTVIEW_SetItemState(infoPtr, nItem, &lvItem);
            if (lvItem.state & LVIS_SELECTED)
                infoPtr->nSelectionMark = nItem;
        }
        bResult = LISTVIEW_SetItemFocus(infoPtr, nItem);
      }
    }
    LISTVIEW_EnsureVisible(infoPtr, nItem, FALSE);
  }

  UpdateWindow(infoPtr->hwndSelf); /* update client area */
  return bResult;
}

static BOOL LISTVIEW_GetItemAtPt(const LISTVIEW_INFO *infoPtr, LPLVITEMW lpLVItem, POINT pt)
{
    LVHITTESTINFO lvHitTestInfo;

    ZeroMemory(&lvHitTestInfo, sizeof(lvHitTestInfo));
    lvHitTestInfo.pt.x = pt.x;
    lvHitTestInfo.pt.y = pt.y;

    LISTVIEW_HitTest(infoPtr, &lvHitTestInfo, TRUE, FALSE);

    lpLVItem->mask = LVIF_PARAM;
    lpLVItem->iItem = lvHitTestInfo.iItem;
    lpLVItem->iSubItem = 0;

    return LISTVIEW_GetItemT(infoPtr, lpLVItem, TRUE);
}

static inline BOOL LISTVIEW_IsHotTracking(const LISTVIEW_INFO *infoPtr)
{
    return ((infoPtr->dwLvExStyle & LVS_EX_TRACKSELECT) ||
            (infoPtr->dwLvExStyle & LVS_EX_ONECLICKACTIVATE) ||
            (infoPtr->dwLvExStyle & LVS_EX_TWOCLICKACTIVATE));
}

/***
 * DESCRIPTION:
 * Called when the mouse is being actively tracked and has hovered for a specified
 * amount of time
 *
 * PARAMETER(S):
 * [I] infoPtr : valid pointer to the listview structure
 * [I] fwKeys : key indicator
 * [I] x,y : mouse position
 *
 * RETURN:
 *   0 if the message was processed, non-zero if there was an error
 *
 * INFO:
 * LVS_EX_TRACKSELECT: An item is automatically selected when the cursor remains
 * over the item for a certain period of time.
 *
 */
static LRESULT LISTVIEW_MouseHover(LISTVIEW_INFO *infoPtr, INT x, INT y)
{
    NMHDR hdr;

    if (notify_hdr(infoPtr, NM_HOVER, &hdr)) return 0;

    if (LISTVIEW_IsHotTracking(infoPtr))
    {
        LVITEMW item;
        POINT pt;

        pt.x = x;
        pt.y = y;

        if (LISTVIEW_GetItemAtPt(infoPtr, &item, pt))
            LISTVIEW_SetSelection(infoPtr, item.iItem);

        SetFocus(infoPtr->hwndSelf);
    }

    return 0;
}

#define SCROLL_LEFT   0x1
#define SCROLL_RIGHT  0x2
#define SCROLL_UP     0x4
#define SCROLL_DOWN   0x8

/***
 * DESCRIPTION:
 * Utility routine to draw and highlight items within a marquee selection rectangle.
 *
 * PARAMETER(S):
 * [I] infoPtr     : valid pointer to the listview structure
 * [I] coords_orig : original co-ordinates of the cursor
 * [I] coords_offs : offsetted coordinates of the cursor
 * [I] offset      : offset amount
 * [I] scroll      : Bitmask of which directions we should scroll, if at all
 *
 * RETURN:
 *   None.
 */
static void LISTVIEW_MarqueeHighlight(LISTVIEW_INFO *infoPtr, const POINT *coords_orig,
                                      INT scroll)
{
    BOOL controlDown = FALSE;
    LVITEMW item;
    ITERATOR old_elems, new_elems;
    RECT rect;
    POINT coords_offs, offset;

    /* Ensure coordinates are within client bounds */
    coords_offs.x = max(min(coords_orig->x, infoPtr->rcList.right), 0);
    coords_offs.y = max(min(coords_orig->y, infoPtr->rcList.bottom), 0);

    /* Get offset */
    LISTVIEW_GetOrigin(infoPtr, &offset);

    /* Offset coordinates by the appropriate amount */
    coords_offs.x -= offset.x;
    coords_offs.y -= offset.y;

    if (coords_offs.x > infoPtr->marqueeOrigin.x)
    {
        rect.left = infoPtr->marqueeOrigin.x;
        rect.right = coords_offs.x;
    }
    else
    {
        rect.left = coords_offs.x;
        rect.right = infoPtr->marqueeOrigin.x;
    }

    if (coords_offs.y > infoPtr->marqueeOrigin.y)
    {
        rect.top = infoPtr->marqueeOrigin.y;
        rect.bottom = coords_offs.y;
    }
    else
    {
        rect.top = coords_offs.y;
        rect.bottom = infoPtr->marqueeOrigin.y;
    }

    /* Cancel out the old marquee rectangle and draw the new one */
    LISTVIEW_InvalidateRect(infoPtr, &infoPtr->marqueeDrawRect);

    /* Scroll by the appropriate distance if applicable - speed up scrolling as
       the cursor is further away */

    if ((scroll & SCROLL_LEFT) && (coords_orig->x <= 0))
        LISTVIEW_Scroll(infoPtr, coords_orig->x, 0);

    if ((scroll & SCROLL_RIGHT) && (coords_orig->x >= infoPtr->rcList.right))
        LISTVIEW_Scroll(infoPtr, (coords_orig->x - infoPtr->rcList.right), 0);

    if ((scroll & SCROLL_UP) && (coords_orig->y <= 0))
        LISTVIEW_Scroll(infoPtr, 0, coords_orig->y);

    if ((scroll & SCROLL_DOWN) && (coords_orig->y >= infoPtr->rcList.bottom))
        LISTVIEW_Scroll(infoPtr, 0, (coords_orig->y - infoPtr->rcList.bottom));

    iterator_frameditems_absolute(&old_elems, infoPtr, &infoPtr->marqueeRect);

    infoPtr->marqueeRect = rect;
    infoPtr->marqueeDrawRect = rect;
    OffsetRect(&infoPtr->marqueeDrawRect, offset.x, offset.y);

    iterator_frameditems_absolute(&new_elems, infoPtr, &infoPtr->marqueeRect);
    iterator_remove_common_items(&old_elems, &new_elems);

    /* Iterate over no longer selected items */
    while (iterator_next(&old_elems))
    {
        if (old_elems.nItem > -1)
        {
            if (LISTVIEW_GetItemState(infoPtr, old_elems.nItem, LVIS_SELECTED) == LVIS_SELECTED)
                item.state = 0;
            else
                item.state = LVIS_SELECTED;

            item.stateMask = LVIS_SELECTED;

            LISTVIEW_SetItemState(infoPtr, old_elems.nItem, &item);
        }
    }
    iterator_destroy(&old_elems);


    /* Iterate over newly selected items */
    if (GetKeyState(VK_CONTROL) & 0x8000)
        controlDown = TRUE;

    while (iterator_next(&new_elems))
    {
        if (new_elems.nItem > -1)
        {
            /* If CTRL is pressed, invert. If not, always select the item. */
            if ((controlDown) && (LISTVIEW_GetItemState(infoPtr, new_elems.nItem, LVIS_SELECTED)))
                item.state = 0;
            else
                item.state = LVIS_SELECTED;

            item.stateMask = LVIS_SELECTED;

            LISTVIEW_SetItemState(infoPtr, new_elems.nItem, &item);
        }
    }
    iterator_destroy(&new_elems);

    LISTVIEW_InvalidateRect(infoPtr, &infoPtr->marqueeDrawRect);
}

/***
 * DESCRIPTION:
 * Called when we are in a marquee selection that involves scrolling the listview (ie,
 * the cursor is outside the bounds of the client area). This is a TIMERPROC.
 *
 * PARAMETER(S):
 * [I] hwnd : Handle to the listview
 * [I] uMsg : WM_TIMER (ignored)
 * [I] idEvent : The timer ID interpreted as a pointer to a LISTVIEW_INFO struct
 * [I] dwTimer : The elapsed time (ignored)
 *
 * RETURN:
 *   None.
 */
static VOID CALLBACK LISTVIEW_ScrollTimer(HWND hWnd, UINT uMsg, UINT_PTR idEvent, DWORD dwTime)
{
    LISTVIEW_INFO *infoPtr;
    SCROLLINFO scrollInfo;
    POINT coords;
    INT scroll = 0;

    infoPtr = (LISTVIEW_INFO *) idEvent;

    if (!infoPtr)
        return;

    /* Get the current cursor position and convert to client coordinates */
    GetCursorPos(&coords);
    ScreenToClient(hWnd, &coords);

    scrollInfo.cbSize = sizeof(SCROLLINFO);
    scrollInfo.fMask = SIF_ALL;

    /* Work out in which directions we can scroll */
    if (GetScrollInfo(infoPtr->hwndSelf, SB_VERT, &scrollInfo))
    {
        if (scrollInfo.nPos != scrollInfo.nMin)
            scroll |= SCROLL_UP;

        if (((scrollInfo.nPage + scrollInfo.nPos) - 1) != scrollInfo.nMax)
            scroll |= SCROLL_DOWN;
    }

    if (GetScrollInfo(infoPtr->hwndSelf, SB_HORZ, &scrollInfo))
    {
        if (scrollInfo.nPos != scrollInfo.nMin)
            scroll |= SCROLL_LEFT;

        if (((scrollInfo.nPage + scrollInfo.nPos) - 1) != scrollInfo.nMax)
            scroll |= SCROLL_RIGHT;
    }

    if (((coords.x <= 0) && (scroll & SCROLL_LEFT)) ||
        ((coords.y <= 0) && (scroll & SCROLL_UP))   ||
        ((coords.x >= infoPtr->rcList.right) && (scroll & SCROLL_RIGHT)) ||
        ((coords.y >= infoPtr->rcList.bottom) && (scroll & SCROLL_DOWN)))
    {
        LISTVIEW_MarqueeHighlight(infoPtr, &coords, scroll);
    }
}

/***
 * DESCRIPTION:
 * Called whenever WM_MOUSEMOVE is received.
 *
 * PARAMETER(S):
 * [I] infoPtr : valid pointer to the listview structure
 * [I] fwKeys : key indicator
 * [I] x,y : mouse position
 *
 * RETURN:
 *   0 if the message is processed, non-zero if there was an error
 */
static LRESULT LISTVIEW_MouseMove(LISTVIEW_INFO *infoPtr, WORD fwKeys, INT x, INT y)
{
    LVHITTESTINFO ht;
    RECT rect;
    POINT pt;

    pt.x = x;
    pt.y = y;

    if (!(fwKeys & MK_LBUTTON))
        infoPtr->bLButtonDown = FALSE;

    if (infoPtr->bLButtonDown)
    {
        rect.left = rect.right = infoPtr->ptClickPos.x;
        rect.top = rect.bottom = infoPtr->ptClickPos.y;

        InflateRect(&rect, GetSystemMetrics(SM_CXDRAG), GetSystemMetrics(SM_CYDRAG));

        if (infoPtr->bMarqueeSelect)
        {
            /* Enable the timer if we're going outside our bounds, in case the user doesn't
               move the mouse again */

            if ((x <= 0) || (y <= 0) || (x >= infoPtr->rcList.right) ||
                (y >= infoPtr->rcList.bottom))
            {
                if (!infoPtr->bScrolling)
                {
                    infoPtr->bScrolling = TRUE;
                    SetTimer(infoPtr->hwndSelf, (UINT_PTR) infoPtr, 1, LISTVIEW_ScrollTimer);
                }
            }
            else
            {
                infoPtr->bScrolling = FALSE;
                KillTimer(infoPtr->hwndSelf, (UINT_PTR) infoPtr);
            }

            LISTVIEW_MarqueeHighlight(infoPtr, &pt, 0);
            return 0;
        }

        ht.pt = pt;
        LISTVIEW_HitTest(infoPtr, &ht, TRUE, TRUE);

        /* reset item marker */
        if (infoPtr->nLButtonDownItem != ht.iItem)
            infoPtr->nLButtonDownItem = -1;

        if (!PtInRect(&rect, pt))
        {
            /* this path covers the following:
               1. WM_LBUTTONDOWN over selected item (sets focus on it)
               2. change focus with keys
               3. move mouse over item from step 1 selects it and moves focus on it */
            if (infoPtr->nLButtonDownItem != -1 &&
               !LISTVIEW_GetItemState(infoPtr, infoPtr->nLButtonDownItem, LVIS_SELECTED))
            {
                LVITEMW lvItem;

                lvItem.state =  LVIS_FOCUSED | LVIS_SELECTED;
                lvItem.stateMask = LVIS_FOCUSED | LVIS_SELECTED;

                LISTVIEW_SetItemState(infoPtr, infoPtr->nLButtonDownItem, &lvItem);
                infoPtr->nLButtonDownItem = -1;
            }

            if (!infoPtr->bDragging)
            {
                ht.pt = infoPtr->ptClickPos;
                LISTVIEW_HitTest(infoPtr, &ht, TRUE, TRUE);

                /* If the click is outside the range of an item, begin a
                   highlight. If not, begin an item drag. */
                if (ht.iItem == -1)
                {
                    NMHDR hdr;

                    /* If we're allowing multiple selections, send notification.
                       If return value is non-zero, cancel. */
                    if (!(infoPtr->dwStyle & LVS_SINGLESEL) && (notify_hdr(infoPtr, LVN_MARQUEEBEGIN, &hdr) == 0))
                    {
                        /* Store the absolute coordinates of the click */
                        POINT offset;
                        LISTVIEW_GetOrigin(infoPtr, &offset);

                        infoPtr->marqueeOrigin.x = infoPtr->ptClickPos.x - offset.x;
                        infoPtr->marqueeOrigin.y = infoPtr->ptClickPos.y - offset.y;

                        /* Begin selection and capture mouse */
                        infoPtr->bMarqueeSelect = TRUE;
                        SetCapture(infoPtr->hwndSelf);
                    }
                }
                else
                {
                    NMLISTVIEW nmlv;

                    ZeroMemory(&nmlv, sizeof(nmlv));
                    nmlv.iItem = ht.iItem;
                    nmlv.ptAction = infoPtr->ptClickPos;

                    notify_listview(infoPtr, LVN_BEGINDRAG, &nmlv);
                    infoPtr->bDragging = TRUE;
                }
            }

            return 0;
        }
    }

    /* see if we are supposed to be tracking mouse hovering */
    if (LISTVIEW_IsHotTracking(infoPtr)) {
        TRACKMOUSEEVENT trackinfo;
        DWORD flags;

        trackinfo.cbSize = sizeof(TRACKMOUSEEVENT);
        trackinfo.dwFlags = TME_QUERY;

        /* see if we are already tracking this hwnd */
        _TrackMouseEvent(&trackinfo);

        flags = TME_LEAVE;
        if(infoPtr->dwLvExStyle & LVS_EX_TRACKSELECT)
            flags |= TME_HOVER;

        if((trackinfo.dwFlags & flags) != flags || trackinfo.hwndTrack != infoPtr->hwndSelf) {
            trackinfo.dwFlags     = flags;
            trackinfo.dwHoverTime = infoPtr->dwHoverTime;
            trackinfo.hwndTrack   = infoPtr->hwndSelf;

            /* call TRACKMOUSEEVENT so we receive WM_MOUSEHOVER messages */
            _TrackMouseEvent(&trackinfo);
        }
    }

    return 0;
}


/***
 * Tests whether the item is assignable to a list with style lStyle
 */
static inline BOOL is_assignable_item(const LVITEMW *lpLVItem, LONG lStyle)
{
    if ( (lpLVItem->mask & LVIF_TEXT) && 
    (lpLVItem->pszText == LPSTR_TEXTCALLBACKW) &&
    (lStyle & (LVS_SORTASCENDING | LVS_SORTDESCENDING)) ) return FALSE;
    
    return TRUE;
}


/***
 * DESCRIPTION:
 * Helper for LISTVIEW_SetItemT and LISTVIEW_InsertItemT: sets item attributes.
 *
 * PARAMETER(S):
 * [I] infoPtr : valid pointer to the listview structure
 * [I] lpLVItem : valid pointer to new item attributes
 * [I] isNew : the item being set is being inserted
 * [I] isW : TRUE if lpLVItem is Unicode, FALSE if it's ANSI
 * [O] bChanged : will be set to TRUE if the item really changed
 *
 * RETURN:
 *   SUCCESS : TRUE
 *   FAILURE : FALSE
 */
static BOOL set_main_item(LISTVIEW_INFO *infoPtr, const LVITEMW *lpLVItem, BOOL isNew, BOOL isW, BOOL *bChanged)
{
    ITEM_INFO *lpItem;
    NMLISTVIEW nmlv;
    UINT uChanged = 0;
    LVITEMW item;
    /* stateMask is ignored for LVM_INSERTITEM */
    UINT stateMask = isNew ? ~0 : lpLVItem->stateMask;

    TRACE("()\n");

    assert(lpLVItem->iItem >= 0 && lpLVItem->iItem < infoPtr->nItemCount);
    
    if (lpLVItem->mask == 0) return TRUE;   

    if (infoPtr->dwStyle & LVS_OWNERDATA)
    {
    /* a virtual listview only stores selection and focus */
    if (lpLVItem->mask & ~LVIF_STATE)
        return FALSE;
    lpItem = NULL;
    }
    else
    {
        HDPA hdpaSubItems = DPA_GetPtr(infoPtr->hdpaItems, lpLVItem->iItem);
        lpItem = DPA_GetPtr(hdpaSubItems, 0);
    assert (lpItem);
    }

    /* we need to get the lParam and state of the item */
    item.iItem = lpLVItem->iItem;
    item.iSubItem = lpLVItem->iSubItem;
    item.mask = LVIF_STATE | LVIF_PARAM;
    item.stateMask = (infoPtr->dwStyle & LVS_OWNERDATA) ? LVIS_FOCUSED | LVIS_SELECTED : ~0;

    item.state = 0;
    item.lParam = 0;
    if (!isNew && !LISTVIEW_GetItemW(infoPtr, &item)) return FALSE;

    TRACE("oldState=%x, newState=%x\n", item.state, lpLVItem->state);
    /* determine what fields will change */    
    if ((lpLVItem->mask & LVIF_STATE) && ((item.state ^ lpLVItem->state) & stateMask & ~infoPtr->uCallbackMask))
    uChanged |= LVIF_STATE;

    if ((lpLVItem->mask & LVIF_IMAGE) && (lpItem->hdr.iImage != lpLVItem->iImage))
    uChanged |= LVIF_IMAGE;

    if ((lpLVItem->mask & LVIF_PARAM) && (lpItem->lParam != lpLVItem->lParam))
    uChanged |= LVIF_PARAM;

    if ((lpLVItem->mask & LVIF_INDENT) && (lpItem->iIndent != lpLVItem->iIndent))
    uChanged |= LVIF_INDENT;

    if ((lpLVItem->mask & LVIF_TEXT) && textcmpWT(lpItem->hdr.pszText, lpLVItem->pszText, isW))
    uChanged |= LVIF_TEXT;
   
    TRACE("change mask=0x%x\n", uChanged);
    
    memset(&nmlv, 0, sizeof(NMLISTVIEW));
    nmlv.iItem = lpLVItem->iItem;
    nmlv.uNewState = (item.state & ~stateMask) | (lpLVItem->state & stateMask);
    nmlv.uOldState = item.state;
    nmlv.uChanged = uChanged ? uChanged : lpLVItem->mask;
    nmlv.lParam = item.lParam;

    /* Send LVN_ITEMCHANGING notification, if the item is not being inserted
       and we are _NOT_ virtual (LVS_OWNERDATA), and change notifications
       are enabled. Even nothing really changed we still need to send this,
       in this case uChanged mask is just set to passed item mask. */
    if(lpItem && !isNew && infoPtr->bDoChangeNotify)
    {
      HWND hwndSelf = infoPtr->hwndSelf;

      if (notify_listview(infoPtr, LVN_ITEMCHANGING, &nmlv))
    return FALSE;
      if (!IsWindow(hwndSelf))
    return FALSE;
    }

    /* When item is inserted we need to shift existing focus index if new item has lower index. */
    if (isNew && (stateMask & ~infoPtr->uCallbackMask & LVIS_FOCUSED) &&
        /* this means we won't hit a focus change path later */
        ((uChanged & LVIF_STATE) == 0 || (!(lpLVItem->state & LVIS_FOCUSED) && (infoPtr->nFocusedItem != lpLVItem->iItem))))
    {
        if (infoPtr->nFocusedItem != -1 && (lpLVItem->iItem <= infoPtr->nFocusedItem))
            infoPtr->nFocusedItem++;
    }

    if (!uChanged) return TRUE;
    *bChanged = TRUE;

    /* copy information */
    if (lpLVItem->mask & LVIF_TEXT)
        textsetptrT(&lpItem->hdr.pszText, lpLVItem->pszText, isW);

    if (lpLVItem->mask & LVIF_IMAGE)
    lpItem->hdr.iImage = lpLVItem->iImage;

    if (lpLVItem->mask & LVIF_PARAM)
    lpItem->lParam = lpLVItem->lParam;

    if (lpLVItem->mask & LVIF_INDENT)
    lpItem->iIndent = lpLVItem->iIndent;

    if (uChanged & LVIF_STATE)
    {
    if (lpItem && (stateMask & ~infoPtr->uCallbackMask))
    {
        lpItem->state &= ~stateMask;
        lpItem->state |= (lpLVItem->state & stateMask);
    }
    if (lpLVItem->state & stateMask & ~infoPtr->uCallbackMask & LVIS_SELECTED)
    {
        if (infoPtr->dwStyle & LVS_SINGLESEL) LISTVIEW_DeselectAllSkipItem(infoPtr, lpLVItem->iItem);
        ranges_additem(infoPtr->selectionRanges, lpLVItem->iItem);
    }
    else if (stateMask & LVIS_SELECTED)
    {
        ranges_delitem(infoPtr->selectionRanges, lpLVItem->iItem);
    }
    /* If we are asked to change focus, and we manage it, do it.
           It's important to have all new item data stored at this point,
           because changing existing focus could result in a redrawing operation,
           which in turn could ask for disp data, application should see all data
           for inserted item when processing LVN_GETDISPINFO.

           The way this works application will see nested item change notifications -
           changed item notifications interrupted by ones from item losing focus. */
    if (stateMask & ~infoPtr->uCallbackMask & LVIS_FOCUSED)
    {
        if (lpLVItem->state & LVIS_FOCUSED)
        {
        /* update selection mark */
        if (infoPtr->nFocusedItem == -1 && infoPtr->nSelectionMark == -1)
            infoPtr->nSelectionMark = lpLVItem->iItem;

        if (infoPtr->nFocusedItem != -1)
        {
            /* remove current focus */
            item.mask  = LVIF_STATE;
            item.state = 0;
            item.stateMask = LVIS_FOCUSED;

            /* recurse with redrawing an item */
            LISTVIEW_SetItemState(infoPtr, infoPtr->nFocusedItem, &item);
        }

        infoPtr->nFocusedItem = lpLVItem->iItem;
            LISTVIEW_EnsureVisible(infoPtr, lpLVItem->iItem, infoPtr->uView == LV_VIEW_LIST);
        }
        else if (infoPtr->nFocusedItem == lpLVItem->iItem)
        {
            infoPtr->nFocusedItem = -1;
        }