indexing a collection

Question

0.00/5 (No votes)

See more:

my assignment is to create a DBMS iv'e created 3 classes witch build an hierarchy similar to the DataTable and DataRow Classes
Entity (T)-> Table -> Record -> Field
the Table is created from an Entity using Reflection
why and how i created them is not the issue .
what i need now is to index the List inside the Table according the the Records fields in order to optimize "query's" , so as to avoid a linear probe of all the Records
lets say for example i need to index using a field called "unitPrice" i need a collection
witch would optimize the search for lets say " .. where unitPrice >= 14"
i thought of using a dictionary
Dictionary<K,int> dict
the value being the index of the Record in the list , but i need a collection witch would except non-unique keys as well as would have the possibility to optimize range query's
so Dictionary , SortedDictionary ,HashTable or SortedList are out of the question because i need non-unique keys to be inserted ,
and a hashtable wouldn't help with range query's any ideas of what collection i could use would be most appreciated

//================================================================================//

iv'e found out i could use something called a LookUp witch is created by from a list , but i need to some how create an expression witch would give me the value of the record as the key (14) and the different positions as the values lets say ( records 15 ,500 ,67 hold a unit price witch is equal to 14 )

further more i thought the hashtable would know how to handle duplicate keys .... isn't that the all point of hashing

10x in advance .eran.

Posted 14-Jul-11 18:45pm

eranotz50

Add a Solution

Comments

BobJanova 15-Jul-11 5:15am

Do you really need to be able to handle non unique keys? Most RDBs only allow you to have a unique key, though you can have a non unique index.

1 solution

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Sergey Alexandrovich Kryukov · Accepted Answer · 2011-07-14T20:06:00

The point of hashing and Dictionary is using the unique keys bur also fast search by the key, which you can call indexing. The speed of search is of O(1), see http://en.wikipedia.org/wiki/Big_O_notation[^]. If you think about it, you will understand that a non-unique key cannot be used with indexing. However, you can use objects with the same key with Dictionary.

For this purpose, for an element type ELEMENT and key type KEY you need to use the combined collection type:

C#

System.Collections.Generic.Dictionary<KEY, System.Collections.Generic.List<ELEMENT>>

Isn't this clear? This is how to add an element to such combined collection:

C#

using KeyedCollection = System.Collections.Generic.Dictionary<Key, System.Collections.Generic.List<int>>;
using ElementList = System.Collections.Generic.List<int>;

//..

class Key {/*...*/} //I don't know what do you need -- anything

//..

KeyedCollection Dictionary new KeyedCollection();

void AddKey(Key key, int element) {
    ElementList list;
    if (!Dictionary.TryGetValue(key, out list)) {
       list = new ElementList();
       Dictionary.Add(key, list);
    } //if
    list.Add(element);
}

If the key is already in dictionary, you get the dictionary value (which is list), and add your element to it, otherwise you add a new list.

You can do the similar thing using SortedDictionary and SortedList.

—SA