Re: Creating a dictionary who's objects are also linked or indexed?

FROM : Wagner Truppel
DATE : Sat Aug 12 23:41:06 2006

What you're attempting to do falls under the name of "rectangular 
range searches", the one-dimensional version of which is: given a 
keyed set of items with a well-defined ordering relation among their 
keys, and given two keys into the set, select the items which fall 
between those keys.

This is a well-studied problem in computational geometry and has a 
simple and efficient solution in the form of a data structure called 
a "range tree". The one-dimensional range search problem uses a 
balanced binary search tree to return all items within the query 
range. The tree can be built in O(n log n) time and uses O(n log n) 
storage, and queries can be performed in O(k + log n) time, where n 
is the total number of items in the set and k is the number of items 
found within the query range. In other words, the time to answer a 
query is essentially linear in the number of items returned.

For details, try googling for "range tree". Also, take a look at 
chapter 5 of the excellent book:

Computational Geometry
http://www.amazon.com/gp/product/3540656200/sr=8-1/qid=1155417398/
ref=sr_1_1/103-2373405-0892656?ie=UTF8

Wagner

============

The difference between an auto mechanic and a quantum mechanic is 
that the quantum mechanic can get the car inside the garage without 
opening the door.


> I'm curious if there is a better Cocoa solution than I've found to 
> the following problem: I often have a list of items (strings, 
> numbers, or dates) where I know the values of the first and last 
> items and need to iterate over the inclusive set of items that fall 
> between the first and last items. I can accomplish this by 
> effectively implementing the lookup capability of a dictionary in 
> an object contained in an array or by adding an index to an object 
> in a dictionary. It can also be handled using Core Data which seems 
> a lot like using a sledgehammer to swat a fly.
>
> For example, I have a list of names and want to enumerate over the 
> set of items from a given item to a given item. My code determines 
> that "Ball" is the first value of interest and "Smith" is the last 
> value, and given these, I need to return the inclusive set of items 
> that fall between (simple alpha comparison) these values in the 
> parent set.
>
> It seems like a fairly common problem and am wondering if Cocoa 
> provides a simpler solution that I'm not seeing?