[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.lang.c

data structure that preserving insertion order

Owner

4/29/2011 2:11:00 AM

Is there any data structure that preserving insertion order
in C?

I need to process unicode mapping and unlike ascii which has

128 codes, unicode has more than roughly 10,000 letters.

I'm looking for..

Data structure that handles large data and preserving inser-

tion order.
16 Answers

Peter Nilsson

4/29/2011 6:02:00 AM

0

Owner <Ow...@Owner-PC.com> wrote:
> Is there any data structure that preserving insertion order

Yes, lots of them. In terms of the 'usual' data structures,
pretty much all of them except trees, graphs and hash tables.

> in C?

Data structures generally aren't language dependant. It doesn't
sound like you have a C issue.

> I need to process unicode mapping and unlike ascii which has
> 128 codes, unicode has more than roughly 10,000 letters.

So store unicode characters in whatever array, list, etc...
you would normally store a sequence of characters.

> I'm looking for..
>
> Data structure that handles large data and preserving inser-
> tion order.

What's the actual problem?

If you're building yet another text editor, but one that will
open a 100MB text file and still run in reasonable time when
the user inserts a line at the beginning, then you just need a
container to house the lines, and manage each line separately.

--
Peter

Owner

4/29/2011 12:07:00 PM

0

On Thu, 28 Apr 2011 23:02:04 -0700, Peter Nilsson wrote:

> Owner <Ow...@Owner-PC.com> wrote:
>> Is there any data structure that preserving insertion order
>
> Yes, lots of them. In terms of the 'usual' data structures,
> pretty much all of them except trees, graphs and hash tables.
>
>> in C?
>
> Data structures generally aren't language dependant. It doesn't
> sound like you have a C issue.
>
>> I need to process unicode mapping and unlike ascii which has
>> 128 codes, unicode has more than roughly 10,000 letters.
>
> So store unicode characters in whatever array, list, etc...
> you would normally store a sequence of characters.
>
>> I'm looking for..
>>
>> Data structure that handles large data and preserving inser-
>> tion order.
>
> What's the actual problem?
>
> If you're building yet another text editor, but one that will
> open a 100MB text file and still run in reasonable time when
> the user inserts a line at the beginning, then you just need a
> container to house the lines, and manage each line separately.

If you can tell me one data structure, I can

research with the clue on the web. but I have no idea

except trees. even if I heard trees (like binary tree,

b-tree..) I dont' know how to relate it to editor or

big data in actual code. but I'm learning step by step.

I already posted similar but shorter post at

comp.programming and it was unproductive.

gw7rib

4/29/2011 12:18:00 PM

0

On Apr 29, 3:10 am, Owner <Ow...@Owner-PC.com> wrote:
> Is there any data structure that preserving insertion order
> in C?
>
> I need to process unicode mapping and unlike ascii which has
>
> 128 codes, unicode has more than roughly 10,000 letters.
>
> I'm looking for..
>
> Data structure that handles large data and preserving inser-
>
> tion order.

I'm afraid you still haven't said enough for us to be able to help
you. When you say "preserving insertion order", what are you planning
on doing to the data that might mess up the order?

For instance, if I do the following:

char buff[10];
char *p = buff;
*(p++) = 'H';
*(p++) = 'e';
*(p++) = 'l';
*(p++) = 'l';
*(p++) = 'o';
*p = 0;

printf(buff);

then this should print all the characters in the order they were
inserted. Presumably you mean something more than this.

Owner

4/29/2011 12:43:00 PM

0

On Fri, 29 Apr 2011 05:18:29 -0700, Paul N wrote:

> On Apr 29, 3:10am, Owner <Ow...@Owner-PC.com> wrote:
>> Is there any data structure that preserving insertion order
>> in C?
>>
>> I need to process unicode mapping and unlike ascii which has
>>
>> 128 codes, unicode has more than roughly 10,000 letters.
>>
>> I'm looking for..
>>
>> Data structure that handles large data and preserving inser-
>>
>> tion order.
>
> I'm afraid you still haven't said enough for us to be able to help
> you. When you say "preserving insertion order", what are you planning
> on doing to the data that might mess up the order?
>
> For instance, if I do the following:
>
> char buff[10];
> char *p = buff;
> *(p++) = 'H';
> *(p++) = 'e';
> *(p++) = 'l';
> *(p++) = 'l';
> *(p++) = 'o';
> *p = 0;
>
> printf(buff);
>
> then this should print all the characters in the order they were
> inserted. Presumably you mean something more than this.

Yes exactly, preserving order like that but with large data

like unicode mapping. data structure preserving the inorder

of character( character has its own value according

character set but when inserted the character in some

sort of data structure, it preserves inorder ) with able

to search the character efficiently.

Ben Bacarisse

4/29/2011 3:23:00 PM

0

Owner <Owner@Owner-PC.com> writes:
<snip>
> Yes exactly, preserving order like that but with large data
> like unicode mapping. data structure preserving the inorder
> of character( character has its own value according
> character set but when inserted the character in some
> sort of data structure, it preserves inorder ) with able
> to search the character efficiently.

I'm still not sure what you want. In particular what is "Unicode
mapping"? Presumably it maps Unicode code points to ... what?

Anyway, any data structure that supports the mapping you want can be
made to record the insertion order, simply by maintaining a list at the
same time. This so simple that I image it is not what you want but I
can't tell. Why not say what the actual problem is that needs to be
solved?

--
Ben.

Owner

4/29/2011 4:16:00 PM

0

On Fri, 29 Apr 2011 16:23:15 +0100, Ben Bacarisse wrote:

> Owner <Owner@Owner-PC.com> writes:
> <snip>
>> Yes exactly, preserving order like that but with large data
>> like unicode mapping. data structure preserving the inorder
>> of character( character has its own value according
>> character set but when inserted the character in some
>> sort of data structure, it preserves inorder ) with able
>> to search the character efficiently.
>
> I'm still not sure what you want. In particular what is "Unicode
> mapping"? Presumably it maps Unicode code points to ... what?
>
> Anyway, any data structure that supports the mapping you want can be
> made to record the insertion order, simply by maintaining a list at the
> same time. This so simple that I image it is not what you want but I
> can't tell. Why not say what the actual problem is that needs to be
> solved?

Trying to build tr unix tool that supports unicode.

ascii is 128 characters so a array can hold characters.

unicode is a little over 10,000 characters.

thought a binary tree could be right structure. but then

I need preserve order which character goes in first.

Thank you for replies by the way.

Scott Fluhrer

4/29/2011 5:08:00 PM

0


"Owner" <Owner@Owner-PC.com> wrote in message
news:pan.2011.04.29.16.16.12.154000@Owner-PC.com...
> On Fri, 29 Apr 2011 16:23:15 +0100, Ben Bacarisse wrote:
>
>> Owner <Owner@Owner-PC.com> writes:
>> <snip>
>>> Yes exactly, preserving order like that but with large data
>>> like unicode mapping. data structure preserving the inorder
>>> of character( character has its own value according
>>> character set but when inserted the character in some
>>> sort of data structure, it preserves inorder ) with able
>>> to search the character efficiently.
>>
>> I'm still not sure what you want. In particular what is "Unicode
>> mapping"? Presumably it maps Unicode code points to ... what?
>>
>> Anyway, any data structure that supports the mapping you want can be
>> made to record the insertion order, simply by maintaining a list at the
>> same time. This so simple that I image it is not what you want but I
>> can't tell. Why not say what the actual problem is that needs to be
>> solved?
>
> Trying to build tr unix tool that supports unicode.
>
> ascii is 128 characters so a array can hold characters.
>
> unicode is a little over 10,000 characters.

Unless you are on a strictly constrained environment, there is no problem
having an array with 65,536 elements. I wouldn't even bother trying to
limit it to 10,000; memory is cheap enough that it doesn't warrent your time
to reduce the size of the array to the unicode characters you'll actually
see.

>
> thought a binary tree could be right structure. but then
>
> I need preserve order which character goes in first.

Why does 'tr' need to remember the order that the characters were specified?
Or, is it possible that a single unicode character might be converted into
multiple (in which case you'll need to remember the order of the replacement
characters)? If the latter, that's easy enough; each array element might
point to a string of unicode characters.

Remember, on today's processors, memory is cheap (unless, again, you're in a
constained environment). If throwing a few megabytes at the problem saves
you time (designing, programming, debugging), it's a good tradeoff.

>
> Thank you for replies by the way.
>


Ben Bacarisse

4/29/2011 5:16:00 PM

0

Owner <Owner@Owner-PC.com> writes:

> On Fri, 29 Apr 2011 16:23:15 +0100, Ben Bacarisse wrote:
>
>> Owner <Owner@Owner-PC.com> writes:
>> <snip>
>>> Yes exactly, preserving order like that but with large data
>>> like unicode mapping. data structure preserving the inorder
>>> of character( character has its own value according
>>> character set but when inserted the character in some
>>> sort of data structure, it preserves inorder ) with able
>>> to search the character efficiently.
>>
>> I'm still not sure what you want. In particular what is "Unicode
>> mapping"? Presumably it maps Unicode code points to ... what?
>>
>> Anyway, any data structure that supports the mapping you want can be
>> made to record the insertion order, simply by maintaining a list at the
>> same time. This so simple that I image it is not what you want but I
>> can't tell. Why not say what the actual problem is that needs to be
>> solved?
>
> Trying to build tr unix tool that supports unicode.
> ascii is 128 characters so a array can hold characters.
> unicode is a little over 10,000 characters.
> thought a binary tree could be right structure. but then
> I need preserve order which character goes in first.

Why? I'd use something like a hash table. I don't see any need to
remember the insertion order. What's your reasoning?

--
Ben.

Owner

4/29/2011 5:36:00 PM

0

On Fri, 29 Apr 2011 18:15:46 +0100, Ben Bacarisse wrote:

> Owner <Owner@Owner-PC.com> writes:
>
>> On Fri, 29 Apr 2011 16:23:15 +0100, Ben Bacarisse wrote:
>>
>>> Owner <Owner@Owner-PC.com> writes:
>>> <snip>
>>>> Yes exactly, preserving order like that but with large data
>>>> like unicode mapping. data structure preserving the inorder
>>>> of character( character has its own value according
>>>> character set but when inserted the character in some
>>>> sort of data structure, it preserves inorder ) with able
>>>> to search the character efficiently.
>>>
>>> I'm still not sure what you want. In particular what is "Unicode
>>> mapping"? Presumably it maps Unicode code points to ... what?
>>>
>>> Anyway, any data structure that supports the mapping you want can be
>>> made to record the insertion order, simply by maintaining a list at the
>>> same time. This so simple that I image it is not what you want but I
>>> can't tell. Why not say what the actual problem is that needs to be
>>> solved?
>>
>> Trying to build tr unix tool that supports unicode.
>> ascii is 128 characters so a array can hold characters.
>> unicode is a little over 10,000 characters.
>> thought a binary tree could be right structure. but then
>> I need preserve order which character goes in first.
>
> Why? I'd use something like a hash table. I don't see any need to
> remember the insertion order. What's your reasoning?

If you command something like "tr hashtable empttable"

replacing same length word hashtable with empttable.

I thought inorder needs to be preserved to replace the word,

no?

William Ahern

4/29/2011 5:54:00 PM

0

Owner <Owner@owner-pc.com> wrote:
<snip>
> unicode is a little over 10,000 characters.

You're off by at least a factor of 10. There are 109,242 assigned graphical
code points in the latest Unicode standard.