A part of the next version of CodeSimian is Immutable Sparse Wave Trees (download WaveTree0.1.jar or WaveTree0.1_source_code.zip, its the same file).

As described on http://sourceforge.net/projects/wavetree/, WaveTree is:
64 bit floating point index & values designed for multi streaming wave data scattered across times, like microseconds since year 1970. Average amplitude, insert, delete, or cut any immutable shared subwave in log time & memory. AVL tree balancing. Java.

Its a small Jar file that lets you cut apart and reassemble audio thousands of times faster than normal, at the cost of 15 to 30 times normal memory usage (30 bytes per audio sample plus internal nodes in the binary tree). For example, a 1 megabyte wave file in my system is 15 to 30 megabytes. But normally if you trade the audio at positions 10%-40% and 50%-80%, that would take 1 extra megabyte (a complete copy of the whole wave), but in my system, it takes about .001 megabytes (times 15 to 30) because the data is not copied. It is pointed at in a tree. Or say you reverse the audio at position 50%-80%. That takes .3 megabytes times 15 to 30 in my system or an extra megabyte the normal way. If you then reverse the whole wave, theoretically when the code of the Wave.intern() function is finished, it will only take .701 megabytes (times 15 to 30) to reverse the whole 1 megabyte (times 15 to 30) partially-reversed wave, because .3 megabytes (times 15 to 30) of it was already reversed.

A 15 to 30 times overhead of memory is a lot, but because most operations can be done in log(x) time and memory (instead of x), with a lot of data, it is usually thousands of times smaller than the normal ways of storing audio data in memory. If you have many variations of the same wave, you can store terabytes of wave data in megabytes.

WaveTree is licensed by LGPL (GNU Library/Lesser General Public License) any version. Its free and open-source. This license is much less restrictive than the GNU GPL 2+ which CodeSimian is under.



This sample code is included in the program and can be run
by double-clicking the Jar file or typing java -jar WaveTree0.1.jar on the command-line.


/** Generates audio (a simple equation of sines), buffers it with a Wave tree,
and plays it by sending bytes to the sound-card which are played on the computer's speakers.


If the sound skips, try increasing Java's memory. Each audio sample takes about 30 bytes. */ public class TestWaveTreeWithSoundCard{ public static void main(String s[]) throws LineUnavailableException{ System.out.println("Source-code should be in this Jar file. Unzip it."); WaveFactory.test(System.out); //valid times are now plus minus about 40 years, //but in this test, only plus minus a few seconds will be used Wave wave = WaveFactory.ampSizle(0., System.currentTimeMillis()*2); int bufferSize = 16 * 1024; //If sound skips, increase this or get a better sound-card double now = System.currentTimeMillis(); double timeStarted = now; SourceDataLine sourceLine = getSourceDataLine(bufferSize); AudioFormat format = sourceLine.getFormat(); System.out.println("DataLine = "+sourceLine); System.out.println("DataLine.getFormat() = "+format); double audioSampleMillis = 1000. / format.getSampleRate(); double sinecount = 0, sinecount2 = 0; double duration = 10000; //would be 10 seconds if playbackSpeed was always 1 int bal = 0; for(double millis=0; millis<duration; millis+=audioSampleMillis){ double amplitude = Math.sin(sinecount += .1*Math.sin(sinecount2 += .0001))*.4; //amplitude must range at most -1 to 1 Wave audioSample = WaveFactory.ampSizle(amplitude, audioSampleMillis); //Its inefficient to create a Wave for each audio sample. //Its more efficient to create a Wave of many audio samples and then merge it with the main Wave. //But this is just a sample code. wave = wave.overwrite(audioSample, now+millis); if(bal++ % 10 == 0) wave = wave.balanceTree(); //must balance before tree exceeds depth 127, //and for efficiency, should do it more often than that } wave = wave.balanceTree(); double playbackSpeed = .9; sourceLine.open(format, bufferSize); sourceLine.start(); System.out.println("Opened and started DataLine"); double playingTime = now; //not syncronized with System.currentTimeMillis() because that doesnt have enough accuracy double doubleArray[] = new double[1024]; //audio samples byte audioData[] = new byte[doubleArray.length*2]; boolean bigEndian = format.isBigEndian(); try{ while(true){ int bytesNotUsedInSoundCardBuffer = sourceLine.available(); if(playbackSpeed != 1.5 && playingTime > timeStarted+duration/2){ System.out.println("WaveTree test is half over. Increasing playback speed."); playbackSpeed = 1.5; } if(playingTime > timeStarted+duration){ System.out.println("WaveTree test ended. You should have heard a smooth sound that changed frequencies."); return; } if(bytesNotUsedInSoundCardBuffer > audioData.length){ double dStart = playingTime; double dSize = doubleArray.length*audioSampleMillis*playbackSpeed; double dIncrement = dSize/doubleArray.length; for(int i=0; i<doubleArray.length; i++){ //doubleArray[i] = wave.amp(dStart+i*dIncrement); //doubleArray[i] = wave.sub(dStart+i*dIncrement, dStart+(i+1)*dIncrement).aveAmp(); double x = dStart+i*dIncrement; doubleArray[i] = wave.sub(x, x+dIncrement).aveAmp(); } for(int i=0; i<doubleArray.length; i++){ double d = doubleArray[i]; d *= Short.MAX_VALUE; short sh = (short) d; audioData[i+i] = (byte)(sh/256); audioData[i+i+1] = (byte)(sh-256*audioData[i+i]); if(!bigEndian){ byte temp = audioData[i+i]; audioData[i+i] = audioData[i+i+1]; audioData[i+i+1] = temp; } //audioData[i+i+1] = (byte) 0; //FIXME: use correct big endian mapping. dont divide. } sourceLine.write(audioData, 0, audioData.length); playingTime += dSize; }else{ try{ Thread.sleep(50); }catch(InterruptedException e){} } } }finally{ sourceLine.close(); } } static SourceDataLine getSourceDataLine(int bufferSize) throws LineUnavailableException{ float sampleRate = 22050; int sampleSizeInBits = 16; int channels = 1; boolean signed = true; boolean bigEndian = true; AudioFormat format = new AudioFormat(sampleRate, sampleSizeInBits, channels, signed, bigEndian); DataLine.Info info = new DataLine.Info(SourceDataLine.class,format,bufferSize); try{ return (SourceDataLine) AudioSystem.getLine(info); }catch(LineUnavailableException e){ e.printStackTrace(); Line.Info[] lineInfos = AudioSystem.getSourceLineInfo(info); if(lineInfos.length == 0) throw new LineUnavailableException("Cant get any SourceDataLine"); return (SourceDataLine) AudioSystem.getLine(lineInfos[0]); } } }

If you have any comments or questions, dont hesitate to email ben@codesimian.com If you have anything to ask or say about CodeSimian or WaveTree, you can call me (Ben) on my cell phone 408.334.7214