C/C++ people please critique this as the basis for an improvement to
std::deque. It seems to have the key functionality of std::deque and
does it much more simply while saving time and space.
https://www.cplusplus.com/reference/deque/deque/

#define tape_element unsigned char

class Tape_Type
{ private:
int Tape_Head = 0; // Can be negative
std::vector<tape_element> Left; // Stores left expansion
std::vector<tape_element> Right; // Stores right expansion
tape_element & operator[](int index);

public:
void move_left(); // Tape_Head--; Left.push_back(0); as needed
void move_right(); // Tape_Head++; Left.push_back(0); as needed
void Write(tape_element Y){ this->operator[](Tape_Head) = Y; };
tape_element Read() { return this->operator[](Tape_Head); };
Tape_Type(){ Right.push_back('_'); } // constructor
void Output();
};

tape_element& Tape_Type::operator[](int index)
{ if (index > 0)
return Right[index];
int Left_Index = ((index * -1) -1);
return Left[Left_Index];
}

void Tape_Type::Output()
{ printf("Tape_Type::Output()\n");

if (Left.size())
{
int Last_One = Left.size() - 1;
for (int N = Last_One; N >= 0; N--)
{
int TH = (N + 1) * -1; // determine Tape_Head from N
printf("[%04d]:%c Left[%02d]\n", TH, Left[N], N);
}
}
if (Right.size())
for (int N = 0; N < Right.size(); N++)
printf("[%04d]:%c Right[%02d]\n", N, Right[N], N);
}

void Tape_Type::move_left()
{ Tape_Head--;
int Left_Index = ((Tape_Head * -1) -1);
if (Left_Index == Left.size())
Left.push_back('_');
}

void Tape_Type::move_right()
{ Tape_Head++;
if (Tape_Head == Right.size())
Right.push_back('_');
}

--
Copyright 2022 Pete Olcott

"Talent hits a target no one else can hit;
Genius hits a target no one else can see."
Arthur Schopenhauer

On Thu, 12 May 2022 17:51:25 -0500
olcott <NoOne@NoWhere.com> wrote:

> C/C++ people please critique this as the basis for an improvement to
> std::deque. It seems to have the key functionality of std::deque and
> does it much more simply while saving time and space.
> https://www.cplusplus.com/reference/deque/deque/
>
> #define tape_element unsigned char
>
> class Tape_Type
> {
> private:
> int Tape_Head = 0; // Can be negative
> std::vector<tape_element> Left; // Stores left expansion
> std::vector<tape_element> Right; // Stores right expansion
> tape_element & operator[](int index);
>
> public:
> void move_left(); // Tape_Head--; Left.push_back(0); as needed
> void move_right(); // Tape_Head++; Left.push_back(0); as needed
> void Write(tape_element Y){ this->operator[](Tape_Head) = Y; };
> tape_element Read() { return this->operator[](Tape_Head); };
> Tape_Type(){ Right.push_back('_'); } // constructor
> void Output();
> };
>
> tape_element& Tape_Type::operator[](int index)
> {
> if (index > 0)
> return Right[index];
> int Left_Index = ((index * -1) -1);
> return Left[Left_Index];
> }
>
> void Tape_Type::Output()
> {
> printf("Tape_Type::Output()\n");
>
> if (Left.size())
> {
> int Last_One = Left.size() - 1;
> for (int N = Last_One; N >= 0; N--)
> {
> int TH = (N + 1) * -1; // determine Tape_Head from N
> printf("[%04d]:%c Left[%02d]\n", TH, Left[N], N);
> }
> }
> if (Right.size())
> for (int N = 0; N < Right.size(); N++)
> printf("[%04d]:%c Right[%02d]\n", N, Right[N], N);
> }
>
> void Tape_Type::move_left()
> {
> Tape_Head--;
> int Left_Index = ((Tape_Head * -1) -1);
> if (Left_Index == Left.size())
> Left.push_back('_');
> }
>
> void Tape_Type::move_right()
> {
> Tape_Head++;
> if (Tape_Head == Right.size())
> Right.push_back('_');
> }

It might be a more appropriate solution than std::deque for your
specific use-case however it is NOT an improvement to std::deque for
the general case -- see my reply in the other thread for why.

/Flibble

On 5/12/2022 5:56 PM, Mr Flibble wrote:
> On Thu, 12 May 2022 17:51:25 -0500
> olcott <NoOne@NoWhere.com> wrote:
>
>> C/C++ people please critique this as the basis for an improvement to
>> std::deque. It seems to have the key functionality of std::deque and
>> does it much more simply while saving time and space.
>> https://www.cplusplus.com/reference/deque/deque/
>>
>> #define tape_element unsigned char
>>
>> class Tape_Type
>> {
>> private:
>> int Tape_Head = 0; // Can be negative
>> std::vector<tape_element> Left; // Stores left expansion
>> std::vector<tape_element> Right; // Stores right expansion
>> tape_element & operator[](int index);
>>
>> public:
>> void move_left(); // Tape_Head--; Left.push_back(0); as needed
>> void move_right(); // Tape_Head++; Left.push_back(0); as needed
>> void Write(tape_element Y){ this->operator[](Tape_Head) = Y; };
>> tape_element Read() { return this->operator[](Tape_Head); };
>> Tape_Type(){ Right.push_back('_'); } // constructor
>> void Output();
>> };
>>
>> tape_element& Tape_Type::operator[](int index)
>> {
>> if (index > 0)
>> return Right[index];
>> int Left_Index = ((index * -1) -1);
>> return Left[Left_Index];
>> }
>>
>> void Tape_Type::Output()
>> {
>> printf("Tape_Type::Output()\n");
>>
>> if (Left.size())
>> {
>> int Last_One = Left.size() - 1;
>> for (int N = Last_One; N >= 0; N--)
>> {
>> int TH = (N + 1) * -1; // determine Tape_Head from N
>> printf("[%04d]:%c Left[%02d]\n", TH, Left[N], N);
>> }
>> }
>> if (Right.size())
>> for (int N = 0; N < Right.size(); N++)
>> printf("[%04d]:%c Right[%02d]\n", N, Right[N], N);
>> }
>>
>> void Tape_Type::move_left()
>> {
>> Tape_Head--;
>> int Left_Index = ((Tape_Head * -1) -1);
>> if (Left_Index == Left.size())
>> Left.push_back('_');
>> }
>>
>> void Tape_Type::move_right()
>> {
>> Tape_Head++;
>> if (Tape_Head == Right.size())
>> Right.push_back('_');
>> }
>
> It might be a more appropriate solution than std::deque for your
> specific use-case however it is NOT an improvement to std::deque for
> the general case -- see my reply in the other thread for why.
>
> /Flibble
>

I didn't see any reason why it would not make a better std::deque.

--
Copyright 2022 Pete Olcott

"Talent hits a target no one else can hit;
Genius hits a target no one else can see."
Arthur Schopenhauer

On Thu, 12 May 2022 18:09:39 -0500
olcott <NoOne@NoWhere.com> wrote:

> On 5/12/2022 5:56 PM, Mr Flibble wrote:
> > On Thu, 12 May 2022 17:51:25 -0500
> > olcott <NoOne@NoWhere.com> wrote:
> >
> >> C/C++ people please critique this as the basis for an improvement
> >> to std::deque. It seems to have the key functionality of
> >> std::deque and does it much more simply while saving time and
> >> space. https://www.cplusplus.com/reference/deque/deque/
> >>
> >> #define tape_element unsigned char
> >>
> >> class Tape_Type
> >> {
> >> private:
> >> int Tape_Head = 0; // Can be negative
> >> std::vector<tape_element> Left; // Stores left expansion
> >> std::vector<tape_element> Right; // Stores right expansion
> >> tape_element & operator[](int index);
> >>
> >> public:
> >> void move_left(); // Tape_Head--; Left.push_back(0); as
> >> needed void move_right(); // Tape_Head++; Left.push_back(0);
> >> as needed void Write(tape_element Y){ this->operator[](Tape_Head)
> >> = Y; }; tape_element Read() { return
> >> this->operator[](Tape_Head); }; Tape_Type(){ Right.push_back('_');
> >> } // constructor void Output();
> >> };
> >>
> >> tape_element& Tape_Type::operator[](int index)
> >> {
> >> if (index > 0)
> >> return Right[index];
> >> int Left_Index = ((index * -1) -1);
> >> return Left[Left_Index];
> >> }
> >>
> >> void Tape_Type::Output()
> >> {
> >> printf("Tape_Type::Output()\n");
> >>
> >> if (Left.size())
> >> {
> >> int Last_One = Left.size() - 1;
> >> for (int N = Last_One; N >= 0; N--)
> >> {
> >> int TH = (N + 1) * -1; // determine Tape_Head from N
> >> printf("[%04d]:%c Left[%02d]\n", TH, Left[N], N);
> >> }
> >> }
> >> if (Right.size())
> >> for (int N = 0; N < Right.size(); N++)
> >> printf("[%04d]:%c Right[%02d]\n", N, Right[N], N);
> >> }
> >>
> >> void Tape_Type::move_left()
> >> {
> >> Tape_Head--;
> >> int Left_Index = ((Tape_Head * -1) -1);
> >> if (Left_Index == Left.size())
> >> Left.push_back('_');
> >> }
> >>
> >> void Tape_Type::move_right()
> >> {
> >> Tape_Head++;
> >> if (Tape_Head == Right.size())
> >> Right.push_back('_');
> >> }
> >
> > It might be a more appropriate solution than std::deque for your
> > specific use-case however it is NOT an improvement to std::deque for
> > the general case -- see my reply in the other thread for why.
> >
> > /Flibble
> >
>
> I didn't see any reason why it would not make a better std::deque.
Because it doesn't meet the complexity and referential integrity
requirements of std::deque.

/Flibble

On 5/12/22 6:51 PM, olcott wrote:
> C/C++ people please critique this as the basis for an improvement to
> std::deque. It seems to have the key functionality of std::deque and
> does it much more simply while saving time and space.
> https://www.cplusplus.com/reference/deque/deque/
>
> #define tape_element unsigned char
>
> class Tape_Type
> {
> private:
>   int Tape_Head = 0;               // Can be negative
>   std::vector<tape_element> Left;  // Stores left expansion
>   std::vector<tape_element> Right; // Stores right expansion
>   tape_element & operator[](int index);
>
> public:
>   void move_left();      // Tape_Head--; Left.push_back(0); as needed
>   void move_right();     // Tape_Head++; Left.push_back(0); as needed
>   void Write(tape_element Y){ this->operator[](Tape_Head) = Y; };
>   tape_element Read()       { return this->operator[](Tape_Head); };
>   Tape_Type(){ Right.push_back('_'); } // constructor
>   void Output();
> };
>
> tape_element& Tape_Type::operator[](int index)
> {
>   if (index > 0)
>     return Right[index];
>   int Left_Index = ((index * -1) -1);
>   return Left[Left_Index];
> }
>
> void Tape_Type::Output()
> {
>   printf("Tape_Type::Output()\n");
>
>   if (Left.size())
>   {
>     int Last_One = Left.size() - 1;
>     for (int N = Last_One; N >= 0; N--)
>     {
>       int TH = (N + 1) * -1; // determine Tape_Head from N
>       printf("[%04d]:%c   Left[%02d]\n", TH, Left[N], N);
>     }
>   }
>   if (Right.size())
>     for (int N = 0; N < Right.size(); N++)
>       printf("[%04d]:%c  Right[%02d]\n", N, Right[N], N);
> }
>
> void Tape_Type::move_left()
> {
>   Tape_Head--;
>   int Left_Index = ((Tape_Head * -1) -1);
>   if (Left_Index == Left.size())
>     Left.push_back('_');
> }
>
> void Tape_Type::move_right()
> {
>   Tape_Head++;
>   if (Tape_Head == Right.size())
>     Right.push_back('_');
> }
>
>
>

Looks at what indexing with an index value of 0 does.

Operator [] want to test index >= 0, not > 0

On 5/12/2022 6:23 PM, Richard Damon wrote:
> On 5/12/22 6:51 PM, olcott wrote:
>> C/C++ people please critique this as the basis for an improvement to
>> std::deque. It seems to have the key functionality of std::deque and
>> does it much more simply while saving time and space.
>> https://www.cplusplus.com/reference/deque/deque/
>>
>> #define tape_element unsigned char
>>
>> class Tape_Type
>> {
>> private:
>>    int Tape_Head = 0;               // Can be negative
>>    std::vector<tape_element> Left;  // Stores left expansion
>>    std::vector<tape_element> Right; // Stores right expansion
>>    tape_element & operator[](int index);
>>
>> public:
>>    void move_left();      // Tape_Head--; Left.push_back(0); as needed
>>    void move_right();     // Tape_Head++; Left.push_back(0); as needed
>>    void Write(tape_element Y){ this->operator[](Tape_Head) = Y; };
>>    tape_element Read()       { return this->operator[](Tape_Head); };
>>    Tape_Type(){ Right.push_back('_'); } // constructor
>>    void Output();
>> };
>>
>> tape_element& Tape_Type::operator[](int index)
>> {
>>    if (index > 0)
>>      return Right[index];
>>    int Left_Index = ((index * -1) -1);
>>    return Left[Left_Index];
>> }
>>
>> void Tape_Type::Output()
>> {
>>    printf("Tape_Type::Output()\n");
>>
>>    if (Left.size())
>>    {
>>      int Last_One = Left.size() - 1;
>>      for (int N = Last_One; N >= 0; N--)
>>      {
>>        int TH = (N + 1) * -1; // determine Tape_Head from N
>>        printf("[%04d]:%c   Left[%02d]\n", TH, Left[N], N);
>>      }
>>    }
>>    if (Right.size())
>>      for (int N = 0; N < Right.size(); N++)
>>        printf("[%04d]:%c  Right[%02d]\n", N, Right[N], N);
>> }
>>
>> void Tape_Type::move_left()
>> {
>>    Tape_Head--;
>>    int Left_Index = ((Tape_Head * -1) -1);
>>    if (Left_Index == Left.size())
>>      Left.push_back('_');
>> }
>>
>> void Tape_Type::move_right()
>> {
>>    Tape_Head++;
>>    if (Tape_Head == Right.size())
>>      Right.push_back('_');
>> }
>>
>>
>>
>
> Looks at what indexing with an index value of 0 does.
>
> Operator [] want to test index >= 0, not > 0

Good catch. I just wrote that function as a simplification.

--
Copyright 2022 Pete Olcott

"Talent hits a target no one else can hit;
Genius hits a target no one else can see."
Arthur Schopenhauer

On 5/12/2022 6:22 PM, Mr Flibble wrote:
> On Thu, 12 May 2022 18:09:39 -0500
> olcott <NoOne@NoWhere.com> wrote:
>
>> On 5/12/2022 5:56 PM, Mr Flibble wrote:
>>> On Thu, 12 May 2022 17:51:25 -0500
>>> olcott <NoOne@NoWhere.com> wrote:
>>>
>>>> C/C++ people please critique this as the basis for an improvement
>>>> to std::deque. It seems to have the key functionality of
>>>> std::deque and does it much more simply while saving time and
>>>> space. https://www.cplusplus.com/reference/deque/deque/
>>>>
>>>> #define tape_element unsigned char
>>>>
>>>> class Tape_Type
>>>> {
>>>> private:
>>>> int Tape_Head = 0; // Can be negative
>>>> std::vector<tape_element> Left; // Stores left expansion
>>>> std::vector<tape_element> Right; // Stores right expansion
>>>> tape_element & operator[](int index);
>>>>
>>>> public:
>>>> void move_left(); // Tape_Head--; Left.push_back(0); as
>>>> needed void move_right(); // Tape_Head++; Left.push_back(0);
>>>> as needed void Write(tape_element Y){ this->operator[](Tape_Head)
>>>> = Y; }; tape_element Read() { return
>>>> this->operator[](Tape_Head); }; Tape_Type(){ Right.push_back('_');
>>>> } // constructor void Output();
>>>> };
>>>>
>>>> tape_element& Tape_Type::operator[](int index)
>>>> {
>>>> if (index > 0)
>>>> return Right[index];
>>>> int Left_Index = ((index * -1) -1);
>>>> return Left[Left_Index];
>>>> }
>>>>
>>>> void Tape_Type::Output()
>>>> {
>>>> printf("Tape_Type::Output()\n");
>>>>
>>>> if (Left.size())
>>>> {
>>>> int Last_One = Left.size() - 1;
>>>> for (int N = Last_One; N >= 0; N--)
>>>> {
>>>> int TH = (N + 1) * -1; // determine Tape_Head from N
>>>> printf("[%04d]:%c Left[%02d]\n", TH, Left[N], N);
>>>> }
>>>> }
>>>> if (Right.size())
>>>> for (int N = 0; N < Right.size(); N++)
>>>> printf("[%04d]:%c Right[%02d]\n", N, Right[N], N);
>>>> }
>>>>
>>>> void Tape_Type::move_left()
>>>> {
>>>> Tape_Head--;
>>>> int Left_Index = ((Tape_Head * -1) -1);
>>>> if (Left_Index == Left.size())
>>>> Left.push_back('_');
>>>> }
>>>>
>>>> void Tape_Type::move_right()
>>>> {
>>>> Tape_Head++;
>>>> if (Tape_Head == Right.size())
>>>> Right.push_back('_');
>>>> }
>>>
>>> It might be a more appropriate solution than std::deque for your
>>> specific use-case however it is NOT an improvement to std::deque for
>>> the general case -- see my reply in the other thread for why.
>>>
>>> /Flibble
>>>
>>
>> I didn't see any reason why it would not make a better std::deque.
>
> Because it doesn't meet the complexity and referential integrity
> requirements of std::deque.
>
> /Flibble
>

It is faster then std::deque.
I couldn't find what you mean by referential integrity it has too many
different meanings. invalidating iterators seemed to be what you mean
otherwise I have no idea.

--
Copyright 2022 Pete Olcott

"Talent hits a target no one else can hit;
Genius hits a target no one else can see."
Arthur Schopenhauer

On Thu, 12 May 2022 18:38:49 -0500
olcott <NoOne@NoWhere.com> wrote:

> On 5/12/2022 6:22 PM, Mr Flibble wrote:
> > On Thu, 12 May 2022 18:09:39 -0500
> > olcott <NoOne@NoWhere.com> wrote:
> >
> >> On 5/12/2022 5:56 PM, Mr Flibble wrote:
> >>> On Thu, 12 May 2022 17:51:25 -0500
> >>> olcott <NoOne@NoWhere.com> wrote:
> >>>
> >>>> C/C++ people please critique this as the basis for an improvement
> >>>> to std::deque. It seems to have the key functionality of
> >>>> std::deque and does it much more simply while saving time and
> >>>> space. https://www.cplusplus.com/reference/deque/deque/
> >>>>
> >>>> #define tape_element unsigned char
> >>>>
> >>>> class Tape_Type
> >>>> {
> >>>> private:
> >>>> int Tape_Head = 0; // Can be negative
> >>>> std::vector<tape_element> Left; // Stores left expansion
> >>>> std::vector<tape_element> Right; // Stores right expansion
> >>>> tape_element & operator[](int index);
> >>>>
> >>>> public:
> >>>> void move_left(); // Tape_Head--; Left.push_back(0); as
> >>>> needed void move_right(); // Tape_Head++; Left.push_back(0);
> >>>> as needed void Write(tape_element Y){ this->operator[](Tape_Head)
> >>>> = Y; }; tape_element Read() { return
> >>>> this->operator[](Tape_Head); }; Tape_Type(){
> >>>> Right.push_back('_'); } // constructor void Output();
> >>>> };
> >>>>
> >>>> tape_element& Tape_Type::operator[](int index)
> >>>> {
> >>>> if (index > 0)
> >>>> return Right[index];
> >>>> int Left_Index = ((index * -1) -1);
> >>>> return Left[Left_Index];
> >>>> }
> >>>>
> >>>> void Tape_Type::Output()
> >>>> {
> >>>> printf("Tape_Type::Output()\n");
> >>>>
> >>>> if (Left.size())
> >>>> {
> >>>> int Last_One = Left.size() - 1;
> >>>> for (int N = Last_One; N >= 0; N--)
> >>>> {
> >>>> int TH = (N + 1) * -1; // determine Tape_Head from N
> >>>> printf("[%04d]:%c Left[%02d]\n", TH, Left[N], N);
> >>>> }
> >>>> }
> >>>> if (Right.size())
> >>>> for (int N = 0; N < Right.size(); N++)
> >>>> printf("[%04d]:%c Right[%02d]\n", N, Right[N], N);
> >>>> }
> >>>>
> >>>> void Tape_Type::move_left()
> >>>> {
> >>>> Tape_Head--;
> >>>> int Left_Index = ((Tape_Head * -1) -1);
> >>>> if (Left_Index == Left.size())
> >>>> Left.push_back('_');
> >>>> }
> >>>>
> >>>> void Tape_Type::move_right()
> >>>> {
> >>>> Tape_Head++;
> >>>> if (Tape_Head == Right.size())
> >>>> Right.push_back('_');
> >>>> }
> >>>
> >>> It might be a more appropriate solution than std::deque for your
> >>> specific use-case however it is NOT an improvement to std::deque
> >>> for the general case -- see my reply in the other thread for why.
> >>>
> >>> /Flibble
> >>>
> >>
> >> I didn't see any reason why it would not make a better std::deque.
> >>
> >
> > Because it doesn't meet the complexity and referential integrity
> > requirements of std::deque.
> >
> > /Flibble
> >
>
> It is faster then std::deque.
> I couldn't find what you mean by referential integrity it has too
> many different meanings. invalidating iterators seemed to be what you
> mean otherwise I have no idea.
I see you are choosing to ignore my reply in the other thread. OK, I
will repost why you are wrong here:

* referential integrity and iterator invalidation are different
things: when you add or remove elements to either end of a
std::deque iterators are indeed invalidated however references to
existing elements remain valid
* If you do 1000 push_fronts followed by 1000 push_backs followed by
1000 pop_fronts all is good however your next pop_front will have
linear complexity, O(n), as it will necessitate removal of the first
element of the right std::vector.

/Flibble

On 5/12/2022 6:40 PM, Mr Flibble wrote:
> On Thu, 12 May 2022 18:38:49 -0500
> olcott <NoOne@NoWhere.com> wrote:
>
>> On 5/12/2022 6:22 PM, Mr Flibble wrote:
>>> On Thu, 12 May 2022 18:09:39 -0500
>>> olcott <NoOne@NoWhere.com> wrote:
>>>
>>>> On 5/12/2022 5:56 PM, Mr Flibble wrote:
>>>>> On Thu, 12 May 2022 17:51:25 -0500
>>>>> olcott <NoOne@NoWhere.com> wrote:
>>>>>
>>>>>> C/C++ people please critique this as the basis for an improvement
>>>>>> to std::deque. It seems to have the key functionality of
>>>>>> std::deque and does it much more simply while saving time and
>>>>>> space. https://www.cplusplus.com/reference/deque/deque/
>>>>>>
>>>>>> #define tape_element unsigned char
>>>>>>
>>>>>> class Tape_Type
>>>>>> {
>>>>>> private:
>>>>>> int Tape_Head = 0; // Can be negative
>>>>>> std::vector<tape_element> Left; // Stores left expansion
>>>>>> std::vector<tape_element> Right; // Stores right expansion
>>>>>> tape_element & operator[](int index);
>>>>>>
>>>>>> public:
>>>>>> void move_left(); // Tape_Head--; Left.push_back(0); as
>>>>>> needed void move_right(); // Tape_Head++; Left.push_back(0);
>>>>>> as needed void Write(tape_element Y){ this->operator[](Tape_Head)
>>>>>> = Y; }; tape_element Read() { return
>>>>>> this->operator[](Tape_Head); }; Tape_Type(){
>>>>>> Right.push_back('_'); } // constructor void Output();
>>>>>> };
>>>>>>
>>>>>> tape_element& Tape_Type::operator[](int index)
>>>>>> {
>>>>>> if (index > 0)
>>>>>> return Right[index];
>>>>>> int Left_Index = ((index * -1) -1);
>>>>>> return Left[Left_Index];
>>>>>> }
>>>>>>
>>>>>> void Tape_Type::Output()
>>>>>> {
>>>>>> printf("Tape_Type::Output()\n");
>>>>>>
>>>>>> if (Left.size())
>>>>>> {
>>>>>> int Last_One = Left.size() - 1;
>>>>>> for (int N = Last_One; N >= 0; N--)
>>>>>> {
>>>>>> int TH = (N + 1) * -1; // determine Tape_Head from N
>>>>>> printf("[%04d]:%c Left[%02d]\n", TH, Left[N], N);
>>>>>> }
>>>>>> }
>>>>>> if (Right.size())
>>>>>> for (int N = 0; N < Right.size(); N++)
>>>>>> printf("[%04d]:%c Right[%02d]\n", N, Right[N], N);
>>>>>> }
>>>>>>
>>>>>> void Tape_Type::move_left()
>>>>>> {
>>>>>> Tape_Head--;
>>>>>> int Left_Index = ((Tape_Head * -1) -1);
>>>>>> if (Left_Index == Left.size())
>>>>>> Left.push_back('_');
>>>>>> }
>>>>>>
>>>>>> void Tape_Type::move_right()
>>>>>> {
>>>>>> Tape_Head++;
>>>>>> if (Tape_Head == Right.size())
>>>>>> Right.push_back('_');
>>>>>> }
>>>>>
>>>>> It might be a more appropriate solution than std::deque for your
>>>>> specific use-case however it is NOT an improvement to std::deque
>>>>> for the general case -- see my reply in the other thread for why.
>>>>>
>>>>> /Flibble
>>>>>
>>>>
>>>> I didn't see any reason why it would not make a better std::deque.
>>>>
>>>
>>> Because it doesn't meet the complexity and referential integrity
>>> requirements of std::deque.
>>>
>>> /Flibble
>>>
>>
>> It is faster then std::deque.
>> I couldn't find what you mean by referential integrity it has too
>> many different meanings. invalidating iterators seemed to be what you
>> mean otherwise I have no idea.
>
> I see you are choosing to ignore my reply in the other thread. OK, I
> will repost why you are wrong here:
>
> * referential integrity and iterator invalidation are different
> things: when you add or remove elements to either end of a
> std::deque iterators are indeed invalidated however references to
> existing elements remain valid

Mine words the same way and has the added benefit of contiguous storage.

> * If you do 1000 push_fronts followed by 1000 push_backs followed by
> 1000 pop_fronts all is good however your next pop_front will have
> linear complexity, O(n), as it will necessitate removal of the first
> element of the right std::vector.

I don't think that this applies to the way that I implemented it.
pop_front pops from the end of Left. pop_back pops from the end of
Right. This is the key aspect that I used from David's two-stack approach.

--
Copyright 2022 Pete Olcott

"Talent hits a target no one else can hit;
Genius hits a target no one else can see."
Arthur Schopenhauer

On Thu, 12 May 2022 18:49:43 -0500
olcott <NoOne@NoWhere.com> wrote:

> On 5/12/2022 6:40 PM, Mr Flibble wrote:
> > On Thu, 12 May 2022 18:38:49 -0500
> > olcott <NoOne@NoWhere.com> wrote:
> >
> >> On 5/12/2022 6:22 PM, Mr Flibble wrote:
> >>> On Thu, 12 May 2022 18:09:39 -0500
> >>> olcott <NoOne@NoWhere.com> wrote:
> >>>
> >>>> On 5/12/2022 5:56 PM, Mr Flibble wrote:
> >>>>> On Thu, 12 May 2022 17:51:25 -0500
> >>>>> olcott <NoOne@NoWhere.com> wrote:
> >>>>>
> >>>>>> C/C++ people please critique this as the basis for an
> >>>>>> improvement to std::deque. It seems to have the key
> >>>>>> functionality of std::deque and does it much more simply while
> >>>>>> saving time and space.
> >>>>>> https://www.cplusplus.com/reference/deque/deque/
> >>>>>>
> >>>>>> #define tape_element unsigned char
> >>>>>>
> >>>>>> class Tape_Type
> >>>>>> {
> >>>>>> private:
> >>>>>> int Tape_Head = 0; // Can be negative
> >>>>>> std::vector<tape_element> Left; // Stores left expansion
> >>>>>> std::vector<tape_element> Right; // Stores right
> >>>>>> expansion tape_element & operator[](int index);
> >>>>>>
> >>>>>> public:
> >>>>>> void move_left(); // Tape_Head--;
> >>>>>> Left.push_back(0); as needed void move_right(); //
> >>>>>> Tape_Head++; Left.push_back(0); as needed void
> >>>>>> Write(tape_element Y){ this->operator[](Tape_Head) = Y; };
> >>>>>> tape_element Read() { return
> >>>>>> this->operator[](Tape_Head); }; Tape_Type(){
> >>>>>> Right.push_back('_'); } // constructor void Output(); };
> >>>>>>
> >>>>>> tape_element& Tape_Type::operator[](int index)
> >>>>>> {
> >>>>>> if (index > 0)
> >>>>>> return Right[index];
> >>>>>> int Left_Index = ((index * -1) -1);
> >>>>>> return Left[Left_Index];
> >>>>>> }
> >>>>>>
> >>>>>> void Tape_Type::Output()
> >>>>>> {
> >>>>>> printf("Tape_Type::Output()\n");
> >>>>>>
> >>>>>> if (Left.size())
> >>>>>> {
> >>>>>> int Last_One = Left.size() - 1;
> >>>>>> for (int N = Last_One; N >= 0; N--)
> >>>>>> {
> >>>>>> int TH = (N + 1) * -1; // determine Tape_Head from N
> >>>>>> printf("[%04d]:%c Left[%02d]\n", TH, Left[N], N);
> >>>>>> }
> >>>>>> }
> >>>>>> if (Right.size())
> >>>>>> for (int N = 0; N < Right.size(); N++)
> >>>>>> printf("[%04d]:%c Right[%02d]\n", N, Right[N], N);
> >>>>>> }
> >>>>>>
> >>>>>> void Tape_Type::move_left()
> >>>>>> {
> >>>>>> Tape_Head--;
> >>>>>> int Left_Index = ((Tape_Head * -1) -1);
> >>>>>> if (Left_Index == Left.size())
> >>>>>> Left.push_back('_');
> >>>>>> }
> >>>>>>
> >>>>>> void Tape_Type::move_right()
> >>>>>> {
> >>>>>> Tape_Head++;
> >>>>>> if (Tape_Head == Right.size())
> >>>>>> Right.push_back('_');
> >>>>>> }
> >>>>>
> >>>>> It might be a more appropriate solution than std::deque for your
> >>>>> specific use-case however it is NOT an improvement to std::deque
> >>>>> for the general case -- see my reply in the other thread for
> >>>>> why.
> >>>>>
> >>>>> /Flibble
> >>>>>
> >>>>
> >>>> I didn't see any reason why it would not make a better
> >>>> std::deque.
> >>>
> >>> Because it doesn't meet the complexity and referential integrity
> >>> requirements of std::deque.
> >>>
> >>> /Flibble
> >>>
> >>
> >> It is faster then std::deque.
> >> I couldn't find what you mean by referential integrity it has too
> >> many different meanings. invalidating iterators seemed to be what
> >> you mean otherwise I have no idea.
> >
> > I see you are choosing to ignore my reply in the other thread. OK, I
> > will repost why you are wrong here:
> >
> > * referential integrity and iterator invalidation are different
> > things: when you add or remove elements to either end of a
> > std::deque iterators are indeed invalidated however references
> > to existing elements remain valid
>
> Mine words the same way and has the added benefit of contiguous
> storage.
>
> > * If you do 1000 push_fronts followed by 1000 push_backs followed
> > by 1000 pop_fronts all is good however your next pop_front will have
> > linear complexity, O(n), as it will necessitate removal of the
> > first element of the right std::vector.
>
> I don't think that this applies to the way that I implemented it.
> pop_front pops from the end of Left. pop_back pops from the end of
> Right. This is the key aspect that I used from David's two-stack
> approach.
Then it is totally different to what std::deque offers: std::deque
allows ALL elements to be either popped from the front or back. Try
reading AND UNDERSTANDING what I wrote again.

/Flibble

olcott <NoOne@NoWhere.com> writes:

I've removed the philosophy group and comp.lang.c as this is C++.

> C/C++ people please critique this as the basis for an improvement to
> std::deque.

You will get critiques of the code on whatever basis people feel
inclined to comment! You can't limit the comments to some particular
context.

> It seems to have the key functionality of std::deque and
> does it much more simply while saving time and space.

It does not have any of the functionality of std::deque. There is a
commonly used (though not particularly efficient) way to implement a
deque using two arrays, but this is not it.

> #define tape_element unsigned char

Use a typedef or using declaration. Also, I'd put the typedef in the
class as the type belongs to the class (as least that appears to be the
case from the name you've chosen).

> class Tape_Type
> {
> private:
> int Tape_Head = 0; // Can be negative
> std::vector<tape_element> Left; // Stores left expansion
> std::vector<tape_element> Right; // Stores right expansion
> tape_element & operator[](int index);
>
> public:
> void move_left(); // Tape_Head--; Left.push_back(0); as needed
> void move_right(); // Tape_Head++; Left.push_back(0); as needed

The comments are wrong since you push_back('_').

> void Write(tape_element Y){ this->operator[](Tape_Head) = Y; };
> tape_element Read() { return this->operator[](Tape_Head); };

I'd write (*this)[Tape_Head] but I suppose that's just a matter of style.

> Tape_Type(){ Right.push_back('_'); } // constructor

The constructor leaves a Tape_Type object in an unusable state, but
that's due to a bug in operator[]. Did you test?

> void Output();
> };
>
> tape_element& Tape_Type::operator[](int index)
> {
> if (index > 0)
> return Right[index];

Bug. You meant index >= 0 I think.

> int Left_Index = ((index * -1) -1);

Why not -index - 1?

> return Left[Left_Index];

Do you think introducing a new variable really make the code clearer
that simply writing

return Left[-index - 1];

? Personally, I'd write the whole thing as

return index >= 0 ? Right[index] : Left[-index - 1];

> }
>
> void Tape_Type::Output()
> {
> printf("Tape_Type::Output()\n");
>
> if (Left.size())
> {
> int Last_One = Left.size() - 1;
> for (int N = Last_One; N >= 0; N--)
> {
> int TH = (N + 1) * -1; // determine Tape_Head from N
> printf("[%04d]:%c Left[%02d]\n", TH, Left[N], N);
> }
> }
> if (Right.size())
> for (int N = 0; N < Right.size(); N++)
> printf("[%04d]:%c Right[%02d]\n", N, Right[N], N);
> }
>
> void Tape_Type::move_left()
> {
> Tape_Head--;
> int Left_Index = ((Tape_Head * -1) -1);
> if (Left_Index == Left.size())
> Left.push_back('_');
> }
>
> void Tape_Type::move_right()
> {
> Tape_Head++;
> if (Tape_Head == Right.size())
> Right.push_back('_');
> }

I find the capitalisation odd and unhelpful as there does not seem to be
any consistency about it.

--
Ben.
"le génie humain a des limites, quand la bêtise humaine n’en a pas"
Alexandre Dumas (fils)

On 5/12/2022 6:53 PM, Mr Flibble wrote:
> On Thu, 12 May 2022 18:49:43 -0500
> olcott <NoOne@NoWhere.com> wrote:
>
>> On 5/12/2022 6:40 PM, Mr Flibble wrote:
>>> On Thu, 12 May 2022 18:38:49 -0500
>>> olcott <NoOne@NoWhere.com> wrote:
>>>
>>>> On 5/12/2022 6:22 PM, Mr Flibble wrote:
>>>>> On Thu, 12 May 2022 18:09:39 -0500
>>>>> olcott <NoOne@NoWhere.com> wrote:
>>>>>
>>>>>> On 5/12/2022 5:56 PM, Mr Flibble wrote:
>>>>>>> On Thu, 12 May 2022 17:51:25 -0500
>>>>>>> olcott <NoOne@NoWhere.com> wrote:
>>>>>>>
>>>>>>>> C/C++ people please critique this as the basis for an
>>>>>>>> improvement to std::deque. It seems to have the key
>>>>>>>> functionality of std::deque and does it much more simply while
>>>>>>>> saving time and space.
>>>>>>>> https://www.cplusplus.com/reference/deque/deque/
>>>>>>>>
>>>>>>>> #define tape_element unsigned char
>>>>>>>>
>>>>>>>> class Tape_Type
>>>>>>>> {
>>>>>>>> private:
>>>>>>>> int Tape_Head = 0; // Can be negative
>>>>>>>> std::vector<tape_element> Left; // Stores left expansion
>>>>>>>> std::vector<tape_element> Right; // Stores right
>>>>>>>> expansion tape_element & operator[](int index);
>>>>>>>>
>>>>>>>> public:
>>>>>>>> void move_left(); // Tape_Head--;
>>>>>>>> Left.push_back(0); as needed void move_right(); //
>>>>>>>> Tape_Head++; Left.push_back(0); as needed void
>>>>>>>> Write(tape_element Y){ this->operator[](Tape_Head) = Y; };
>>>>>>>> tape_element Read() { return
>>>>>>>> this->operator[](Tape_Head); }; Tape_Type(){
>>>>>>>> Right.push_back('_'); } // constructor void Output(); };
>>>>>>>>
>>>>>>>> tape_element& Tape_Type::operator[](int index)
>>>>>>>> {
>>>>>>>> if (index > 0)
>>>>>>>> return Right[index];
>>>>>>>> int Left_Index = ((index * -1) -1);
>>>>>>>> return Left[Left_Index];
>>>>>>>> }
>>>>>>>>
>>>>>>>> void Tape_Type::Output()
>>>>>>>> {
>>>>>>>> printf("Tape_Type::Output()\n");
>>>>>>>>
>>>>>>>> if (Left.size())
>>>>>>>> {
>>>>>>>> int Last_One = Left.size() - 1;
>>>>>>>> for (int N = Last_One; N >= 0; N--)
>>>>>>>> {
>>>>>>>> int TH = (N + 1) * -1; // determine Tape_Head from N
>>>>>>>> printf("[%04d]:%c Left[%02d]\n", TH, Left[N], N);
>>>>>>>> }
>>>>>>>> }
>>>>>>>> if (Right.size())
>>>>>>>> for (int N = 0; N < Right.size(); N++)
>>>>>>>> printf("[%04d]:%c Right[%02d]\n", N, Right[N], N);
>>>>>>>> }
>>>>>>>>
>>>>>>>> void Tape_Type::move_left()
>>>>>>>> {
>>>>>>>> Tape_Head--;
>>>>>>>> int Left_Index = ((Tape_Head * -1) -1);
>>>>>>>> if (Left_Index == Left.size())
>>>>>>>> Left.push_back('_');
>>>>>>>> }
>>>>>>>>
>>>>>>>> void Tape_Type::move_right()
>>>>>>>> {
>>>>>>>> Tape_Head++;
>>>>>>>> if (Tape_Head == Right.size())
>>>>>>>> Right.push_back('_');
>>>>>>>> }
>>>>>>>
>>>>>>> It might be a more appropriate solution than std::deque for your
>>>>>>> specific use-case however it is NOT an improvement to std::deque
>>>>>>> for the general case -- see my reply in the other thread for
>>>>>>> why.
>>>>>>>
>>>>>>> /Flibble
>>>>>>>
>>>>>>
>>>>>> I didn't see any reason why it would not make a better
>>>>>> std::deque.
>>>>>
>>>>> Because it doesn't meet the complexity and referential integrity
>>>>> requirements of std::deque.
>>>>>
>>>>> /Flibble
>>>>>
>>>>
>>>> It is faster then std::deque.
>>>> I couldn't find what you mean by referential integrity it has too
>>>> many different meanings. invalidating iterators seemed to be what
>>>> you mean otherwise I have no idea.
>>>
>>> I see you are choosing to ignore my reply in the other thread. OK, I
>>> will repost why you are wrong here:
>>>
>>> * referential integrity and iterator invalidation are different
>>> things: when you add or remove elements to either end of a
>>> std::deque iterators are indeed invalidated however references
>>> to existing elements remain valid
>>
>> Mine words the same way and has the added benefit of contiguous
>> storage.
>>
>>> * If you do 1000 push_fronts followed by 1000 push_backs followed
>>> by 1000 pop_fronts all is good however your next pop_front will have
>>> linear complexity, O(n), as it will necessitate removal of the
>>> first element of the right std::vector.
>>
>> I don't think that this applies to the way that I implemented it.
>> pop_front pops from the end of Left. pop_back pops from the end of
>> Right. This is the key aspect that I used from David's two-stack
>> approach.
>
> Then it is totally different to what std::deque offers: std::deque
> allows ALL elements to be either popped from the front or back. Try
> reading AND UNDERSTANDING what I wrote again.
>
> /Flibble
>

I could allow all elements to be popped from the front or the back too.
Mine is much faster when you need far less than all elements.

--
Copyright 2022 Pete Olcott

"Talent hits a target no one else can hit;
Genius hits a target no one else can see."
Arthur Schopenhauer

On 5/12/2022 7:06 PM, Ben wrote:
> olcott <NoOne@NoWhere.com> writes:
>
> I've removed the philosophy group and comp.lang.c as this is C++.
>
>> C/C++ people please critique this as the basis for an improvement to
>> std::deque.
>
> You will get critiques of the code on whatever basis people feel
> inclined to comment! You can't limit the comments to some particular
> context.
>
>> It seems to have the key functionality of std::deque and
>> does it much more simply while saving time and space.
>
> It does not have any of the functionality of std::deque.

That is a ridiculously stupid thing to say. It has the key most
important functionality of a std:deque

Double ended queue
deque (usually pronounced like "deck") is an irregular acronym of
double-ended queue. Double-ended queues are sequence containers with
dynamic sizes that can be expanded or contracted on both ends (either
its front or its back).

All of the rest of the functionality of std::deque can be added as needed.

> There is a
> commonly used (though not particularly efficient) way to implement a
> deque using two arrays, but this is not it.
>
>> #define tape_element unsigned char
>
> Use a typedef or using declaration. Also, I'd put the typedef in the
> class as the type belongs to the class (as least that appears to be the
> case from the name you've chosen).
>
>> class Tape_Type
>> {
>> private:
>> int Tape_Head = 0; // Can be negative
>> std::vector<tape_element> Left; // Stores left expansion
>> std::vector<tape_element> Right; // Stores right expansion
>> tape_element & operator[](int index);
>>
>> public:
>> void move_left(); // Tape_Head--; Left.push_back(0); as needed
>> void move_right(); // Tape_Head++; Left.push_back(0); as needed
>
> The comments are wrong since you push_back('_').
>
>> void Write(tape_element Y){ this->operator[](Tape_Head) = Y; };
>> tape_element Read() { return this->operator[](Tape_Head); };
>
> I'd write (*this)[Tape_Head] but I suppose that's just a matter of style.
>
>> Tape_Type(){ Right.push_back('_'); } // constructor
>
> The constructor leaves a Tape_Type object in an unusable state, but
> that's due to a bug in operator[]. Did you test?
>

Yes I tested so I don't see what you mean.

>> void Output();
>> };
>>
>> tape_element& Tape_Type::operator[](int index)
>> {
>> if (index > 0)
>> return Right[index];
>
> Bug. You meant index >= 0 I think.

Yes Richard caught that. That was a new refactoring.

>
>> int Left_Index = ((index * -1) -1);
>
> Why not -index - 1?
>
>> return Left[Left_Index];
>
> Do you think introducing a new variable really make the code clearer
> that simply writing
>
> return Left[-index - 1];
>
> ? Personally, I'd write the whole thing as
>
> return index >= 0 ? Right[index] : Left[-index - 1];
>
>> }
>>
>> void Tape_Type::Output()
>> {
>> printf("Tape_Type::Output()\n");
>>
>> if (Left.size())
>> {
>> int Last_One = Left.size() - 1;
>> for (int N = Last_One; N >= 0; N--)
>> {
>> int TH = (N + 1) * -1; // determine Tape_Head from N
>> printf("[%04d]:%c Left[%02d]\n", TH, Left[N], N);
>> }
>> }
>> if (Right.size())
>> for (int N = 0; N < Right.size(); N++)
>> printf("[%04d]:%c Right[%02d]\n", N, Right[N], N);
>> }
>>
>> void Tape_Type::move_left()
>> {
>> Tape_Head--;
>> int Left_Index = ((Tape_Head * -1) -1);
>> if (Left_Index == Left.size())
>> Left.push_back('_');
>> }
>>
>> void Tape_Type::move_right()
>> {
>> Tape_Head++;
>> if (Tape_Head == Right.size())
>> Right.push_back('_');
>> }
>
> I find the capitalisation odd and unhelpful as there does not seem to be
> any consistency about it.
>

I found all of your suggestions very helpful.
I don't see the bug in the constructor.
I like mixed case because it is easier to read, mine not be consistent.

Here they are implemented.

//
// Tape_Type implements a two-way Turing machine tape.
// Right contains Tape_Head >= 0 values (right expansion)
// Left contains Tape_Head < 0 values (left expansion)
//
// Tape_Type has functionality very similar to std::deque
// yet implements this functionality much more simply.
// This saves time and space.
//
class Tape_Type
{ typedef unsigned char tape_element;
private:
int Tape_Head = 0; // Can be negative
std::vector<tape_element> Left; // Stores left expansion
std::vector<tape_element> Right; // Stores right expansion

tape_element& operator[](int index)
{
return index >= 0 ? Right[index] : Left[-index - 1];
}

public:
Tape_Type(){ Right.push_back('_'); } // constructor
void Write(tape_element Y){ (*this)[Tape_Head] = Y; };
tape_element Read() { return (*this)[Tape_Head]; };

void move_left()
{
Tape_Head--;
int Left_Index = ((Tape_Head * -1) -1);
if (Left_Index == Left.size())
Left.push_back('_');
}

void move_right()
{
Tape_Head++;
if (Tape_Head == Right.size())
Right.push_back('_');
}

void Output()
{
printf("Tape_Type::Output()\n");
if (Left.size())
{
int Last_One = Left.size() - 1;
for (int N = Last_One; N >= 0; N--)
{
int TH = (N + 1) * -1; // determine Tape_Head from N
printf("[%04d]:%c Left[%02d]\n", TH, Left[N], N);
}
}
if (Right.size())
for (int N = 0; N < Right.size(); N++)
printf("[%04d]:%c Right[%02d]\n", N, Right[N], N);
}
};

--
Copyright 2022 Pete Olcott

"Talent hits a target no one else can hit;
Genius hits a target no one else can see."
Arthur Schopenhauer

On Thu, 12 May 2022 19:12:22 -0500
olcott <NoOne@NoWhere.com> wrote:

> On 5/12/2022 6:53 PM, Mr Flibble wrote:
> > On Thu, 12 May 2022 18:49:43 -0500
> > olcott <NoOne@NoWhere.com> wrote:
> >
> >> On 5/12/2022 6:40 PM, Mr Flibble wrote:
> >>> On Thu, 12 May 2022 18:38:49 -0500
> >>> olcott <NoOne@NoWhere.com> wrote:
> >>>
> >>>> On 5/12/2022 6:22 PM, Mr Flibble wrote:
> >>>>> On Thu, 12 May 2022 18:09:39 -0500
> >>>>> olcott <NoOne@NoWhere.com> wrote:
> >>>>>
> >>>>>> On 5/12/2022 5:56 PM, Mr Flibble wrote:
> >>>>>>> On Thu, 12 May 2022 17:51:25 -0500
> >>>>>>> olcott <NoOne@NoWhere.com> wrote:
> >>>>>>>
> >>>>>>>> C/C++ people please critique this as the basis for an
> >>>>>>>> improvement to std::deque. It seems to have the key
> >>>>>>>> functionality of std::deque and does it much more simply
> >>>>>>>> while saving time and space.
> >>>>>>>> https://www.cplusplus.com/reference/deque/deque/
> >>>>>>>>
> >>>>>>>> #define tape_element unsigned char
> >>>>>>>>
> >>>>>>>> class Tape_Type
> >>>>>>>> {
> >>>>>>>> private:
> >>>>>>>> int Tape_Head = 0; // Can be negative
> >>>>>>>> std::vector<tape_element> Left; // Stores left
> >>>>>>>> expansion std::vector<tape_element> Right; // Stores right
> >>>>>>>> expansion tape_element & operator[](int index);
> >>>>>>>>
> >>>>>>>> public:
> >>>>>>>> void move_left(); // Tape_Head--;
> >>>>>>>> Left.push_back(0); as needed void move_right(); //
> >>>>>>>> Tape_Head++; Left.push_back(0); as needed void
> >>>>>>>> Write(tape_element Y){ this->operator[](Tape_Head) = Y; };
> >>>>>>>> tape_element Read() { return
> >>>>>>>> this->operator[](Tape_Head); }; Tape_Type(){
> >>>>>>>> Right.push_back('_'); } // constructor void Output(); };
> >>>>>>>>
> >>>>>>>> tape_element& Tape_Type::operator[](int index)
> >>>>>>>> {
> >>>>>>>> if (index > 0)
> >>>>>>>> return Right[index];
> >>>>>>>> int Left_Index = ((index * -1) -1);
> >>>>>>>> return Left[Left_Index];
> >>>>>>>> }
> >>>>>>>>
> >>>>>>>> void Tape_Type::Output()
> >>>>>>>> {
> >>>>>>>> printf("Tape_Type::Output()\n");
> >>>>>>>>
> >>>>>>>> if (Left.size())
> >>>>>>>> {
> >>>>>>>> int Last_One = Left.size() - 1;
> >>>>>>>> for (int N = Last_One; N >= 0; N--)
> >>>>>>>> {
> >>>>>>>> int TH = (N + 1) * -1; // determine Tape_Head
> >>>>>>>> from N printf("[%04d]:%c Left[%02d]\n", TH, Left[N], N);
> >>>>>>>> }
> >>>>>>>> }
> >>>>>>>> if (Right.size())
> >>>>>>>> for (int N = 0; N < Right.size(); N++)
> >>>>>>>> printf("[%04d]:%c Right[%02d]\n", N, Right[N],
> >>>>>>>> N); }
> >>>>>>>>
> >>>>>>>> void Tape_Type::move_left()
> >>>>>>>> {
> >>>>>>>> Tape_Head--;
> >>>>>>>> int Left_Index = ((Tape_Head * -1) -1);
> >>>>>>>> if (Left_Index == Left.size())
> >>>>>>>> Left.push_back('_');
> >>>>>>>> }
> >>>>>>>>
> >>>>>>>> void Tape_Type::move_right()
> >>>>>>>> {
> >>>>>>>> Tape_Head++;
> >>>>>>>> if (Tape_Head == Right.size())
> >>>>>>>> Right.push_back('_');
> >>>>>>>> }
> >>>>>>>
> >>>>>>> It might be a more appropriate solution than std::deque for
> >>>>>>> your specific use-case however it is NOT an improvement to
> >>>>>>> std::deque for the general case -- see my reply in the other
> >>>>>>> thread for why.
> >>>>>>>
> >>>>>>> /Flibble
> >>>>>>>
> >>>>>>
> >>>>>> I didn't see any reason why it would not make a better
> >>>>>> std::deque.
> >>>>>
> >>>>> Because it doesn't meet the complexity and referential integrity
> >>>>> requirements of std::deque.
> >>>>>
> >>>>> /Flibble
> >>>>>
> >>>>
> >>>> It is faster then std::deque.
> >>>> I couldn't find what you mean by referential integrity it has too
> >>>> many different meanings. invalidating iterators seemed to be what
> >>>> you mean otherwise I have no idea.
> >>>
> >>> I see you are choosing to ignore my reply in the other thread.
> >>> OK, I will repost why you are wrong here:
> >>>
> >>> * referential integrity and iterator invalidation are different
> >>> things: when you add or remove elements to either end of a
> >>> std::deque iterators are indeed invalidated however
> >>> references to existing elements remain valid
> >>
> >> Mine words the same way and has the added benefit of contiguous
> >> storage.
> >>
> >>> * If you do 1000 push_fronts followed by 1000 push_backs
> >>> followed by 1000 pop_fronts all is good however your next
> >>> pop_front will have linear complexity, O(n), as it will
> >>> necessitate removal of the first element of the right
> >>> std::vector.
> >>
> >> I don't think that this applies to the way that I implemented it.
> >> pop_front pops from the end of Left. pop_back pops from the end of
> >> Right. This is the key aspect that I used from David's two-stack
> >> approach.
> >
> > Then it is totally different to what std::deque offers: std::deque
> > allows ALL elements to be either popped from the front or back. Try
> > reading AND UNDERSTANDING what I wrote again.
> >
> > /Flibble
> >
>
> I could allow all elements to be popped from the front or the back
> too. Mine is much faster when you need far less than all elements.
What you have does not offer what std::deque offers so is not
equivalent to std::deque so can't be considered better than std::deque
for the general case (I don't care about your specific use-case).

/Flibble

On Thu, 12 May 2022 19:55:44 -0500
olcott <NoOne@NoWhere.com> wrote:

> On 5/12/2022 7:06 PM, Ben wrote:
> > olcott <NoOne@NoWhere.com> writes:
> >
> > I've removed the philosophy group and comp.lang.c as this is C++.
> >
> >> C/C++ people please critique this as the basis for an improvement
> >> to std::deque.
> >
> > You will get critiques of the code on whatever basis people feel
> > inclined to comment! You can't limit the comments to some
> > particular context.
> >
> >> It seems to have the key functionality of std::deque and
> >> does it much more simply while saving time and space.
> >
> > It does not have any of the functionality of std::deque.
>
> That is a ridiculously stupid thing to say. It has the key most
> important functionality of a std:deque
>
> Double ended queue
> deque (usually pronounced like "deck") is an irregular acronym of
> double-ended queue. Double-ended queues are sequence containers with
> dynamic sizes that can be expanded or contracted on both ends (either
> its front or its back).
>
> All of the rest of the functionality of std::deque can be added as
> needed.

Not with your chosen data structure of two std::vectors it can't as it
wouldn't meet the complexity and referential integrity
requirements offered by std::deque. I have told you this three times
now.

/Flibble

On 5/12/2022 7:58 PM, Mr Flibble wrote:
> On Thu, 12 May 2022 19:12:22 -0500
> olcott <NoOne@NoWhere.com> wrote:
>
>> On 5/12/2022 6:53 PM, Mr Flibble wrote:
>>> On Thu, 12 May 2022 18:49:43 -0500
>>> olcott <NoOne@NoWhere.com> wrote:
>>>
>>>> On 5/12/2022 6:40 PM, Mr Flibble wrote:
>>>>> On Thu, 12 May 2022 18:38:49 -0500
>>>>> olcott <NoOne@NoWhere.com> wrote:
>>>>>
>>>>>> On 5/12/2022 6:22 PM, Mr Flibble wrote:
>>>>>>> On Thu, 12 May 2022 18:09:39 -0500
>>>>>>> olcott <NoOne@NoWhere.com> wrote:
>>>>>>>
>>>>>>>> On 5/12/2022 5:56 PM, Mr Flibble wrote:
>>>>>>>>> On Thu, 12 May 2022 17:51:25 -0500
>>>>>>>>> olcott <NoOne@NoWhere.com> wrote:
>>>>>>>>>
>>>>>>>>>> C/C++ people please critique this as the basis for an
>>>>>>>>>> improvement to std::deque. It seems to have the key
>>>>>>>>>> functionality of std::deque and does it much more simply
>>>>>>>>>> while saving time and space.
>>>>>>>>>> https://www.cplusplus.com/reference/deque/deque/
>>>>>>>>>>
>>>>>>>>>> #define tape_element unsigned char
>>>>>>>>>>
>>>>>>>>>> class Tape_Type
>>>>>>>>>> {
>>>>>>>>>> private:
>>>>>>>>>> int Tape_Head = 0; // Can be negative
>>>>>>>>>> std::vector<tape_element> Left; // Stores left
>>>>>>>>>> expansion std::vector<tape_element> Right; // Stores right
>>>>>>>>>> expansion tape_element & operator[](int index);
>>>>>>>>>>
>>>>>>>>>> public:
>>>>>>>>>> void move_left(); // Tape_Head--;
>>>>>>>>>> Left.push_back(0); as needed void move_right(); //
>>>>>>>>>> Tape_Head++; Left.push_back(0); as needed void
>>>>>>>>>> Write(tape_element Y){ this->operator[](Tape_Head) = Y; };
>>>>>>>>>> tape_element Read() { return
>>>>>>>>>> this->operator[](Tape_Head); }; Tape_Type(){
>>>>>>>>>> Right.push_back('_'); } // constructor void Output(); };
>>>>>>>>>>
>>>>>>>>>> tape_element& Tape_Type::operator[](int index)
>>>>>>>>>> {
>>>>>>>>>> if (index > 0)
>>>>>>>>>> return Right[index];
>>>>>>>>>> int Left_Index = ((index * -1) -1);
>>>>>>>>>> return Left[Left_Index];
>>>>>>>>>> }
>>>>>>>>>>
>>>>>>>>>> void Tape_Type::Output()
>>>>>>>>>> {
>>>>>>>>>> printf("Tape_Type::Output()\n");
>>>>>>>>>>
>>>>>>>>>> if (Left.size())
>>>>>>>>>> {
>>>>>>>>>> int Last_One = Left.size() - 1;
>>>>>>>>>> for (int N = Last_One; N >= 0; N--)
>>>>>>>>>> {
>>>>>>>>>> int TH = (N + 1) * -1; // determine Tape_Head
>>>>>>>>>> from N printf("[%04d]:%c Left[%02d]\n", TH, Left[N], N);
>>>>>>>>>> }
>>>>>>>>>> }
>>>>>>>>>> if (Right.size())
>>>>>>>>>> for (int N = 0; N < Right.size(); N++)
>>>>>>>>>> printf("[%04d]:%c Right[%02d]\n", N, Right[N],
>>>>>>>>>> N); }
>>>>>>>>>>
>>>>>>>>>> void Tape_Type::move_left()
>>>>>>>>>> {
>>>>>>>>>> Tape_Head--;
>>>>>>>>>> int Left_Index = ((Tape_Head * -1) -1);
>>>>>>>>>> if (Left_Index == Left.size())
>>>>>>>>>> Left.push_back('_');
>>>>>>>>>> }
>>>>>>>>>>
>>>>>>>>>> void Tape_Type::move_right()
>>>>>>>>>> {
>>>>>>>>>> Tape_Head++;
>>>>>>>>>> if (Tape_Head == Right.size())
>>>>>>>>>> Right.push_back('_');
>>>>>>>>>> }
>>>>>>>>>
>>>>>>>>> It might be a more appropriate solution than std::deque for
>>>>>>>>> your specific use-case however it is NOT an improvement to
>>>>>>>>> std::deque for the general case -- see my reply in the other
>>>>>>>>> thread for why.
>>>>>>>>>
>>>>>>>>> /Flibble
>>>>>>>>>
>>>>>>>>
>>>>>>>> I didn't see any reason why it would not make a better
>>>>>>>> std::deque.
>>>>>>>
>>>>>>> Because it doesn't meet the complexity and referential integrity
>>>>>>> requirements of std::deque.
>>>>>>>
>>>>>>> /Flibble
>>>>>>>
>>>>>>
>>>>>> It is faster then std::deque.
>>>>>> I couldn't find what you mean by referential integrity it has too
>>>>>> many different meanings. invalidating iterators seemed to be what
>>>>>> you mean otherwise I have no idea.
>>>>>
>>>>> I see you are choosing to ignore my reply in the other thread.
>>>>> OK, I will repost why you are wrong here:
>>>>>
>>>>> * referential integrity and iterator invalidation are different
>>>>> things: when you add or remove elements to either end of a
>>>>> std::deque iterators are indeed invalidated however
>>>>> references to existing elements remain valid
>>>>
>>>> Mine words the same way and has the added benefit of contiguous
>>>> storage.
>>>>
>>>>> * If you do 1000 push_fronts followed by 1000 push_backs
>>>>> followed by 1000 pop_fronts all is good however your next
>>>>> pop_front will have linear complexity, O(n), as it will
>>>>> necessitate removal of the first element of the right
>>>>> std::vector.
>>>>
>>>> I don't think that this applies to the way that I implemented it.
>>>> pop_front pops from the end of Left. pop_back pops from the end of
>>>> Right. This is the key aspect that I used from David's two-stack
>>>> approach.
>>>
>>> Then it is totally different to what std::deque offers: std::deque
>>> allows ALL elements to be either popped from the front or back. Try
>>> reading AND UNDERSTANDING what I wrote again.
>>>
>>> /Flibble
>>>
>>
>> I could allow all elements to be popped from the front or the back
>> too. Mine is much faster when you need far less than all elements.
>
> What you have does not offer what std::deque offers so is not

All these things can be added and we end up with a simple, faster,
std:deque that has most the conventional overhead and complexity abolished.

> equivalent to std::deque so can't be considered better than std::deque
> for the general case (I don't care about your specific use-case).
>
> /Flibble
>

It just a matter of defining more member functions.

--
Copyright 2022 Pete Olcott

"Talent hits a target no one else can hit;
Genius hits a target no one else can see."
Arthur Schopenhauer

On 5/12/2022 8:01 PM, Mr Flibble wrote:
> On Thu, 12 May 2022 19:55:44 -0500
> olcott <NoOne@NoWhere.com> wrote:
>
>> On 5/12/2022 7:06 PM, Ben wrote:
>>> olcott <NoOne@NoWhere.com> writes:
>>>
>>> I've removed the philosophy group and comp.lang.c as this is C++.
>>>
>>>> C/C++ people please critique this as the basis for an improvement
>>>> to std::deque.
>>>
>>> You will get critiques of the code on whatever basis people feel
>>> inclined to comment! You can't limit the comments to some
>>> particular context.
>>>
>>>> It seems to have the key functionality of std::deque and
>>>> does it much more simply while saving time and space.
>>>
>>> It does not have any of the functionality of std::deque.
>>
>> That is a ridiculously stupid thing to say. It has the key most
>> important functionality of a std:deque
>>
>> Double ended queue
>> deque (usually pronounced like "deck") is an irregular acronym of
>> double-ended queue. Double-ended queues are sequence containers with
>> dynamic sizes that can be expanded or contracted on both ends (either
>> its front or its back).
>>
>> All of the rest of the functionality of std::deque can be added as
>> needed.
>
> Not with your chosen data structure of two std::vectors it can't as it
> wouldn't meet the complexity

It already has the same complexity.

> and referential integrity

and better referential integrity.

> requirements offered by std::deque. I have told you this three times
> now.
>
> /Flibble
>

--
Copyright 2022 Pete Olcott

"Talent hits a target no one else can hit;
Genius hits a target no one else can see."
Arthur Schopenhauer

olcott <NoOne@NoWhere.com> writes:

> On 5/12/2022 7:06 PM, Ben wrote:
>> olcott <NoOne@NoWhere.com> writes:
>> I've removed the philosophy group and comp.lang.c as this is C++.
>>
>>> C/C++ people please critique this as the basis for an improvement to
>>> std::deque.
>> You will get critiques of the code on whatever basis people feel
>> inclined to comment! You can't limit the comments to some particular
>> context.
>>
>>> It seems to have the key functionality of std::deque and
>>> does it much more simply while saving time and space.
>> It does not have any of the functionality of std::deque.
>
> That is a ridiculously stupid thing to say. It has the key most
> important functionality of a std:deque

Generally, when you think I am saying something absurd, you should
re-consider.

A deque has (at least) these operations:

front
back
pop_front
push_front
pop_back
push_back

Your Tape_Type has none of these. Even internally it does not maintain
the right data to be able to provide them.

> Double ended queue
> deque (usually pronounced like "deck") is an irregular acronym of
> double-ended queue. Double-ended queues are sequence containers with
> dynamic sizes that can be expanded or contracted on both ends (either
> its front or its back).
>
> All of the rest of the functionality of std::deque can be added as
> needed.

You mean you could implement a deque using two arrays if you chose to?
So what? All I am saying is that you haven't got a deque.

>> There is a
>> commonly used (though not particularly efficient) way to implement a
>> deque using two arrays, but this is not it.
>>
>>> #define tape_element unsigned char
>> Use a typedef or using declaration. Also, I'd put the typedef in the
>> class as the type belongs to the class (as least that appears to be the
>> case from the name you've chosen).
>>
>>> class Tape_Type
>>> {
>>> private:
>>> int Tape_Head = 0; // Can be negative
>>> std::vector<tape_element> Left; // Stores left expansion
>>> std::vector<tape_element> Right; // Stores right expansion
>>> tape_element & operator[](int index);
>>>
>>> public:
>>> void move_left(); // Tape_Head--; Left.push_back(0); as needed
>>> void move_right(); // Tape_Head++; Left.push_back(0); as needed
>> The comments are wrong since you push_back('_').
>>
>>> void Write(tape_element Y){ this->operator[](Tape_Head) = Y; };
>>> tape_element Read() { return this->operator[](Tape_Head); };
>> I'd write (*this)[Tape_Head] but I suppose that's just a matter of style.
>>
>>> Tape_Type(){ Right.push_back('_'); } // constructor
>> The constructor leaves a Tape_Type object in an unusable state, but
>> that's due to a bug in operator[]. Did you test?
>
> Yes I tested so I don't see what you mean.

Testing should have caught the bug in operator[].

>>> void Output();
>>> };
>>>
>>> tape_element& Tape_Type::operator[](int index)
>>> {
>>> if (index > 0)
>>> return Right[index];
>> Bug. You meant index >= 0 I think.
>
> Yes Richard caught that. That was a new refactoring.
>>
>>> int Left_Index = ((index * -1) -1);
>> Why not -index - 1?
>>
>>> return Left[Left_Index];
>> Do you think introducing a new variable really make the code clearer
>> that simply writing
>> return Left[-index - 1];
>> ? Personally, I'd write the whole thing as
>> return index >= 0 ? Right[index] : Left[-index - 1];
>>
>>> }
>>>
>>> void Tape_Type::Output()
>>> {
>>> printf("Tape_Type::Output()\n");
>>>
>>> if (Left.size())
>>> {
>>> int Last_One = Left.size() - 1;
>>> for (int N = Last_One; N >= 0; N--)
>>> {
>>> int TH = (N + 1) * -1; // determine Tape_Head from N
>>> printf("[%04d]:%c Left[%02d]\n", TH, Left[N], N);
>>> }
>>> }
>>> if (Right.size())
>>> for (int N = 0; N < Right.size(); N++)
>>> printf("[%04d]:%c Right[%02d]\n", N, Right[N], N);
>>> }
>>>
>>> void Tape_Type::move_left()
>>> {
>>> Tape_Head--;
>>> int Left_Index = ((Tape_Head * -1) -1);
>>> if (Left_Index == Left.size())
>>> Left.push_back('_');
>>> }
>>>
>>> void Tape_Type::move_right()
>>> {
>>> Tape_Head++;
>>> if (Tape_Head == Right.size())
>>> Right.push_back('_');
>>> }
>>
>> I find the capitalisation odd and unhelpful as there does not seem to be
>> any consistency about it.
>
> I found all of your suggestions very helpful.
> I don't see the bug in the constructor.

There is none. I just said the constructor leaves the tape unusable
because of the bug in operator[].

> I like mixed case because it is easier to read, mine not be consistent.
>
> Here they are implemented.
>
> //
> // Tape_Type implements a two-way Turing machine tape.
> // Right contains Tape_Head >= 0 values (right expansion)
> // Left contains Tape_Head < 0 values (left expansion)
> //
> // Tape_Type has functionality very similar to std::deque

This comment is not correct.

> // yet implements this functionality much more simply.
> // This saves time and space.
> //
> class Tape_Type
> {
> typedef unsigned char tape_element;

You probably want that to be a public typedef. And now that it's in the
class, the name can be sorter. The usual convention is _t for types:

typedef unsigned char element_t;

I plugged your tape class into my C++ TM interpreter and it made it
slightly slower for the "big" BB(5) test compared with my naive tape
that just uses a single string.

Note: this is not a comment on the design of your tape. There's nothing
wrong with it (except a little inconvenience, see below). The speed
will be determined almost entirely by how std::string and std::vector
are implemented. You might see completely different timings just by
linking with a different library.

Mind you, I prefer using a string to all the other methods I've tried
because it's so convenient. You can set up the TM with an input simply
by writing

tape = input

and you can debug by printing the tape any time you like. And I use a
string_view to get the non-blank "result" out of the TM and the end of a
run. All easy to get round with a couple of functions, but still, since
it's fast I see no reason t change.

--
Ben.
"le génie humain a des limites, quand la bêtise humaine n’en a pas"
Alexandre Dumas (fils)

On 5/12/2022 8:38 PM, Ben wrote:
> olcott <NoOne@NoWhere.com> writes:
>
>> On 5/12/2022 7:06 PM, Ben wrote:
>>> olcott <NoOne@NoWhere.com> writes:
>>> I've removed the philosophy group and comp.lang.c as this is C++.
>>>
>>>> C/C++ people please critique this as the basis for an improvement to
>>>> std::deque.
>>> You will get critiques of the code on whatever basis people feel
>>> inclined to comment! You can't limit the comments to some particular
>>> context.
>>>
>>>> It seems to have the key functionality of std::deque and
>>>> does it much more simply while saving time and space.
>>> It does not have any of the functionality of std::deque.
>>
>> That is a ridiculously stupid thing to say. It has the key most
>> important functionality of a std:deque
>
> Generally, when you think I am saying something absurd, you should
> re-consider.
>
> A deque has (at least) these operations:
>
> front
> back
> push_front
> push_back
> pop_front
> pop_back
>
> Your Tape_Type has none of these. Even internally it does not maintain
> the right data to be able to provide them.

I also added a reserve so you could do a pre-allocated speed test.

It was easy to add these in terms of the current implementation:

public:
tape_element& front( ) { return Left.back(); }
tape_element& back() { return Right.back(); }
void pop_front() { Left.pop_back(); }
void pop_back() { Right.pop_back(); }
void push_front(tape_element& E) { Left.push_back(E); }
void push_back(tape_element& E) { Right.push_back(E); }

void reserve(unsigned int N)
{ Left.reserve(N); Right.reserve(N); }

>> Double ended queue
>> deque (usually pronounced like "deck") is an irregular acronym of
>> double-ended queue. Double-ended queues are sequence containers with
>> dynamic sizes that can be expanded or contracted on both ends (either
>> its front or its back).
>>
>> All of the rest of the functionality of std::deque can be added as
>> needed.
>
> You mean you could implement a deque using two arrays if you chose to?
> So what? All I am saying is that you haven't got a deque.

If I added these things then I would have a much better deque.

>>> There is a
>>> commonly used (though not particularly efficient) way to implement a
>>> deque using two arrays, but this is not it.
>>>
>>>> #define tape_element unsigned char
>>> Use a typedef or using declaration. Also, I'd put the typedef in the
>>> class as the type belongs to the class (as least that appears to be the
>>> case from the name you've chosen).
>>>
>>>> class Tape_Type
>>>> {
>>>> private:
>>>> int Tape_Head = 0; // Can be negative
>>>> std::vector<tape_element> Left; // Stores left expansion
>>>> std::vector<tape_element> Right; // Stores right expansion
>>>> tape_element & operator[](int index);
>>>>
>>>> public:
>>>> void move_left(); // Tape_Head--; Left.push_back(0); as needed
>>>> void move_right(); // Tape_Head++; Left.push_back(0); as needed
>>> The comments are wrong since you push_back('_').
>>>
>>>> void Write(tape_element Y){ this->operator[](Tape_Head) = Y; };
>>>> tape_element Read() { return this->operator[](Tape_Head); };
>>> I'd write (*this)[Tape_Head] but I suppose that's just a matter of style.
>>>
>>>> Tape_Type(){ Right.push_back('_'); } // constructor
>>> The constructor leaves a Tape_Type object in an unusable state, but
>>> that's due to a bug in operator[]. Did you test?
>>
>> Yes I tested so I don't see what you mean.
>
> Testing should have caught the bug in operator[].

It is was a new refactoring of existing working code.

>>>> void Output();
>>>> };
>>>>
>>>> tape_element& Tape_Type::operator[](int index)
>>>> {
>>>> if (index > 0)
>>>> return Right[index];
>>> Bug. You meant index >= 0 I think.
>>
>> Yes Richard caught that. That was a new refactoring.
>>>
>>>> int Left_Index = ((index * -1) -1);
>>> Why not -index - 1?
>>>
>>>> return Left[Left_Index];
>>> Do you think introducing a new variable really make the code clearer
>>> that simply writing
>>> return Left[-index - 1];
>>> ? Personally, I'd write the whole thing as
>>> return index >= 0 ? Right[index] : Left[-index - 1];
>>>
>>>> }
>>>>
>>>> void Tape_Type::Output()
>>>> {
>>>> printf("Tape_Type::Output()\n");
>>>>
>>>> if (Left.size())
>>>> {
>>>> int Last_One = Left.size() - 1;
>>>> for (int N = Last_One; N >= 0; N--)
>>>> {
>>>> int TH = (N + 1) * -1; // determine Tape_Head from N
>>>> printf("[%04d]:%c Left[%02d]\n", TH, Left[N], N);
>>>> }
>>>> }
>>>> if (Right.size())
>>>> for (int N = 0; N < Right.size(); N++)
>>>> printf("[%04d]:%c Right[%02d]\n", N, Right[N], N);
>>>> }
>>>>
>>>> void Tape_Type::move_left()
>>>> {
>>>> Tape_Head--;
>>>> int Left_Index = ((Tape_Head * -1) -1);
>>>> if (Left_Index == Left.size())
>>>> Left.push_back('_');
>>>> }
>>>>
>>>> void Tape_Type::move_right()
>>>> {
>>>> Tape_Head++;
>>>> if (Tape_Head == Right.size())
>>>> Right.push_back('_');
>>>> }
>>>
>>> I find the capitalisation odd and unhelpful as there does not seem to be
>>> any consistency about it.
>>
>> I found all of your suggestions very helpful.
>> I don't see the bug in the constructor.
>
> There is none. I just said the constructor leaves the tape unusable
> because of the bug in operator[].

Oh, OK.

>
>> I like mixed case because it is easier to read, mine not be consistent.
>>
>> Here they are implemented.
>>
>> //
>> // Tape_Type implements a two-way Turing machine tape.
>> // Right contains Tape_Head >= 0 values (right expansion)
>> // Left contains Tape_Head < 0 values (left expansion)
>> //
>> // Tape_Type has functionality very similar to std::deque
>
> This comment is not correct.
>
>> // yet implements this functionality much more simply.
>> // This saves time and space.
>> //
>> class Tape_Type
>> {
>> typedef unsigned char tape_element;
>
> You probably want that to be a public typedef. And now that it's in the
> class, the name can be sorter. The usual convention is _t for types:
>
> typedef unsigned char element_t;
>
> I plugged your tape class into my C++ TM interpreter and it made it
> slightly slower for the "big" BB(5) test compared with my naive tape
> that just uses a single string.
>

std::string or char * ?
If char * was pre-allocated that would give it a big speed advantage.

I could add reserve(left/right):
void reserve(unsigned int N)
{ Left.reserve(N); Right.reserve(N); }

> Note: this is not a comment on the design of your tape. There's nothing
> wrong with it (except a little inconvenience, see below). The speed
> will be determined almost entirely by how std::string and std::vector
> are implemented. You might see completely different timings just by
> linking with a different library.
>
> Mind you, I prefer using a string to all the other methods I've tried
> because it's so convenient. You can set up the TM with an input simply
> by writing
>
> tape = input
>
> and you can debug by printing the tape any time you like. And I use a
> string_view to get the non-blank "result" out of the TM and the end of a
> run. All easy to get round with a couple of functions, but still, since
> it's fast I see no reason t change.
>

Peter Olcott wrote:
> On 5/12/2022 8:38 PM, Ben wrote:
>> olcott <NoOne@NoWhere.com> writes:
>>
>>> On 5/12/2022 7:06 PM, Ben wrote:
>>>> olcott <NoOne@NoWhere.com> writes:
>>>> I've removed the philosophy group and comp.lang.c as this is C++.
>>>>
>>>>> C/C++ people please critique this as the basis for an improvement to
>>>>> std::deque.
>>>> You will get critiques of the code on whatever basis people feel
>>>> inclined to comment!  You can't limit the comments to some particular
>>>> context.
>>>>
>>>>> It seems to have the key functionality of std::deque and
>>>>> does it much more simply while saving time and space.
>>>> It does not have any of the functionality of std::deque.
>>>
>>> That is a ridiculously stupid thing to say. It has the key most
>>> important functionality of a std:deque
>>
>> Generally, when you think I am saying something absurd, you should
>> re-consider.
>>
>> A deque has (at least) these operations:
>>
>>    front
>>    back
>>    push_front
>>    push_back
>>    pop_front
>>    pop_back
>>
>> Your Tape_Type has none of these.  Even internally it does not maintain
>> the right data to be able to provide them.
>
> I also added a reserve so you could do a pre-allocated speed test.
>
> It was easy to add these in terms of the current implementation:
>
> public:
>   tape_element& front( )      { return Left.back();       }
>   tape_element& back()        { return Right.back();      }
>   void pop_front()                  { Left.pop_back();    }
>   void pop_back()                   { Right.pop_back();   }
>   void push_front(tape_element& E)  { Left.push_back(E);  }
>   void push_back(tape_element& E)   { Right.push_back(E); }
>
>   void reserve(unsigned int N)
>                      { Left.reserve(N); Right.reserve(N); }

Could you add eggs, bacon and beans? Thanks Peter.

On Thu, 12 May 2022 20:34:41 -0500
olcott <NoOne@NoWhere.com> wrote:

> On 5/12/2022 7:58 PM, Mr Flibble wrote:
> > On Thu, 12 May 2022 19:12:22 -0500
> > olcott <NoOne@NoWhere.com> wrote:
> >
> >> On 5/12/2022 6:53 PM, Mr Flibble wrote:
> >>> On Thu, 12 May 2022 18:49:43 -0500
> >>> olcott <NoOne@NoWhere.com> wrote:
> >>>
> >>>> On 5/12/2022 6:40 PM, Mr Flibble wrote:
> >>>>> On Thu, 12 May 2022 18:38:49 -0500
> >>>>> olcott <NoOne@NoWhere.com> wrote:
> >>>>>
> >>>>>> On 5/12/2022 6:22 PM, Mr Flibble wrote:
> >>>>>>> On Thu, 12 May 2022 18:09:39 -0500
> >>>>>>> olcott <NoOne@NoWhere.com> wrote:
> >>>>>>>
> >>>>>>>> On 5/12/2022 5:56 PM, Mr Flibble wrote:
> >>>>>>>>> On Thu, 12 May 2022 17:51:25 -0500
> >>>>>>>>> olcott <NoOne@NoWhere.com> wrote:
> >>>>>>>>>
> >>>>>>>>>> C/C++ people please critique this as the basis for an
> >>>>>>>>>> improvement to std::deque. It seems to have the key
> >>>>>>>>>> functionality of std::deque and does it much more simply
> >>>>>>>>>> while saving time and space.
> >>>>>>>>>> https://www.cplusplus.com/reference/deque/deque/
> >>>>>>>>>>
> >>>>>>>>>> #define tape_element unsigned char
> >>>>>>>>>>
> >>>>>>>>>> class Tape_Type
> >>>>>>>>>> {
> >>>>>>>>>> private:
> >>>>>>>>>> int Tape_Head = 0; // Can be negative
> >>>>>>>>>> std::vector<tape_element> Left; // Stores left
> >>>>>>>>>> expansion std::vector<tape_element> Right; // Stores right
> >>>>>>>>>> expansion tape_element & operator[](int index);
> >>>>>>>>>>
> >>>>>>>>>> public:
> >>>>>>>>>> void move_left(); // Tape_Head--;
> >>>>>>>>>> Left.push_back(0); as needed void move_right(); //
> >>>>>>>>>> Tape_Head++; Left.push_back(0); as needed void
> >>>>>>>>>> Write(tape_element Y){ this->operator[](Tape_Head) = Y; };
> >>>>>>>>>> tape_element Read() { return
> >>>>>>>>>> this->operator[](Tape_Head); }; Tape_Type(){
> >>>>>>>>>> Right.push_back('_'); } // constructor void Output(); };
> >>>>>>>>>>
> >>>>>>>>>> tape_element& Tape_Type::operator[](int index)
> >>>>>>>>>> {
> >>>>>>>>>> if (index > 0)
> >>>>>>>>>> return Right[index];
> >>>>>>>>>> int Left_Index = ((index * -1) -1);
> >>>>>>>>>> return Left[Left_Index];
> >>>>>>>>>> }
> >>>>>>>>>>
> >>>>>>>>>> void Tape_Type::Output()
> >>>>>>>>>> {
> >>>>>>>>>> printf("Tape_Type::Output()\n");
> >>>>>>>>>>
> >>>>>>>>>> if (Left.size())
> >>>>>>>>>> {
> >>>>>>>>>> int Last_One = Left.size() - 1;
> >>>>>>>>>> for (int N = Last_One; N >= 0; N--)
> >>>>>>>>>> {
> >>>>>>>>>> int TH = (N + 1) * -1; // determine Tape_Head
> >>>>>>>>>> from N printf("[%04d]:%c Left[%02d]\n", TH, Left[N], N);
> >>>>>>>>>> }
> >>>>>>>>>> }
> >>>>>>>>>> if (Right.size())
> >>>>>>>>>> for (int N = 0; N < Right.size(); N++)
> >>>>>>>>>> printf("[%04d]:%c Right[%02d]\n", N, Right[N],
> >>>>>>>>>> N); }
> >>>>>>>>>>
> >>>>>>>>>> void Tape_Type::move_left()
> >>>>>>>>>> {
> >>>>>>>>>> Tape_Head--;
> >>>>>>>>>> int Left_Index = ((Tape_Head * -1) -1);
> >>>>>>>>>> if (Left_Index == Left.size())
> >>>>>>>>>> Left.push_back('_');
> >>>>>>>>>> }
> >>>>>>>>>>
> >>>>>>>>>> void Tape_Type::move_right()
> >>>>>>>>>> {
> >>>>>>>>>> Tape_Head++;
> >>>>>>>>>> if (Tape_Head == Right.size())
> >>>>>>>>>> Right.push_back('_');
> >>>>>>>>>> }
> >>>>>>>>>
> >>>>>>>>> It might be a more appropriate solution than std::deque for
> >>>>>>>>> your specific use-case however it is NOT an improvement to
> >>>>>>>>> std::deque for the general case -- see my reply in the other
> >>>>>>>>> thread for why.
> >>>>>>>>>
> >>>>>>>>> /Flibble
> >>>>>>>>>
> >>>>>>>>
> >>>>>>>> I didn't see any reason why it would not make a better
> >>>>>>>> std::deque.
> >>>>>>>
> >>>>>>> Because it doesn't meet the complexity and referential
> >>>>>>> integrity requirements of std::deque.
> >>>>>>>
> >>>>>>> /Flibble
> >>>>>>>
> >>>>>>
> >>>>>> It is faster then std::deque.
> >>>>>> I couldn't find what you mean by referential integrity it has
> >>>>>> too many different meanings. invalidating iterators seemed to
> >>>>>> be what you mean otherwise I have no idea.
> >>>>>
> >>>>> I see you are choosing to ignore my reply in the other thread.
> >>>>> OK, I will repost why you are wrong here:
> >>>>>
> >>>>> * referential integrity and iterator invalidation are
> >>>>> different things: when you add or remove elements to either end
> >>>>> of a std::deque iterators are indeed invalidated however
> >>>>> references to existing elements remain valid
> >>>>
> >>>> Mine words the same way and has the added benefit of contiguous
> >>>> storage.
> >>>>
> >>>>> * If you do 1000 push_fronts followed by 1000 push_backs
> >>>>> followed by 1000 pop_fronts all is good however your next
> >>>>> pop_front will have linear complexity, O(n), as it will
> >>>>> necessitate removal of the first element of the right
> >>>>> std::vector.
> >>>>
> >>>> I don't think that this applies to the way that I implemented it.
> >>>> pop_front pops from the end of Left. pop_back pops from the end
> >>>> of Right. This is the key aspect that I used from David's
> >>>> two-stack approach.
> >>>
> >>> Then it is totally different to what std::deque offers: std::deque
> >>> allows ALL elements to be either popped from the front or back.
> >>> Try reading AND UNDERSTANDING what I wrote again.
> >>>
> >>> /Flibble
> >>>
> >>
> >> I could allow all elements to be popped from the front or the back
> >> too. Mine is much faster when you need far less than all elements.
> >>
> >
> > What you have does not offer what std::deque offers so is not
>
> All these things can be added and we end up with a simple, faster,
> std:deque that has most the conventional overhead and complexity
> abolished.
>
> > equivalent to std::deque so can't be considered better than
> > std::deque for the general case (I don't care about your specific
> > use-case).
> >
> > /Flibble
> >
>
> It just a matter of defining more member functions.

Click here to read the complete article

On Thu, 12 May 2022 20:36:02 -0500
olcott <NoOne@NoWhere.com> wrote:

> On 5/12/2022 8:01 PM, Mr Flibble wrote:
> > On Thu, 12 May 2022 19:55:44 -0500
> > olcott <NoOne@NoWhere.com> wrote:
> >
> >> On 5/12/2022 7:06 PM, Ben wrote:
> >>> olcott <NoOne@NoWhere.com> writes:
> >>>
> >>> I've removed the philosophy group and comp.lang.c as this is C++.
> >>>
> >>>> C/C++ people please critique this as the basis for an improvement
> >>>> to std::deque.
> >>>
> >>> You will get critiques of the code on whatever basis people feel
> >>> inclined to comment! You can't limit the comments to some
> >>> particular context.
> >>>
> >>>> It seems to have the key functionality of std::deque and
> >>>> does it much more simply while saving time and space.
> >>>
> >>> It does not have any of the functionality of std::deque.
> >>
> >> That is a ridiculously stupid thing to say. It has the key most
> >> important functionality of a std:deque
> >>
> >> Double ended queue
> >> deque (usually pronounced like "deck") is an irregular acronym of
> >> double-ended queue. Double-ended queues are sequence containers
> >> with dynamic sizes that can be expanded or contracted on both ends
> >> (either its front or its back).
> >>
> >> All of the rest of the functionality of std::deque can be added as
> >> needed.
> >
> > Not with your chosen data structure of two std::vectors it can't as
> > it wouldn't meet the complexity
>
> It already has the same complexity.
>
> > and referential integrity
>
> and better referential integrity.

You are a fucking obtuse idiot, mate.

/Flibble

On 5/13/22 09:02, Mr Flibble wrote:

> You cannot implement all of std::deque's member functions meeting
> std::deque requirements using your chosen data structure of two
> std::vectors.

Not with any version of the C language.

--
+-------------------------------------------------------------------+
| sphinx of black quartz, judge my vow. |
+-------------------------------------------------------------------+

olcott <NoOne@NoWhere.com> writes:

> On 5/12/2022 8:38 PM, Ben wrote:
>> olcott <NoOne@NoWhere.com> writes:
>>
>>> On 5/12/2022 7:06 PM, Ben wrote:
>>>> olcott <NoOne@NoWhere.com> writes:
>>>> I've removed the philosophy group and comp.lang.c as this is C++.
>>>>
>>>>> C/C++ people please critique this as the basis for an improvement to
>>>>> std::deque.
>>>> You will get critiques of the code on whatever basis people feel
>>>> inclined to comment! You can't limit the comments to some particular
>>>> context.
>>>>
>>>>> It seems to have the key functionality of std::deque and
>>>>> does it much more simply while saving time and space.
>>>> It does not have any of the functionality of std::deque.
>>>
>>> That is a ridiculously stupid thing to say. It has the key most
>>> important functionality of a std:deque
>> Generally, when you think I am saying something absurd, you should
>> re-consider.
>> A deque has (at least) these operations:
>> front
>> back
>> push_front
>> push_back
>> pop_front
>> pop_back
>> Your Tape_Type has none of these. Even internally it does not maintain
>> the right data to be able to provide them.
>
> I also added a reserve so you could do a pre-allocated speed test.
>
> It was easy to add these in terms of the current implementation:

You have not provided the correct operations, so you have no idea how
hard it might be to do that. This keeps looking more and more like a
distraction to put off having to do what you said.

> public:
> tape_element& front( ) { return Left.back(); }
> tape_element& back() { return Right.back(); }
> void pop_front() { Left.pop_back(); }
> void pop_back() { Right.pop_back(); }
> void push_front(tape_element& E) { Left.push_back(E); }
> void push_back(tape_element& E) { Right.push_back(E); }
>
> void reserve(unsigned int N)
> { Left.reserve(N); Right.reserve(N); }

Not correct. Test first.

>>> Double ended queue
>>> deque (usually pronounced like "deck") is an irregular acronym of
>>> double-ended queue. Double-ended queues are sequence containers with
>>> dynamic sizes that can be expanded or contracted on both ends (either
>>> its front or its back).
>>>
>>> All of the rest of the functionality of std::deque can be added as
>>> needed.
>> You mean you could implement a deque using two arrays if you chose to?
>> So what? All I am saying is that you haven't got a deque.
>
> If I added these things then I would have a much better deque.

If you added them correctly and then removed the things that a deque
should not have. In other words, if you implemented a deque.

>>> Yes I tested so I don't see what you mean.
>> Testing should have caught the bug in operator[].
>
> It is was a new refactoring of existing working code.

A software engineer runs all the tests after every edit (or at least
before every commit). (I am not a software engineer.)

>> I plugged your tape class into my C++ TM interpreter and it made it
>> slightly slower for the "big" BB(5) test compared with my naive tape
>> that just uses a single string.
>>
>
> std::string or char * ?

std::string.

> If char * was pre-allocated that would give it a big speed advantage.

Nothing pre-allocated.

>> Mind you, I prefer using a string to all the other methods I've tried
>> because it's so convenient. You can set up the TM with an input simply
>> by writing
>> tape = input
>> and you can debug by printing the tape any time you like. And I use a
>> string_view to get the non-blank "result" out of the TM and the end of a
>> run. All easy to get round with a couple of functions, but still, since
>> it's fast I see no reason t change.
>
> What about memory allocation?

What about it? std::string does it.

--
Ben.
"le génie humain a des limites, quand la bêtise humaine n’en a pas"
Alexandre Dumas (fils)

On 5/13/2022 6:01 AM, Ben wrote:
> olcott <NoOne@NoWhere.com> writes:
>
>> On 5/12/2022 8:38 PM, Ben wrote:
>>> olcott <NoOne@NoWhere.com> writes:
>>>
>>>> On 5/12/2022 7:06 PM, Ben wrote:
>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>> I've removed the philosophy group and comp.lang.c as this is C++.
>>>>>
>>>>>> C/C++ people please critique this as the basis for an improvement to
>>>>>> std::deque.
>>>>> You will get critiques of the code on whatever basis people feel
>>>>> inclined to comment! You can't limit the comments to some particular
>>>>> context.
>>>>>
>>>>>> It seems to have the key functionality of std::deque and
>>>>>> does it much more simply while saving time and space.
>>>>> It does not have any of the functionality of std::deque.
>>>>
>>>> That is a ridiculously stupid thing to say. It has the key most
>>>> important functionality of a std:deque
>>> Generally, when you think I am saying something absurd, you should
>>> re-consider.
>>> A deque has (at least) these operations:
>>> front
>>> back
>>> push_front
>>> push_back
>>> pop_front
>>> pop_back
>>> Your Tape_Type has none of these. Even internally it does not maintain
>>> the right data to be able to provide them.
>>
>> I also added a reserve so you could do a pre-allocated speed test.
>>
>> It was easy to add these in terms of the current implementation:
>
> You have not provided the correct operations, so you have no idea how
> hard it might be to do that. This keeps looking more and more like a
> distraction to put off having to do what you said.
>
>> public:
>> tape_element& front( ) { return Left.back(); }
>> tape_element& back() { return Right.back(); }
>> void pop_front() { Left.pop_back(); }
>> void pop_back() { Right.pop_back(); }
>> void push_front(tape_element& E) { Left.push_back(E); }
>> void push_back(tape_element& E) { Right.push_back(E); }
>>
>> void reserve(unsigned int N)
>> { Left.reserve(N); Right.reserve(N); }
>
> Not correct. Test first.

They are all correct. I don't see how you can say that they are not when
you don't know my design.

>
>>>> Double ended queue
>>>> deque (usually pronounced like "deck") is an irregular acronym of
>>>> double-ended queue. Double-ended queues are sequence containers with
>>>> dynamic sizes that can be expanded or contracted on both ends (either
>>>> its front or its back).
>>>>
>>>> All of the rest of the functionality of std::deque can be added as
>>>> needed.
>>> You mean you could implement a deque using two arrays if you chose to?
>>> So what? All I am saying is that you haven't got a deque.
>>
>> If I added these things then I would have a much better deque.
>
> If you added them correctly and then removed the things that a deque
> should not have. In other words, if you implemented a deque.
>

I mere want to know that the most basic functionality of my deque is
(a) simpler (b) faster (c) smaller than a std:deque.
If Tape_Type.reserve() is used it should be your std::string.

>>>> Yes I tested so I don't see what you mean.
>>> Testing should have caught the bug in operator[].
>>
>> It is was a new refactoring of existing working code.
>
> A software engineer runs all the tests after every edit (or at least
> before every commit). (I am not a software engineer.)
>
>>> I plugged your tape class into my C++ TM interpreter and it made it
>>> slightly slower for the "big" BB(5) test compared with my naive tape
>>> that just uses a single string.
>>>
>>
>> std::string or char * ?
>
> std::string.
>
>> If char * was pre-allocated that would give it a big speed advantage.
>
> Nothing pre-allocated.
>
>>> Mind you, I prefer using a string to all the other methods I've tried
>>> because it's so convenient. You can set up the TM with an input simply
>>> by writing
>>> tape = input
>>> and you can debug by printing the tape any time you like. And I use a
>>> string_view to get the non-blank "result" out of the TM and the end of a
>>> run. All easy to get round with a couple of functions, but still, since
>>> it's fast I see no reason t change.
>>
>> What about memory allocation?
>
> What about it? std::string does it.
>

It is probably much slower than my system now that I added reserve.
I do like the idea of simplicity, it is my primary design goal.

--
Copyright 2022 Pete Olcott

"Talent hits a target no one else can hit;
Genius hits a target no one else can see."
Arthur Schopenhauer