Popular Tags

Who's online

There are currently 0 users and 7 guests online.

User login

The revisions let you track differences between multiple versions of a post.

Overview

Have you ever lamented the absence of queues, stacks, and trees from the Cocoa API? How many times have you considered writing your own, or scoured the web to see if someone else had? Well, look no further, the work has been done for you!

CHDataStructures.framework is 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.

For details about the project, consult the ReadMe file.

Source Code

Since this framework is still under very active development, and anything is liable to change with no notice, there is currently not a binary release. However, you can download the code and build it yourself in Xcode, or just view the files online.

Browse Online

Thanks to WebSVN, the source code is available for online browsing at the following link:

    http://dysart.cs.byu.edu/websvn/

Check Out and Build

To check out the project from Subversion, type this command in Terminal:

    svn checkout http://dysart.cs.byu.edu/chsvn/CHDataStructures/

When you build the Framework target in Xcode, the framework will be compiled and copied to:

    ~/Library/Frameworks/

NOTE: This project is built in Xcode 3 and requires Leopard or higher. Also, projects that use this framework may need to change the C Language Dialect build setting in Xcode to GNU99, since this project uses anonymous structs and unions, a feature not supported by the C99 standard.

Documentation

Documentation for the project (auto-generated after each commit) is available online at this link:

    http://dysart.cs.byu.edu/CHDataStructures/

It can also be auto-generated from the Xcode project via the Documentation target. This requires that Doxygen be installed, and that the doxygen binary executable be on your path.

For the extremely curious and/or cautious, it can be nice to know if you can really expect the code to work. Accordingly, the latest coverage report for the unit tests (which can also be generated from Xcode) is posted here:

    http://dysart.cs.byu.edu/CHDataStructures/coverage/source/

Future Improvements

Let's just say it: no software is perfect. It would be foolish (and a lie) to claim that this framework is flawless. There are several things that need to be improved, and admitting you have a problem is the first step....

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!

Known Issues

Known bugs are documented in the code, and are available in the online documentation at this link:

    http://dysart.cs.byu.edu/CHDataStructures/bug.html

Currently, the biggest issue is that the -[CHRedBlackTree removeObject:] method is reeeeaaaaaly slow. You may notice that the time complexity increases exponentially, not linearly. It turns out that implementing a non-recursive remove for Red-Black trees is non-trivial, and the current solution works correctly but needs work. (For now, I suggest using CHAVLTree or CHAnderssonTree instead.)

Wish List

A number of desired future improvements are documented in the code, and are available in the online documentation at this link:

    http://dysart.cs.byu.edu/CHDataStructures/todo.html

License Information

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.

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.

Contributing to the Framework

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.

Please email Quinn Taylor if you're interested in contributing to the project, discussing improvements or additions you'd like to see, or even just letting him know that you're getting some use from it.

Your rating: None Average: 4.7 (22 votes)

Search

UPDATES

The site has recently been updated. You may notice some of the following issues:

  • Some URLs no longer work. Please use the search box.
  • File uploads should now be working. If you experience problems, please contact us.