EXP-1770 WIP Drag and drop visual selection can be off across hierarchies

made shift-selection work consistently across folder boundaries

4 files changed, 223 insertions, 188 deletions

diff --git a/indra/newview/llfolderview.cpp b/indra/newview/llfolderview.cpp
index ecd4c2c3de..3167c51970 100644
--- a/indra/newview/llfolderview.cpp
+++ b/indra/newview/llfolderview.cpp
@@ -349,10 +349,6 @@ BOOL LLFolderView::addFolder( LLFolderViewFolder* folder)
 	{
 		mFolders.insert(mFolders.begin(), folder);
 	}
-	if (folder->numSelected())
-	{
-		recursiveIncrementNumDescendantsSelected(folder->numSelected());
-	}
 	folder->setShowLoadStatus(mShowLoadStatus);
 	folder->setOrigin(0, 0);
 	folder->reshape(getRect().getWidth(), 0);
@@ -694,26 +690,6 @@ BOOL LLFolderView::changeSelection(LLFolderViewItem* selection, BOOL selected)
 	return rv;
 }
 
-void LLFolderView::extendSelection(LLFolderViewItem* selection, LLFolderViewItem* last_selected, LLDynamicArray<LLFolderViewItem*>& items)
-{
-	// now store resulting selection
-	if (mAllowMultiSelect)
-	{
-		LLFolderViewItem *cur_selection = getCurSelectedItem();
-		LLFolderViewFolder::extendSelection(selection, cur_selection, items);
-		for (S32 i = 0; i < items.count(); i++)
-		{
-			addToSelectionList(items[i]);
-		}
-	}
-	else
-	{
-		setSelection(selection, FALSE, FALSE);
-	}
-
-	mSignalSelectCallback = SIGNAL_KEYBOARD_FOCUS;
-}
-
 static LLFastTimer::DeclareTimer FTM_SANITIZE_SELECTION("Sanitize Selection");
 void LLFolderView::sanitizeSelection()
 {
diff --git a/indra/newview/llfolderview.h b/indra/newview/llfolderview.h
index 8af01e9102..d4305a2fe2 100644
--- a/indra/newview/llfolderview.h
+++ b/indra/newview/llfolderview.h
@@ -106,6 +106,8 @@ public:
 	U32 getSortOrder() const;
 	BOOL isFilterModified();
 
+	bool getAllowMultiSelect() { return mAllowMultiSelect; }
+
 	// Close all folders in the view
 	void closeAllFolders();
 	void openTopLevelFolders();
@@ -141,8 +143,6 @@ public:
 	// children, and keeps track of selected objects.
 	virtual BOOL changeSelection(LLFolderViewItem* selection, BOOL selected);
 
-	virtual void extendSelection(LLFolderViewItem* selection, LLFolderViewItem* last_selected, LLDynamicArray<LLFolderViewItem*>& items);
-
 	virtual std::set<LLUUID> getSelectionList() const;
 
 	// make sure if ancestor is selected, descendents are not
@@ -156,7 +156,6 @@ public:
 	void setDraggingOverItem(LLFolderViewItem* item) { mDraggingOverItem = item; }
 	LLFolderViewItem* getDraggingOverItem() { return mDraggingOverItem; }
 
-
 	// deletion functionality
  	void removeSelectedItems();
 
diff --git a/indra/newview/llfolderviewitem.cpp b/indra/newview/llfolderviewitem.cpp
index f27fd035db..ca7e4bc1d0 100644
--- a/indra/newview/llfolderviewitem.cpp
+++ b/indra/newview/llfolderviewitem.cpp
@@ -386,13 +386,6 @@ void LLFolderViewItem::changeSelectionFromRoot(LLFolderViewItem* selection, BOOL
 	getRoot()->changeSelection(selection, selected);
 }
 
-void LLFolderViewItem::extendSelectionFromRoot(LLFolderViewItem* selection)
-{
-	LLDynamicArray<LLFolderViewItem*> selected_items;
-
-	getRoot()->extendSelection(selection, NULL, selected_items);
-}
-
 std::set<LLUUID> LLFolderViewItem::getSelectionList() const
 {
 	std::set<LLUUID> selection;
@@ -496,10 +489,6 @@ BOOL LLFolderViewItem::setSelection(LLFolderViewItem* selection, BOOL openitem,
 	if (selection == this && !mIsSelected)
 	{
 		selectItem();
-		if (mListener)
-		{
-			mListener->selectItem();
-		}
 	}
 	else if (mIsSelected)	// Deselect everything else.
 	{
@@ -520,10 +509,6 @@ BOOL LLFolderViewItem::changeSelection(LLFolderViewItem* selection, BOOL selecte
 		{
 			selectItem();
 		}
-		if (mListener)
-		{
-			mListener->selectItem();
-		}
 		return TRUE;
 	}
 	return FALSE;
@@ -531,30 +516,16 @@ BOOL LLFolderViewItem::changeSelection(LLFolderViewItem* selection, BOOL selecte
 
 void LLFolderViewItem::deselectItem(void)
 {
-	llassert(mIsSelected);
-
 	mIsSelected = FALSE;
-
-	// Update ancestors' count of selected descendents.
-	LLFolderViewFolder* parent_folder = getParentFolder();
-	if (parent_folder)
-	{
-		parent_folder->recursiveIncrementNumDescendantsSelected(-1);
-	}
 }
 
 void LLFolderViewItem::selectItem(void)
 {
-	llassert(!mIsSelected);
-
-	mIsSelected = TRUE;
-
-	// Update ancestors' count of selected descendents.
-	LLFolderViewFolder* parent_folder = getParentFolder();
-	if (parent_folder)
+	if (mListener)
 	{
-		parent_folder->recursiveIncrementNumDescendantsSelected(1);
+		mListener->selectItem();
 	}
+	mIsSelected = TRUE;
 }
 
 BOOL LLFolderViewItem::isMovable()
@@ -697,7 +668,7 @@ BOOL LLFolderViewItem::handleMouseDown( S32 x, S32 y, MASK mask )
 		}
 		else if (mask & MASK_SHIFT)
 		{
-			extendSelectionFromRoot(this);
+			getParentFolder()->extendSelectionTo(this);
 		}
 		else
 		{
@@ -812,7 +783,7 @@ BOOL LLFolderViewItem::handleMouseUp( S32 x, S32 y, MASK mask )
 		}
 		else if (mask & MASK_SHIFT)
 		{
-			extendSelectionFromRoot(this);
+			getParentFolder()->extendSelectionTo(this);
 		}
 		else
 		{
@@ -1125,7 +1096,6 @@ void LLFolderViewItem::draw()
 
 LLFolderViewFolder::LLFolderViewFolder( const LLFolderViewItem::Params& p ): 
 	LLFolderViewItem( p ),	// 0 = no create time
-	mNumDescendantsSelected(0),
 	mIsOpen(FALSE),
 	mExpanderHighlighted(FALSE),
 	mCurHeight(0.f),
@@ -1572,21 +1542,6 @@ BOOL LLFolderViewFolder::hasFilteredDescendants()
 	return mMostFilteredDescendantGeneration >= getRoot()->getFilter()->getCurrentGeneration();
 }
 
-void LLFolderViewFolder::recursiveIncrementNumDescendantsSelected(S32 increment)
-{
-	LLFolderViewFolder* parent_folder = this;
-	do
-	{
-		parent_folder->mNumDescendantsSelected += increment;
-
-		// Make sure we don't have negative values.
-		llassert(parent_folder->mNumDescendantsSelected >= 0);
-
-		parent_folder = parent_folder->getParentFolder();
-	}
-	while(parent_folder);
-}
-
 // Passes selection information on to children and record selection
 // information if necessary.
 BOOL LLFolderViewFolder::setSelection(LLFolderViewItem* selection, BOOL openitem,
@@ -1599,10 +1554,6 @@ BOOL LLFolderViewFolder::setSelection(LLFolderViewItem* selection, BOOL openitem
 		{
 			selectItem();
 		}
-		if (mListener)
-		{
-			mListener->selectItem();
-		}
 		rv = TRUE;
 	}
 	else
@@ -1663,10 +1614,6 @@ BOOL LLFolderViewFolder::changeSelection(LLFolderViewItem* selection, BOOL selec
 				deselectItem();
 			}
 		}
-		if (mListener && selected)
-		{
-			mListener->selectItem();
-		}
 	}
 
 	for (folders_t::iterator iter = mFolders.begin();
@@ -1690,119 +1637,261 @@ BOOL LLFolderViewFolder::changeSelection(LLFolderViewItem* selection, BOOL selec
 	return rv;
 }
 
-void LLFolderViewFolder::extendSelection(LLFolderViewItem* selection, LLFolderViewItem* last_selected, LLDynamicArray<LLFolderViewItem*>& selected_items)
+LLFolderViewFolder* LLFolderViewFolder::getCommonAncestor(LLFolderViewItem* item_a, LLFolderViewItem* item_b, bool& reverse)
 {
-	// pass on to child folders first
-	for (folders_t::iterator iter = mFolders.begin();
-		iter != mFolders.end();)
+	if (!item_a->getParentFolder() || !item_b->getParentFolder()) return NULL;
+
+	std::deque<LLFolderViewFolder*> item_a_ancestors;
+
+	LLFolderViewFolder* parent = item_a->getParentFolder();
+	while(parent)
 	{
-		folders_t::iterator fit = iter++;
-		(*fit)->extendSelection(selection, last_selected, selected_items);
+		item_a_ancestors.push_back(parent);
+		parent = parent->getParentFolder();
 	}
 
-	// handle selection of our immediate children...
-	BOOL reverse_select = FALSE;
-	BOOL found_last_selected = FALSE;
-	BOOL found_selection = FALSE;
-	LLDynamicArray<LLFolderViewItem*> items_to_select;
-	LLFolderViewItem* item;
+	std::deque<LLFolderViewFolder*> item_b_ancestors;
+	
+	parent = item_b->getParentFolder();
+	while(parent)
+	{
+		item_b_ancestors.push_back(parent);
+		parent = parent->getParentFolder();
+	}
 
-	//...folders first...
-	for (folders_t::iterator iter = mFolders.begin();
-		iter != mFolders.end();)
+	LLFolderViewFolder* common_ancestor = item_a->getRoot();
+
+	while(item_a_ancestors.size() > item_b_ancestors.size())
 	{
-		folders_t::iterator fit = iter++;
-		item = (*fit);
-		if(item == selection)
-		{
-			found_selection = TRUE;
-		}
-		else if (item == last_selected)
+		item_a = item_a_ancestors.front();
+		item_a_ancestors.pop_front();
+	}
+
+	while(item_b_ancestors.size() > item_a_ancestors.size())
+	{
+		item_b = item_b_ancestors.front();
+		item_b_ancestors.pop_front();
+	}
+
+	while(item_a_ancestors.size())
+	{
+		common_ancestor = item_a_ancestors.front();
+
+		if (item_a_ancestors.front() == item_b_ancestors.front())
 		{
-			found_last_selected = TRUE;
-			if (found_selection)
+			// which came first, sibling a or sibling b?
+			for (folders_t::iterator it = common_ancestor->mFolders.begin(), end_it = common_ancestor->mFolders.end();
+				it != end_it;
+				++it)
 			{
-				reverse_select = TRUE;
+				LLFolderViewItem* item = *it;
+
+				if (item == item_a)
+				{
+					reverse = false;
+					return common_ancestor;
+				}
+				if (item == item_b)
+				{
+					reverse = true;
+					return common_ancestor;
+				}
 			}
-		}
 
-		if (found_selection || found_last_selected)
-		{
-			// deselect currently selected items so they can be pushed back on queue
-			if (item->isSelected())
+			for (items_t::iterator it = common_ancestor->mItems.begin(), end_it = common_ancestor->mItems.end();
+				it != end_it;
+				++it)
 			{
-				item->changeSelection(item, FALSE);
+				LLFolderViewItem* item = *it;
+
+				if (item == item_a)
+				{
+					reverse = false;
+					return common_ancestor;
+				}
+				if (item == item_b)
+				{
+					reverse = true;
+					return common_ancestor;
+				}
 			}
-			items_to_select.put(item);
+			break;
 		}
 
-		if (found_selection && found_last_selected)
-		{
-			break;
-		}		
+		item_a = item_a_ancestors.front();
+		item_a_ancestors.pop_front();
+		item_b = item_b_ancestors.front();
+		item_b_ancestors.pop_front();
 	}
 
-	if (!(found_selection && found_last_selected))
+	return NULL;
+}
+
+void LLFolderViewFolder::gatherChildRangeExclusive(LLFolderViewItem* start, LLFolderViewItem* end, bool reverse, std::vector<LLFolderViewItem*>& items)
+{
+	bool selecting = start == NULL;
+	if (reverse)
 	{
-		//,,,then items
-		for (items_t::iterator iter = mItems.begin();
-			iter != mItems.end();)
+		for (items_t::reverse_iterator it = mItems.rbegin(), end_it = mItems.rend();
+			it != end_it;
+			++it)
 		{
-			items_t::iterator iit = iter++;
-			item = (*iit);
-			if(item == selection)
+			if (*it == end)
 			{
-				found_selection = TRUE;
+				return;
 			}
-			else if (item == last_selected)
+			if (selecting)
 			{
-				found_last_selected = TRUE;
-				if (found_selection)
-				{
-					reverse_select = TRUE;
-				}
+				items.push_back(*it);
 			}
 
-			if (found_selection || found_last_selected)
+			if (*it == start)
 			{
-				// deselect currently selected items so they can be pushed back on queue
-				if (item->isSelected())
-				{
-					item->changeSelection(item, FALSE);
-				}
-				items_to_select.put(item);
+				selecting = true;
+			}
+		}
+		for (folders_t::reverse_iterator it = mFolders.rbegin(), end_it = mFolders.rend();
+			it != end_it;
+			++it)
+		{
+			if (*it == end)
+			{
+				return;
 			}
 
-			if (found_selection && found_last_selected)
+			if (selecting)
 			{
-				break;
+				items.push_back(*it);
+			}
+
+			if (*it == start)
+			{
+				selecting = true;
 			}
 		}
 	}
-
-	if (found_last_selected && found_selection)
+	else
 	{
-		// we have a complete selection inside this folder
-		for (S32 index = reverse_select ? items_to_select.getLength() - 1 : 0; 
-			reverse_select ? index >= 0 : index < items_to_select.getLength(); reverse_select ? index-- : index++)
+		for (folders_t::iterator it = mFolders.begin(), end_it = mFolders.end();
+			it != end_it;
+			++it)
+		{
+			if (*it == end)
+			{
+				return;
+			}
+
+			if (selecting)
+			{
+				items.push_back(*it);
+			}
+
+			if (*it == start)
+			{
+				selecting = true;
+			}
+		}
+		for (items_t::iterator it = mItems.begin(), end_it = mItems.end();
+			it != end_it;
+			++it)
 		{
-			LLFolderViewItem* item = items_to_select[index];
-			if (item->changeSelection(item, TRUE))
+			if (*it == end)
+			{
+				return;
+			}
+
+			if (selecting)
+			{
+				items.push_back(*it);
+			}
+
+			if (*it == start)
 			{
-				selected_items.put(item);
+				selecting = true;
 			}
 		}
 	}
-	else if (found_selection)
+}
+
+void LLFolderViewFolder::extendSelectionTo(LLFolderViewItem* new_selection)
+{
+	if (getRoot()->getAllowMultiSelect() == FALSE) return;
+
+	LLFolderViewItem* cur_selected_item = getRoot()->getCurSelectedItem();
+	if (cur_selected_item == NULL)
+	{
+		cur_selected_item = new_selection;
+	}
+
+
+	bool reverse = false;
+	LLFolderViewFolder* common_ancestor = getCommonAncestor(cur_selected_item, new_selection, reverse);
+	if (!common_ancestor) return;
+
+	LLFolderViewItem* last_selected_item_from_cur = cur_selected_item;
+	LLFolderViewFolder* cur_folder = cur_selected_item->getParentFolder();
+
+	std::vector<LLFolderViewItem*> items_to_select_forward;
+
+	while(cur_folder != common_ancestor)
+	{
+		cur_folder->gatherChildRangeExclusive(last_selected_item_from_cur, NULL, reverse, items_to_select_forward);
+			
+		last_selected_item_from_cur = cur_folder;
+		cur_folder = cur_folder->getParentFolder();
+	}
+
+	std::vector<LLFolderViewItem*> items_to_select_reverse;
+
+	LLFolderViewItem* last_selected_item_from_new = new_selection;
+	cur_folder = new_selection->getParentFolder();
+	while(cur_folder != common_ancestor)
+	{
+		cur_folder->gatherChildRangeExclusive(last_selected_item_from_new, NULL, !reverse, items_to_select_reverse);
+
+		last_selected_item_from_new = cur_folder;
+		cur_folder = cur_folder->getParentFolder();
+	}
+
+	common_ancestor->gatherChildRangeExclusive(last_selected_item_from_cur, last_selected_item_from_new, reverse, items_to_select_forward);
+
+	for (std::vector<LLFolderViewItem*>::reverse_iterator it = items_to_select_reverse.rbegin(), end_it = items_to_select_reverse.rend();
+		it != end_it;
+		++it)
 	{
-		// last selection was not in this folder....go ahead and select just the new item
-		if (selection->changeSelection(selection, TRUE))
+		items_to_select_forward.push_back(*it);
+	}
+
+	LLFolderView* root = getRoot();
+
+	for (std::vector<LLFolderViewItem*>::iterator it = items_to_select_forward.begin(), end_it = items_to_select_forward.end();
+		it != end_it;
+		++it)
+	{
+		LLFolderViewItem* item = *it;
+		if (item->isSelected())
+		{
+			root->removeFromSelectionList(item);
+		}
+		else
 		{
-			selected_items.put(selection);
+			item->selectItem();
 		}
+		root->addToSelectionList(item);
 	}
+
+	if (new_selection->isSelected())
+	{
+		root->removeFromSelectionList(new_selection);
+	}
+	else
+	{
+		new_selection->selectItem();
+	}
+	root->addToSelectionList(new_selection);
 }
 
+
 void LLFolderViewFolder::destroyView()
 {
 	for (items_t::iterator iter = mItems.begin();
@@ -1874,19 +1963,11 @@ void LLFolderViewFolder::extractItem( LLFolderViewItem* item )
 		ft = std::find(mFolders.begin(), mFolders.end(), f);
 		if (ft != mFolders.end())
 		{
-			if ((*ft)->numSelected())
-			{
-				recursiveIncrementNumDescendantsSelected(-(*ft)->numSelected());
-			}
 			mFolders.erase(ft);
 		}
 	}
 	else
 	{
-		if ((*it)->isSelected())
-		{
-			recursiveIncrementNumDescendantsSelected(-1);
-		}
 		mItems.erase(it);
 	}
 	//item has been removed, need to update filter
@@ -2055,11 +2136,6 @@ BOOL LLFolderViewFolder::addItem(LLFolderViewItem* item)
 {
 	mItems.push_back(item);
 	
-	if (item->isSelected())
-	{
-		recursiveIncrementNumDescendantsSelected(1);
-	}
-	
 	item->setRect(LLRect(0, 0, getRect().getWidth(), 0));
 	item->setVisible(FALSE);
 	
@@ -2097,10 +2173,6 @@ BOOL LLFolderViewFolder::addItem(LLFolderViewItem* item)
 BOOL LLFolderViewFolder::addFolder(LLFolderViewFolder* folder)
 {
 	mFolders.push_back(folder);
-	if (folder->numSelected())
-	{
-		recursiveIncrementNumDescendantsSelected(folder->numSelected());
-	}
 	folder->setOrigin(0, 0);
 	folder->reshape(getRect().getWidth(), 0);
 	folder->setVisible(FALSE);
diff --git a/indra/newview/llfolderviewitem.h b/indra/newview/llfolderviewitem.h
index 3433e3f7f3..29c5b2246d 100644
--- a/indra/newview/llfolderviewitem.h
+++ b/indra/newview/llfolderviewitem.h
@@ -164,9 +164,6 @@ protected:
 	// helper function to change the selection from the root.
 	void changeSelectionFromRoot(LLFolderViewItem* selection, BOOL selected);
 
-	// helper function to change the selection from the root.
-	void extendSelectionFromRoot(LLFolderViewItem* selection);
-
 	// this is an internal method used for adding items to folders. A
 	// no-op at this level, but reimplemented in derived classes.
 	virtual BOOL addItem(LLFolderViewItem*) { return FALSE; }
@@ -224,9 +221,6 @@ public:
 	// Returns TRUE if the selection state of this item was changed.
 	virtual BOOL changeSelection(LLFolderViewItem* selection, BOOL selected);
 
-	// this method is used to group select items
-	virtual void extendSelection(LLFolderViewItem* selection, LLFolderViewItem* last_selected, LLDynamicArray<LLFolderViewItem*>& items) { }
-
 	// this method is used to deselect this element
 	void deselectItem();
 
@@ -373,13 +367,6 @@ public:
 	typedef std::list<LLFolderViewItem*> items_t;
 	typedef std::list<LLFolderViewFolder*> folders_t;
 
-private:
-	S32		mNumDescendantsSelected;
-
-public:		// Accessed needed by LLFolderViewItem
-	void recursiveIncrementNumDescendantsSelected(S32 increment);
-	S32 numSelected(void) const { return mNumDescendantsSelected + (isSelected() ? 1 : 0); }
-
 protected:
 	items_t mItems;
 	folders_t mFolders;
@@ -461,7 +448,7 @@ public:
 	virtual BOOL changeSelection(LLFolderViewItem* selection, BOOL selected);
 
 	// this method is used to group select items
-	virtual void extendSelection(LLFolderViewItem* selection, LLFolderViewItem* last_selected, LLDynamicArray<LLFolderViewItem*>& items);
+	void extendSelectionTo(LLFolderViewItem* selection);
 
 	// Returns true is this object and all of its children can be removed.
 	virtual BOOL isRemovable();
@@ -551,7 +538,6 @@ public:
 
 	time_t getCreationDate() const;
 	bool isTrash() const;
-	S32 getNumSelectedDescendants(void) const { return mNumDescendantsSelected; }
 
 	folders_t::const_iterator getFoldersBegin() const { return mFolders.begin(); }
 	folders_t::const_iterator getFoldersEnd() const { return mFolders.end(); }
@@ -560,6 +546,8 @@ public:
 	items_t::const_iterator getItemsBegin() const { return mItems.begin(); }
 	items_t::const_iterator getItemsEnd() const { return mItems.end(); }
 	items_t::size_type getItemsCount() const { return mItems.size(); }
+	LLFolderViewFolder* getCommonAncestor(LLFolderViewItem* item_a, LLFolderViewItem* item_b, bool& reverse);
+	void gatherChildRangeExclusive(LLFolderViewItem* start, LLFolderViewItem* end, bool reverse,  std::vector<LLFolderViewItem*>& items);
 };
 
 //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~