Implementing a two-way Turing Machine tape as an improvement to std::deque

[olcott]

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

[Mr Flibble]

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

[olcott]

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

[Mr Flibble]

Because it doesn't meet the complexity and referential integrity
requirements of std::deque.

/Flibble

[Richard Damon]

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

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

[olcott]

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

[olcott]

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.

[Mr Flibble]

On Thu, 12 May 2022 18:38:49 -0500

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

[olcott]

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.

[Mr Flibble]

On Thu, 12 May 2022 18:49:43 -0500

Then it is totally different to what std::deque offers: std::deque
allows ALL elements to be either popped from the front or back. Try
reading AND UNDERSTANDING what I wrote again.

/Flibble

[olcott]

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.

[Mr Flibble]

On Thu, 12 May 2022 19:12:22 -0500

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

[olcott]

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.

[Mr Flibble]

On Thu, 12 May 2022 20:34:41 -0500

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

/Flibble

[tth]

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

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

Not with any version of the C language.

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

[olcott]

// 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); }

[Mr Flibble]

On Fri, 13 May 2022 10:58:56 -0500

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

/Flibble

[Chris M. Thomasson]

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.