// Selection.h #if _MSC_VER > 1000 #pragma once #endif // _MSC_VER > 1000 #ifndef Selectionh #define Selectionh #include "SList.h" #include "FixedArray.h" /* This class encapsulates complex selection behaviour with a simple interface. Multiple Selection Mode is the default, and the simplest process: The user can click on multiple objects to select them, you add a Long Identifier (ID) representing each item they selected to the SelectionSet object, and it holds the array for you. Querying the SelectionSet to see if an ID is selected is very fast (uses binary chop algorithm). Single Selection Mode allows the user to click the mouse over multiple items. Each time they click the mouse, a different item is highlighted. You simply add all the items to the SelectionSet and ask it to pick one to highlight. Each time the user clicks the mouse in the same area, you add all the items as before and ask the SelectionSet to pick one, and it will pick a different one. If the mouse moves a little and some of the objects are no longer close enough to the mouse, the SelectionSet will Still loop sensibly through the available objects. The renderer can know if it is supposed to draw an entity in it's selected state or not with as little overhead as possible. I've tried separating the Single and Multi select as classes derived from a SelectionBase class but the final polymorphic class is slower than this. Normally, for Multiple Selection: Toggle(i) would be called when the user has clicked on an entity. Has(i) would be called by the renderer when deciding how to draw an Entity (selected or not). You can get at the Selection Array with GetArray() or access individual elements with operator[]. For Single Selection: The user clicks (once) and it is possible that many overlapping Entities are selectable. Add(i) would be called many times, once for each overlapping Entity. When all the Entities are added, OnSelChanged() is called which chooses one of the Entites to select. Has(i) would be called by the renderer when deciding how to draw an entity (selected or not). If the user didn't get the Entity they wanted, they may click again and the next call to OnSelChanged() will select a different Entity. The order of cyclic selection is the reverse order of the ID integer and is unlikely to relate to the topology. If the user clicks where nothing is selectable, OnSelChanged() is called with Entites Empty which clears the selection. */ class CSelection { protected: struct CEntity { // Used to hold a List of IDs of selected entities int i; // The ID of this Entity. CEntity(int i) : i(i) {} int Compare(const CEntity& e) const {return i-e.i;} }; CSList Entities; // Selected Entities. // Single Selection with Cycling: int ID; // Single selection so we don't bother using Array. CSList History; // Circular Queue of Selected Entities. // Multi-selection: mutable CFixedArray Array; // A cached snapshot of the Entities which provides fast searches for renderers. mutable bool Cached; bool Single; public: CSelection(bool Single=false) : Cached(false), Single(Single), ID(INT_MAX) {} CSelection(int Count, const int* Array, bool Single=false) : Cached(false), Single(Single), ID(INT_MAX) {Append(Count, Array);} virtual ~CSelection() {try{SetSingle(false);}catch(...){ASSERT(0);}} bool IsSingle() const {return Single;} void SetSingle(bool _Single=true) { // Used to change between Multi-Select and Single-Select Modes. Single=_Single; History.Empty(); Empty(); } void Empty() { Entities.Empty(); Array.Empty(); Cached=false; ID=INT_MAX; } void Append(int Count, const int* Array) {while(Count--) Add(*Array++);} // Adds many items from an Array: bool Toggle(int i) {Cached=false; return Entities.Delete(i) ? false : Add(i);} // Flip selected state. Returns true if i is left selected. bool Add(int i) { // Returns true if Added i if(Entities.Find(i)) return false; // Already in. Cached=false; return Entities.Append(new CEntity(i)); // First one added stays as first in list. } bool Remove(int i) { // Returns true if Removed i. if(!Entities.Find(i)) return false; // Not found. Cached=false; return Entities.Delete(i); } bool IsEmpty() const {return GetCount()==0;} int GetCount() const {return Single ? (ID!=INT_MAX) : Entities.GetCount();} bool Has(int i) const {Cache(); return Single ? (ID==i) : Array.Find(i);} // Very fast "Find" function for Renderers. const int* GetArray() const {Cache(); return Single ? &ID : Array.Data ;} int operator[](int i) const {Cache(); return Single ? ID : Array.Data[i];} void Cache() const { // Copy the Entities List to the Sorted Array for fast searching using Has(i); if(Cached) return; CSList Sorted; // A sorted List of pointers into the Selected Entities List. CSListConstIterator it(Entities); while(it) Sorted.Insert(it++.GetData()); // Insertion sort the Entities list by ID for fast find during Render Array.SetSize(Entities.GetCount()); int* dst=Array.Data; // Copy the sorted data to the Array: for(it.Set(Sorted); it; *dst++=it++->i); Sorted.DropAll(); // Don't delete the Data: it's still owned by the Entities List! Cached=true; } void OnSelChanged() { // Called in Single Selection Mode to cycle through the Selectable entities: if(!Single) return; if(Entities.IsEmpty()) { ID=INT_MAX; return; } bool NewSet=History.IsEmpty(); if(!NewSet) { // Subsequent clicks put new Entities at the front: NewSet=true; // Assumes we don't find any Entities in the History. History.Rotate(); // Make the current selection the last in the list for(CSListIterator it(Entities); it; ++it) { if(History.Find(it->i)) NewSet=false; // We found an Entity in the History so don't clear the History. else History.Add(new CEntity(it->i)); // Add any new Entities } } if(NewSet) { // For the first selection we must maintain the list order: History.Empty(); // Done here for when the latest Entities bear no relation to the History. for(CSListIterator it(Entities); it; ++it) History.Append(new CEntity(it->i)); // Add any new Entities } while(!Entities.Find(History->i)) History.Rotate(); // Find the next one in the History list ID=History->i; } }; #ifdef Assert static struct CSelectionTester : Tester, public CSelection { CSelectionTester() { // Test Multi-selecting with Toggle: Assert(IsEmpty()); Toggle(1); Assert( GetCount()==1); Assert(!IsEmpty()); Assert( Has(1)); Assert(!Has(2)); Assert(!Has(3)); Assert( Toggle(2)); Assert( GetCount()==2); Assert( Has(1)); Assert( Has(2)); Assert(!Has(3)); Assert( Toggle(3)); Assert( GetCount()==3); Assert( Has(1)); Assert( Has(2)); Assert(!Toggle(2)); Assert( GetCount()==2); Assert( Has(1)); Assert(!Has(2)); Assert( Has(3)); Assert(!Toggle(1)); Assert( GetCount()==1); Assert(!Has(1)); Assert(!Has(2)); Assert( Has(3)); Assert(!IsEmpty()); Empty(); Assert( IsEmpty()); // Test Multi-selecting with Add and Remove: Add(1); Assert( GetCount()==1); Assert(!IsEmpty()); Assert( Has(1)); Assert(!Has(2)); Assert(!Has(3)); Add(2); Assert( GetCount()==2); Assert( Has(1)); Assert( Has(2)); Assert(!Has(3)); Add(3); Assert( GetCount()==3); Assert( Has(1)); Assert( Has(2)); Remove(2); Assert( GetCount()==2); Assert( Has(1)); Assert(!Has(2)); Assert( Has(3)); Remove(1); Assert( GetCount()==1); Assert(!Has(1)); Assert(!Has(2)); Assert( Has(3)); Assert(!IsEmpty()); Remove(3); Assert( IsEmpty()); // Test Single Selection SetSingle(); Assert(IsEmpty()); Add(1); // 1 Add(2); // 1 2 Add(3); // 1 2 3 Assert( IsEmpty()); // Prior to OnSelChanged nothing should be selected. Assert(!Has(1)); OnSelChanged(); // New selection set Assert(!IsEmpty()); Assert( Has(1));// Picks the first one added Add(0); // 0 1 2 3 Add(4); // 0 1 2 3 4 OnSelChanged(); // Picks the last new value added Assert(Has(4)); Remove(0); // 1 2 3 4 Remove(2); // 1 3 4 Remove(3); // 1 4 OnSelChanged(); // Pick the other one remaining Assert(Has(1)); Remove(1); // 4 OnSelChanged(); // Selects only remaining entry Assert(Has(4)); OnSelChanged(); // Selection doesn't change Assert(Has(4)); Add(2); // 2 4 OnSelChanged(); // Selects new entry Assert(Has(2)); OnSelChanged(); // Toggles to other value Assert(Has(4)); Add(0); // 0 2 4 OnSelChanged(); // Extends the selection set Assert(Has(0)); Empty(); // Shouldn't effect the History Add(0); // 0 Add(2); // 0 2 Add(4); // 0 2 4 OnSelChanged(); Assert(Has(2)); // Remembers that 2 comes after 0 Empty(); Add(5); // 5 OnSelChanged(); // New selection set (No History Matches, so History gets cleared). Assert(Has(5)); Assert(Entities.GetCount()==1); Assert(History .GetCount()==1); } } SelectionTester; #endif // def Assert #endif // ndef Selectionh