|
|
The test cases, which are not directly part of the library, are published under the The GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version.
The code of the PBL library includes the following modules:
PBL BASE - Some base functions, see pbl_* functions,
PBL COLLECTION - An open source C implementation of a collection used by the list and set implementations.
PBL LIST - An open source C implementation of array lists and linked lists similar to the Java List interface, see pblList* functions,
Open source C resizable-array implementation equivalent to the Java ArrayList class.
Implements most optional list operations, and permits all elements, including NULL. In addition to implementing the List operations, this module provides methods to manipulate the size of the array that is used internally to store the list.
The size, isEmpty, get, set, iterator, and listIterator operations run in constant time. The add operation runs in amortized constant time, that is, adding n elements requires O(n) time. All of the other operations run in linear time (roughly speaking). The constant factor is low compared to that for the LinkedList implementation.
Each pblArrayList instance has a capacity. The capacity is the size of the array used to store the elements in the list. It is always at least as large as the list size. As elements are added to an ArrayList, its capacity grows automatically. The details of the growth policy are not specified beyond the fact that adding an element has constant amortized time cost.
An application can increase the capacity of an ArrayList instance before adding a large number of elements using the ensureCapacity operation. This may reduce the amount of incremental reallocation.
Open source C linked list implementation equivalent to the Java LinkedList class.
Implements most optional list operations, and permits all elements (including null). In addition to implementing the List operations, this module provides uniformly named methods to get, remove and insert an element at the beginning and end of the list. These operations allow linked lists to be used as a stack, queue, or double-ended queue (deque).
The module implements the Queue operations, providing first-in-first-out queue operations for add, poll, etc. Other stack and deque operations could be easily recast in terms of the standard list operations.
All of the operations perform as could be expected for a doubly-linked list. Operations that index into the list will traverse the list from the beginning or the end, whichever is closer to the specified index.
Open source C Iterator implementation equivalent to the Java ListIterator interface.
An iterator for lists that allows the programmer to traverse the list in either direction, modify the list during iteration, and obtain the iterator's current position in the list. A ListIterator has no current element; its cursor position always lies between the element that would be returned by a call to previous() and the element that would be returned by a call to next(). In a list of length n, there are n+1 valid index values, from 0 to n, inclusive.
Note that the remove() and set(Object) methods are not defined in terms of the cursor position; they are defined to operate on the last element returned by a call to next() or previous().
PBL Set - An open source C implementation of hash sets and tree sets similar to the Java Set interface, see pblSet* functions,
Open source C resizable hash set implementation equivalent to the Java HashSet class.
Hash sets make no guarantees as to the iteration order of the set; in particular, it does not guarantee that the order will remain constant over time. This module does not permit the NULL element.
Hash sets offer constant time performance for the basic operations
(add, remove, contains and size),
assuming the hash function disperses the elements properly among the buckets.
Iterating over this set requires time proportional to the sum of the HashSet
instance's size (the number of elements) plus the "capacity" of the instance
(the number of buckets).
Thus, it's very important not to set the initial capacity too high
(or the load factor too low) if iteration performance is important.
Open source C avl-tree-based balanced tree set implementation equivalent to the Java TreeSet class.
Tree sets guarantees that the sorted set will be in ascending element order, sorted according to the natural order of the elements, or by the comparator provided.
This implementation provides guaranteed log(n) time cost for the basic operations (add, remove and contains).
PBL Map - An open source C implementation of hash maps and tree maps similar to the Java Map interface, see pblMap* functions,
Open source C avl-tree-based balanced tree map implementation equivalent to the
Java TreeMap
class.
Tree maps guarantee that the sorted map will be in ascending element order,
sorted according to the natural order of the elements,
or by the comparator provided.
This implementation provides guaranteed log(n) time cost for the basic operations
(add, remove and contains).
PBL HEAP -- Heap in C, C heap, heap in C, C-Heap, binary heap in C, binary min-max heap in C
This heap orders elements according to a compare function specified. A heap does not permit null elements.
PBL PRIORITY QUEUE -- PriorityQueue in C, C priority queue, priority queue in C, Heap in C, C-Heap, binary heap in C, binary max heap in C
An open source C memory hash table implementation, see pblHt* functions,
An open source C key file implementation, see pblKf* functions,
An open source C ISAM file implementation, see pblIsam* functions
AvlDictionary<TKey,TValue> is an open source C# Avl-Tree based generic IDictionary<TKey,TValue> implementation. See the AvlDictionary documentation.
In order to use AvlDictionary<TKey,TValue> copy AvlDictionary.cs to your solution and use the AVL-Tree based generic AvlDictionary<TKey,TValue> like you use the hash based generic Dictionary<TKey,TValue>.
PriorityQueue<T>: -- C# .NET List<T> based generic min-heap PriorityQueue<T>. See the priority queue documentation.
In order to use PriorityQueue<T> copy PriorityQueue.cs to your solution and use the List<T> based generic min-heap PriorityQueue<T>.
Version 1.01, Fri Nov 1 2002 - improved memory management, see pblkf.c Revision 1.2, 1.3
Version 1.02, Wed Feb 19 2003 - fixed a bug reported by Csaba Palos, see pblisam.c Revision 1.2
Version 1.03, Sun Apr 4 2004 - fixed a bug reported by Jari Aalto, see pbl.h Revision 1.3
Version 1.04, Sun Mar 1 2009 - Optimizations during MAC OS X port. Exposed the array list, linked list, tree set and hash set functions.
Version 1.04.02, Sun May 30 2010 - Exposed the map interface functions.
Version 1.04.03, Sun Aug 8 2010 - Exposed the priority queue functions.
Version 1.04.04, Sun Sep 5 2010 - Exposed the heap functions.