Want a key value collection that maintains ordering

[illegal.prime]

Hi all, is there a key value collection in .Net that maintains the
ordering in which I add items.

I'm finding that I'm creating a number of classes that contain a name
and then some object. I would prefer just to use some collection that
maintains the ordering in which I add things (like ArrayList), but that
maps a key to a value.

I thought NameValueCollection was the right one - but it doesn't
guarantee ordering.

If it doesn't exist, why not? If it doesn't what is the "right" way to
build it? Just have wrap your class around an instance of ArrayList
and have some internal class that takes the key given in the Add method
and instantiates this generic class with two members (a string key and
an object value), then add that to the internal ArrayList?

Thanks,
Novice

[Bruce Wood]

I would create a class that wraps an ArrayList and a Hashtable.
Whenever anything is added to your class, add it to both the ArrayList
and the Hashtable. When you want to return an iterator, return an
iterator into the ArrayList. When you want a lookup by key, look it up
in the Hashtable.

[illegal.prime]

I was actually thinking of doing something like that originally since
it is all reference based, there would be minimal cost (memory) to do
something like that - i.e. to have the ArrayList and the Hashtable to
point to the various elements.

Does anyone know of any reason why I should just rip off the
implementation of PhoneNumberDictionary (that extends DictionaryBase)
from here:
http://www.codeproject.com/csharp/collection1.asp

I'm not doing a PhoneNumberDictionary, but it seems to provide what I
want in terms of allowing me to specify an arbitrary name and an
arbitrary object. And when I get them all, they will be returned in
the order I added them.

Does that sound right?

Thanks,
Novice

[illegal.prime]

Crud!

I've tried using DictionaryBase, but the compiler gives me
DictionaryBase could not be found. I guess that means it is a .Net 2
class?

That sucks.

[illegal.prime]

Never mind - looks like the executable wasn't getting regenerated or
something - fresh build and the compiler was okay with it.

[illegal.prime]

Well, this doesn't work, it doesn't maintain the order in which I added
them when I iterate through it.

So I guess I will just do something like (not compileable code):
class DictionaryEntryCollection
{
private ArrayList mKeyValues;

public DictionaryEntryCollection()
{
mKeyValues = new ArrayList();
}

public void Add (object key, object value)
{
DictionaryEntry keyValue = new DictionaryEntry(key, value);
mKeyValues.Add(keyValue);
}

public DictionaryEntry[] GetKeyValueElements()
{
//iterate over all the elements in my arraylist
}
}

Sound right?

Thanks,
Novice

[jeremiah johnson]

Bruce Wood wrote:

I would create a class that wraps an ArrayList and a Hashtable.
Whenever anything is added to your class, add it to both the ArrayList
and the Hashtable. When you want to return an iterator, return an
iterator into the ArrayList. When you want a lookup by key, look it up
in the Hashtable.

What if you add something with the same key twice? It will show up in
the hashtable just once but in the ArrayList twice. That is probably
not what he's looking for.

I'd create a new collection that wrapped an ArrayList<Object[]> and
massage the add method to check for duplicates, while maintaining order.

I just whipped something up in Java. Its untested, unsynchronized,
probably slow, and the syntax is slightly different for C# (the for
loop). Here it is; it might help you, it might not.

public class HashList {

private ArrayList<Object[]> coll;

public HashList() {
coll = new ArrayList<Object[]>();
}

public void add(Object key, Object value) {
boolean alreadyAdded = false;

for (Object[] s : coll) {
if (s[0] == key) {
int me = coll.indexOf(s);
coll.remove(me);
coll.add(me, s);
alreadyAdded = true;
}
}

if (!alreadyAdded) {
coll.add(new Object[] { key, value });
}
}

}

[Nicholas Paldino [.NET/C# MVP]]

Novice,

You can just use the SortedList<TKey, TValue> generic class. It will
allow you to perform lookups, and order the list as well.

Hope this helps.
--
- Nicholas Paldino [.NET/C# MVP]
- mv*@spam.guard.caspershouse.com

<il***********@gmail.com> wrote in message
news:11**********************@j73g2000cwa.googlegr oups.com...

Hi all, is there a key value collection in .Net that maintains the
ordering in which I add items.

I'm finding that I'm creating a number of classes that contain a name
and then some object. I would prefer just to use some collection that
maintains the ordering in which I add things (like ArrayList), but that
maps a key to a value.

I thought NameValueCollection was the right one - but it doesn't
guarantee ordering.

If it doesn't exist, why not? If it doesn't what is the "right" way to
build it? Just have wrap your class around an instance of ArrayList
and have some internal class that takes the key given in the Add method
and instantiates this generic class with two members (a string key and
an object value), then add that to the internal ArrayList?

Thanks,
Novice

[MSDN]

Nicholas,

new to Generics, is SortedList already generic?

Why can I ! say SortedList<string,string> ??? Throws Error
if (!Page.IsPostBack)
{
AlwaysSortedList = new SortedList();
Session.Add("ASL",AlwaysSortedList);
}

in button handler....

((SortedList)Session["ASL"]).Add(TextBox1.Text,TextBox1.Text);
DropDownList1.DataSource = ((SortedList)Session["ASL"]); //AlwaysSortedList;
DropDownList1.DataTextField = "key";
DropDownList1.DataValueField = "value";
DropDownList1.DataBind();

"Nicholas Paldino [.NET/C# MVP]" <mv*@spam.guard.caspershouse.com> wrote in
message news:%2******************@TK2MSFTNGP04.phx.gbl...

Novice,

You can just use the SortedList<TKey, TValue> generic class. It will
allow you to perform lookups, and order the list as well.

Hope this helps.
--
- Nicholas Paldino [.NET/C# MVP]
- mv*@spam.guard.caspershouse.com

<il***********@gmail.com> wrote in message
news:11**********************@j73g2000cwa.googlegr oups.com...

Hi all, is there a key value collection in .Net that maintains the
ordering in which I add items.

I'm finding that I'm creating a number of classes that contain a name
and then some object. I would prefer just to use some collection that
maintains the ordering in which I add things (like ArrayList), but that
maps a key to a value.

I thought NameValueCollection was the right one - but it doesn't
guarantee ordering.

If it doesn't exist, why not? If it doesn't what is the "right" way to
build it? Just have wrap your class around an instance of ArrayList
and have some internal class that takes the key given in the Add method
and instantiates this generic class with two members (a string key and
an object value), then add that to the internal ArrayList?

Thanks,
Novice

[Michael D. Ober]

Yes. In VB 2005, you would use

dim AlwaysSortedList as new SortedList(of String, String)
AlwaysSortedList.add("Key1", "This is Key1")

debug.print(AlwaysSortedList("Key1") displays "This is Key1" in the
Immediate window.

Mike Ober.

"MSDN" <sq**********@hotmail.com> wrote in message
news:eh**************@TK2MSFTNGP04.phx.gbl...

Nicholas,

new to Generics, is SortedList already generic?

Why can I ! say SortedList<string,string> ??? Throws Error
if (!Page.IsPostBack)
{
AlwaysSortedList = new SortedList();
Session.Add("ASL",AlwaysSortedList);
}

in button handler....

((SortedList)Session["ASL"]).Add(TextBox1.Text,TextBox1.Text);
DropDownList1.DataSource = ((SortedList)Session["ASL"]); //AlwaysSortedList; DropDownList1.DataTextField = "key";
DropDownList1.DataValueField = "value";
DropDownList1.DataBind();

"Nicholas Paldino [.NET/C# MVP]" <mv*@spam.guard.caspershouse.com> wrote in message news:%2******************@TK2MSFTNGP04.phx.gbl...

Novice,

You can just use the SortedList<TKey, TValue> generic class. It will
allow you to perform lookups, and order the list as well.

Hope this helps.
--
- Nicholas Paldino [.NET/C# MVP]
- mv*@spam.guard.caspershouse.com

<il***********@gmail.com> wrote in message
news:11**********************@j73g2000cwa.googlegr oups.com...

Hi all, is there a key value collection in .Net that maintains the
ordering in which I add items.

I'm finding that I'm creating a number of classes that contain a name
and then some object. I would prefer just to use some collection that
maintains the ordering in which I add things (like ArrayList), but that
maps a key to a value.

I thought NameValueCollection was the right one - but it doesn't
guarantee ordering.

If it doesn't exist, why not? If it doesn't what is the "right" way to
build it? Just have wrap your class around an instance of ArrayList
and have some internal class that takes the key given in the Add method
and instantiates this generic class with two members (a string key and
an object value), then add that to the internal ArrayList?

Thanks,
Novice

[illegal.prime]

I can't use .Net 2 yet... I'm stuck with my current version of .Net -
but thanks for the suggestion none the less.

Novice

[Bruce Wood]

But the OP asked that the entries be maintained in their original
order, not in key order. That's why I didn't suggest SortedList.

[Bruce Wood]

Why not add a Hashtable to that and avoid the iteration over the
ArrayList looking for the item? A linear search is terribly slow.

[Bruce Wood]

> What if you add something with the same key twice? It will show up in

the hashtable just once but in the ArrayList twice. That is probably
not what he's looking for.

There's a simple solution to that:

public void Add(object key, object item)
{
object existingItem = this._hash[key];
if (existingItem != null)
{
this._array.Remove(existingItem);
}
this._hash[key] = item;
this._array.Add(item);
}

Much better than doing a linear search every time you add an item.

If the OP wants instead a collection that permits duplicates (two items
with the same key) then it's no longer clear what the indexer should
return.

[Brian Gideon]

Novice,

Bruce's idea is really the best one IMO. Here's a link to an
implementation.

<http://www.codeproject.com/csharp/keyedlist.asp#xx701821xx>

Brian

il***********@gmail.com wrote:

Hi all, is there a key value collection in .Net that maintains the
ordering in which I add items.

I'm finding that I'm creating a number of classes that contain a name
and then some object. I would prefer just to use some collection that
maintains the ordering in which I add things (like ArrayList), but that
maps a key to a value.

I thought NameValueCollection was the right one - but it doesn't
guarantee ordering.

If it doesn't exist, why not? If it doesn't what is the "right" way to
build it? Just have wrap your class around an instance of ArrayList
and have some internal class that takes the key given in the Add method
and instantiates this generic class with two members (a string key and
an object value), then add that to the internal ArrayList?

Thanks,
Novice

[illegal.prime]

So in case anyone is interested I did something even more simple than
Bruce's idea. I.E. I just wrapped ArrayList. The reason I don't also
use Hashtable is two fold:
1. My Collection also needs to be capable of containing other instances
of itself - i.e. I need a collection that can contain regular
key/value pairs, but any of those values could potentially be another
instance of itself. Therefore, I may end up with nested keys that are
identical - hence hashtable wouldn't work - unless I also embed
Hashtables in Hashtables - but that defeats the purpose of using
Hashtable for searching
2. Really just restating the last bit of point 1 - that is, a Hashtable
can't search on nested instances of itself - i.e. if I add a Hashtable
Object like this:
Hashtable hashtable = getHashtable1();
Hashtable hashtable2 = getHashtable2();
hashtable.Add("blah", hashtable2);

Now searching on hashtable2 won't be done.

However, after writing all that - perhaps I could come up with a clever
naming system, whereby nested instances get characters in them much
like folders/directories in the various OS'.

So I could use some illegal character for my names as a separator and
then search using that...

Hmm... that could work,
Novice

[Michael D. Ober]

That's simple to solve. Use the data as the key. If you want to keep them
in the original order, any of the array list and collection objects will do
this by default - it's the way they're implemented.

Mike Ober.

"Bruce Wood" <br*******@canada.com> wrote in message
news:11**********************@g10g2000cwb.googlegr oups.com...

But the OP asked that the entries be maintained in their original
order, not in key order. That's why I didn't suggest SortedList.

[Helge Jensen]

jeremiah johnson wrote:

Bruce Wood wrote: I just whipped something up in Java. Its untested, unsynchronized,

Java have a LinkedHashMap (or something like that) which does exactly
what OP want's.

The "good" (TM :) solution is to store double-linked-lists with
insertion-order and let the values in the hash contain references to
their linked-list representation.

This allows O(1) insert,update and remove, as well as ordered traversal
(forward and backward) and is exactly what the correspoding JAVA class does.

--
Helge

[Helge Jensen]

Michael D. Ober wrote:

That's simple to solve. Use the data as the key. If you want to keep them
in the original order, any of the array list and collection objects will do
this by default - it's the way they're implemented.

IDictionary have no ordering, which was what OP wanted.

You *could* embed the ordering into the keys, and use SortedList, but I
don't like the idea of embedding collection-containment info into the
contained objects. For one thing each object can only be contained in
one such list.

A better alternative is to do linked-list-hashtables.

--
Helge

[Helge Jensen]

il***********@gmail.com wrote:

So in case anyone is interested I did something even more simple than
Bruce's idea. I.E. I just wrapped ArrayList. The reason I don't also
use Hashtable is two fold:
So you've chosen linear lookup-time.
1. My Collection also needs to be capable of containing other instances
of itself - i.e. I need a collection that can contain regular
key/value pairs, but any of those values could potentially be another
instance of itself. Therefore, I may end up with nested keys that are
identical - hence hashtable wouldn't work - unless I also embed
*Nested* identical keys shouldn't be a problem. They are contained in
separate data-structures.
Hashtables in Hashtables - but that defeats the purpose of using
Hashtable for searching
Well,... atleast in multiple layers. Why don't you just have
IDictionary'es, and then use a hashtable for the "big" ones and
something else for the "smaller" ones?
2. Really just restating the last bit of point 1 - that is, a Hashtable
can't search on nested instances of itself - i.e. if I add a Hashtable
Object like this:
Hashtable hashtable = getHashtable1();
Hashtable hashtable2 = getHashtable2();
hashtable.Add("blah", hashtable2);

Now searching on hashtable2 won't be done.
If you have a flat data-structure encoded in a recursive data-structure
(for performance) the recursion shouldn't be visible to the user.

If you have an inherently recursive data-structure you should probably
show that to the user, and do recursive lookup, and everything would be
fine.

What exactly is the type of your keys? which type are they? single:
"foo", or tupled: ("x", "y"), or list-like: ["x", "y", ...] ?
However, after writing all that - perhaps I could come up with a clever
naming system, whereby nested instances get characters in them much
like folders/directories in the various OS'.
Thats called linearization. Perhaps you *are* having a recursive
data-structure and you're just not doing lookup in a way corresponding
to that?

It sounds a lot like a tree with indexed children to me :)
So I could use some illegal character for my names as a separator and
then search using that...

Hmm... that could work,

Watch out, along that bumpy road lies all the dangers of linearization:

- escaping
- delinearization
- parsing, and error-handling of unparseable data
- formulation of searches

If your data *is* recursively structured, you are probably best off
storing the recursively and doing recursive lookups:

void object lookup(params object[] keys) {
IDictionary d = TopDict;
for ( int i = 0; i < keys.Length - 1; ++i )
d = (IDictionary)d[keys[i]];
return d[keys[keys.Length - 1]];
}

dict.lookup("foo", "foo", "baz");
--
Helge

[Bruce Wood]

Going back to your original post...

is there a key value collection in .Net that maintains the
ordering in which I add items. I would prefer just to use some collection that
maintains the ordering in which I add things (like ArrayList), but that
maps a key to a value.

So... this isn't exactly what you want after all. What you want is
something that maps a _multi-part_ key onto a value, or perhaps stores
values in a hierarchical structure but also in insertion order? Your
solution isn't "simpler" than mine... rather, it solves a different
problem.

Since your original post doesn't completely state your problem, could
you restate the problem so that we understand, completely, what it is
that you need to do?

[illegal.prime]

I seem to have offended you - sorry for that.

I have always wanted the same thing, but you're right I could have
provided more details on what I want.

I still want a "key value collection in .Net that maintains the
ordering in which I add items. I would prefer just to use some
collection that maintains the ordering in which I add things (like
ArrayList), but that maps a key to a value."

However, this key value collection also needs to be able to hold a
hierarchy of collections. Therefore, the values need to be able to be
traversed - since they values could themselves be key value
collections.

I have a working solution, if not an efficient one. I'm just surprised
that short of getting .Net 2 there is no generic solution.

Thanks,
Novice

[Bruce Wood]

Don't worry. You didn't offend me. I was just pointing out that your
requirements seemed to have changed, in hopes of getting more details.

Your solution may be efficient enough if there are few elements in your
collection. If there are very many, though, you may want to implement
Brian Gideon's class and then just use a hierarchy of them.

I don't believe that there's a generic solution even in .NET 2.0
(unless I missed something in the conversation). Yours isn't a very
common requirement: most people want either a straight hash or a
_sorted_ list of items with quick access by key.

[Brian Gideon]

Bruce Wood wrote:

Your solution may be efficient enough if there are few elements in your
collection. If there are very many, though, you may want to implement
Brian Gideon's class and then just use a hierarchy of them.

I should give credit where credit is due. It isn't actually my class.
Someone else wrote that article :)