CHDataStructures.framework is an attempt to create a library of standard data structures which can be used in any Objective-C program, for educational purposes or as a foundation for other data structures to build on. Data structures in this framework adopt Objective-C protocols that define the functionality of and API for interacting with any implementation thereof, regardless of its internals.
This framework provides Objective-C implementations of common data structures which are currently beyond the purview of Apple's extensive and flexible Cocoa frameworks. Collections that are a part of Cocoa are highly optimized and amenable to many situations. However, sometimes an honest-to-goodness stack, queue, linked list, tree, etc. can greatly improve the clarity and comprehensibility of code. The currently supported abstract data types include: deque, heap, linked list, queue, stack, and tree.
The code is written for Mac OS X and does use some features of Objective-C 2.0 (part of 10.5 "Leopard"), but most of the code could be easily ported to other Objective-C environments, such as GNUStep. However, such efforts would be better accomplished by forking this project rather than integrating with it, for several main reasons:
While certain implementations utilize straight C for their internals, this framework is fairly high-level, and uses composition rather than inheritance in most cases. The framework began its existence as an exercise in writing Objective-C code and consisted mainly of ported Java code. In later revisions, performance has gained greater emphasis, but the primary motivation is to provide friendly, intuitive Objective-C interfaces for data structures, not to maximize speed at any cost (a common outcome when using C++ and the STL). The algorithms should all be sound (i.e., you won't get O(n) performance when it should be O(log n) or O(1), etc.) and perform quite well in general. If your choice of data structure type and implementation are dependent on performance or memory usage, it would be wise to run the benchmarks from Xcode and choose based on the time and memory complexity for specific implementations.
All source code and resources for the framework are freely available at this link. They are organized in an Xcode 3 project with all relevant dependencies.
If you only need a few of the classes in the framework, you can cut down on code size by either excluding the parts you don't need from the framework, or just including the parts you do need in your own code. Please don't forget to include relevant copyright and license information if you choose to do so!
The original page for the framework when it was maintained by Phillip Morelock (back when its name was "Cocoa Data Structures Framework") is here.
The framework is a directory called CHDataStructures.framework. When building from source, compile the All target in the Release configuration, which produces a disk image containing the framework. You can either copy the framework directory to /Library/Frameworks/ for all applications, or bundle it inside your own application. (For details, consult the Framework Programming Guide.)
To use code from the framework, simply #import <CHDataStructures/CHDataStructures.h> where necessary. This will import all the public headers in the framework, just as happens with #import <Cocoa/Cocoa.h>. If you want to use only a specific subset of functionality, replace the name of the .h file with the one you want to use. (Use one #import for each header file.)
Documentation is auto-generated after each Subversion commit, and is available online here: http://dysart.cs.byu.edu/CHDataStructures/
Let's just say it: no software is perfect. It would be foolish (and a lie) to claim that this framework is flawless, or even complete. There are several things that could be improved, and admitting you have a problem is the first step.... Accordingly, the online documentation includes lists of known bugs and wish list items that are documented in the code.
Please know that it is not my intent to leave the hard things "as an exercise to the reader." (Believe me, writing a generic, iterative, state-saving tree traversal enumerator was no walk in the park!) However, I would love to draw on the talents of others who can provide solutions which currently evade me, or which I haven't had time to implement yet. If you have ideas (or even better, a fix) for one of these items, email me and we'll talk. Thanks!
This framework is is licensed under a variant of the ISC license, an extremely simple and permissive free software license approved by the Free Software Foundation (FSF) and Open Source Initiative (OSI). The license for this framework is included in every source file, and is repoduced in its entirety here:
Permission to use, copy, modify, and/or distribute this software for any purpose with or without fee is hereby granted, provided that the above copyright notice and this permission notice appear in all copies.
The software is provided "as is", without warranty of any kind, including all implied warranties of merchantability and fitness. In no event shall the authors or copyright holders be liable for any claim, damages, or other liability, whether in an action of contract, tort, or otherwise, arising from, out of, or in connection with the software or the use or other dealings in the software.
This license is functionally equivalent to the MIT and two-clause BSD licenses, and replaces the previous use of the GNU Lesser General Public License (LGPL), which is much more complex and frequently misunderstood. In addition, using GPL-style licenses (which are generally unfriendly towards commercial software) makes little sense for Mac developers, whether open-source or proprietary.
This README file is also considered a source file, and you must include it if you redistribute the framework in source form. If you change the framework, you should add your own README and include it with the source, describing your changes. If you contribute source code to the framework, you may keep your copyright or assign it to me, but you must agree to license the code under this license.
All contributions (including bug reports and fixes, optimizations, new data structures, etc.) are welcomed and encouraged. In keeping with this project's goals, new features are subject to consideration prior to approval—there are no guarantees of adoption. Modifications that are deemed beneficial to the community as a whole will fit with the vision of this project and improve it. However, not all potential contributions make sense to add to the framework. For example, additions or enhancements that only apply for a specific project would be more appropriate to add as categories or subclasses in that code.
Email me if you're interested in contributing to the project, discussing improvements or additions you'd like to see, or even just letting me know that you're getting some use from it.
Major contributors are listed below, alphabetically by last name:
.xcodeproj format, organization of project resources, use of Objective-C 2.0 features.