Sections:
The namespace for all skiplists is CS.
This library has a total of 28 containers along with 5 delegate containers. See Feature Matrix for the functionality and runtime complexity of each container. There are two sets of documentation. There is the standard docs by clicking on "CLASSES" up above in the menu. There is also the grid version with the functionality of each container. This documentation can be accessed via the list of containers below.
For the containers that require a key with each element, there are four possible prefixes that can be combined for a total of 24 containers. Here are the possible prefixes in order.
All skiplist names end with SkipList.
Here are all the standard containers including those that are indexed.
The first 24 containers require a key. The last three do not use a key and support arbitrary positioning of elements as well as arbitrary indexing in logarithmic time.
IndexedTinySkiplist is exactly like IndexedSSkipList except that the level count is not included in the node and thus uses less memory. Although the runtime complexity is also identical, the timing of some operations may be slower as most operations will now scan from the top level every time. This is true of moving forward by an arbitrary amount. Short jumps will not be as efficient and will take the full logarithmic time instead of only going up a level or two before finding the correct element.
In other words, optimizations that were possible with IndexedSSkipList that make use of the level number will no longer be possible. These are mostly operations that have to do with random access.
This library also has a composite container called XBidiCompositeSkipList where you can build your own container to support multiple sortings and orderings on the same elements. The user declares internal delegate containers that define the type of ordering and sorting to be used.
The user has five delegate containers to choose from.
Note that the above containers must appear in that order with respect to their index into the delegate array.
Suppose we have the following data.
struct myData { int ID; int priority; };
Now suppose that we need to order N elements of myData in three different ways. We need to order by ID. We need to order by priority where we'd also like it to be indexable. And finally, we need to order by order of arrival.
What this means is that the same elements have three different orderings or sorted arrangement. We need to define our own container derived from XBidiCompositeSkipList and then have members for each of the delegate containers we need (one for each ordering).
// functor for comparing by ID template <class T, class Pr > class XPredID : std::binary_function<T, T, bool> { private: Pr pred; XPredID() {} public: XPredID(const Pr &pred) : pred(pred) {} bool operator()(const T &a, const T &b) const { return pred(a.ID,b.ID); } }; // functor for comparing by priority template <class T, class Pr > class XPredPriority : std::binary_function<T, T, bool> { private: Pr pred; XPredPriority() {} public: XPredPriority(const Pr &pred) : pred(pred) {} bool operator()(const T &a, const T &b) const { return pred(a.priority,b.priority); } }; class V : public CS::XBidiCompositeSkipList<myData,3,2> { public: typedef myData T; typedef XIndexedSkipList<0,V> TL0; // Order by arrival. typedef XMultiAutoSkipList<1,V, XPredPriority<T,std::less<T> > > TL1; // Order by priority. typedef XMultiSkipList<2,V, XPredID<T,std::less<T> > > TL2; // Order by ID. // Declare delegate containers TL0 ArrivalList; TL1 PriorityList; TL2 IDList; // Insert our delegate containers into the delegate container array. // And then initialize the internal linked list. V() : XBidiCompositeSkipList<myData,3,2>() { Containers[0] = &ArrivalList; Containers[1] = &PriorityList; Containers[2] = &IDList; data.InitData(); } };
Now you can use the delegate containers to manipulate the elements. Inserting should be done with the indexed list called ArrivalList. This is because you can insert the element where you want. And at the same time, because the other two lists use a key (ID and Priority), they will automatically be inserted at their correct position in their respective lists. If you have more than one indexed list, then the element will be inserted at the end (as if done by push_back()) for those other lists. You may then use move() to move them to their correct location in those other indexed lists.
The composite container has three template parameters. The first is the data type of the elements. Note that any keys used must be part of the element itself. The next parameter is how many delegate container your are declaring in total. In our example, there are three delegate containers. The final parameter is how many delegate containers are indexed. We have two. XIndexedSkipList and XMultiAutoSkipList are both indexable.
Now onto defining the types for each delegate container.
All delegate containers have the same first four parameters. Only delagate containers that use a key need a fifth parameter for the comparison predicate.
The first parameter is the index of the delegate container in the container array. Simply number from 0 to N. Make sure that XIndexedSkipList have the lowest indexes followed by XMultiAutoSkipList and finally XMultiSkipList.
The second parameter is the type of the element. It should be identical to the first paramater of the base class XBidiCompositeSkipList.
The third and fourth parameters should always be node_type and data_type. They are defined in the base class XBidiCompositeSkipList.
Containers that use a key require a fifth parameter to specify the comparison predicate. In our example, we supplied one to compare the priority and another to compare the ID.
One may now declare each delegate container.
In the constructor, make sure to add each delegate container into the Containers array in the correct location. Also invoke data.InitData() to initialize the internal linked list that contains all the nodes and elements.
The composite container is now ready to be used via its delegate containers. Almost all the same functionality as the standard skiplist containers will be available. Note that inserting and erasing elements will be slower as all the lists must be updated. But random access, searching and other functionality will retain their original runtime complexity.
One final detail is that with XIndexedSkipList, one should use move() and swap() methods to move and swap elements around. Not only is it faster than erase() and insert(), push_back(), push_front(), etc., but it's the only way to alter the list without also altering the other XIndexedSkipLists within the composite container. Even if you only have one XIndexedSkipList delegate container, using mave() and swap() is advised.
Iterators can be converted from one delegate container to another by using the iterator's copy constructor or the assignment operator.
All containers can increment iterators in constant time.
Double linked list will decrement iterators in constant time.
Single linked lists will decrement iterators in logarithmic time.
All indexed lists (this includes Auto type lists) can do random access in logarithmic time.
There are four kinds of iterators used in this library.
For standard iterator types and overview, please see SGI Documentation.
For all indexed list and Auto type lists, the iterator contains the current index of the current element. If you insert or erase an element that comes before the current iterator, then the current iterator will be partially invalidated. In other words, the index will no longer be valid although the iterator still points to the correct element. Call refresh() on the iterator to recalculate the index. This works in logarithmic time. Certain operations are still possible even when the iterator is partially invalidated. However, two operations are guaranteed to be supported in future versions.
All iterators that support indexing will have the getIndex() method as well as the read-only 'index' property.
Since all SkipList containers require a random number generator, the three classes responsible for this functionality must be included within your project. Those files are CSRNG.cpp, moa.cpp and r250.cpp.
One may create their own RNG class as well. Only the "unsigned int rand()" and "double drand()" methods need to be implemented. Look at CSRNG.cpp for an implementation. In such a case, the above three files need not be included.
Other than that, simply include the header file for the container you are using. All the containers are header files only (aside from the RNG of course). There are no .cpp files to add to the project.
Add the directories where the header files are for both the containers and RNG files. Then include the files directly without specifying the directory since the containers include a few other files in the same directory.
The containers are not thread safe as they all use the same random number generator instance. One may specify RNG_threaded as the RNG and a new instance (taking about 4K of RAM each) will be created for each container. This will allow each thread to safely use separate instances of any container.
One may create their own RNG class as well. Only the "unsigned int rand()" and "double drand()" methods need to be implemented.
However, one instance of a container may not be used by more than one thread at the same time under any circumstance. The container must be locked by a thread before using it in such cases.
The following issues are found in the library. They will be fixed or implemented in future versions.
TODO List. These are NOT implemented yet.
These are functionality changes that will happen in future versions.
If there are problems compiling the index property using Borland or MSVC++ compilers, use -DNOPROP or define the NOPROP macro globally. The property will still be there, but it will use generic C++ code instead of compiler specific code.
For gcc, use the following commands.
tar -jxvf csskiplist.tar.bz2 cd csskiplist make -f Makefile.gcc test
At the end, it will run tests on all the containers. If everything went well, it will list something like the result below without any failures. The amount of tests can change with future versions.
tests summary: ok:3910
For Borland, CodeGear or Embarcadero C++ Builder or C++ compilers based on C++ Builder, use the following commands. Unzip the package somewhere and then open a command line (Start Menu, Run... and type 'cmd' without quotes and click on OK) and then change into the csskiplist directory that you just unzipped.
make -f Makefile.bcc test
If you have problems linking, copy the ilink32.cfg file from your compiler's installation bin directory into the directory where the Makefile is located and try again.
At the end, it will run tests on all the containers. If everything went well, it will list something like the result below without any failures. The amount of tests can change with future versions.
tests summary: ok:3910
For all other compilers, include all the .cpp files in the rng and tests directories. Make sure to add the include directories of include, rng, tests, tut-include.
Then make the project and run the executable.
Much of the documentation is based on the existing documentation at SGI. Therefore we place all documentation for the SkipList library under the same license. Note that ONLY the documentation is placed under this license. The software is under the Apache License Version 2. Also note that SGI and HP only speak of their own software and not of any software created by Cleo Saulnier, the author of the SkipList library.
Here is a copy of the documentation license.
Copyright (c) 2010 Cleo Saulnier cleosaulnier [at] yahoo.com
Permission to use, copy, modify, distribute and sell this documentation for any purpose is hereby granted without fee, provided that the above copyright notice appears in all copies and that both that copyright notice and this permission notice appear in supporting documentation. Cleo Saulnier makes no representations about the suitability of this documentation for any purpose. It is provided "as is" without express or implied warranty.
This license applies to the CS::SkipList Library documentation only. HP and SGI software and documentation fall under their licenses below.
Copyright (c) 1996-1999 Silicon Graphics Computer Systems, Inc.
Permission to use, copy, modify, distribute and sell this software and its documentation for any purpose is hereby granted without fee, provided that the above copyright notice appears in all copies and that both that copyright notice and this permission notice appear in supporting documentation. Silicon Graphics makes no representations about the suitability of this software for any purpose. It is provided "as is" without express or implied warranty.
Copyright (c) 1994 Hewlett-Packard Company
Permission to use, copy, modify, distribute and sell this software and its documentation for any purpose is hereby granted without fee, provided that the above copyright notice appears in all copies and that both that copyright notice and this permission notice appear in supporting documentation. Hewlett-Packard Company makes no representations about the suitability of this software for any purpose. It is provided "as is" without express or implied warranty.
Here is a copy of the copyright notice for the CS::SkipList Library software.
Copyright 2010 Cleo Saulnier
Licensed under the Apache License, Version 2.0 (the "License"); you may not use this software except in compliance with the License. You may obtain a copy of the License at
http://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.
The r250 and MOA code for random number generation have separate licensing and may be used for any purpose.
See moa.cpp, moa.h, r250.cpp and r250.h for more details.
There are tests included with the CS::SkipList Library. These tests use the TUT unit test library. Only a portion of this library is included. The full library can be found here:
http://tut-framework.sourceforge.net/
Note that TUT is NOT part of the CS::SkipList Library. It is included for convenience in compiling the tests only. TUT is NOT required to use the CS::SkipList Library.
The license for TUT is as follows.
Copyright 2002-2006 Vladimir Dyuzhev Copyright 2007 Denis Kononenko Copyright 2008-2009 Michał Rzechonek
Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:
Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.
Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.
THIS SOFTWARE IS PROVIDED “AS IS” AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1.7.3
