Ways of implementing a queue

Place to talk about all that new hardware and decaying software you have.

Moderator: General Mods

Post Reply
lordmissus
Ignorant Child
Posts: 326
Joined: Mon Apr 06, 2009 10:10 pm
Location: 1984

Ways of implementing a queue

Post by lordmissus »

Post your method. Mine implements a queue of bytes.

The following is in C#

Code: Select all

    public class fqueue
    {
      //private data:

        private bool empty;
        private bool full;

        private int begin, end;

        private byte[] x; // each queue item is a single byte

      //public data:

        public fqueue()
        {
            empty = !(full = false);
            begin = end = 0;

            x = new byte[256];
            return;
        }

        public fqueue(int size)
        {
            if (1 > size) 
                throw new IndexOutOfRangeException();

            empty = !(full = false);
            begin = end = 0;

            x = new byte[size];
            return;
        }

        public byte add
        {
            set
            {
                if(full) throw new Exception("Write: Queue is full");

                end = empty ? end : (end + 1) % x.Length;
                full = ((end + 1) % x.Length) == begin;

                empty = false;
                x[end] = value;
            }
        }

        public byte read
        {
            get
            {
                if(empty) throw new Exception("Read: Queue is empty");
                full = false;

                byte ret = x[begin];

                begin = (empty=end==begin) ?
                    begin :
                    (begin + 1) % x.Length;

                return ret;
            }
        }

        public int maxSize
        {
            get
            {
                return x.Length;
            }
        }

        public int queueSize
        {
            get
            {
                return end - begin + (empty ? 0 : 1 + ((end < begin) ? x.Length : 0));
            }
        }

        public bool isEmpty
        {
            get
            {
                return empty;
            }
        }

        public bool isFull
        {
            get
            {
                return full;
            }
        }        
    }
Mine uses a static array, but it does not move any bytes when reading from the queue. It uses a "circular" technique. It is faster than the normal method using static arrays, and uses less memory than a linked list method (since it doesn't store a pointer for every element in the list).
grinvader
ZSNES Shake Shake Prinny
Posts: 5632
Joined: Wed Jul 28, 2004 4:15 pm
Location: PAL50, dood !

Re: Ways of implementing a queue

Post by grinvader »

edit: LAWL DISREGARD THIS I SUCK COCKS

nice enough, although i'd store the next free block in end to simplify tests.
皆黙って俺について来い!!

Code: Select all

<jmr> bsnes has the most accurate wiki page but it takes forever to load (or something)
Pantheon: Gideon Zhi | CaitSith2 | Nach | kode54
lordmissus
Ignorant Child
Posts: 326
Joined: Mon Apr 06, 2009 10:10 pm
Location: 1984

Re: Ways of implementing a queue

Post by lordmissus »

It acts like a stack when appending bytes on the queue. However, usually when using a static array to implement a queue you would do this:

Code: Select all

  for(int i = 1; i < x.Length; i++)
  {
    x[i-1] = x[i];
  }
  x[x.Length-1] = 0;
This means shuffling along each byte not in the index (position 0) to the index 1 to the left. This is slow, and is the usual method for reading off the front of a queue implemented with a static array.

Mine, however, when reading, simply increments the pointer to the byte at the front of the queue, so that it points to the byte second in line. Think of it like the front desk moving towards the queue, rather than the people not at the front of the queue moving towards the desk when the person at the front leaves.

This means that sometimes, the byte at the back of the queue is at the beginning of the array. For example, if we did:

x = new byte[256];

and filled it up with 0xA2 values. begin points to x[0], end points to x[255].
Now we read from the queue. We get the value pointed to by begin (x[0]), then increment begin. Now the following is true:

begin points to x[1], end points to x[255]. Now when we add to the queue, the following is true:

begin points to x[1], end points to x[0]

I'm pretty sure someone has already implemented queues this way. If they haven't, I'll call it a "circle queue".
Another appropriate name would be a "bulldozer queue", since the desk moves to the people in line, rather than the people in line moving forwards to the desk.

This "desk" happens to literally be a bulldozer. It could also be a mammoth. Depends on what era we're in.




If begin is equal to (end+1)%x.Length, and no byte has been written to where end points to, that means the queue is full since there is no more free space.
If begin is equal to end, and no byte has been written, or if a byte that is the only byte in the queue is read, the queue is marked as empty.

In this way, we don't actually delete bytes (i.e. write zero's over them). We simply disregard that they are there. Hence "bulldozer queue", since we are stepping over and crushing their pretty faces when we write over them.


This is obviously faster than using the method as shown by the code snippet above in this post. It is not much faster (but still slightly faster) than using a linked list, but has the advantage of not using nearly as much memory. In other words, my method is awesome.


It still has the detriment of not being easily expandable, however, without incurring a speed penalty. What if we want the max size of the queue to be bigger, while still retaining what is in the queue? If we expand the array, suddenly we'd have to move stuff around anyway (once for expanding the array, and if end is lower than begin, one for moving everything from the array position at begin, to the literal end of the actual array to the right at least once (if we were expanding the max size by 1, we'd only move them all once, but if we were to expand the array by about, say 60, so as to be able to fit 60 more bytes, we'd have to move so much more...)), which would incur a further penalty, increasing depending on the literal size of the array. Then of course you would temporarily have to create a copy of the array, so as to expand it without losing anything. This copy of the array can be deleted after it is no longer needed, thus freeing up memory, but it's still using more memory needlessly while it is there, when it could be put to much better use. This isn't a problem if we don't expand often. What if we are constantly expanding/contracting the array? However, no good programmer allows their arrays/lists to be expanded indefinitely (hence malloc() if you are using C/C++), so this point is moot...

...if you only want a fixed maximum size for your queue (for example, you want the queue to be no larger than 1024 bytes), my method is not only fast, but uses a minimum amount of memory.

Of course, if the maximum size of the queue is 1024, you create a 1024 byte array. What if only 1 byte is currently stored in the array? You are wasting 1023 bytes. I could set a max size the array can be expanded to. That way we can use a 23 byte array to store 23 bytes. We expand it to 24 when adding a new byte. And so on. This would use even less memory than my currently method. However, it would be incredibly slow, especially if we are performing read/write to the queue very often.

So I've kind of made the best trade off I can, gaining a middle ground between memory usage and CPU time.





I hope that this rather long winded explanation explains my thinking.
lordmissus
Ignorant Child
Posts: 326
Joined: Mon Apr 06, 2009 10:10 pm
Location: 1984

Re: Ways of implementing a queue

Post by lordmissus »

Ah, yes, it turns out that "circular queue" actually is the name for this technique. See the following Java applet:
http://maven.smith.edu/~streinu/Teachin ... pplet.html

It implements a queue that works exactly the same way that my C# one does.
I still prefer the informal name "bulldozer queue", though.

It is an excellent feeling to invent something, and then find out it has already been invented. You discovered it on your own, without help from others.
I imagine that there are plenty of ameteur physics students discovering things already demonstrated for at least 100 years. It is the best way to learn.

Turns out circular buffering is actually what is used for buffering data streams in telecommunications.
http://en.wikipedia.org/wiki/Circular_buffer

A name for this is a "ring buffer".

Shows how little I know/knew >_<
lordmissus
Ignorant Child
Posts: 326
Joined: Mon Apr 06, 2009 10:10 pm
Location: 1984

Re: Ways of implementing a queue

Post by lordmissus »

Sorry for triple post, but otherwise it would be a very long post. I made a slight change to fqueue. I also wrote some code to test the implementation, to see if it works properly. Observe:

Code: Select all

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace quick_queue
{





    public class fqueue
    {
      //private data:

        private bool empty;
        private bool full;

        private int begin, end;

        private byte[] x; // each queue item is a single byte

      //public data:

        public fqueue()
        {
            empty = !(full = false);
            begin = end = 0;

            x = new byte[256];
            return;
        }

        public fqueue(int size)
        {
            if (1 > size) 
                throw new IndexOutOfRangeException();

            empty = !(full = false);
            begin = end = 0;

            x = new byte[size];
            return;
        }

        public byte add
        {
            set
            {
                if(full) throw new Exception("Write: Queue is full");

                end = empty ? end : (end + 1) % x.Length;

                full = ((end + 1) % x.Length) == begin;
                empty = false;

                x[end] = value;
            }
        }

        public byte read
        {
            get
            {
                if(empty) throw new Exception("Read: Queue is empty");
                full = false;

                byte ret = x[begin];

                begin = (empty=end==begin) ?
                    begin :
                    (begin + 1) % x.Length;

                return ret;
            }
        }

        public int maxSize
        {
            get
            {
                return x.Length;
            }
        }

        public int queueSize
        {
            get
            {
                return end - begin + (empty ? 0 : 1 + ((end < begin) ? x.Length : 0));
            }
        }

        public bool isEmpty
        {
            get
            {
                return empty;
            }
        }

        public bool isFull
        {
            get
            {
                return full;
            }
        }

        public int start
        {
            get
            {
                return begin;
            }
        }        

        public int finish
        {
            get
            {
                return end;
            }
        }
    }







    class Program
    {
        static string chex(byte x)
        {
            string c = "0123456789ABCDEF";
            return c[x >> 4] + "" + c[x & 0xf];
        }

        static void printStats(fqueue q)
        {
            Console.Write(

                " - Max size = {0}\n"+
                " - Current size = {1}\n"+
                " - Start position = {2}\n"+
                " - End position = {3}\n"+
                " - Empty = {4}\n"+
                " - Full = {5}\n",
            
                q.maxSize,
                q.queueSize,
                q.start,
                q.finish,
                q.isEmpty,
                q.isFull

            );
        }

        static bool fqCorrect() // Check whether the implementation of fqueue is correct
        {
            fqueue q;

            // Detect whether the implementation checks the given maximum size during initialization
            try
            {
                Console.Write("Creating an invalid queue of size 0\n");
                q = new fqueue(0);
                Console.Write("ERROR: queue implementation does not check whether the max size is zero.\n");
                return false;
            }
            catch(Exception x)
            {
                Console.Write(x.Message);
                Console.Write(".\nGood, the implementation checks for zero-size.\nCreating an invalid queue of size -1\n");
                try
                {
                    q = new fqueue(-1);
                    Console.Write("ERROR: queue implementation does not check whether the max size is negative.\n");
                    return false;
                }
                catch(Exception fail)
                {
                    Console.Write(fail.Message);
                    Console.Write(".\nGood, the implementation checks for negative size.\n\n");
                }
            }

            Console.Write("Creating queue of max size 200 bytes...\n\n");
            q = new fqueue(200);

            // Check to see if initialization is to spec:
            Console.Write("Initialized queue:\n");
            printStats(q);
            if(q.isFull)
            {
                Console.Write("ERROR: Queue is full, when upon init it should be empty\n");
                return false;
            }
            if(!q.isEmpty)
            {
                Console.Write("ERROR: Queue is not empty, when it should be upon init\n");
                return false;
            }
            if(q.start != q.finish)
            {
                Console.Write("ERROR: Start and Finish do not equate, but upon init they should be equal\n");
                return false;
            }
            if(q.queueSize != 0)
            {
                Console.Write("ERROR: Queue size not zero, when it should be upon init\n");
                return false;
            }
            if(q.maxSize != 200)
            {
                Console.Write("ERROR: Max queue size is not 200, but this is what was set when calling the initialization\n");
                return false;
            }



            //Now fill the queue, to see if it acts as expected.

            byte[] rex = new byte[q.maxSize];
            for (int i = 0; i < rex.Length; i++)
            {
                rex[i] = (byte)~(byte)i;
            }
            // We just filled the above array with values that should be stored correctly in the queue
            //Now we will actually store them:
            Console.Write("Filling the queue...\n");
            Console.Write("This is what we are writing in order:\n");
            for(int i = 0; i < rex.Length; i++)
            {
                Console.Write("{0}, ", chex(rex[i]));
            }
            Console.Write("\nNow we will write all of this...\n");
            for(int i = 0; i < rex.Length; i++)
            {
                q.add = rex[i];
            }

            Console.Write("Filled queue, no overlapping:\n");
            printStats(q);
            if(!q.isFull)
            {
                Console.Write("ERROR: Queue not marked full, when it ought to be\n");
                return false;
            }
            if(q.isEmpty)
            {
                Console.Write("ERROR: Queue is marked as empty, when it shouldn't be\n");
                return false;
            }
            if(q.start == q.finish)
            {
                Console.Write("ERROR: Start position and end position are equal, when they shouldn't be\n");
                return false;
            }
            if(q.queueSize != 200)
            {
                Console.Write("ERROR: Marked queue size not 200, when it ought to be\n");
                return false;
            }

            Console.Write("Creating a copy of the queue,\ntesting to see if the bytes were correctly written:\nREADING FROM QUEUE...\n");
            fqueue qCopy = new fqueue(200);
            for(int i = 0; i < q.maxSize; i++)
            {
                qCopy.add = rex[i];
            }
            for (int i = 0; i < rex.Length; i++)
            {
                byte tmp = qCopy.read;
                Console.Write("{0}, ", chex(tmp));
                if (rex[i] != tmp)
                {
                    Console.Write("\nERROR: They weren't\n");
                    return false;
                }
            }
            Console.Write("\n...They were\n");

            Console.Write("The queue should be full... stats:\n");
            printStats(q);
            Console.Write("Attempting to write to the queue, having filled it already...\n");
            try
            {
                q.add = 0xA2;
                Console.Write("ERROR: writes to the queue when full, should NOT be allowed.\n");
                return false;
            }
            catch(Exception x)
            {
                Console.Write(" ...'{0}'.\n{1}\n", x.Message, " ...good, it raises an exception.\n");
            }


            
            Console.Write("Testing to see if the implementation is circular...\n\n");


            Console.Write("Reading one byte off the queue, we get the following stats:\n");
            byte sta = q.read;
            printStats(q);
            if(q.start != 1)
            {
                Console.Write("ERROR: Start position is not 1, therefore the queue is not circular. FAIL\n");
                return false;
            }
            if(q.queueSize != 199)
            {
                Console.Write("ERROR: Size of queue is not 199, but it should be. FAIL\n");
                return false;
            }
            Console.Write("\n");



            Console.Write("Adding a new byte (0xA2) to the queue, we get the following stats:\n");
            q.add = 0xA2;
            printStats(q);
            if(q.finish != 0)
            {
                Console.Write("ERROR: Finish position is not 0, therefore the queue is not circular. FAIL\n");
                return false;
            }
            if(q.queueSize != 200)
            {
                Console.Write("ERROR: Size of queue is not 200, but it should be. FAIL\n");
                return false;
            }
            Console.Write("\n");


            bool foo;
            Console.Write("Emptying the queue, then attempting to read from it...\n");
            for(;;)
            {
                try
                {
                    foo = q.isEmpty;
                    sta = q.read;
                    if(foo)
                    {
                        Console.Write("ERROR: Reads from the queue when empty should NOT be allowed\n");
                        return false;
                    }
                }
                catch(Exception fail)
                {
                    Console.Write("...'{0}'\n{1}\n", fail.Message, "...good, it raises an exception when reading from an empty queue...\n\n");
                    ConsoleColor c = Console.ForegroundColor;
                    Console.ForegroundColor = ConsoleColor.Green;
                    Console.Write("CONGRATULATIONS! fqueue is implemented correctly, with no known bugs.\n\n");
                    Console.ForegroundColor = c;

                    return true;
                }
            }


        }

        static void Main(string[] args)
        {
            Console.SetWindowSize(80,50);

            bool correct = fqCorrect();
            if(!correct)
            {
                ConsoleColor c = Console.ForegroundColor;
                Console.ForegroundColor = ConsoleColor.Red;
                Console.Write("\n\n____YOU SUCK____\n\n");
                Console.ForegroundColor = c;
            }

            Console.ReadKey(true);
                       
        }
    }






}
Here is the output from the above program:
Image




Though it doesn't matter where the start and end pointers begin on a circular buffer, provided they are equal during initialization, my code assumes that all implementations should have the two pointers starting at 0. This makes detecting whether the queue implementation is correctly circular a lot easier.

So, any implementation of fqueue, be it a rewrite of the above, modification or otherwise, begin/end must both start at zero.
lordmissus
Ignorant Child
Posts: 326
Joined: Mon Apr 06, 2009 10:10 pm
Location: 1984

Re: Ways of implementing a queue

Post by lordmissus »

Here is another method, again in C#. ulong is 8 bytes. So declare a ulong and use it as an array of bytes, right? We just need to setup 3 pointers; index, begin, end. This code also features an interface; the user can add new bytes to the queue, or delete bytes. They can see the exact state of the queue after each operation on it, including any errors (reading from empty queue, writing to full queue...).

So,

Code: Select all

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace circle_queue
{
    unsafe class Program
    {


    // Hexadecimal conversion:
        unsafe static string chex(byte x)
        {
            string rex = "0123456789ABCDEF";
            return rex[x >> 4] + "" + rex[x & 0xf];
        }


    // Functions for handling the queue:
        unsafe static string write(byte value, ref byte* index, 
                          ref byte* end, ref bool full, ref bool empty, 
                          ref int count)
        {
            if(full) return("Write error: queue is full\n");

            ++count;
            full = 8 == count;

            if(!empty) end = (end == index + 7) ? index : ++end;
            empty = false;

            *end = value;

            return("Write was successful. Wrote: " + chex(value) + ".\n");
        }

        unsafe static string read(ref byte ret, ref byte* index, 
                        ref byte* begin, ref bool full, ref bool empty,
                        ref int count)
        {
            if(empty) return("Read error: queue is empty\n");

            ret = *begin;

            --count;
            empty = 0 == count;

            if(!empty) begin = (begin == index + 7) ? index : ++begin;
            full = false;

            return("Read was successful. Got: " + chex(ret) + ".\n");
        }


    // Function for outputting the contents of the queue
        unsafe static string reveal(byte* index, byte* begin, byte* end, bool empty)
        {
            if(empty) return("__ __ __ __ __ __ __ __");
            string ret = "";
            if(end == begin)
            {
                for(int i = (int)index; i < (int)end; i++)             ret += "__ ";
                                                                       ret += chex(*begin) + " ";
                for(int i = (int)begin + 1; i < ((int)index + 8); i++) ret += "__ ";
            }
            else if(end < begin)
            {
                for(int i = (int)index; i < ((int)end + 1); i++)   ret += chex(*(byte*)i) + " ";
                for(int i = (int)end + 1; i < (int)begin; i++)     ret += "__ ";
                for(int i = (int)begin; i < ((int)index + 8); i++) ret += chex(*(byte*)i) + " ";
            }
            else //if(end > begin)
            {
                for(int i = (int)index; i < (int)begin; i++)         ret += "__ ";
                for(int i = (int)begin; i < ((int)end + 1); i++)     ret += chex(*(byte*)i) + " ";
                for(int i = (int)end + 1; i < ((int)index + 8); i++) ret += "__ ";
            }
            return ret;
        }


    // Function for outputting both the contents of the queue, and other stats
        unsafe static string qStats(byte* index, byte* begin, byte* end,
                                    bool empty, bool full, int count)
        {
            string ret = "";
            ret += "\n" + reveal(index, begin, end, empty) + "\n\n";
            ret += "Empty: " + empty + "\n";
            ret += "Full: " + full + "\n";
            ret += "Size: " + Convert.ToString(count) + "\n\n";
            return ret;
        }


    // Function for resetting the queue to its default state
        unsafe static string reset(ref ulong x, ref byte* index, ref byte* begin, ref byte* end,
                          ref bool empty, ref bool full, ref int count)
        {
            x = 0;
            begin = end = index;
            empty = !(full = false);
            count = 0;
            return("Queue reset to its default state");
        }    


    // Initialization, and interface
        unsafe static void Main(string[] args)
        {
            //byte dex = *(byte*)0xAAAAFFFF; // I really need to learn how to disable memory protection so I can do some evil stuff in c#...

          // data used for the queue
            ulong x = 0;             // used the initialize the queue. The queue can store a max of 8 bytes
            byte* index, begin, end; // indicates how data is currently stored in the queue
            index = begin = end = (byte*)&x;
            
            bool empty, full; // indicates whether the queue is empty or full, respectively
            empty = !(full = false);

            int count = 0;  // indicates how large the queue is
            byte ret = 0;   // stores the byte that is read when reading from the queue

            byte[] v = new byte[] {0xAA, 0xE3, 0x04, 0x80, 0x33, 0x87, 0xCC, 0xEA};
            int insDex = 0;
            
            string db = "";

          // handle the queue based on user input
            for(;;)
            {
                try
                {
                    Console.Write(qStats(index, begin, end, empty, full, count));
                    Console.Write("F1:Insert .. F2:delete .. F3:reset .. Esc:QUIT\n\n");
                    Console.Write(db);
                    switch (Console.ReadKey(true).Key)
                    {
                        case ConsoleKey.F1:
                            db = write(v[insDex], ref index, ref end, ref full, ref empty, ref count);
                            insDex = insDex == 7 ? 0 : ++insDex;
                            break;

                        case ConsoleKey.F2:
                            db = read(ref ret, ref index, ref begin, ref full, ref empty, ref count);
                            break;

                        case ConsoleKey.F3:
                            index = (byte*)&x;
                            db = reset(ref x, ref index, ref begin, ref end, ref empty, ref full, ref count);
                            break;

                        case ConsoleKey.Escape:
                            return;

                        default:
                            break;
                    }
                    if(index != (byte*)&x) throw new Exception("The GC has moved x, so begin, end and index are no longer valid.\n");
                    Console.Clear();
                }
                catch(Exception attemptedRestrictedMemoryAccessOmgTheWorldWillEnd) 
                      // If this occurs, it means the garbage collector moved x, and so the pointers no longer correlate
                {     // Thus, we need to completely reset the queue due to it's pointers now no longer being valid
                    db = attemptedRestrictedMemoryAccessOmgTheWorldWillEnd.Message;
                    index = (byte*)&x;
                    db += "\n" + reset(ref x, ref index, ref begin, ref end, ref empty, ref full, ref count);
                    continue;
                }
            }
        }


    }
}
mudlord
has wat u liek
Posts: 559
Joined: Tue Sep 11, 2007 2:54 pm
Location: Banland.

Re: Ways of implementing a queue

Post by mudlord »

Turns out circular buffering is actually what is used for buffering data streams in telecommunications.
http://en.wikipedia.org/wiki/Circular_buffer

A name for this is a "ring buffer".

Shows how little I know/knew >_<
And its used all the time in audio DSP.

Code: Select all

Echo::Echo()
{
	history = NULL;
	rate = 44100;
	SetDelay(200);		// default delay is 200ms
	SetAmp(128);		// default amplification is 50%
	pos = 0;
}


Echo::~Echo()
{
	delete [] history;
	history = NULL;
}


void Echo::SetDelay( int ms )
{
	// calculate number of samples needed for history
	int newDelay = ms * rate / 1000;

	// create new history buffer
	float *newHistory = new float[newDelay];
	memset( newHistory, 0, newDelay * sizeof(float) );

	// if there already is a history buffer, fill the new one with
	// old data (might not work right in all situations)
	if ( history )
	{
		int howMuch = delay - pos;
		howMuch = min( howMuch, newDelay );
		memcpy( newHistory, history + pos, howMuch * sizeof(float) );
		if ( howMuch < newDelay )
		{
			int i = howMuch;
			howMuch = newDelay - howMuch;
			howMuch = min( howMuch, delay );
			howMuch = min( howMuch, pos );
			memcpy( newHistory + i, history, howMuch * sizeof(float) );
		}
		delete [] history;
	}

	// remember new values
	history = newHistory;
	pos = 0;
	delay = newDelay;
	this->ms = ms;
}


// amp is in [0, 256] where 0 means no echoes and 256 means infinite echoes
void Echo::SetAmp( int amp )
{
	this->amp = amp;
	f_amp = ( float ) amp / 256.0f;
}


void Echo::SetSampleRate( int rate )
{
	if ( this->rate != rate )
	{
		this->rate = rate;
		SetDelay( ms );
	}
}


int Echo::GetDelay() const
{
	return ms;
}


int Echo::GetAmp() const
{
	return amp;
}


int Echo::GetSampleRate() const
{
	return rate;
}


// do the echo effect
float Echo::Process(float in)
{
	// mix each sample in the input buffer with the appropriately
	// delayed and amplified sample in the history buffer
	float smp = history[pos];   // read sample from history
	smp *= f_amp;				// amplify
	smp += in;                  // add to the matching sample from the input
	history[pos] = smp;         // write sample to the history buffer

	pos = ( pos + 1 ) % delay;

	return smp;
}
This person is a fucking douchebag, they should die.
Post Reply