A circular (or ring) buffer (https://en.wikipedia.org/wiki/Circular_buffer) that allows overwrite (when full, new data overwrites the 'oldest' data). Data is never removed / popped from buffer, only added and contents read. But 'popping' can probably be added; I don't need that.
I plan to this for a 'rolling oscilloscope' function in my power logger/plotter program (for the TPlink HS110 device).
'-------------------------- Example data type ----------------------------------
type data_type
dim as double absTime
dim as integer sample
declare constructor()
declare constructor(absTime as double, sample as integer)
declare operator cast() as string
end type
constructor data_type()
this.absTime = 0.0 : this.sample = 0
end constructor
constructor data_type(absTime as double, sample as integer)
this.absTime = absTime : this.sample = sample
end constructor
operator data_type.cast() as string
return str(absTime) & "," & str(sample)
end operator
'---------------------------- Circular buffer ----------------------------------
type rolling_buffer_type
private:
dim as data_type myData(any)
dim as integer first, reader, numRead, numData, bufferSize
public:
declare constructor(dataSize as integer)
declare destructor()
declare function add(newData as data_type) as integer
declare sub readerReset()
declare function getValue(byref readData as data_type) as integer
declare sub show()
end type
constructor rolling_buffer_type(bufferSize as integer)
redim myData(bufferSize - 1)
this.bufferSize = bufferSize
end constructor
destructor rolling_buffer_type()
erase myData
bufferSize = 0
end destructor
function rolling_buffer_type.add(newData as data_type) as integer
dim as integer index
if numData < bufferSize then
'add data
index = first + numData
if index >= bufferSize then index -= bufferSize
numData += 1
myData(index) = newData
else
'replace data
myData(first) = newData
first += 1 'move first pointer
if first >= bufferSize then first -= bufferSize
end if
return 0 'always zero for now
end function
'normally not needed
sub rolling_buffer_type.readerReset()
numRead = 0
end sub
'returns -1 when last item is reached
function rolling_buffer_type.getValue(byref readData as data_type) as integer
if numData > numRead then
reader = first + numRead
if reader >= bufferSize then reader -= bufferSize
readData = myData(reader)
numRead += 1
return 0
else
numRead = 0
return -1
end if
end function
'for debugging
sub rolling_buffer_type.show()
print "bufferSize: " & bufferSize
print "numData: " & numData
print "numRead: " & numRead
print "first: " & first
print "reader: " & reader
for i as integer = 0 to bufferSize - 1
print myData(i)
next
end sub
'----------------------------- Main program ------------------------------------
'create a buffer for 4 items
dim as rolling_buffer_type buffer = rolling_buffer_type(4)
dim as data_type readData
'add 3 items
for i as integer = 1 to 3
buffer.add(data_type(i, i))
next
'read and print buffer contents
print "Buffer:"
while buffer.getValue(readData) = 0
print readData
wend
'add 2 more items, last one overwrites the first
for i as integer = 4 to 5
buffer.add(data_type(i, i))
next
'read and print buffer contents
print "Buffer:"
while buffer.getValue(readData) = 0
print readData
wend
'-------------------------- Example data type ----------------------------------
type data_type
dim as double absTime
dim as integer sample
declare constructor()
declare constructor(absTime as double, sample as integer)
declare operator cast() as string
end type
constructor data_type()
this.absTime = 0.0 : this.sample = 0
end constructor
constructor data_type(absTime as double, sample as integer)
this.absTime = absTime : this.sample = sample
end constructor
operator data_type.cast() as string
return str(absTime) & "," & str(sample)
end operator
'---------------------------- Circular buffer ----------------------------------
type rolling_buffer_type
private:
dim as data_type myData(any)
dim as integer first, reader, numRead, numData, bufferSize
public:
declare constructor(dataSize as integer)
declare destructor()
declare function add(newData as data_type) as integer
declare function pop(byref readData as data_type) as integer
declare sub readerReset()
declare function getValue(byref readData as data_type) as integer
declare function getNumData() as integer
declare sub show()
end type
constructor rolling_buffer_type(bufferSize as integer)
redim myData(bufferSize - 1)
this.bufferSize = bufferSize
end constructor
destructor rolling_buffer_type()
erase myData
bufferSize = 0
end destructor
function rolling_buffer_type.add(newData as data_type) as integer
dim as integer index
if numData < bufferSize then
'add data
index = first + numData
if index >= bufferSize then index -= bufferSize
numData += 1
myData(index) = newData
else
'replace data
myData(first) = newData
first += 1 'move first pointer
if first >= bufferSize then first -= bufferSize
end if
return 0 'always zero for now
end function
'Get and remove first / oldest item from list
'don't mix / interleave with getValue calls
function rolling_buffer_type.pop(byref readData as data_type) as integer
if numData > 0 then
readData = myData(first)
first += 1
if first >= bufferSize then first -= bufferSize
numData -= 1
else
return -1
end if
end function
'normally not needed
sub rolling_buffer_type.readerReset()
numRead = 0
end sub
'returns -1 when last item is reached
function rolling_buffer_type.getValue(byref readData as data_type) as integer
if numData > numRead then
reader = first + numRead
if reader >= bufferSize then reader -= bufferSize
readData = myData(reader)
numRead += 1
return 0
else
numRead = 0
return -1
end if
end function
function rolling_buffer_type.getNumData() as integer
return numData
end function
'for debugging
sub rolling_buffer_type.show()
print "bufferSize: " & bufferSize
print "numData: " & numData
print "numRead: " & numRead
print "first: " & first
print "reader: " & reader
for i as integer = 0 to bufferSize - 1
print myData(i)
next
end sub
'----------------------------- Main program ------------------------------------
'create a buffer for 4 items
dim as rolling_buffer_type buffer = rolling_buffer_type(4)
dim as data_type readData
'add 3 items
for i as integer = 1 to 3
buffer.add(data_type(i, i))
next
'read and print buffer contents
print "Buffer (after 3 items added):"
while buffer.getValue(readData) = 0
print readData
wend
'add 2 more items, last one overwrites the first
for i as integer = 4 to 5
buffer.add(data_type(i, i))
next
'read and print buffer contents
print "Buffer (after 2 more added):"
while buffer.getValue(readData) = 0
print readData
wend
'pop first item from list
print "Removed item:"
if buffer.pop(readData) = 0 then
print readData
end if
'read and print buffer contents
print "Buffer (after 1 item removed):"
while buffer.getValue(readData) = 0
print readData
wend
'pop all remaing items from list
print "Removed items:"
while buffer.pop(readData) = 0
print readData
wend
print "Number of items in buffer: " & buffer.getNumData()
I really like this idea. I can imagine using this for my own project. I need to replace off screen data with incoming data to replace it. I have a similar method in place already for map data but when it gets more complex I'll want something more robust. This makes me think of how the early side scroller games worked by replacing off screen data with the new screen data. I think I remember that being a new thing when Carmack worked on a Mario brothers clone for the PC. It turned into the Commander Keen series after Nintendo told him no thanks.
sero wrote:I really like this idea. I can imagine using this for my own project. I need to replace off screen data with incoming data to replace it. I have a similar method in place already for map data but when it gets more complex I'll want something more robust. This makes me think of how the early side scroller games worked by replacing off screen data with the new screen data. I think I remember that being a new thing when Carmack worked on a Mario brothers clone for the PC. It turned into the Commander Keen series after Nintendo told him no thanks.
If a map (of tiles indexes) is not too big, you can keep the whole map in memory. And in addition an array of the tiles images. During the game you only draw the tiles that are visible. No need to copy maps during drawing. I have posted some demo's in the past, lets if I can find them...
* One with hexagon tiles: viewtopic.php?f=7&t=21153
* Oblique view and square tiles: viewtopic.php?f=15&t=24464
(not tested with new compiler versions)
For a large or infinite map, the method often used is to load (and unload) 'chunks' of map sections.