03.02.2011 19:34, Nrgyzer пишет:
> == Auszug aus Steven Schveighoffer (schveiguy@yahoo.com)'s Artikel
>> This only works if you rarely remove elements (removal in an
>> array is an O(n) operation).
>> -Steve
> I already thought about using an dynamic array like T[] (which contains all
> elements that should be drawn) and a second like uint[hash_t] which contains
> the indices in the first array. But it does only shit the problem that I can't
> remove an index from a dynamic array.
>
> Thanks for your suggestions.
>
Why can't you?

You can:

1) Get an index i from hash, do arr = arr[0..i] ~ arr[i+1..$] and then reindex all arr[i..$] elements. This is costly, because, as Steven mentioned, such removal is O(n) plus you have to iterate all elements with index >= i, and this traversal is O(n) in the worst case.

2) Use unstable removal. Since you store indices separately, you can just swap an element to be removed with last element in the array, shrink array using slicing (arr = arr[0..$-1]) and reindex a single element (the one that was previously last in the array). The drawback is that this approach doesn't preserve order of elements in the array.

== Auszug aus Stanislav Blinov (blinov@loniir.ru)'s Artikel
> 03.02.2011 19:34, Nrgyzer пишет:
> > == Auszug aus Steven Schveighoffer (schveiguy@yahoo.com)'s Artikel
> >> This only works if you rarely remove elements (removal in an
> >> array is an O(n) operation).
> >> -Steve
> > I already thought about using an dynamic array like T[] (which
contains all
> > elements that should be drawn) and a second like uint[hash_t]
which contains
> > the indices in the first array. But it does only shit the problem
that I can't
> > remove an index from a dynamic array.
> >
> > Thanks for your suggestions.
> >
> Why can't you?
> You can:
> 1) Get an index i from hash, do arr = arr[0..i] ~ arr[i+1..$] and
then
> reindex all arr[i..$] elements. This is costly, because, as Steven mentioned, such removal is O(n) plus you have to iterate all
elements
> with index >= i, and this traversal is O(n) in the worst case.
> 2) Use unstable removal. Since you store indices separately, you can
> just swap an element to be removed with last element in the array,
> shrink array using slicing (arr = arr[0..$-1]) and reindex a single
> element (the one that was previously last in the array). The
drawback is
> that this approach doesn't preserve order of elements in the array.

Ah, okay... I already tried some things with [0..i] ~ [i + 1..$] but there was always an error and I thought, it must be done more simply. I'm just using a simple, dynamic array and use a for-loop to remove them. I don't need remove() often, but I thought there is any way to do it in O(1).

On 02/03/2011 04:29 PM, Steven Schveighoffer wrote:
> Again, I'm not sure what the point is of starting in the middle of the array.
> Are you expecting something different from a hashtable?

Maybe what he needs is a plain Lisp-like symbol table (in D, an array of (key value) pairs)?

Denis
-- 
_________________
vita es estrany
spir.wikidot.com

On 02/03/2011 04:41 PM, Nrgyzer wrote:
> == Auszug aus Steven Schveighoffer (schveiguy@yahoo.com)'s Artikel
>> On Thu, 03 Feb 2011 09:35:44 -0500, Nrgyzer<nrgyzer@gmail.com>
> wrote:
>>> == Auszug aus bearophile (bearophileHUGS@lycos.com)'s Artikel
>>>> Nrgyzer:
>>>>> Is there any chance to cast/convert this array to an indexed
>>> array or
>>>>> is it possible to iterate over specific indices? I know that
>>> there is
>>>>> something like next() for the foreach-statement but when the
> array
>>>>> contains some thousand instances and I only want iterate over
> (for
>>>>> example) 5 elements I think that's the wrong way.
>>>> Show a hypothetical code example of what you desire to do,
> please.
>>>> Bye,
>>>> bearophile
>>>
>>> Example:
>>>
>>> ...
>>> class Example(T : Drawable) : Drawable {
>>>
>>> 	T[hash_t] pObjectsToDraw;
>>>
>>> 	uint pFrom, pTo;
>>>
>>> 	void setLimit(from, to) {
>>> 		pFrom = from;
>>> 		pTo = to;
>>> 	}
>>>
>>> 	void remove(T objToRemove) {
>>> 		pObjectsToDraw.remove(objToRemove.toHash());
>>> 	}
>>>
>>> 	override void draw() {
>>> 		for (uint i = pFrom; i<  pTo; i++) {
>>> 			pOjectsToDraw[i].draw(); // cannot call
>>> because pObjectsToDraw is an associative and no static or dynamic
>>> array
>>> 		}
>>> 	}
>>>
>>> }
>> First, hashes are not stored in any particular order, so I'm not
> sure what
>> you expect to accomplish except "give me (pTo - pFrom) random
> elements
>>   from the array"
>> Second, you can use a foreach loop to get data out of an AA, and
> then
>> break when you've retrieved enough elements.
>> Again, I'm not sure what the point is of starting in the middle of
> the
>> array.  Are you expecting something different from a hashtable?
>> -Steve
>
> I know that hashes aren't stored in any order... but lets take the
> LinkedHashSet in Java. The LinkedHashSet/Map stores the hashes in
> order of inserting. With the toArray()-method I can loop over
> specific elements/indices... but I can also remove the elements by
> their hash. I'm looking for a similar technique in D - you can find
> an Java example on http://www.java2s.com/Code/JavaAPI/java.util/
> LinkedHashSettoArray.htm.

Ruby hashes are like that, but I don't think it would be easy to do in D. You'd better maintain the insertion order yourself in a // array of keys, or make elements link list nodes.

Denis
-- 
_________________
vita es estrany
spir.wikidot.com

On 02/03/2011 08:01 PM, Nrgyzer wrote:
> == Auszug aus Stanislav Blinov (blinov@loniir.ru)'s Artikel
>> 03.02.2011 19:34, Nrgyzer пишет:
>>> == Auszug aus Steven Schveighoffer (schveiguy@yahoo.com)'s Artikel
>>>> This only works if you rarely remove elements (removal in an
>>>> array is an O(n) operation).
>>>> -Steve
>>> I already thought about using an dynamic array like T[] (which
> contains all
>>> elements that should be drawn) and a second like uint[hash_t]
> which contains
>>> the indices in the first array. But it does only shit the problem
> that I can't
>>> remove an index from a dynamic array.
>>>
>>> Thanks for your suggestions.
>>>
>> Why can't you?
>> You can:
>> 1) Get an index i from hash, do arr = arr[0..i] ~ arr[i+1..$] and
> then
>> reindex all arr[i..$] elements. This is costly, because, as Steven
>> mentioned, such removal is O(n) plus you have to iterate all
> elements
>> with index>= i, and this traversal is O(n) in the worst case.
>> 2) Use unstable removal. Since you store indices separately, you can
>> just swap an element to be removed with last element in the array,
>> shrink array using slicing (arr = arr[0..$-1]) and reindex a single
>> element (the one that was previously last in the array). The
> drawback is
>> that this approach doesn't preserve order of elements in the array.
>
> Ah, okay... I already tried some things with [0..i] ~ [i + 1..$] but
> there was always an error and I thought, it must be done more simply.

There is no possible simplier way of removing an arbitrary element from an array than doing that. Well, maybe there is: if your data is POD you could use a memmove with subsequent slice-shrink, but I see we're talking about storing references in this case.

> I'm just using a simple, dynamic array and use a for-loop to remove
> them. I don't need remove() often, but I thought there is any way to
> do it in O(1).

Actually, method (2) is O(1) if you discount hash lookup and possible postblit (which is absent in case of references). You could even employ intrusive indexing (when objects store indices), if that is suitable for your application, thus discarding hash table entirely.

Stanislav Blinov:

> Nrgyzer:
> > Ah, okay... I already tried some things with [0..i] ~ [i + 1..$] but there was always an error and I thought, it must be done more simply.
> 
> There is no possible simplier way of removing an arbitrary element from an array than doing that. Well, maybe there is: if your data is POD you could use a memmove with subsequent slice-shrink, but I see we're talking about storing references in this case.

~ performs a memory allocation, while generally moving items inside an array doesn't require it.

Bye,
bearophile

On 02/04/2011 12:48 AM, bearophile wrote:
> Stanislav Blinov:
>
>> Nrgyzer:
>>> Ah, okay... I already tried some things with [0..i] ~ [i + 1..$] but
>>> there was always an error and I thought, it must be done more simply.
>>
>> There is no possible simplier way of removing an arbitrary element from
>> an array than doing that. Well, maybe there is: if your data is POD you
>> could use a memmove with subsequent slice-shrink, but I see we're
>> talking about storing references in this case.
>
> ~ performs a memory allocation, while generally moving items inside an array doesn't require it.
>

Certainly. Forgot to mention that, thanks.

On 02/04/2011 01:19 AM, Stanislav Blinov wrote:
> On 02/04/2011 12:48 AM, bearophile wrote:
>> Stanislav Blinov:
>>
>>> Nrgyzer:
>>>> Ah, okay... I already tried some things with [0..i] ~ [i + 1..$] but
>>>> there was always an error and I thought, it must be done more simply.
>>>
>>> There is no possible simplier way of removing an arbitrary element from
>>> an array than doing that. Well, maybe there is: if your data is POD you
>>> could use a memmove with subsequent slice-shrink, but I see we're
>>> talking about storing references in this case.
>>
>> ~ performs a memory allocation, while generally moving items inside an
>> array doesn't require it.
>>
>
> Certainly. Forgot to mention that, thanks.

Hmm... Come to think of it, is it ever bad to memmove a reference? I wouldn't think so. I think I got C++ classes in mind when I wrote that.