Rocksolid Light

Welcome to novaBBS (click a section below)

mail  files  register  nodelist  faq  login

If Machiavelli were a programmer, he'd have worked for AT&T.


computers / comp.ai.philosophy / Re: Implementing a two-way Turing Machine tape as an improvement to std::deque

SubjectAuthor
* Implementing a two-way Turing Machine tape as an improvement toolcott
+* Re: Implementing a two-way Turing Machine tape as an improvement toMr Flibble
|`* Re: Implementing a two-way Turing Machine tape as an improvement toolcott
| `* Re: Implementing a two-way Turing Machine tape as an improvement toMr Flibble
|  `* Re: Implementing a two-way Turing Machine tape as an improvement toolcott
|   `* Re: Implementing a two-way Turing Machine tape as an improvement toMr Flibble
|    `* Re: Implementing a two-way Turing Machine tape as an improvement toolcott
|     `* Re: Implementing a two-way Turing Machine tape as an improvement toMr Flibble
|      `* Re: Implementing a two-way Turing Machine tape as an improvement toolcott
|       `* Re: Implementing a two-way Turing Machine tape as an improvement toMr Flibble
|        `* Re: Implementing a two-way Turing Machine tape as an improvement toolcott
|         `* Re: Implementing a two-way Turing Machine tape as an improvement to std::dMr Flibble
|          +- Re: Implementing a two-way Turing Machine tape as an improvement totth
|          `* Re: Implementing a two-way Turing Machine tape as an improvement toolcott
|           `* Re: Implementing a two-way Turing Machine tape as an improvement toMr Flibble
|            `- Re: Implementing a two-way Turing Machine tape as an improvement toChris M. Thomasson
`* Re: Implementing a two-way Turing Machine tape as an improvement to std::dRichard Damon
 `- Re: Implementing a two-way Turing Machine tape as an improvement toolcott

1
Subject: Implementing a two-way Turing Machine tape as an improvement to std::deque
From: olcott
Newsgroups: comp.theory, comp.ai.philosophy, comp.lang.c, comp.lang.c++
Date: Thu, 12 May 2022 22:51 UTC
Path: i2pn2.org!i2pn.org!weretis.net!feeder8.news.weretis.net!2.eu.feeder.erje.net!feeder.erje.net!border1.nntp.dca1.giganews.com!nntp.giganews.com!buffer1.nntp.dca1.giganews.com!news.giganews.com.POSTED!not-for-mail
NNTP-Posting-Date: Thu, 12 May 2022 17:51:26 -0500
Date: Thu, 12 May 2022 17:51:25 -0500
MIME-Version: 1.0
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
Thunderbird/91.9.0
Newsgroups: comp.theory,comp.ai.philosophy,comp.lang.c,comp.lang.c++
Content-Language: en-US
From: NoO...@NoWhere.com (olcott)
Subject: Implementing a two-way Turing Machine tape as an improvement to
std::deque
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Message-ID: <cNWdnXqV1cXzEuD_nZ2dnUU7_8zNnZ2d@giganews.com>
Lines: 73
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-AIJS7dEXgZRLmh/gp8WXPQkzpku47w4dclkYOqwMxc5biHF6VLIHTP01dVtctQ2BJpR4PrW2e2fhG+K!VvO74/p1LFPxAWFEAquTzqUyd02r963BbT1o9iel0e32ZO9OZUGNRFfT9hn54lvIRzLTjRXbons=
X-Complaints-To: abuse@giganews.com
X-DMCA-Notifications: http://www.giganews.com/info/dmca.html
X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers
X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly
X-Postfilter: 1.3.40
X-Original-Bytes: 3123
View all headers
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


Subject: Re: Implementing a two-way Turing Machine tape as an improvement to std::deque
From: Mr Flibble
Newsgroups: comp.theory, comp.ai.philosophy, comp.lang.c, comp.lang.c++
Organization: Jupiter Mining Corp
Date: Thu, 12 May 2022 22:56 UTC
References: 1
Path: i2pn2.org!i2pn.org!weretis.net!feeder8.news.weretis.net!news.roellig-ltd.de!open-news-network.org!peer01.ams4!peer.am4.highwinds-media.com!news.highwinds-media.com!fx01.ams4.POSTED!not-for-mail
From: flib...@reddwarf.jmc (Mr Flibble)
Newsgroups: comp.theory,comp.ai.philosophy,comp.lang.c,comp.lang.c++
Subject: Re: Implementing a two-way Turing Machine tape as an improvement to
std::deque
Message-ID: <20220512235610.00004914@reddwarf.jmc>
References: <cNWdnXqV1cXzEuD_nZ2dnUU7_8zNnZ2d@giganews.com>
Organization: Jupiter Mining Corp
X-Newsreader: Claws Mail 3.17.8 (GTK+ 2.24.33; x86_64-w64-mingw32)
MIME-Version: 1.0
Content-Type: text/plain; charset=US-ASCII
Content-Transfer-Encoding: 7bit
Lines: 74
X-Complaints-To: abuse@eweka.nl
NNTP-Posting-Date: Thu, 12 May 2022 22:56:09 UTC
Date: Thu, 12 May 2022 23:56:10 +0100
X-Received-Bytes: 2929
View all headers
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



Subject: Re: Implementing a two-way Turing Machine tape as an improvement to std::deque
From: olcott
Newsgroups: comp.theory, comp.ai.philosophy, comp.lang.c, comp.lang.c++
Date: Thu, 12 May 2022 23:09 UTC
References: 1 2
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!news.misty.com!border2.nntp.dca1.giganews.com!nntp.giganews.com!buffer2.nntp.dca1.giganews.com!buffer1.nntp.dca1.giganews.com!news.giganews.com.POSTED!not-for-mail
NNTP-Posting-Date: Thu, 12 May 2022 18:09:40 -0500
Date: Thu, 12 May 2022 18:09:39 -0500
MIME-Version: 1.0
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
Thunderbird/91.9.0
Subject: Re: Implementing a two-way Turing Machine tape as an improvement to
std::deque
Content-Language: en-US
Newsgroups: comp.theory,comp.ai.philosophy,comp.lang.c,comp.lang.c++
References: <cNWdnXqV1cXzEuD_nZ2dnUU7_8zNnZ2d@giganews.com>
<20220512235610.00004914@reddwarf.jmc>
From: NoO...@NoWhere.com (olcott)
In-Reply-To: <20220512235610.00004914@reddwarf.jmc>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Message-ID: <Vf2dnR9fAewpDuD_nZ2dnUU7_8xh4p2d@giganews.com>
Lines: 84
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-JqqL1dgkOmMhV4Fvo4aLYDD4OGXZ1bYgQJ3ghFUK6hiprUdCbFKEpY16hWKJETwOI5hVgwJfemjIfJk!+0aGHCdnFp5pbztBphW8U4+OD5ugPLdfZdpyRuIYi9wMylfwWxEjbOS6ALvpO35KQG0gwMjjL/U=
X-Complaints-To: abuse@giganews.com
X-DMCA-Notifications: http://www.giganews.com/info/dmca.html
X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers
X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly
X-Postfilter: 1.3.40
X-Original-Bytes: 3914
View all headers
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


Subject: Re: Implementing a two-way Turing Machine tape as an improvement to std::deque
From: Mr Flibble
Newsgroups: comp.theory, comp.ai.philosophy, comp.lang.c, comp.lang.c++
Organization: Jupiter Mining Corp
Date: Thu, 12 May 2022 23:22 UTC
References: 1 2 3
Path: i2pn2.org!i2pn.org!weretis.net!feeder8.news.weretis.net!feeder1.feed.usenet.farm!feed.usenet.farm!peer03.ams4!peer.am4.highwinds-media.com!news.highwinds-media.com!fx01.ams4.POSTED!not-for-mail
From: flib...@reddwarf.jmc (Mr Flibble)
Newsgroups: comp.theory,comp.ai.philosophy,comp.lang.c,comp.lang.c++
Subject: Re: Implementing a two-way Turing Machine tape as an improvement to
std::deque
Message-ID: <20220513002218.00003fa0@reddwarf.jmc>
References: <cNWdnXqV1cXzEuD_nZ2dnUU7_8zNnZ2d@giganews.com>
<20220512235610.00004914@reddwarf.jmc>
<Vf2dnR9fAewpDuD_nZ2dnUU7_8xh4p2d@giganews.com>
Organization: Jupiter Mining Corp
X-Newsreader: Claws Mail 3.17.8 (GTK+ 2.24.33; x86_64-w64-mingw32)
MIME-Version: 1.0
Content-Type: text/plain; charset=US-ASCII
Content-Transfer-Encoding: 7bit
Lines: 86
X-Complaints-To: abuse@eweka.nl
NNTP-Posting-Date: Thu, 12 May 2022 23:22:17 UTC
Date: Fri, 13 May 2022 00:22:18 +0100
X-Received-Bytes: 3565
View all headers
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



Subject: Re: Implementing a two-way Turing Machine tape as an improvement to std::deque
From: Richard Damon
Newsgroups: comp.theory, comp.ai.philosophy, comp.lang.c, comp.lang.c++
Organization: Forte - www.forteinc.com
Date: Thu, 12 May 2022 23:23 UTC
References: 1
Path: i2pn2.org!i2pn.org!aioe.org!news.uzoreto.com!feeder.usenetexpress.com!tr2.eu1.usenetexpress.com!feeder1.feed.usenet.farm!feed.usenet.farm!peer02.ams4!peer.am4.highwinds-media.com!peer03.iad!feed-me.highwinds-media.com!news.highwinds-media.com!fx45.iad.POSTED!not-for-mail
MIME-Version: 1.0
User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.15; rv:91.0) Gecko/20100101 Thunderbird/91.9.0
Subject: Re: Implementing a two-way Turing Machine tape as an improvement to std::deque
Content-Language: en-US
Newsgroups: comp.theory,comp.ai.philosophy,comp.lang.c,comp.lang.c++
References: <cNWdnXqV1cXzEuD_nZ2dnUU7_8zNnZ2d@giganews.com>
From: Rich...@Damon-Family.org (Richard Damon)
In-Reply-To: <cNWdnXqV1cXzEuD_nZ2dnUU7_8zNnZ2d@giganews.com>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Lines: 72
Message-ID: <5GgfK.2451$R6W6.1148@fx45.iad>
X-Complaints-To: abuse@easynews.com
Organization: Forte - www.forteinc.com
X-Complaints-Info: Please be sure to forward a copy of ALL headers otherwise we will be unable to process your complaint properly.
Date: Thu, 12 May 2022 19:23:47 -0400
X-Received-Bytes: 3201
View all headers
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


Subject: Re: Implementing a two-way Turing Machine tape as an improvement to std::deque
From: olcott
Newsgroups: comp.theory, comp.ai.philosophy, comp.lang.c, comp.lang.c++
Date: Thu, 12 May 2022 23:32 UTC
References: 1 2
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!news.misty.com!border2.nntp.dca1.giganews.com!nntp.giganews.com!buffer2.nntp.dca1.giganews.com!news.giganews.com.POSTED!not-for-mail
NNTP-Posting-Date: Thu, 12 May 2022 18:32:59 -0500
Date: Thu, 12 May 2022 18:32:58 -0500
MIME-Version: 1.0
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
Thunderbird/91.9.0
Subject: Re: Implementing a two-way Turing Machine tape as an improvement to
std::deque
Content-Language: en-US
Newsgroups: comp.theory,comp.ai.philosophy,comp.lang.c,comp.lang.c++
References: <cNWdnXqV1cXzEuD_nZ2dnUU7_8zNnZ2d@giganews.com>
<5GgfK.2451$R6W6.1148@fx45.iad>
From: NoO...@NoWhere.com (olcott)
In-Reply-To: <5GgfK.2451$R6W6.1148@fx45.iad>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Message-ID: <Up-dnYjT5e-2BOD_nZ2dnUU7_8zNnZ2d@giganews.com>
Lines: 82
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-vGrpRxzUoae2RSj+SoUHDuCXDZHmB19EajhhnyWoN3QqGezEAliZBTT33ijz+dJmkDzmk/B5FvMUQhm!waVqGgvxOiV4jcsL8buzvM026Tkmj13jrJZY98yZGoSXSi3yTJaV3hpQw1m14uJlidhdc/VOIII=
X-Complaints-To: abuse@giganews.com
X-DMCA-Notifications: http://www.giganews.com/info/dmca.html
X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers
X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly
X-Postfilter: 1.3.40
X-Original-Bytes: 3846
View all headers
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


Subject: Re: Implementing a two-way Turing Machine tape as an improvement to std::deque
From: olcott
Newsgroups: comp.theory, comp.ai.philosophy, comp.lang.c, comp.lang.c++
Date: Thu, 12 May 2022 23:38 UTC
References: 1 2 3 4
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!news.misty.com!border2.nntp.dca1.giganews.com!nntp.giganews.com!buffer2.nntp.dca1.giganews.com!news.giganews.com.POSTED!not-for-mail
NNTP-Posting-Date: Thu, 12 May 2022 18:38:50 -0500
Date: Thu, 12 May 2022 18:38:49 -0500
MIME-Version: 1.0
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
Thunderbird/91.9.0
Subject: Re: Implementing a two-way Turing Machine tape as an improvement to
std::deque
Content-Language: en-US
Newsgroups: comp.theory,comp.ai.philosophy,comp.lang.c,comp.lang.c++
References: <cNWdnXqV1cXzEuD_nZ2dnUU7_8zNnZ2d@giganews.com>
<20220512235610.00004914@reddwarf.jmc>
<Vf2dnR9fAewpDuD_nZ2dnUU7_8xh4p2d@giganews.com>
<20220513002218.00003fa0@reddwarf.jmc>
From: NoO...@NoWhere.com (olcott)
In-Reply-To: <20220513002218.00003fa0@reddwarf.jmc>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Message-ID: <-s-dncjVifoXB-D_nZ2dnUU7_83NnZ2d@giganews.com>
Lines: 99
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-ujsi0yPI96ki8sVBwjfA6IRq5Ws3UwFvv6e4I/qE+9YXAiv7nU9DDwsLqC6LXub66Epm7ia7WRGwW7c!sWBBDa6IxMO5RMnRNy4tOXn88bnS487apUJFW7wrKDr0tPrEZhtoAA4hy+5ZYK6mrcSnUmuVShw=
X-Complaints-To: abuse@giganews.com
X-DMCA-Notifications: http://www.giganews.com/info/dmca.html
X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers
X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly
X-Postfilter: 1.3.40
X-Original-Bytes: 4624
View all headers
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


Subject: Re: Implementing a two-way Turing Machine tape as an improvement to std::deque
From: Mr Flibble
Newsgroups: comp.theory, comp.ai.philosophy, comp.lang.c, comp.lang.c++
Organization: Jupiter Mining Corp
Date: Thu, 12 May 2022 23:40 UTC
References: 1 2 3 4 5
Path: i2pn2.org!i2pn.org!weretis.net!feeder8.news.weretis.net!news.roellig-ltd.de!open-news-network.org!peer01.ams4!peer.am4.highwinds-media.com!news.highwinds-media.com!fx04.ams4.POSTED!not-for-mail
From: flib...@reddwarf.jmc (Mr Flibble)
Newsgroups: comp.theory,comp.ai.philosophy,comp.lang.c,comp.lang.c++
Subject: Re: Implementing a two-way Turing Machine tape as an improvement to
std::deque
Message-ID: <20220513004049.00000d64@reddwarf.jmc>
References: <cNWdnXqV1cXzEuD_nZ2dnUU7_8zNnZ2d@giganews.com>
<20220512235610.00004914@reddwarf.jmc>
<Vf2dnR9fAewpDuD_nZ2dnUU7_8xh4p2d@giganews.com>
<20220513002218.00003fa0@reddwarf.jmc>
<-s-dncjVifoXB-D_nZ2dnUU7_83NnZ2d@giganews.com>
Organization: Jupiter Mining Corp
X-Newsreader: Claws Mail 3.17.8 (GTK+ 2.24.33; x86_64-w64-mingw32)
MIME-Version: 1.0
Content-Type: text/plain; charset=US-ASCII
Content-Transfer-Encoding: 7bit
Lines: 111
X-Complaints-To: abuse@eweka.nl
NNTP-Posting-Date: Thu, 12 May 2022 23:40:48 UTC
Date: Fri, 13 May 2022 00:40:49 +0100
X-Received-Bytes: 4838
View all headers
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



Subject: Re: Implementing a two-way Turing Machine tape as an improvement to std::deque
From: olcott
Newsgroups: comp.theory, comp.ai.philosophy, comp.lang.c, comp.lang.c++
Date: Thu, 12 May 2022 23:49 UTC
References: 1 2 3 4 5 6
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!news.misty.com!border2.nntp.dca1.giganews.com!nntp.giganews.com!buffer2.nntp.dca1.giganews.com!buffer1.nntp.dca1.giganews.com!news.giganews.com.POSTED!not-for-mail
NNTP-Posting-Date: Thu, 12 May 2022 18:49:44 -0500
Date: Thu, 12 May 2022 18:49:43 -0500
MIME-Version: 1.0
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
Thunderbird/91.9.0
Subject: Re: Implementing a two-way Turing Machine tape as an improvement to
std::deque
Content-Language: en-US
Newsgroups: comp.theory,comp.ai.philosophy,comp.lang.c,comp.lang.c++
References: <cNWdnXqV1cXzEuD_nZ2dnUU7_8zNnZ2d@giganews.com>
<20220512235610.00004914@reddwarf.jmc>
<Vf2dnR9fAewpDuD_nZ2dnUU7_8xh4p2d@giganews.com>
<20220513002218.00003fa0@reddwarf.jmc>
<-s-dncjVifoXB-D_nZ2dnUU7_83NnZ2d@giganews.com>
<20220513004049.00000d64@reddwarf.jmc>
From: NoO...@NoWhere.com (olcott)
In-Reply-To: <20220513004049.00000d64@reddwarf.jmc>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Message-ID: <HYudneQqVdKFAOD_nZ2dnUU7_83NnZ2d@giganews.com>
Lines: 123
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-mDMgyaSrZTEDJyPQuXiWSxEGypvSWqVf0rqRfJ4UhLslr+O8rFUjZD6PkU+3HDhNORFCI8JGC2j2pn2!zfJifi5+AQgNYUJxTaVtJ+KEy4PMik4AJZLly/sNQnb2xtu9zfFgUmf1MxYpNmyRNd4RX/VZeR0=
X-Complaints-To: abuse@giganews.com
X-DMCA-Notifications: http://www.giganews.com/info/dmca.html
X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers
X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly
X-Postfilter: 1.3.40
X-Original-Bytes: 5996
View all headers
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


Subject: Re: Implementing a two-way Turing Machine tape as an improvement to std::deque
From: Mr Flibble
Newsgroups: comp.theory, comp.ai.philosophy, comp.lang.c, comp.lang.c++
Organization: Jupiter Mining Corp
Date: Thu, 12 May 2022 23:53 UTC
References: 1 2 3 4 5 6 7
Path: i2pn2.org!i2pn.org!weretis.net!feeder8.news.weretis.net!ecngs!feeder2.ecngs.de!178.20.174.213.MISMATCH!feeder1.feed.usenet.farm!feed.usenet.farm!peer01.ams4!peer.am4.highwinds-media.com!news.highwinds-media.com!fx04.ams4.POSTED!not-for-mail
From: flib...@reddwarf.jmc (Mr Flibble)
Newsgroups: comp.theory,comp.ai.philosophy,comp.lang.c,comp.lang.c++
Subject: Re: Implementing a two-way Turing Machine tape as an improvement to
std::deque
Message-ID: <20220513005340.00001694@reddwarf.jmc>
References: <cNWdnXqV1cXzEuD_nZ2dnUU7_8zNnZ2d@giganews.com>
<20220512235610.00004914@reddwarf.jmc>
<Vf2dnR9fAewpDuD_nZ2dnUU7_8xh4p2d@giganews.com>
<20220513002218.00003fa0@reddwarf.jmc>
<-s-dncjVifoXB-D_nZ2dnUU7_83NnZ2d@giganews.com>
<20220513004049.00000d64@reddwarf.jmc>
<HYudneQqVdKFAOD_nZ2dnUU7_83NnZ2d@giganews.com>
Organization: Jupiter Mining Corp
X-Newsreader: Claws Mail 3.17.8 (GTK+ 2.24.33; x86_64-w64-mingw32)
MIME-Version: 1.0
Content-Type: text/plain; charset=US-ASCII
Content-Transfer-Encoding: 7bit
Lines: 130
X-Complaints-To: abuse@eweka.nl
NNTP-Posting-Date: Thu, 12 May 2022 23:53:39 UTC
Date: Fri, 13 May 2022 00:53:40 +0100
X-Received-Bytes: 5834
View all headers
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



Subject: Re: Implementing a two-way Turing Machine tape as an improvement to std::deque
From: olcott
Newsgroups: comp.theory, comp.ai.philosophy, comp.lang.c, comp.lang.c++
Date: Fri, 13 May 2022 00:12 UTC
References: 1 2 3 4 5 6 7 8
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!news.misty.com!border2.nntp.dca1.giganews.com!nntp.giganews.com!buffer2.nntp.dca1.giganews.com!news.giganews.com.POSTED!not-for-mail
NNTP-Posting-Date: Thu, 12 May 2022 19:12:23 -0500
Date: Thu, 12 May 2022 19:12:22 -0500
MIME-Version: 1.0
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
Thunderbird/91.9.0
Subject: Re: Implementing a two-way Turing Machine tape as an improvement to
std::deque
Content-Language: en-US
Newsgroups: comp.theory,comp.ai.philosophy,comp.lang.c,comp.lang.c++
References: <cNWdnXqV1cXzEuD_nZ2dnUU7_8zNnZ2d@giganews.com>
<20220512235610.00004914@reddwarf.jmc>
<Vf2dnR9fAewpDuD_nZ2dnUU7_8xh4p2d@giganews.com>
<20220513002218.00003fa0@reddwarf.jmc>
<-s-dncjVifoXB-D_nZ2dnUU7_83NnZ2d@giganews.com>
<20220513004049.00000d64@reddwarf.jmc>
<HYudneQqVdKFAOD_nZ2dnUU7_83NnZ2d@giganews.com>
<20220513005340.00001694@reddwarf.jmc>
From: NoO...@NoWhere.com (olcott)
In-Reply-To: <20220513005340.00001694@reddwarf.jmc>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Message-ID: <Bo-dnemL1eT6P-D_nZ2dnUU7_81g4p2d@giganews.com>
Lines: 141
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-OoPTKurhr50QG0qUGDMJ9rahN6Bfnlcfm74cV4CQR2Xq3LB4zCeYoEEqr7AGOavLPZQHvaPajp83XVk!/LjTsVYcGwpma91K+swR6GF7voIWU+EmbqzcYwgD8FsKqH/yDSUvfTrU58jWcyP6Ly7YjJXVOFw=
X-Complaints-To: abuse@giganews.com
X-DMCA-Notifications: http://www.giganews.com/info/dmca.html
X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers
X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly
X-Postfilter: 1.3.40
X-Original-Bytes: 6841
View all headers
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


Subject: Re: Implementing a two-way Turing Machine tape as an improvement to std::deque
From: Mr Flibble
Newsgroups: comp.theory, comp.ai.philosophy, comp.lang.c, comp.lang.c++
Organization: Jupiter Mining Corp
Date: Fri, 13 May 2022 00:58 UTC
References: 1 2 3 4 5 6 7 8 9
Path: i2pn2.org!i2pn.org!weretis.net!feeder8.news.weretis.net!news.roellig-ltd.de!open-news-network.org!peer02.ams4!peer.am4.highwinds-media.com!news.highwinds-media.com!fx04.ams4.POSTED!not-for-mail
From: flib...@reddwarf.jmc (Mr Flibble)
Newsgroups: comp.theory,comp.ai.philosophy,comp.lang.c,comp.lang.c++
Subject: Re: Implementing a two-way Turing Machine tape as an improvement to
std::deque
Message-ID: <20220513015816.00006f57@reddwarf.jmc>
References: <cNWdnXqV1cXzEuD_nZ2dnUU7_8zNnZ2d@giganews.com>
<20220512235610.00004914@reddwarf.jmc>
<Vf2dnR9fAewpDuD_nZ2dnUU7_8xh4p2d@giganews.com>
<20220513002218.00003fa0@reddwarf.jmc>
<-s-dncjVifoXB-D_nZ2dnUU7_83NnZ2d@giganews.com>
<20220513004049.00000d64@reddwarf.jmc>
<HYudneQqVdKFAOD_nZ2dnUU7_83NnZ2d@giganews.com>
<20220513005340.00001694@reddwarf.jmc>
<Bo-dnemL1eT6P-D_nZ2dnUU7_81g4p2d@giganews.com>
Organization: Jupiter Mining Corp
X-Newsreader: Claws Mail 3.17.8 (GTK+ 2.24.33; x86_64-w64-mingw32)
MIME-Version: 1.0
Content-Type: text/plain; charset=US-ASCII
Content-Transfer-Encoding: 7bit
Lines: 145
X-Complaints-To: abuse@eweka.nl
NNTP-Posting-Date: Fri, 13 May 2022 00:58:15 UTC
Date: Fri, 13 May 2022 01:58:16 +0100
X-Received-Bytes: 6745
View all headers
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



Subject: Re: Implementing a two-way Turing Machine tape as an improvement to std::deque
From: olcott
Newsgroups: comp.theory, comp.ai.philosophy, comp.lang.c, comp.lang.c++
Date: Fri, 13 May 2022 01:34 UTC
References: 1 2 3 4 5 6 7 8 9 10
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!news.misty.com!border2.nntp.dca1.giganews.com!nntp.giganews.com!buffer2.nntp.dca1.giganews.com!buffer1.nntp.dca1.giganews.com!news.giganews.com.POSTED!not-for-mail
NNTP-Posting-Date: Thu, 12 May 2022 20:34:42 -0500
Date: Thu, 12 May 2022 20:34:41 -0500
MIME-Version: 1.0
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
Thunderbird/91.9.0
Subject: Re: Implementing a two-way Turing Machine tape as an improvement to
std::deque
Content-Language: en-US
Newsgroups: comp.theory,comp.ai.philosophy,comp.lang.c,comp.lang.c++
References: <cNWdnXqV1cXzEuD_nZ2dnUU7_8zNnZ2d@giganews.com>
<20220512235610.00004914@reddwarf.jmc>
<Vf2dnR9fAewpDuD_nZ2dnUU7_8xh4p2d@giganews.com>
<20220513002218.00003fa0@reddwarf.jmc>
<-s-dncjVifoXB-D_nZ2dnUU7_83NnZ2d@giganews.com>
<20220513004049.00000d64@reddwarf.jmc>
<HYudneQqVdKFAOD_nZ2dnUU7_83NnZ2d@giganews.com>
<20220513005340.00001694@reddwarf.jmc>
<Bo-dnemL1eT6P-D_nZ2dnUU7_81g4p2d@giganews.com>
<20220513015816.00006f57@reddwarf.jmc>
From: NoO...@NoWhere.com (olcott)
In-Reply-To: <20220513015816.00006f57@reddwarf.jmc>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Message-ID: <D7WdnSjo4swvKOD_nZ2dnUU7_81g4p2d@giganews.com>
Lines: 159
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-iUPOWC+2qIQq3WJ49fnjT5ZzYOzHHnh3LpiU1Ft3OHDbfP0v6kIDeGcodGDAd7qpahYjgnUOJTIJbdB!7cabS8H8GCd2J+Jvs/JvVqi0zvIGwDPnyyOYcAbjO1XW6lLswSEGkvrxLndFmPYI52JTJajFs9Y=
X-Complaints-To: abuse@giganews.com
X-DMCA-Notifications: http://www.giganews.com/info/dmca.html
X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers
X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly
X-Postfilter: 1.3.40
X-Original-Bytes: 7802
View all headers
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


Subject: Re: Implementing a two-way Turing Machine tape as an improvement to std::deque
From: Mr Flibble
Newsgroups: comp.theory, comp.ai.philosophy, comp.lang.c, comp.lang.c++
Organization: Jupiter Mining Corp
Date: Fri, 13 May 2022 07:02 UTC
References: 1 2 3 4 5 6 7 8 9 10 11
Path: i2pn2.org!i2pn.org!aioe.org!news.uzoreto.com!feeder.usenetexpress.com!tr2.eu1.usenetexpress.com!81.171.65.13.MISMATCH!peer01.ams4!peer.am4.highwinds-media.com!news.highwinds-media.com!fx04.ams4.POSTED!not-for-mail
From: flib...@reddwarf.jmc (Mr Flibble)
Newsgroups: comp.theory,comp.ai.philosophy,comp.lang.c,comp.lang.c++
Subject: Re: Implementing a two-way Turing Machine tape as an improvement to std::deque
Message-ID: <20220513080247.000077d7@reddwarf.jmc>
References: <cNWdnXqV1cXzEuD_nZ2dnUU7_8zNnZ2d@giganews.com> <20220512235610.00004914@reddwarf.jmc> <Vf2dnR9fAewpDuD_nZ2dnUU7_8xh4p2d@giganews.com> <20220513002218.00003fa0@reddwarf.jmc> <-s-dncjVifoXB-D_nZ2dnUU7_83NnZ2d@giganews.com> <20220513004049.00000d64@reddwarf.jmc> <HYudneQqVdKFAOD_nZ2dnUU7_83NnZ2d@giganews.com> <20220513005340.00001694@reddwarf.jmc> <Bo-dnemL1eT6P-D_nZ2dnUU7_81g4p2d@giganews.com> <20220513015816.00006f57@reddwarf.jmc> <D7WdnSjo4swvKOD_nZ2dnUU7_81g4p2d@giganews.com>
Organization: Jupiter Mining Corp
X-Newsreader: Claws Mail 3.17.8 (GTK+ 2.24.33; x86_64-w64-mingw32)
MIME-Version: 1.0
Content-Type: text/plain; charset=US-ASCII
Content-Transfer-Encoding: 7bit
Lines: 165
X-Complaints-To: abuse@eweka.nl
NNTP-Posting-Date: Fri, 13 May 2022 07:02:46 UTC
Date: Fri, 13 May 2022 08:02:47 +0100
X-Received-Bytes: 7714
View all headers
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.
 
You cannot implement all of std::deque's member functions meeting
std::deque requirements using your chosen data structure of two
std::vectors.

/Flibble



Subject: Re: Implementing a two-way Turing Machine tape as an improvement to std::deque
From: tth
Newsgroups: comp.theory, comp.ai.philosophy, comp.lang.c, comp.lang.c++
Followup: comp.lang.c++
Organization: Gegeweb News Server
Date: Fri, 13 May 2022 07:10 UTC
References: 1 2 3 4 5 6 7 8 9 10 11 12
Path: i2pn2.org!i2pn.org!news.niel.me!news.gegeweb.eu!gegeweb.org!.POSTED.2001:861:5e50:f690:159b:da31:48b1:869d!not-for-mail
From: tth...@none.invalid (tth)
Newsgroups: comp.theory,comp.ai.philosophy,comp.lang.c,comp.lang.c++
Subject: Re: Implementing a two-way Turing Machine tape as an improvement to
std::deque
Followup-To: comp.lang.c++
Date: Fri, 13 May 2022 09:10:24 +0200
Organization: Gegeweb News Server
Message-ID: <t5l090$2f3k$1@news.gegeweb.eu>
References: <cNWdnXqV1cXzEuD_nZ2dnUU7_8zNnZ2d@giganews.com>
<20220512235610.00004914@reddwarf.jmc>
<Vf2dnR9fAewpDuD_nZ2dnUU7_8xh4p2d@giganews.com>
<20220513002218.00003fa0@reddwarf.jmc>
<-s-dncjVifoXB-D_nZ2dnUU7_83NnZ2d@giganews.com>
<20220513004049.00000d64@reddwarf.jmc>
<HYudneQqVdKFAOD_nZ2dnUU7_83NnZ2d@giganews.com>
<20220513005340.00001694@reddwarf.jmc>
<Bo-dnemL1eT6P-D_nZ2dnUU7_81g4p2d@giganews.com>
<20220513015816.00006f57@reddwarf.jmc>
<D7WdnSjo4swvKOD_nZ2dnUU7_81g4p2d@giganews.com>
<20220513080247.000077d7@reddwarf.jmc>
Mime-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Fri, 13 May 2022 07:10:24 -0000 (UTC)
Injection-Info: news.gegeweb.eu; posting-account="tontonth@usenet.local"; posting-host="2001:861:5e50:f690:159b:da31:48b1:869d";
logging-data="81012"; mail-complaints-to="abuse@gegeweb.eu"
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:91.0) Gecko/20100101
Thunderbird/91.8.0
Cancel-Lock: sha256:YgbXW+ljbbpnqPQ/orEEycqi/i1kpdklvKQYxrvS+MM=
Content-Language: en-US
In-Reply-To: <20220513080247.000077d7@reddwarf.jmc>
View all headers
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.        |
+-------------------------------------------------------------------+


Subject: Re: Implementing a two-way Turing Machine tape as an improvement to std::deque
From: olcott
Newsgroups: comp.theory, comp.ai.philosophy, comp.lang.c, comp.lang.c++
Date: Fri, 13 May 2022 15:58 UTC
References: 1 2 3 4 5 6 7 8 9 10 11 12
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!news.misty.com!border2.nntp.dca1.giganews.com!nntp.giganews.com!buffer2.nntp.dca1.giganews.com!news.giganews.com.POSTED!not-for-mail
NNTP-Posting-Date: Fri, 13 May 2022 10:58:56 -0500
Date: Fri, 13 May 2022 10:58:56 -0500
MIME-Version: 1.0
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
Thunderbird/91.9.0
Subject: Re: Implementing a two-way Turing Machine tape as an improvement to
std::deque
Content-Language: en-US
Newsgroups: comp.theory,comp.ai.philosophy,comp.lang.c,comp.lang.c++
References: <cNWdnXqV1cXzEuD_nZ2dnUU7_8zNnZ2d@giganews.com>
<20220512235610.00004914@reddwarf.jmc>
<Vf2dnR9fAewpDuD_nZ2dnUU7_8xh4p2d@giganews.com>
<20220513002218.00003fa0@reddwarf.jmc>
<-s-dncjVifoXB-D_nZ2dnUU7_83NnZ2d@giganews.com>
<20220513004049.00000d64@reddwarf.jmc>
<HYudneQqVdKFAOD_nZ2dnUU7_83NnZ2d@giganews.com>
<20220513005340.00001694@reddwarf.jmc>
<Bo-dnemL1eT6P-D_nZ2dnUU7_81g4p2d@giganews.com>
<20220513015816.00006f57@reddwarf.jmc>
<D7WdnSjo4swvKOD_nZ2dnUU7_81g4p2d@giganews.com>
<20220513080247.000077d7@reddwarf.jmc>
From: NoO...@NoWhere.com (olcott)
In-Reply-To: <20220513080247.000077d7@reddwarf.jmc>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Message-ID: <zdmdnV7tirvcHeP_nZ2dnUU7_8xQAAAA@giganews.com>
Lines: 211
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-ofSLRgWJvnbYo7bdrrwvPPx3uTaUhL6ta0Dk+Qm+/xOlD0m8IJpD9TyinvE7lgUoOEU6AY8LhiwLsSL!+htfqZCySP1ho8PyaRtDcKRbm80mlq3YxnbDF3mXU2L1J0Wcj9TPvzNFbEdb2iwVZ4F6+I3Al9A=
X-Complaints-To: abuse@giganews.com
X-DMCA-Notifications: http://www.giganews.com/info/dmca.html
X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers
X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly
X-Postfilter: 1.3.40
X-Original-Bytes: 9882
View all headers
On 5/13/2022 2:02 AM, Mr Flibble wrote:
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.
  You cannot implement all of std::deque's member functions meeting
std::deque requirements using your chosen data structure of two
std::vectors.

/Flibble


// 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)
//
// Grows with Right.push_back() as Tape_Head increases above 0.
// Grows with Left.push_back() as Tape_Head decreases below 0.
//
// Tape_Type has functionality very similar to std::deque
// yet implements this functionality much more simply.
// This saves time and space.
//
class Tape_Type
{
public:
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_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); }



--
Copyright 2022 Pete Olcott

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


Subject: Re: Implementing a two-way Turing Machine tape as an improvement to std::deque
From: Mr Flibble
Newsgroups: comp.theory, comp.ai.philosophy, comp.lang.c, comp.lang.c++
Organization: Jupiter Mining Corp
Date: Fri, 13 May 2022 16:02 UTC
References: 1 2 3 4 5 6 7 8 9 10 11 12 13
Path: i2pn2.org!i2pn.org!aioe.org!news.uzoreto.com!feeder1.feed.usenet.farm!feed.usenet.farm!peer01.ams4!peer.am4.highwinds-media.com!news.highwinds-media.com!fx14.ams4.POSTED!not-for-mail
From: flib...@reddwarf.jmc (Mr Flibble)
Newsgroups: comp.theory,comp.ai.philosophy,comp.lang.c,comp.lang.c++
Subject: Re: Implementing a two-way Turing Machine tape as an improvement to
std::deque
Message-ID: <20220513170239.0000273b@reddwarf.jmc>
References: <cNWdnXqV1cXzEuD_nZ2dnUU7_8zNnZ2d@giganews.com>
<20220512235610.00004914@reddwarf.jmc>
<Vf2dnR9fAewpDuD_nZ2dnUU7_8xh4p2d@giganews.com>
<20220513002218.00003fa0@reddwarf.jmc>
<-s-dncjVifoXB-D_nZ2dnUU7_83NnZ2d@giganews.com>
<20220513004049.00000d64@reddwarf.jmc>
<HYudneQqVdKFAOD_nZ2dnUU7_83NnZ2d@giganews.com>
<20220513005340.00001694@reddwarf.jmc>
<Bo-dnemL1eT6P-D_nZ2dnUU7_81g4p2d@giganews.com>
<20220513015816.00006f57@reddwarf.jmc>
<D7WdnSjo4swvKOD_nZ2dnUU7_81g4p2d@giganews.com>
<20220513080247.000077d7@reddwarf.jmc>
<zdmdnV7tirvcHeP_nZ2dnUU7_8xQAAAA@giganews.com>
Organization: Jupiter Mining Corp
X-Newsreader: Claws Mail 3.17.8 (GTK+ 2.24.33; x86_64-w64-mingw32)
MIME-Version: 1.0
Content-Type: text/plain; charset=US-ASCII
Content-Transfer-Encoding: 7bit
Lines: 211
X-Complaints-To: abuse@eweka.nl
NNTP-Posting-Date: Fri, 13 May 2022 16:02:38 UTC
Date: Fri, 13 May 2022 17:02:39 +0100
X-Received-Bytes: 9809
View all headers
On Fri, 13 May 2022 10:58:56 -0500
olcott <NoOne@NoWhere.com> wrote:

On 5/13/2022 2:02 AM, Mr Flibble wrote:
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. 
 
You cannot implement all of std::deque's member functions meeting
std::deque requirements using your chosen data structure of two
std::vectors.

/Flibble
 

// 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)
//
// Grows with Right.push_back() as Tape_Head increases above 0.
// Grows with Left.push_back() as Tape_Head decreases below 0.
//
// Tape_Type has functionality very similar to std::deque
// yet implements this functionality much more simply.
// This saves time and space.
//
class Tape_Type
{
public:
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_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); }

And what happens if Left is empty, Right is non-empty and you call
pop_front()?

/Flibble



Subject: Re: Implementing a two-way Turing Machine tape as an improvement to std::deque
From: Chris M. Thomasson
Newsgroups: comp.theory, comp.ai.philosophy, comp.lang.c, comp.lang.c++
Organization: A noiseless patient Spider
Date: Fri, 13 May 2022 19:44 UTC
References: 1 2 3 4 5 6 7 8 9 10 11 12 13 14
Path: i2pn2.org!i2pn.org!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: chris.m....@gmail.com (Chris M. Thomasson)
Newsgroups: comp.theory,comp.ai.philosophy,comp.lang.c,comp.lang.c++
Subject: Re: Implementing a two-way Turing Machine tape as an improvement to
std::deque
Date: Fri, 13 May 2022 12:44:05 -0700
Organization: A noiseless patient Spider
Lines: 237
Message-ID: <t5mce6$ij6$1@dont-email.me>
References: <cNWdnXqV1cXzEuD_nZ2dnUU7_8zNnZ2d@giganews.com>
<20220512235610.00004914@reddwarf.jmc>
<Vf2dnR9fAewpDuD_nZ2dnUU7_8xh4p2d@giganews.com>
<20220513002218.00003fa0@reddwarf.jmc>
<-s-dncjVifoXB-D_nZ2dnUU7_83NnZ2d@giganews.com>
<20220513004049.00000d64@reddwarf.jmc>
<HYudneQqVdKFAOD_nZ2dnUU7_83NnZ2d@giganews.com>
<20220513005340.00001694@reddwarf.jmc>
<Bo-dnemL1eT6P-D_nZ2dnUU7_81g4p2d@giganews.com>
<20220513015816.00006f57@reddwarf.jmc>
<D7WdnSjo4swvKOD_nZ2dnUU7_81g4p2d@giganews.com>
<20220513080247.000077d7@reddwarf.jmc>
<zdmdnV7tirvcHeP_nZ2dnUU7_8xQAAAA@giganews.com>
<20220513170239.0000273b@reddwarf.jmc>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Fri, 13 May 2022 19:44:06 -0000 (UTC)
Injection-Info: reader02.eternal-september.org; posting-host="9e0404c658f08f4bf7ea56fefb5cef5d";
logging-data="19046"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19T/UmUQKCOniMNDOz1tYwL5hsQ6c/jQwM="
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
Thunderbird/91.9.0
Cancel-Lock: sha1:8UOLRFmg89b6HySbb96cNw28VdA=
In-Reply-To: <20220513170239.0000273b@reddwarf.jmc>
Content-Language: en-US
View all headers
On 5/13/2022 9:02 AM, Mr Flibble wrote:
On Fri, 13 May 2022 10:58:56 -0500
olcott <NoOne@NoWhere.com> wrote:

On 5/13/2022 2:02 AM, Mr Flibble wrote:
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.
   You cannot implement all of std::deque's member functions meeting
std::deque requirements using your chosen data structure of two
std::vectors.

/Flibble
  

// 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)
//
// Grows with Right.push_back() as Tape_Head increases above 0.
// Grows with Left.push_back() as Tape_Head decreases below 0.
//
// Tape_Type has functionality very similar to std::deque
// yet implements this functionality much more simply.
// This saves time and space.
//
class Tape_Type
{
public:
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_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); }

And what happens if Left is empty, Right is non-empty and you call
pop_front()?


Flip a coin; heads left, tails right.

Heads, try to pop from left.
Tails, try to pop from right.

Just joking around here, in a sense... ;^)

Actually, back in the day with my threading work, I have subdivided a lock-free stack into regions to amortize things. It was nothing like a deque. It was a long time ago, damn near 20 years. The cool part was that multiple threads could push/pop items without interfering with one another in a lot of use cases that respected locality. It was layered up:

per-thread container
hash bucket container
global container

Iirc, to pop an element from the container:

check per-thread
check hash bucket
check the global

if all checks fail, return nullptr, if not return the popped node.

I think I might still have this code on an old hard drive.


1
rocksolid light 0.7.2
clearneti2ptor