(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::PrivateNotConstructibleImplementation::ChainedList< T, 0, NotConstructiblePolicy::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::PrivateNotConstructibleImplementation::ChainedList<T, 0, NotConstructiblePolicy::SearchPolicy<T> > Container::NotConstructible< 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);