(C) An X-Ryl669 project 2007
This document describes Unlimited Zooming Interface source code. UZI stands for Unlimited Zooming Interface, and source code license is
#include <Container.hpp>
Public Types | |
| typedef ::Container::PrivateGenericImplementation::Array< T, Policy, false > | Array |
| The array takes ownership of the element passed in. Pros : Fastest possible access time once constructed (as fast as pointer dereferencing). Element order is always preserved. Cons : Construction / Adding and Remove operations are slow because copying is done on per element basis For usage,
| |
| typedef ::Container::PrivateGenericImplementation::ChainedList< T, 4, PlainOldDataPolicy::SearchPolicy< T > > | ChainedList |
| ChainedList class usage. ChainedList is a template double chained list that allow high efficiency access and advantages of chained list. In usual chained list, parsing the list is an O(N) operation In this list, parsing the list is an O(N/M) operation. The list chains allocated blocks of M pointers. When accessing the i-th element, not all (i-1) elements are accessed, but only (j)/M elements are accessed with j being the minimum distance from both ends. (Example : For reach the 41st element in a usual list you have to cross the first 40 element. Here, if the array is 16 pointers wide, you will cross 2 array elements and 8 pointer elements, that is 10 operations, not 40) While appending data is almost a free operation [O(1)], inserting/removing data in such list impose accessing O(N) elements in the worst case in order to preserve list integrity. If insertion and removing are to be frequent compared to indexed access, then consider using Insert and Remove method instead of Add and Sub. Insert and Remove both loose list integrity, so next indexed access will be O(j) again, but then the list will act like any standard chained list. So, if you don't need to use these improvements, simply use the list in a usual way, via inserting and removing functions, it will act as an usual chained list. Another improvement with this list are the adding functions. You could insert pointer to an element in the list, and they will be deleted when list is deleted (usual owning chained list), OR, you can insert a element in the list, and a copy of it will be insert in the list and deleted. No need to know if you should delete the object. This list also provide very fast parsing system. If you want extremely fast access to the list call the ParseList method, that return the next pointer.
// Create a int based chained list ChainedList<int> myList0; // Create a int chained list, with 8 = 2^3 pointer wide blocks ChainedList<int, 3> myList1; // Add an element to list myList0.Add(3); // Or simply myList0.Add(new int(3)); myList1 += 45; // Access the i-th element cout << myList0[i]; // Remove the i-th list element myList0.Sub(i); myList0 -= 3; // To insert an element before the i-th position myList0.Insert(7896, i); // To swap 2 elements, at i and j position myList0.Swap(i,j); // Change an element value, in the i-th position myList0.Change(456,i); // To parse the list, first time, beginning with i-th // position int * a = myList0.Parse(i); // To parse the list, next time int * b = myList0.Parse(); // To find the position of an inserted element int pos = myList0.Find(456); | |
| typedef ::Container::PrivateGenericImplementation::IndexList< T, PlainOldDataPolicy::DefaultMemoryListPolicy< T >, false > | IndexList |
| The IndexList holds pointers to object passed in. Pros : Almost as fast as array's access time once constructed. Element order is always preserved. Cons : Construction / Adding and Remove operations are slow (but faster than array) because of some copying is done for each pointer in the list It's best if used like // Create an index list IndexList<MyObj> myList; myList.Append(new MyObj(something)); // This will delete the inserted object by using the selected policy (delete in this example) myList.Remove(0); myList.insertBefore(2, new MyObj(foo)); // Index can be out of range myList.insertBefore(0, new MyObj(bar)); // Get a reference on the list element const MyObj & ref = myList[1]; // Search for an element based on its address assert(1 == myList.indexOf(&ref)); // Search for an element based on its value (much slower) assert(1 == myList.indexOfMatching(ref)); Policy must follow the MemoryPolicy interface
| |
| typedef ::Container::PrivateGenericImplementation::Array<T, Policy, false> Container::PlainOldData< T, Policy >::Array |
The array takes ownership of the element passed in.
Pros : Fastest possible access time once constructed (as fast as pointer dereferencing). Element order is always preserved. Cons : Construction / Adding and Remove operations are slow because copying is done on per element basis
For usage,
| typedef ::Container::PrivateGenericImplementation::ChainedList<T, 4, PlainOldDataPolicy::SearchPolicy<T> > Container::PlainOldData< T, Policy >::ChainedList |
ChainedList class usage.
ChainedList is a template double chained list that allow high efficiency access and advantages of chained list.
In usual chained list, parsing the list is an O(N) operation In this list, parsing the list is an O(N/M) operation. The list chains allocated blocks of M pointers. When accessing the i-th element, not all (i-1) elements are accessed, but only (j)/M elements are accessed with j being the minimum distance from both ends.
(Example : For reach the 41st element in a usual list you have to cross the first 40 element. Here, if the array is 16 pointers wide, you will cross 2 array elements and 8 pointer elements, that is 10 operations, not 40)
While appending data is almost a free operation [O(1)], inserting/removing data in such list impose accessing O(N) elements in the worst case in order to preserve list integrity.
If insertion and removing are to be frequent compared to indexed access, then consider using Insert and Remove method instead of Add and Sub.
Insert and Remove both loose list integrity, so next indexed access will be O(j) again, but then the list will act like any standard chained list.
So, if you don't need to use these improvements, simply use the list in a usual way, via inserting and removing functions, it will act as an usual chained list.
Another improvement with this list are the adding functions. You could insert pointer to an element in the list, and they will be deleted when list is deleted (usual owning chained list), OR, you can insert a element in the list, and a copy of it will be insert in the list and deleted. No need to know if you should delete the object.
This list also provide very fast parsing system. If you want extremely fast access to the list call the ParseList method, that return the next pointer.
// Create a int based chained list ChainedList<int> myList0; // Create a int chained list, with 8 = 2^3 pointer wide blocks ChainedList<int, 3> myList1; // Add an element to list myList0.Add(3); // Or simply myList0.Add(new int(3)); myList1 += 45; // Access the i-th element cout << myList0[i]; // Remove the i-th list element myList0.Sub(i); myList0 -= 3; // To insert an element before the i-th position myList0.Insert(7896, i); // To swap 2 elements, at i and j position myList0.Swap(i,j); // Change an element value, in the i-th position myList0.Change(456,i); // To parse the list, first time, beginning with i-th // position int * a = myList0.Parse(i); // To parse the list, next time int * b = myList0.Parse(); // To find the position of an inserted element int pos = myList0.Find(456);
| typedef ::Container::PrivateGenericImplementation::IndexList<T, PlainOldDataPolicy::DefaultMemoryListPolicy<T>, false> Container::PlainOldData< T, Policy >::IndexList |
The IndexList holds pointers to object passed in.
Pros : Almost as fast as array's access time once constructed. Element order is always preserved. Cons : Construction / Adding and Remove operations are slow (but faster than array) because of some copying is done for each pointer in the list
It's best if used like
// Create an index list IndexList<MyObj> myList; myList.Append(new MyObj(something)); // This will delete the inserted object by using the selected policy (delete in this example) myList.Remove(0); myList.insertBefore(2, new MyObj(foo)); // Index can be out of range myList.insertBefore(0, new MyObj(bar)); // Get a reference on the list element const MyObj & ref = myList[1]; // Search for an element based on its address assert(1 == myList.indexOf(&ref)); // Search for an element based on its value (much slower) assert(1 == myList.indexOfMatching(ref));
Policy must follow the MemoryPolicy interface