Friday, July 6, 2018

Digest for comp.lang.c++@googlegroups.com - 23 updates in 7 topics

"Rick C. Hodgin" <rick.c.hodgin@gmail.com>: Jul 05 09:39PM -0400

I have a two-way link-list that traverses a long chain (10s to 100s of
thousands of nodes). The final chain that's prepared is made up of
things that are comprised of sub-parts.
 
Initially I start out with something like this:
_ _ _ _ _
|a|--|b|--|c|--|d|-- ... --|z|
 
It's a node that's in the range of a..z (26 nodes let's say for this
example). I have a control structure that indicates where it starts
and stops:
 
struct SControl
{
SNode *beg; // First node, points to a
SNode *end; // Last node, points to z
};
 
In normal processing, need to process other things which produce new
node chains, and then inject them into the original a..z node chain,
making that chain longer. It can be visualized like this:
_ _ _ _ _
|a|--|b|-+ +-|c|--|d|-- ... --|z|
| |
+-----+ +-----+
| _ _ _ |
+-|1|--|2|--|3|-+
 
So the 1..3 nodes were injected into the a..z chain, making the whole
chain longer. This is no problem and I have code which does this
nicely.
 
However, when I add these new nodes I maintain information about the
injection, resulting in two SControl structs which are populated as
such (pseudo-code):
 
SControl nodes[2] =
{
{ a, z }, // First part starts a, ends z
{ 1, 3 } // Second part starts 1, ends 3
};
 
From here, I continue processing which may consume/inject nodes here
and there, and I need a good way to maintain the beg and end members
throughout as they are processed. If node |1| was consumed, then
the beg member would need to move to |2|. If |3| was consumed, the
end member would need to move to |2|, and so on. If a new |4| node
was added after |3|, then the end member needs to move to |4|, and
so on. And if 1..3 are all deleted, then its nodes[] entry needs to
be set to NULL on both pointers, with |b| being again directly linked
to |c|.
 
However, during my processing, I am not maintaining information that
is relative to the loaded SControl structure. I simply traverse the
chain node-by-node as I go through it.
 
The only solutions I can think of are to (1) add a callback function
to my delete_node() function which calls a function designed to scan
through nodes[] to see if the node being deleted touches any of the
beg or end members indicated, or (2) to add a new member to each SNode
struct which is a pointer to the parent SControl it relates to. (1)
is doable and is my algorithm of choice at present, and (2) seems like
it would waste memory but be faster.
 
Does anybody have better suggestion or an alternate algorithm?
 
Thank you in advance.
 
--
Rick C. Hodgin
Siri Cruise <chine.bleu@yahoo.com>: Jul 05 07:55PM -0700

In article <phmh9a$514$1@dont-email.me>,
> { a, z }, // First part starts a, ends z
> { 1, 3 } // Second part starts 1, ends 3
> };
 
Why? If this is what is causing you problems, reconsider if you need it.
 
If you're doing this to impose a tree on the list, why not use a tree?
 
--
:-<> Siri Seal of Disavowal #000-001. Disavowed. Denied. Deleted. @
'I desire mercy, not sacrifice.' /|\
I'm saving up to buy the Donald a blue stone This post / \
from Metebelis 3. All praise the Great Don! insults Islam. Mohammed
nobody@example.org (Scott): Jul 06 05:03AM

On Thu, 5 Jul 2018 21:39:52 -0400, "Rick C. Hodgin"
 
>However, during my processing, I am not maintaining information that
>is relative to the loaded SControl structure. I simply traverse the
>chain node-by-node as I go through it.
...
>Does anybody have better suggestion or an alternate algorithm?
 
Most of the time, if adding or removing linked list nodes involves
scanning the list, it means you're not really understanding how to use
a linked list.
 
That said, it seems to me that your data structure is really a list of
lists. In your example, you'd begin with a list of one list [A-Z], and
end up with a list of three lists [A-B], [1-3] and [C-Z]. Keeping
track of all the endpoints is automatic and inherent to the data
structure, with no cruft.
Rosario19 <Ros@invalid.invalid>: Jul 06 11:58AM +0200

On Thu, 5 Jul 2018 21:39:52 -0400, "Rick C. Hodgin" wrote:
 
> +-----+ +-----+
> | _ _ _ |
> +-|1|--|2|--|3|-+
 
for me you have to have at last one pointer to the first node of the
list so the situation is
 
pointerStart->|a|--|b|-+ +-|c|--|d|-- ... --|z|
| |
+-----+ +-----+
| _ _ _ |
+-|1|--|2|--|3|-+
 
 
and when add some sub node pointerStart can change
example
 
pointerStart->+ |a|-|b|-|c|--|d|-- ... --|z|
| |
| +-----+-----+
| _ _ _ |
+-|1|--|2|--|3|-+
 
if double linked list for find the node |z| it would be enougt
node |1| (or in general the first node or the node pointerStart point
to) has its prec pointer point to |z| the last
 
but possible i remember wrong... what i remember of my linker list
is that each linked list and each node of it has one value, one
signature that identify the list ( i don't remember why i put the
extra space, possibly for not make easy using some data trhu some
pointer for corrupt all the list)
 
linkedList a;
 
a would be
u32* pointeStart
u32 size
u32 randomValueIdentifyTheList
 
but possible i not understand
 
Richard Damon <Richard@Damon-Family.org>: Jul 06 10:20AM -0700

On 7/5/18 6:39 PM, Rick C. Hodgin wrote:
> it would waste memory but be faster.
 
> Does anybody have better suggestion or an alternate algorithm?
 
> Thank you in advance.
 
A fundamental property is that if an update to object A requires some
change to object B then there needs to be some way to find object B
given object A. It helps to have those changes to object A be localized
(so the code to initiate the update to B is also localized).
 
Your comment that you are not maintaining the information in SControl
says that something is not being done right.
 
If the SControl information is fundamental to the list operation, then
it should be part of it, and the maintenance of it part of the primitives.
 
If the SControl information is an addon, then the list operations
wouldn't have that information, but all accesses to the list should be
through an API layer that uses the basic list operations but adds the
needed updates to the SControl structures.
 
In C++, you could make this SControl based list derive from the basic
linked list, and use virtual functions to do this API redirect, allowing
much of the code to not need to know the distinction. This is harder to
do is C.
"Rick C. Hodgin" <rick.c.hodgin@gmail.com>: Jul 06 01:35PM -0400

On 7/6/2018 1:20 PM, Richard Damon wrote:
> (so the code to initiate the update to B is also localized).
 
> Your comment that you are not maintaining the information in SControl
> says that something is not being done right.
 
Oh, I thought I did make it clear above that I am maintaining SControl.
It is setup to be as the structure and pseudo-code initialization data
above indicates. I have the initial list from a..z, and as portions
are added, such as the 1..3 portion, the SControl list expands to hold
all start/end nodes for each portion of the link list
 
> If the SControl information is fundamental to the list operation, then
> it should be part of it, and the maintenance of it part of the primitives.
 
Agreed. This is my current solution the (1) solution above.
 
> wouldn't have that information, but all accesses to the list should be
> through an API layer that uses the basic list operations but adds the
> needed updates to the SControl structures.
 
..
 
> linked list, and use virtual functions to do this API redirect, allowing
> much of the code to not need to know the distinction. This is harder to
> do is C.
 
I appreciate the consideration, thought, and advice, Richard. I have
considered using C++ for this code, but my goals are toward CAlive, and
whereas I will support some features of C++ in CAlive, I will not support
them all, nor even 1/3rd of them. As such, I stick closer to C until I
am able to later boostrap my code in my language, and expand it as the
needs arise.
 
--
Rick C. Hodgin
Bart <bc@freeuk.com>: Jul 06 08:17PM +0100

On 06/07/2018 18:35, Rick C. Hodgin wrote:
> above indicates.  I have the initial list from a..z, and as portions
> are added, such as the 1..3 portion, the SControl list expands to hold
> all start/end nodes for each portion of the link list
 
Are there only two levels of list? So you can't have this:
 
A B C D
1 2 3
x y
 
Is it possible for two second level lists to meet? Like this:
 
A B C D
1 2 3 x y
 
Can a second level list be before the first top-level item or after the
last? Like this:
 
A B C D or: A B C D
1 2 3 1 2 3
 
Can items from the top level list be deleted to result in any of those
situations?
 
Will there always be one top level portion, and 0 to N second level
lists? Can the top level list be empty? Can it become empty while there
are still second level lists?
 
Is the control structure also a linked list? Is the first entry always
the bounds of the top level list, and any subsequent ones always the
second level?
 
How is the insertion point specified; would it be {B,C} for my top
example (so always with two elements), or after {B} or before {C}?
 
If a second level span is deleted, does its entry disappear in the
control structure? (Here whether it is a linked list is important; if
not, then any back pointers into it will be problematical if the list
needs to close up.)
 
Sorry these are just random questions but you need to know the answers
before attempting any coding and I think we're all somewhat in the dark.
 
So a more rigorous specification might be in order.
 
--
bart
"Rick C. Hodgin" <rick.c.hodgin@gmail.com>: Jul 06 03:28PM -0400

On 7/6/2018 3:17 PM, Bart wrote:
>> are added, such as the 1..3 portion, the SControl list expands to hold
>> all start/end nodes for each portion of the link list
 
> Are there only two levels of list?
 
There are no levels. It is a continuous list that is at the same level.
 
>  1 2 3                                     1 2 3
 
> Can items from the top level list be deleted to result in any of those
> situations?
 
The 1 2 3 items are simply injected somewhere between A and Z in the
A B C .. X Y Z chain.
 
> second level lists?
 
> Is the control structure also a linked list? Is the first entry always the
> bounds of the top level list, and any subsequent ones always the second level?
 
For the SControl structure, I use something called a builder, which
is an array that expands up/down as needed. It basically contains
these members:
 
struct SBuilder
{
char* buffer;
int populated_length;
int allocated_length;
};
 
When allocated, populated_length is 0, allocated_length is some pre-
defined size (like 4KB). Each SControl structure is 8 bytes, for
example. So it continues up to reach 4KB before it re-allocates and
expands its size.
 
So, to answer succinctly: they are sequential in a buffer.
 
> How is the insertion point specified; would it be {B,C} for my top example
> (so always with two elements), or after {B} or before {C}?
 
You can add before or after any node. In my original example, the
chain 1..2..3 exists, and it is inserted between b and c, meaning
it could be injected after b, or before c.
 
 
> Sorry these are just random questions but you need to know the answers before
> attempting any coding and I think we're all somewhat in the dark.
 
> So a more rigorous specification might be in order.
 
It's more or less as I laid out. A literal two-way link-list, and
it has pointers to the start and end of each chain, and those chains
can be inserted anywhere in the middle of the list. And after they
are inserted, any of them can be deleted, or have others inserted,
before or after, any other node.
 
--
Rick C. Hodgin
Bart <bc@freeuk.com>: Jul 06 09:22PM +0100

On 06/07/2018 20:28, Rick C. Hodgin wrote:
>>> all start/end nodes for each portion of the link list
 
>> Are there only two levels of list?
 
> There are no levels.  It is a continuous list that is at the same level.
 
So you insert {1 2 3} between B and C in {A B C D} to result in:
 
A B 1 2 3 C D
 
This is just ordinary linked list processing where you insert or delete
single items or insert sequences.
 
But you have a separate structure that keeps tabs on certain
subsequences in that list (like the injected {1 2 3} sequence, but
noting the start and end item (as {1, 3} for this example), as well as
the original starting sequence {A,D}.
 
And you want to keep that structure up to date as a subsequences change.
Adding extra stuff in the middle is not a problem (if allowed), but
removing one of the end items (or the only item if subsequence is only
one element long) means an update in the other structure.
 
It sounds like you would rather not add extra links to each node to
point into an entry in that structure but that seems the most sensible
to me.
 
This can be done with a link in each node of an insertion (but a long
insertion can mean 1000s of updates). Or possible a link on the start
item only, but this means that if deleted an item in the middle, you
have to search for the start node.
 
--
bart
Anton Shepelev <anton.txt@gmail.com>: Jul 06 11:23PM +0300

Rick C. Hodgin:
 
> is doable and is my algorithm of choice at present, and (2) seems like
> it would waste memory but be faster.
 
> Does anybody have better suggestion or an alternate algorithm?
 
Can you maintain hash-tables of all the 'beg' and 'end'
members and
 
a. at deletion check whether the node being deleted is
the beginning or the end of some chain,
 
b. at insertion check whether the node before the one
inserted is the end of some chain and the node after
the one inserted is the beginning of some chain?
 
That should work in O(1) time.
 
--
() ascii ribbon campaign -- against html e-mail
/\ http://preview.tinyurl.com/qcy6mjc [archived]
"Rick C. Hodgin" <rick.c.hodgin@gmail.com>: Jul 06 04:30PM -0400

On 7/6/2018 4:22 PM, Bart wrote:
> that list (like the injected {1 2 3} sequence, but noting the start and end
> item (as {1, 3} for this example), as well as the original starting sequence
> {A,D}.
 
Correct.
 
> Adding extra stuff in the middle is not a problem (if allowed), but removing
> one of the end items (or the only item if subsequence is only one element
> long) means an update in the other structure.
 
Correct.
 
> It sounds like you would rather not add extra links to each node to point
> into an entry in that structure but that seems the most sensible to me.
 
It's my second option, and one I'm leaning toward the more I think
about it.
 
> insertion can mean 1000s of updates). Or possible a link on the start item
> only, but this means that if deleted an item in the middle, you have to
> search for the start node.
 
Correct. And memory's cheap these days.
 
--
Rick C. Hodgin
Richard Damon <Richard@Damon-Family.org>: Jul 06 03:38PM -0700

On 7/6/18 10:35 AM, Rick C. Hodgin wrote:
> above indicates.  I have the initial list from a..z, and as portions
> are added, such as the 1..3 portion, the SControl list expands to hold
> all start/end nodes for each portion of the link list
 
My comment was about your statement that:
>>> However, during my processing, I am not maintaining information that
>>> is relative to the loaded SControl structure. I simply traverse the
>>> chain node-by-node as I go through it.
 
If keeping these structures up to date is part of your requirements,
then you need to maintain them. This should be part of your basic
design, not something you try to 'bolt on' at the end. (And late changes
of this type can be costly is development and/or processing time).
 
>> it should be part of it, and the maintenance of it part of the
>> primitives.
 
> Agreed.  This is my current solution the (1) solution above.
 
(1) Using call backs would be more in line with my second case, where
the SControl is considered an addon, and the basic list routines are
providing hooks for a higher level set of controls.
 
Your (2), putting a pointer to the SControls (you need plural, probably
through a form of linked list) that started it would be one way to build
it in, and likely the fastest. Cheaper on memory but more costly on time
would be to have a list of the SControl structures available, and scan
them every time you delete a node.
 
> them all, nor even 1/3rd of them.  As such, I stick closer to C until I
> am able to later boostrap my code in my language, and expand it as the
> needs arise.
 
I gave some C++ advise, as you posted to both comp.lang.c and
comp.lang.c++, while C++ derived from C, the 'C++ way' to do things is
very often very different from the 'C Way' to do things.
"Chris M. Thomasson" <invalid_chris_thomasson@invalid.invalid>: Jul 06 03:51PM -0700

On 7/5/2018 6:39 PM, Rick C. Hodgin wrote:
>        +-----+   +-----+
>        |  _    _    _  |
>        +-|1|--|2|--|3|-+
 
Fwiw, one hackish way to identify a user node from a SControl node would
be to steal a low order bit and use it as a tag.
 
a -> b c -> d -> ... -> z
| ^
v |
cs(b->1) cs(3->c)
| ^
v |
1 -> 2 -> 3
 
 
b would have a control structure that made it point to 1 -> 2 -> 3
 
3 would have a control structure that made it point to c -> d -> ... -> z.
 
Check the stolen bit in the pointer value to tell normal nodes to ones
with control structures. b and 3 would have this bit set. All others
would not.
 
Still not exactly sure why a double linked list would not work out here.
One can easily inject multiple nodes at once anywhere in a doubly linked
list.
 
The stolen bits trick can allow for multiple different data structures
to exist in the same overall data-structure. It tells us what type the
pointer is pointing too.
 
 
 
Richard Damon <Richard@Damon-Family.org>: Jul 06 04:24PM -0700

On 7/6/18 3:51 PM, Chris M. Thomasson wrote:
 
> Still not exactly sure why a double linked list would not work out here.
> One can easily inject multiple nodes at once anywhere in a doubly linked
> list.
 
He says the list is a "two-way linked-list", so I presume that is what
you mean by double linked list (a has a pointer to b, and b has a back
pointer to a).
 
What it seems that Rick wants is to have saved "sub lists" on the main
list so that he can either navigate the whole list a-b-1-2-3-c-d-e-...
or he could navigate the sub list of 1-2-3 by calling up the SControl
structure for the list (start at beg, and go till you have visited end).
ram@zedat.fu-berlin.de (Stefan Ram): Jul 06 06:05PM

>On 06/30/2018 09:30 AM, Stefan Ram wrote:
>>Do C++ programmers have a word for a value that will yield an
^^^^^^^^^^^^^^^^^^
>>iterator when being the argument value in a call to cbegin?
^^^^^^^^
woodbrian77@gmail.com: Jul 06 10:22AM -0700

> six months on your project if we use my software as
> part of the project. There are more details here:
> http://webEbenezer.net/about.html
 
This is still available.
 
 
Brian
James Kuyper <jameskuyper@alumni.caltech.edu>: Jul 05 08:40PM -0400

On 07/05/2018 04:11 AM, Ian Collins wrote:
> On 16/06/18 11:54, James Kuyper wrote:
>> On 06/15/2018 05:30 PM, Ian Collins wrote:
>>> On 16/06/18 03:47, James Kuyper wrote:
...
 
> The key point form my side is that there often aren't "true
> requirements", at least not in great detail. The customer says she
> wants something to happen when an item is selected, she doesn't care how!
 
The true requirements are the ones that the customer would articulate,
if she could, and it's the system analyst's job to help her do so.
 
I have met people so inarticulate that they've done the equivalent of
claiming that the only requirement on the function sum() is that
sum(1,2)==3. However, I've usually been able to convince them that what
they actually mean is that sum(x,y) should return the sum of x and y.
In more complicated cases, where I couldn't figure out what they were
asking for the program to do, I've refused to start work on the program
until they could articulate it more clearly - giving them the equivalent
of int sum(int x, int y) { return 3;} would not have served any useful
purpose.
 
I was once hired specifically because of my expertise in APL, to take
existing APL code and modify it to achieve a particular goal. I had no
trouble reading the other guy's APL code (well-written APL is NOT
actually a write-only language, jokes to the contrary notwithstanding).
However, I could never get a clear explanation from my boss of what the
modified program should do. So I spent most of my time of that job doing
other tasks that involved C and PC/FOCUS.
 
>> the possible inputs. I find it easier to imagine such software if it's
>> only a small subroutine, and not an entire application.
 
> You could argue the same form any testing philosophy.
 
To the best of my knowledge, TDD is the only testing philosophy for
which it is claimed, at least by some people, that the tests define the
requirements. Therefore, it's the only one for which the fact that they
can't define the requirements is a problem. Other testing philosophies,
at least implicitly, accept that what tests can do is limited to
sparsely sampling the set of all possible inputs, looking for failures
to meet requirements. The key implication is that while failing a test
proves that a requirement has not been met, passing all test does NOT
prove that all requirements have been met. Therefore, the test can never
be treated as semantically equivalent to a proper statement of the
requirements.
Ian Collins <ian-news@hotmail.com>: Jul 06 10:03PM +1200

On 06/07/18 12:40, James Kuyper wrote:
>> wants something to happen when an item is selected, she doesn't care how!
 
> The true requirements are the ones that the customer would articulate,
> if she could, and it's the system analyst's job to help her do so.
 
Most small software outfits don't have system analysts!
 
> To the best of my knowledge, TDD is the only testing philosophy for
> which it is claimed, at least by some people, that the tests define the
> requirements.
 
Maybe we should say in many cases, the TDD tests are the only form of
requirements...
 
--
Ian.
James Kuyper <jameskuyper@alumni.caltech.edu>: Jul 06 07:33AM -0400

On 07/06/2018 06:03 AM, Ian Collins wrote:
> On 06/07/18 12:40, James Kuyper wrote:
>> On 07/05/2018 04:11 AM, Ian Collins wrote:
>>> On 16/06/18 11:54, James Kuyper wrote:
...
 
>> The true requirements are the ones that the customer would articulate,
>> if she could, and it's the system analyst's job to help her do so.
 
> Most small software outfits don't have system analysts!
 
Which means that some person who has other tasks as well, possibly
without adequate training, will have to act as a system analyst when
dealing with the customer. That's no different, in principle, from the
fact that sufficiently small outfits also don't necessarily have a
single person specializing in HR, or Marketing, or QA, or testing, or
Accounting, or janitorial work. Sufficiently small outfits don't even
have someone specializing in management - the "Boss" may simply be one
of the developers who also performs management tasks. Each of those
tasks still need to be done, even if there's not enough work to justify
hiring a specialist to do it. However, the lack of specialization also
means that the task might not be done as well as it could have been done
by a specialist.
 
>> requirements.
 
> Maybe we should say in many cases, the TDD tests are the only form of
> requirements...
 
Inadequately defined requirements are a very common problem - but that
problem should be acknowledged as such. Formal requirements which are
cross-referenced by the tests, rather than being defined by them, should
at least be acknowledged as an inconvenient but desirable ideal.
Instead, the supposed lack of need for such requirements seems to be
trumpeted as an advantage of TDD, at least by some people.
woodbrian77@gmail.com: Jul 06 10:13AM -0700

On Sunday, June 24, 2018 at 2:04:18 AM UTC-5, bitrex wrote:
 
 
 
 
Brian
Ebenezer Enterprises - Enjoying programming again.
https://github.com/Ebenezer-group/onwards
Manfred <invalid@add.invalid>: Jul 06 01:06PM +0200

On 7/5/2018 8:58 PM, Bart wrote:
 
> I would say that that was quite difficult to do.
In fact it is not how <windows.h> is supposed to be used.
 
 
> Such a header will anyway be the result of one 'rendering' of a header;
> the next one may produce different results because there has been a
> subtle change in the environment.
 
It is much better to use the #define's that are indicated in <windows.h>
#define WIN32_LEAN_AND_MEAN will result in a minimal set, otherwise
macros like NOGDI will suppress the related items (GDI functionality in
this case)
Random news lurker <grobbel@gmail.com>: Jul 06 09:03AM


> > > The imposter here posted from an "en-GB" timezone using Giganews.
 
> > I hope all of the mimicry could be halted sometime....
 
> where is rick now?
 
I hope he is doing well.
Yes, he is a bit odd, but isn't everyone who is still reading newsgroups?
His non-relevant posting are just as easily skipped as the Amine's for
instance, but the hatefull replies hurt my old eyes.
 
A nice day to all who make this group worth reading!
James Kuyper <jameskuyper@alumni.caltech.edu>: Jul 05 08:08PM -0400

On 06/30/2018 09:30 AM, Stefan Ram wrote:
 
> For example, cbegin would meaningfully accept an array,
> a vector, an initialization list, or a string, but not
> a pair (AFAIK), a stream, or a fundamental object.
 
24.7 p6 describes the only cbegin() in the standard that can take an
argument and isn't a member function. It returns std::begin(c), and as a
result of using a template with auto and decltype, doesn't care much
about what type c or std::begin(c) has. 24.7p1 describes std::begin(c)
as returning c.begin(). Again, as a result of templating, auto, and
decltype, it doesn't care much what type c or c.begin() has. Therefore,
I conclude that the only requirement for cbegin(c) is that c must have a
class type with a member function named begin() that can be invoked with
no arguments.
 
Am I missing something? If not, is there any point in naming such a concept?
You received this digest because you're subscribed to updates for this group. You can change your settings on the group membership page.
To unsubscribe from this group and stop receiving emails from it send an email to comp.lang.c+++unsubscribe@googlegroups.com.
Posted by at

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)