www.digitalmars.com         C & C++   DMDScript  

c++.stlsoft - Interesting? Maybe even for 1.7.1?

reply "Anton Sekeris" <no.spam inter.nl.net> writes:
This is a multipart message in MIME format

--Xananews.1.2.3

Matthew,

I have a long story, please bear with me. Today I ran into a problem at
work where I needed to splice a list into another list at a given
position. I needed the source list to remain intact with all its
iterators still valid. I also needed the item pointed to by the
iterator before which the second list to be removed. Preferably all
iterators on the first list must remain valid as well. If you're still
with me: bravo.

An example to illustrate: 
list 1: 1 2 3 4 5
list 2: 6 7 8 9 10
when my iterator it reaches the item 3 in list 1, it splices in list 2,
removes item 3 and can resume iterating, thus resulting effectively in
1 2 (3) 6 7 8 9 10 4 5

The practical problem at hand is the parsing of a list of items in
which particular items need to be substitued with list of other items
when encountered, sort of like parsing macro instances in a source file
while traversing a tokenlist.

I didn't find anything in stlsoft doing this or achieving this easily
(but I may have overlooked something), so I figured it might be of
interest to you/others.

I was in a huge hurry so a quickly hacked out the function below (see
also attached source including simple test). Off the bat i'd say it at
least needs polishing, error handling and is probably completely wrong,
but it works for me at this time. If you want to pick up the idea be my
guest. If you have something similar or better to use in stlsoft or
elsewhere, please let me know. I prefer using good tested code of
regarded others to my own shortsighted hacks.

Kind regards,
Anton Sekeris.

//
// function      : splice_replace
// description   : Splice the specified range of items (default begin
to end) from oListSrc into rListDest, in front of
//                 the position indicated by rDestPos. The item at
rDestPos itself is removed.
//                 Effectively a given item im the destination list is
replaced by a (range of items from) a source
//                 list.
//
// precondition  : source != destionation. Behaviour is undefined if
source and destination lists are equal
//
// postconditions: - iterators on the destination list should still be
valid
//                 - the iterator passed in as destination will point
at the start of the spliced in range of elements
//                 - the source list and any of its iterators should be
valid and unchanged
//
// notes         : This operation pretty is expensive.
//
template <typename T>
void splice_replace (
  list<T> &rListDest,
  list<T>::iterator& rDestPos,
  list<T> oListSrc,
  list<T>::iterator oBegin = 0,
  list<T>::iterator oEnd = 0
)
{
  list<T>::iterator oBeginLocal = (oBegin == 0 ? oListSrc.begin () :
oBegin);
  list<T>::iterator oEndLocal = (oEnd == 0 ? oListSrc.end () : oEnd);

  int iDist = distance (oBeginLocal, oEndLocal);

  rListDest.splice (rDestPos, oListSrc, oBeginLocal, oEndLocal);
  rListDest.erase (rDestPos);
  advance (rDestPos, -iDist);
}


--Xananews.1.2.3
Content-Type: Application/Octet-Stream; name=listtest.cpp
Content-Transfer-Encoding: base64

I2luY2x1ZGUgPGxpc3Q+DQojaW5jbHVkZSA8aW9zdHJlYW0+DQoNCnVzaW5nIHN0ZDo6bGlzdDsN
CnVzaW5nIHN0ZDo6Y291dDsNCnVzaW5nIHN0ZDo6ZW5kbDsNCg0KLy8NCi8vIGZ1bmN0aW9uICAg
ICAgOiBzcGxpY2VfcmVwbGFjZQ0KLy8gZGVzY3JpcHRpb24gICA6IFNwbGljZSB0aGUgc3BlY2lm
aWVkIHJhbmdlIG9mIGl0ZW1zIChkZWZhdWx0IGJlZ2luIHRvIGVuZCkgZnJvbSBvTGlzdFNyYyBp
bnRvIHJMaXN0RGVzdCwgaW4gZnJvbnQgb2YNCi8vICAgICAgICAgICAgICAgICB0aGUgcG9zaXRp
b24gaW5kaWNhdGVkIGJ5IHJEZXN0UG9zLiBUaGUgaXRlbSBhdCByRGVzdFBvcyBpdHNlbGYgaXMg
cmVtb3ZlZC4NCi8vICAgICAgICAgICAgICAgICBFZmZlY3RpdmVseSBhIGdpdmVuIGl0ZW0gaW0g
dGhlIGRlc3RpbmF0aW9uIGxpc3QgaXMgcmVwbGFjZWQgYnkgYSAocmFuZ2Ugb2YgaXRlbXMgZnJv
bSkgYSBzb3VyY2UNCi8vICAgICAgICAgICAgICAgICBsaXN0Lg0KLy8NCi8vIHByZWNvbmRpdGlv
biAgOiBzb3VyY2UgIT0gZGVzdGlvbmF0aW9uLiBCZWhhdmlvdXIgaXMgdW5kZWZpbmVkIGlmIHNv
dXJjZSBhbmQgZGVzdGluYXRpb24gbGlzdHMgYXJlIGVxdWFsDQovLw0KLy8gcG9zdGNvbmRpdGlv
bnM6IC0gaXRlcmF0b3JzIG9uIHRoZSBkZXN0aW5hdGlvbiBsaXN0IHNob3VsZCBzdGlsbCBiZSB2
YWxpZA0KLy8gICAgICAgICAgICAgICAgIC0gdGhlIGl0ZXJhdG9yIHBhc3NlZCBpbiBhcyBkZXN0
aW5hdGlvbiB3aWxsIHBvaW50IGF0IHRoZSBzdGFydCBvZiB0aGUgc3BsaWNlZCBpbiByYW5nZSBv
ZiBlbGVtZW50cw0KLy8gICAgICAgICAgICAgICAgIC0gdGhlIHNvdXJjZSBsaXN0IGFuZCBhbnkg
b2YgaXRzIGl0ZXJhdG9ycyBzaG91bGQgYmUgdmFsaWQgYW5kIHVuY2hhbmdlZA0KLy8NCi8vIG5v
dGVzICAgICAgICAgOiBUaGlzIG9wZXJhdGlvbiBwcmV0dHkgaXMgZXhwZW5zaXZlLg0KLy8NCnRl
bXBsYXRlIDx0eXBlbmFtZSBUPg0Kdm9pZCBzcGxpY2VfcmVwbGFjZSAoDQogIGxpc3Q8VD4gJnJM
aXN0RGVzdCwNCiAgbGlzdDxUPjo6aXRlcmF0b3ImIHJEZXN0UG9zLA0KICBsaXN0PFQ+IG9MaXN0
U3JjLA0KICBsaXN0PFQ+OjppdGVyYXRvciBvQmVnaW4gPSAwLA0KICBsaXN0PFQ+OjppdGVyYXRv
ciBvRW5kID0gMA0KKQ0Kew0KICBsaXN0PFQ+OjppdGVyYXRvciBvQmVnaW5Mb2NhbCA9IChvQmVn
aW4gPT0gMCA/IG9MaXN0U3JjLmJlZ2luICgpIDogb0JlZ2luKTsNCiAgbGlzdDxUPjo6aXRlcmF0
b3Igb0VuZExvY2FsID0gKG9FbmQgPT0gMCA/IG9MaXN0U3JjLmVuZCAoKSA6IG9FbmQpOw0KDQog
IGludCBpRGlzdCA9IGRpc3RhbmNlIChvQmVnaW5Mb2NhbCwgb0VuZExvY2FsKTsNCg0KICByTGlz
dERlc3Quc3BsaWNlIChyRGVzdFBvcywgb0xpc3RTcmMsIG9CZWdpbkxvY2FsLCBvRW5kTG9jYWwp
Ow0KICByTGlzdERlc3QuZXJhc2UgKHJEZXN0UG9zKTsNCiAgYWR2YW5jZSAockRlc3RQb3MsIC1p
RGlzdCk7DQp9DQoNCmludCBtYWluICgpDQp7DQogIGxpc3Q8aW50PiBvOw0KICBsaXN0PGludD4g
bzI7DQoNCiAgby5wdXNoX2JhY2sgKDApOw0KICBvLnB1c2hfYmFjayAoMSk7DQogIG8ucHVzaF9i
YWNrICgyKTsNCiAgby5wdXNoX2JhY2sgKDMpOw0KICBvLnB1c2hfYmFjayAoNCk7DQogIG8ucHVz
aF9iYWNrICg1KTsNCg0KICBvMi5wdXNoX2JhY2sgKDYpOw0KICBvMi5wdXNoX2JhY2sgKDcpOw0K
ICBvMi5wdXNoX2JhY2sgKDgpOw0KICBvMi5wdXNoX2JhY2sgKDkpOw0KICBvMi5wdXNoX2JhY2sg
KDEwKTsNCiAgbzIucHVzaF9iYWNrICgxMSk7DQoNCiAgaW50X2xpc3RfaXRlciBpdGVyOw0KICBp
bnRfbGlzdF9pdGVyIGl0ZXIyOw0KICBpbnRfbGlzdF9pdGVyIGl0ZXIzOw0KICBpbnRfbGlzdF9p
dGVyIGl0ZXI0Ow0KDQogIGNvdXQgPDwgIm8gICAgICAgICAgIDogIjsNCiAgZm9yIChpdGVyID0g
by5iZWdpbiAoKTsgaXRlciAhPSBvLmVuZCAoKTsgKytpdGVyKQ0KICB7DQogICAgY291dCA8PCAq
aXRlciA8PCAiICI7DQogIH0NCg0KICBpdGVyMiA9IG8yLmJlZ2luICgpOw0KICArK2l0ZXIyOw0K
ICArK2l0ZXIyOw0KICBjb3V0IDw8IGVuZGwgPDwgIml0ZXIyOiAiIDw8ICppdGVyMiA8PCBlbmRs
Ow0KDQogIGl0ZXIzID0gby5iZWdpbiAoKTsNCiAgKytpdGVyMzsNCiAgKytpdGVyMzsNCiAgY291
dCA8PCAiaXRlcjM6ICIgPDwgKml0ZXIzIDw8IGVuZGw7DQoNCiAgaXRlcjQgPSBvLmVuZCAoKTsN
CiAgLS1pdGVyNDsNCiAgY291dCA8PCAiaXRlcjQ6ICIgPDwgKml0ZXI0IDw8IGVuZGw7DQoNCiAg
Y291dCA8PCBlbmRsDQogICAgICAgPDwgIm8gc3BsaWNlZCBvMjogIjsNCiAgZm9yIChpdGVyID0g
by5iZWdpbiAoKTsgaXRlciAhPSBvLmVuZCAoKTsgKytpdGVyKQ0KICB7DQogICAgY291dCA8PCAq
aXRlciA8PCAiICI7DQogICAgaWYgKCppdGVyID09IDMpDQogICAgew0KICAgICAgZm5TcGxpY2VJ
bjxpbnQ+IChvLCBpdGVyLCBvMik7DQogICAgfQ0KICB9DQoNCiAgY291dCA8PCBlbmRsDQogICAg
ICAgPDwgIm8yICAgICAgICAgIDogIjsNCiAgZm9yIChpdGVyID0gbzIuYmVnaW4gKCk7IGl0ZXIg
IT0gbzIuZW5kICgpOyArK2l0ZXIpDQogIHsNCiAgICBjb3V0IDw8ICppdGVyIDw8ICIgIjsNCiAg
fQ0KDQogIGNvdXQgPDwgZW5kbCA8PCAiaXRlcjI6ICIgPDwgKml0ZXIyIDw8IGVuZGw7DQogIGNv
dXQgPDwgIml0ZXIzOiAiIDw8ICppdGVyMyA8PCBlbmRsOw0KICBjb3V0IDw8ICJpdGVyNDogIiA8
PCAqaXRlcjQgPDwgZW5kbDsNCg0KICByZXR1cm4gMDsNCn0NCg0KLy8gRW5kIG9mIGZpbGUuDQo=

--Xananews.1.2.3--
Mar 10 2004
parent reply "Matthew" <matthew stlsoft.org> writes:
Anton

Just wanted to acknowledge your post. I'll look into it in the next few days
and let you know.

Thanks for the interest.

Cheers

Matthew

"Anton Sekeris" <no.spam inter.nl.net> wrote in message
news:c2o2gg$2fsd$1 digitaldaemon.com...
 Matthew,

 I have a long story, please bear with me. Today I ran into a problem at
 work where I needed to splice a list into another list at a given
 position. I needed the source list to remain intact with all its
 iterators still valid. I also needed the item pointed to by the
 iterator before which the second list to be removed. Preferably all
 iterators on the first list must remain valid as well. If you're still
 with me: bravo.

 An example to illustrate:
 list 1: 1 2 3 4 5
 list 2: 6 7 8 9 10
 when my iterator it reaches the item 3 in list 1, it splices in list 2,
 removes item 3 and can resume iterating, thus resulting effectively in
 1 2 (3) 6 7 8 9 10 4 5

 The practical problem at hand is the parsing of a list of items in
 which particular items need to be substitued with list of other items
 when encountered, sort of like parsing macro instances in a source file
 while traversing a tokenlist.

 I didn't find anything in stlsoft doing this or achieving this easily
 (but I may have overlooked something), so I figured it might be of
 interest to you/others.

 I was in a huge hurry so a quickly hacked out the function below (see
 also attached source including simple test). Off the bat i'd say it at
 least needs polishing, error handling and is probably completely wrong,
 but it works for me at this time. If you want to pick up the idea be my
 guest. If you have something similar or better to use in stlsoft or
 elsewhere, please let me know. I prefer using good tested code of
 regarded others to my own shortsighted hacks.

 Kind regards,
 Anton Sekeris.

 //
 // function      : splice_replace
 // description   : Splice the specified range of items (default begin
 to end) from oListSrc into rListDest, in front of
 //                 the position indicated by rDestPos. The item at
 rDestPos itself is removed.
 //                 Effectively a given item im the destination list is
 replaced by a (range of items from) a source
 //                 list.
 //
 // precondition  : source != destionation. Behaviour is undefined if
 source and destination lists are equal
 //
 // postconditions: - iterators on the destination list should still be
 valid
 //                 - the iterator passed in as destination will point
 at the start of the spliced in range of elements
 //                 - the source list and any of its iterators should be
 valid and unchanged
 //
 // notes         : This operation pretty is expensive.
 //
 template <typename T>
 void splice_replace (
   list<T> &rListDest,
   list<T>::iterator& rDestPos,
   list<T> oListSrc,
   list<T>::iterator oBegin = 0,
   list<T>::iterator oEnd = 0
 )
 {
   list<T>::iterator oBeginLocal = (oBegin == 0 ? oListSrc.begin () :
 oBegin);
   list<T>::iterator oEndLocal = (oEnd == 0 ? oListSrc.end () : oEnd);

   int iDist = distance (oBeginLocal, oEndLocal);

   rListDest.splice (rDestPos, oListSrc, oBeginLocal, oEndLocal);
   rListDest.erase (rDestPos);
   advance (rDestPos, -iDist);
 }

Mar 10 2004
parent reply "Anton Sekeris" <no.spam inter.nl.net> writes:
Matthew,

I think I was having a very bad day when I wrote my splice_replace. I
forgot all about using an inserter as a parameter to the STL copy
algorithm. Using that and a simple erase to remove the element to
replace solves it all. Which makes the entire matter a lot less
interesting.

Sorry for wasting your time.

Anton.

P.S. My lapse of sanity was actually pointed out to me by one of my
junior engineers. I'll never hear the end of it :-(


Matthew wrote:

 Anton
 
 Just wanted to acknowledge your post. I'll look into it in the next
 few days and let you know.
 
 Thanks for the interest.
 
 Cheers
 
 Matthew
 

Mar 15 2004
parent "Matthew" <matthew stlsoft.org> writes:
LOL! I shall congratulate myself for wisely not having expended any effort
on it as yet. ;)

"Anton Sekeris" <no.spam inter.nl.net> wrote in message
news:c357m6$cte$1 digitaldaemon.com...
 Matthew,

 I think I was having a very bad day when I wrote my splice_replace. I
 forgot all about using an inserter as a parameter to the STL copy
 algorithm. Using that and a simple erase to remove the element to
 replace solves it all. Which makes the entire matter a lot less
 interesting.

 Sorry for wasting your time.

 Anton.

 P.S. My lapse of sanity was actually pointed out to me by one of my
 junior engineers. I'll never hear the end of it :-(


 Matthew wrote:

 Anton

 Just wanted to acknowledge your post. I'll look into it in the next
 few days and let you know.

 Thanks for the interest.

 Cheers

 Matthew


Mar 15 2004