DZone Snippets: tree code

Numbering left and right attributes of a nested set

iamwil (wilhelm) — Fri, 06 Jun 2008 19:29:00 GMT

Uses a hash to model a tree that numbers the left and right attributes of a nested set.

# test case for depth_first traversal
#
# tree = { :electronics => {
# :televisions => { :tube => {},
# :lcd => {},
# :plasma => {} },
# :portable_elec => { :mp3_players => {
# :flash => { }
# },
# :cd_player => { },
# :two_way_radio => { }
# }
# }
# }
#
# tree.depth_first do |name, parent_name, lft, rgt|
# puts "#{parent_name}/#{name}: #{lft} - #{rgt}"
# end



class Hash

  def depth_first(&block)

    root_node = self.keys.first

    root_children = self[root_node]

    depth_first_helper(root_node, root_children, nil, 1, &block)

  end



  private

  def depth_first_helper(name, children, parent_name, lft, &block)

    if children.empty?

      rgt = lft + 1

    else

      children_lft = lft + 1

      children.each do |child_name, grandchildren|

        rgt = depth_first_helper(child_name, grandchildren, name, children_lft, &block)

        children_lft = rgt

      end

    end

    block.call(name, parent_name, lft, rgt)

    return rgt + 1

  end

end

Disjoint Set Class in Ruby

dr_saturn (Stuart Coyle) — Sun, 10 Feb 2008 02:49:59 GMT

A disjoint Set can be used for creating minimal spanning trees.
The union-find algorithm is fast, faster than linked lists for some uses.
See: Wikipedia Disjoint Set

It's fast and simple. Just add a DisjointSetNode object to the
objects that you want to create a tree of.



# This is a disjoint set implementing union-find

# It can be used for generating a minimal spanning

# tree using Kruskal's algorithm.

# http://en.wikipedia.org/wiki/Kruskal's_algorithm



class DisjointSetNode

  attr_accessor :parent, :rank



  def initialize

    @parent = self

    @rank = 0

  end



  # An optimised union by rank. Attaches smaller tree to larger.

  def union(other)

    self_root = self.find

    other_root = other.find

    if self_root.rank > other_root.rank

      other_root.parent = self_root

    elsif self_root.rank < other_root.rank

      self_root.parent = other_root

    elsif self_root != other_root

      other_root.parent = self_root

      self_root.rank += 1

    end

  end



  def find

    if self.parent === self

      self

    else

      self.parent = self.parent.find

    end

  end



end   # class DisjointSetNode

Some simple test code:



require 'disjointsetnode'

require 'test/unit'

require 'test/unit/ui/console/testrunner'



    class DisjointSetTest < Test::Unit::TestCase

      N_Nodes = 1000



      def setup

        @nodes = Array.new

        (1..N_Nodes).each do |node|

        @nodes << DisjointSetNode.new

        end

      end



      # def teardown

      # end



      def test_creation

        @nodes.each do |node|

          assert !node.nil?, "A Node is nil!"

        end

      end



      def test_initial_values

        @nodes.each do |node|

          assert node.parent === node, "self #{node}, parent #{node.parent} not equal."

          assert node.rank == 0, " A node's rtank is not 0."

        end

      end



      def test_union

        # Join all nodes in sequence

        @nodes.each do |node|

          if !@lastnode.nil?

            node.union(@lastnode)

            node_f = node.find

            lnode_f = @lastnode.find

            assert node_f == lnode_f, "Join not completed: node_f: #{node_f}, lnode_f: #{lnode_f}"

          end

          @lastnode = node

        end

      end



      def test_random_union

        (1..N_Nodes-1).each do |n|

          node = @nodes[n]

          other = @nodes[rand(N_Nodes-1)]

          node.union(other)

          node_f = node.find

          onode_f = other.find

          assert node_f == onode_f, "Join not completed: node_f: #{node_f}, onode_f: #{onode_f}"

        end

      end

    end



# This runs the tests for ya! 

Test::Unit::UI::Console::TestRunner.run(DisjointSetTest)

Prim's Algorithm for Finding Minimum Spanning Trees in C

scvalex (Alexandru Scvortov) — Fri, 09 Nov 2007 12:31:11 GMT

The is a straight-forward implementation of Prim's Algorithm for finding the minimum spanning tree of a graph.

A detailed explanation is given here.



#include 



/*

	The input file (weight.txt) look something like this

		4

		0 0 0 21

		0 0 8 17

		0 8 0 16

		21 17 16 0



	The first line contains n, the number of nodes.

	Next is an nxn matrix containg the distances between the nodes

	NOTE: The distance between a node and itself should be 0

*/



int n; /* The number of nodes in the graph */



int weight[100][100]; /* weight[i][j] is the distance between node i and node j;

			if there is no path between i and j, weight[i][j] should

			be 0 */



char inTree[100]; /* inTree[i] is 1 if the node i is already in the minimum

			spanning tree; 0 otherwise*/



int d[100]; /* d[i] is the distance between node i and the minimum spanning

		tree; this is initially infinity (100000); if i is already in

		the tree, then d[i] is undefined;

		this is just a temporary variable. It's not necessary but speeds

		up execution considerably (by a factor of n) */



int whoTo[100]; /* whoTo[i] holds the index of the node i would have to be

			linked to in order to get a distance of d[i] */



/* updateDistances(int target)

	should be called immediately after target is added to the tree;

	updates d so that the values are correct (goes through target's

	neighbours making sure that the distances between them and the tree

	are indeed minimum)

*/

void updateDistances(int target) {

	int i;

	for (i = 0; i < n; ++i)

		if ((weight[target][i] != 0) && (d[i] > weight[target][i])) {

			d[i] = weight[target][i];

			whoTo[i] = target;

		}

}



int main(int argc, char *argv[]) {

	FILE *f = fopen("dist.txt", "r");

	fscanf(f, "%d", &n);

	int i, j;

	for (i = 0; i < n; ++i)

		for (j = 0; j < n; ++j)

			fscanf(f, "%d", &weight[i][j]);

	fclose(f);



	/* Initialise d with infinity */

	for (i = 0; i < n; ++i)

		d[i] = 100000;



	/* Mark all nodes as NOT beeing in the minimum spanning tree */

	for (i = 0; i < n; ++i)

		inTree[i] = 0;



	/* Add the first node to the tree */

	printf("Adding node %c\n", 0 + 'A');

	inTree[0] = 1;

	updateDistances(0);



	int total = 0;

	int treeSize;

	for (treeSize = 1; treeSize < n; ++treeSize) {

		/* Find the node with the smallest distance to the tree */

		int min = -1;

		for (i = 0; i < n; ++i)

			if (!inTree[i])

				if ((min == -1) || (d[min] > d[i]))

					min = i;



		/* And add it */

		printf("Adding edge %c-%c\n", whoTo[min] + 'A', min + 'A');

		inTree[min] = 1;

		total += d[min];



		updateDistances(min);

	}



	printf("Total distance: %d\n", total);



	return 0;

}

Expression tree builder

scvalex (Alexandru Scvortov) — Fri, 22 Jun 2007 14:21:31 GMT

EvalExp(s) turns the string s into an expression tree and returns it.

Inorder, preorder and postorder can then be used to turn transform the tree into inorder, preorder or postorder expressions.



function inorder(T) {

  if ((T.cargo  == '+') || (T.cargo  == '-') || (T.cargo  == '*') || (T.cargo  == '/'))

    return [].concat(inorder(T.left)).concat(T.cargo).concat(inorder(T.right));



  return new Array(T.cargo);

}



function preorder(T) {

  if ((T.cargo  == '+') || (T.cargo  == '-') || (T.cargo  == '*') || (T.cargo  == '/'))

    return [].concat(T.cargo).concat(preorder(T.left)).concat(preorder(T.right));



  return new Array(T.cargo);

}



function postorder(T) {

  if ((T.cargo  == '+') || (T.cargo  == '-') || (T.cargo  == '*') || (T.cargo  == '/'))

    return [].concat(postorder(T.left)).concat(postorder(T.right)).concat(T.cargo);



  return new Array(T.cargo);

}



function Tree(cargo, left, right) {

  this.cargo = cargo;

  this.left = left;

  this.right = right;

}



function split(s) {

  var r = [];

  var cur = '';

  for (var i = 0; i < s.length; ++i) {

    var c = s.charAt(i);

    if ((c == '+') || (c == '-') || (c == '*') || (c == '/') || (c == '(') || (c == ')')) {

      cur.replace(" ", "");

      if (cur.length > 0) {

        r.push(cur);

        cur = '';

      }

      r.push(c);

    } else {

      cur += c;

    }

  }

  if (cur.length > 0)

    r.push(cur);



  return r;

}



function getToken(tokens, expected) {

  if (tokens[0] == expected) {

    tokens.splice(0, 1);

    return true;

  }

    return false;

}



function getVar(tokens) {

  if (getToken(tokens, '(')) {

    var a = getSum(tokens);

    getToken(tokens, ')');



    return a;

  } else {

    var aux = tokens[0];

    tokens.splice(0, 1);



    return new Tree(aux, undefined, undefined);

  }

}



function getProduct(tokens) {

  var a = getVar(tokens);



  if (getToken(tokens, '*')) {

    var b = getProduct(tokens);



    return new Tree('*', a, b);

  } else if (getToken(tokens, '/')) {

    var b = getProduct(tokens);



    return new Tree('/', a, b);

  }



  return a;

}



function getSum(tokens) {

  var a = getProduct(tokens);



  if (getToken(tokens, '+')) {

    var b = getSum(tokens);



    return new Tree('+', a, b);

  } else if (getToken(tokens, '-')) {

    var b = getSum(tokens);



    return new Tree('-', a, b);

  }



  return a;

}



function evalExp(s) {

  var tokens = split(s);



  //alert(tokens);



  return t = getSum(tokens);

}

Visit Python Abstract Syntax Tree

maxme (Maxime Biais) — Wed, 24 Jan 2007 13:03:54 GMT

Simplest AST visitor. More on this blog post :
http://www.biais.org/blog/index.php/2007/01/10/9-visit-python-abstract-syntax-tree



import compiler

 

class CodePrinter:

    def __init__(self):

        self.src = ''

 

    def visitName(self,t):

        self.src += t.name

 

    def visitConst(self,t):

        self.src += str(t.value)

 

    def visitStmt(self, t):

        for i in t:

            a = pretty_print(i)

            self.src += a + "\n"

 

    def visitAssName(self, t):

        self.src += t.name + " = "

 

def pretty_print(node):

    myvisitor = CodePrinter()

    # compiler.walk return the visitor instance : 2nd arg

    return compiler.walk(node, myvisitor).src

Acts As Tree Category Display

ioda006 () — Sun, 16 Apr 2006 15:32:57 GMT

You should have a categories table with a parent_id field. Root categories should have the parent_id of 0.

I modified this post:
http://www.bigbold.com/snippets/posts/show/296

because the first one worked if you did stuff in your view to make the root categories come up, but I agree with the commenter that things should be contained to the helper - however I've managed to break the DRY rule in doing so. If anyone has any suggestions for a better way around this I'd love to hear it, so please comment. So anyway.. this should list your root categories ONLY and NOT your other sub-cats as well so that you have a very pretty little tree.

Slap this in your view:



<%= display_categories(@categories) %>

And put this in a helper file. You'll need it in the application helper most likely since you'll want to call it from multiple views.



      def display_categories(categories)

	    	   ret = ""

	   for category in categories

		   if category.parent_id == 0

			ret += ""

			ret += link_to category.name

			ret += find_all_subcategories(category)

			ret += ""

		   end

		   

	   end

	   ret += ""

    end

    

   def find_all_subcategories(category)

    if category.children.size > 0

      ret = ''

      category.children.each { |subcat| 

        if subcat.children.size > 0

          ret += ''

          ret += link_to h(subcat.name), :action => 'edit', :id => subcat

          ret += find_all_subcategories(subcat)

          ret += ''

        else

          ret += ''

          ret += link_to h(subcat.name), :action => 'edit', :id => subcat 

          ret += ''

        end

        }

      ret += ''

    end

  end

a binary tree structure "PersistentTree"

jonasraoni (Jonas Raoni Soares Silva) — Sat, 02 Jul 2005 03:50:02 GMT

unit StreamAdapter.pas



//+ Jonas Raoni Soares Silva

//@ http://jsfromhell.com



unit StreamAdapter;



interface



uses

  Classes;



type

  IStream = interface( IInterface )

    ['{FBEF199A-09BC-4B61-89EA-1EF8B22C93A5}']

    function Read(var Buffer; const Count: Longint): Longint;

    function Write(const Buffer; const Count: Longint): Longint;

    function Seek(const Offset: Int64; Origin: TSeekOrigin): Int64;

    procedure ReadBuffer(var Buffer; const Count: Longint);

    procedure WriteBuffer(const Buffer; const Count: Longint);

    function CopyFrom(Source: TStream; const Count: Int64): Int64;

    function WriteTo(Dest: TStream; const Count: Int64): Int64;



    procedure SetPosition( const Value: Int64 );

    procedure SetSize( const Value: Int64 );

    function GetPosition: Int64;

    function GetSize: Int64;



    property Position: Int64 read GetPosition write SetPosition;

    property Size: Int64 read GetSize write SetSize;

  end;



  TStreamAdapter = class( TInterfacedObject, IStream )

  private

    FStream: TStream;

    procedure SetPosition( const Value: Int64 );

    procedure SetSize( const Value: Int64 );

    function GetPosition: Int64;

    function GetSize: Int64;



  public

    constructor Create( Stream: TStream );

    destructor Destroy; override;



    function Read(var Buffer; const Count: Longint): Longint;

    function Write(const Buffer; const Count: Longint): Longint;



    procedure ReadBuffer(var Buffer; const Count: Longint);

    procedure WriteBuffer(const Buffer; const Count: Longint);



    function CopyFrom(Source: TStream; const Count: Int64): Int64;

    function WriteTo(Dest: TStream; const Count: Int64): Int64;



    function Seek(const Offset: Int64; Origin: TSeekOrigin): Int64;



    property Position: Int64 read GetPosition write SetPosition;

    property Size: Int64 read GetSize write SetSize;

  end;



implementation



{ TStreamAdapter }



function TStreamAdapter.CopyFrom(Source: TStream; const Count: Int64): Int64;

begin

  Result := FStream.CopyFrom( Source, Count );

end;



constructor TStreamAdapter.Create(Stream: TStream);

begin

  FStream := Stream;

end;



destructor TStreamAdapter.Destroy;

begin

  FStream.Free;

  inherited;

end;



function TStreamAdapter.GetPosition: Int64;

begin

  Result := FStream.Position;

end;



function TStreamAdapter.GetSize: Int64;

begin

  Result := FStream.Size;

end;



function TStreamAdapter.Read(var Buffer; const Count: Integer): Longint;

begin

  Result := FStream.Read( Buffer, Count );

end;



procedure TStreamAdapter.ReadBuffer(var Buffer; const Count: Integer);

begin

  FStream.ReadBuffer( Buffer, Count );

end;



function TStreamAdapter.Seek(const Offset: Int64;

  Origin: TSeekOrigin): Int64;

begin

  Result := FStream.Seek( Offset, Origin );

end;



procedure TStreamAdapter.SetPosition(const Value: Int64);

begin

  FStream.Position := Value;

end;



procedure TStreamAdapter.SetSize(const Value: Int64);

begin

  FStream.Size := Value;

end;



function TStreamAdapter.Write(const Buffer; const Count: Integer): Longint;

begin

  Result := FStream.Write( Buffer, Count );

end;



procedure TStreamAdapter.WriteBuffer(const Buffer; const Count: Integer);

begin

  FStream.WriteBuffer( Buffer, Count );

end;



function TStreamAdapter.WriteTo(Dest: TStream; const Count: Int64): Int64;

begin

  Result := Dest.CopyFrom( FStream, Count );

end;



end.

unit PersistentTree.pas



//+ Jonas Raoni Soares Silva

//@ http://jsfromhell.com



unit PersistentTree;



interface



uses

  Windows, Classes, SysUtils, StreamAdapter;



type

  EPersistentTree = class( Exception );



  TPersistentTree = class;



  TPersistentTreeClass = class of TPersistentTree;



  TPersistentTree = class( TStream )

  private

    FStream: IStream;

    FList: TList;

    FBaseClass: TPersistentTreeClass;

    FOwner, FParent: TPersistentTree;

    FOwnStream: Boolean;

    FDataFilename, FFilename: string;

    FLastPosition, FDataBegin, FDataLength: Int64;



    function GetItem(const Index: Integer): TPersistentTree;

    function GetCount: Integer;

    function GetStream: TStream;

    function Import( Item: TPersistentTree ): Boolean;

    procedure ClearData;

    procedure RecreateStream( const Pos: Int64; const Deep: Boolean = False );

    procedure Synchronize;



  protected

    //override to provide writing/reading notifications

    procedure Loaded; virtual;

    procedure Saving; virtual;



    //derived from TStream

    function GetSize: Int64; override;

    procedure SetSize(NewSize: Longint); override;

    procedure SetSize(const NewSize: Int64); override;



  public

    constructor Create; virtual;

    destructor Destroy; override;



    //derived from TStream

    function Read( var Buffer; Count: Longint ): Longint; override;

    function Write( const Buffer; Count: Longint ): Longint; override;

    function Seek(const Offset: Int64; Origin: TSeekOrigin): Int64; override;



    function Truncate: Int64;

    function ReadString: string;

    procedure WriteString( const Data: string );



    procedure Save( const AFilename: string ); overload;

    procedure Save( Stream: TStream ); overload;

    procedure Load( const AFilename: string ); overload;

    procedure Load( Stream: IStream ); overload;

    procedure Load( Stream: TStream ); overload;



    function Add: TPersistentTree; overload;

    function Add( Item: TPersistentTree ): Integer; overload;

    procedure Insert( const Index: Integer; Item: TPersistentTree);

    function IndexOf( Item: TPersistentTree ): Integer;

    function Remove( Item: TPersistentTree ): Integer;

    procedure Delete( const Index: Integer);

    function Extract( Item: TPersistentTree ): TPersistentTree;

    procedure Exchange( const IndexA, IndexB: Integer );

    procedure Move(const CurIndex, NewIndex: Integer);

    procedure Clear;



    property Items[ const Index: Integer ]: TPersistentTree read GetItem; default;

    property Count: Integer read GetCount;

    property Owner: TPersistentTree read FOwner;

    property Parent: TPersistentTree read FParent;

    property Filename: string read FFilename;

    property BaseClass: TPersistentTreeClass read FBaseClass write FBaseClass;

  end;



  TPersistentTreeHeader = packed record

    Sig: array[0..4] of Char;

    Ver: Word;

  end;



const

  PERSISTENT_TREE_HEADER: TPersistentTreeHeader = ( Sig: 'PTREE'; Ver: 1 );



function GetTempFile: string;





implementation



function GetTempFile: string;

var

  Path: array[0..MAX_PATH-1] of Char;

begin

  GetTempPath( MAX_PATH, Path );

  GetTempFileName( Path, 'BUF', 0, Path );

  Result := Path;

end;



{ TPersistentTree }



procedure TPersistentTree.Clear;

var

  I: Integer;

begin

  for I := FList.Count - 1 downto 0 do

  begin

    TPersistentTree( FList[I] ).Free;

    FList.Delete( I );

  end;

end;



constructor TPersistentTree.Create;

begin

  FBaseClass := TPersistentTreeClass( Self.ClassType );

  FList := TList.Create;

  FStream := TStreamAdapter.Create( GetStream );

  FOwnStream := True;

end;



destructor TPersistentTree.Destroy;

begin

  ClearData;

  FList.Free;

  inherited;

end;



procedure TPersistentTree.Exchange(const IndexA, IndexB: Integer);

begin

  FList.Exchange( IndexA, IndexB );

end;



function TPersistentTree.GetCount: Integer;

begin

  Result := FList.Count;

end;



function TPersistentTree.GetItem(const Index: Integer): TPersistentTree;

begin

  Result := FList[ Index ];

end;



function TPersistentTree.IndexOf(

  Item: TPersistentTree): Integer;

begin

  Result := FList.IndexOf( Item );

end;



procedure TPersistentTree.Load(const AFilename: string);

var

  FS: TFileStream;

  //Header: TPersistentTreeHeader;

begin

  FS := TFileStream.Create( AFilename, fmOpenRead or fmShareDenyWrite );

  try

    //FS.Read( Header, SizeOf( TPersistentTreeHeader ) );

    //if not CompareMem( @Header, @PERSISTENT_TREE_HEADER, SizeOf( TPersistentTreeHeader ) ) then

    //  raise EPersistentTree.CreateFmt( '%s.LoadFromFile :: "%s" Not Recognized', [ClassName, AFilename] );

    Load( FS );

    FFilename := AFilename;

  except

    FS.Free;

    raise;

  end;

end;



procedure TPersistentTree.Load(Stream: TStream);

begin

  Load( TStreamAdapter.Create( Stream ) );

end;



function TPersistentTree.Remove(Item: TPersistentTree): Integer;

begin

  Result := FList.Remove( Item );

  if Result >= 0 then

    Item.Free;

end;



procedure TPersistentTree.Save( const AFilename: string );

var

  FS: TFileStream;

begin

  FS := TFileStream.Create( AFilename, fmCreate or fmShareDenyWrite );

  try

    //FS.Write( PERSISTENT_TREE_HEADER, SizeOf( TPersistentTreeHeader ) );

    Save( FS );

  finally

    FS.Free;

  end;

end;



procedure TPersistentTree.Save(Stream: TStream);

var

  I: LongInt;

begin

  Seek( 0, soBeginning );

  Saving;



  FDataLength := Size;

  Stream.Write( FDataLength, SizeOf( FDataLength ) );

  Stream.CopyFrom( Self, 0 );



  I := FList.Count;

  Stream.Write( I, SizeOf( I ) );

  for I := 0 to FList.Count-1 do

    Self[I].Save( Stream );

end;



function TPersistentTree.Write( const Buffer; Count: Longint ): Longint;

begin

  if FOwnStream then

    Result := FStream.Write( Buffer, Count )

  else

  begin

    Synchronize;

    if Position + Count > Size then

      RecreateStream( Position );

    Result := FStream.Write( Buffer, Count );

    FLastPosition := FStream.Position;          

  end;



end;



function TPersistentTree.Read( var Buffer; Count: Longint): Longint;

begin

  if FOwnStream then

    Result := FStream.Read( Buffer, Count )

  else

  begin

    Synchronize;

    if Count < 0 then

      Count := 0

    else if Count > Size - Position then

      Count := Size - Position;

    Result := FStream.Read( Buffer, Count );

    FLastPosition := FStream.Position;

  end

end;



function TPersistentTree.Seek(const Offset: Int64;

  Origin: TSeekOrigin): Int64;

begin

  if FOwnStream then

    Result := FStream.Seek( Offset, Origin )

  else

  begin

    Synchronize;

    case Origin of

      soBeginning: Result := FDataBegin + Offset;

      soCurrent: Result := FStream.Position + Offset;

      soEnd: Result := FDataBegin + Size - Offset;

    else

      Result := 0;

    end;

    if Result > -1 then

      if Result <= FDataBegin + Size then

        Result := FStream.Seek( Result, soBeginning ) - FDataBegin

      else

      begin

        RecreateStream( Size );

        Result := FStream.Seek( Result, soBeginning );

      end;

    FLastPosition := FStream.Position;

  end;

end;



procedure TPersistentTree.SetSize(const NewSize: Int64);

begin

  if FOwnStream then

    FStream.Size := NewSize

  else begin

    if NewSize <= 0 then

      RecreateStream( 0 )

    else if NewSize > Size then

      RecreateStream( Size )

    else

    begin

      FDataLength := NewSize;

      Seek( 0, soEnd );

    end;

    FLastPosition := FStream.Position;

  end;

end;



procedure TPersistentTree.Synchronize;

begin

  if not FOwnStream and ( ( FStream.Position < FDataBegin ) or ( FStream.Position - FDataBegin > FDataLength ) ) then

    FStream.Seek( FLastPosition, soBeginning );

end;



procedure TPersistentTree.Load( Stream: IStream);

var

  I: LongInt;

begin

  ClearData;



  FStream := Stream;

  FOwnStream := False;



  Stream.Read( FDataLength, SizeOf( FDataLength ) );

  FDataBegin := FStream.Position;

  FLastPosition := FDataBegin;



  Stream.Seek( FDataLength, soCurrent );



  Stream.Read( I, SizeOf( I ) );

  for I := I - 1 downto 0 do

    Add.Load( FStream );



  //Seek( 0, soBeginning ); it isnt needed since synchonize will do it anyway

  Loaded;

  FStream.Seek( FDataBegin + FDataLength + SizeOf( I ), soBeginning );

end;



function TPersistentTree.Extract( Item: TPersistentTree): TPersistentTree;

begin

  Result := FList.Extract( Item );

  if Assigned( Result ) then begin

    Result.FParent := nil;

    Result.FOwner := nil;

    Result.RecreateStream( Size, True );

  end;

end;





function TPersistentTree.GetSize: Int64;

begin

  if FOwnStream then

    Result := FStream.Size

  else

    Result := FDataLength;

end;



procedure TPersistentTree.WriteString(const Data: string);

var

  I: LongWord;

begin

  I := Length( Data );

  Write( I, SizeOf( I ) );

  Write( Pointer( Data )^, I );

end;



function TPersistentTree.ReadString: string;

var

  I: LongWord;

begin

  Read( I, SizeOf( I ) );

  SetLength( Result, I );

  Read( Pointer( Result )^, I );

end;



procedure TPersistentTree.SetSize(NewSize: Integer);

begin

  SetSize( Int64( NewSize ) );

end;



procedure TPersistentTree.RecreateStream( const Pos: Int64; const Deep: Boolean );

var

  FS: TStream;

  I: Integer;

begin

  if not FOwnStream then

  begin

    FS := GetStream;

    if Pos > 0 then

    begin

      Seek( 0, soBeginning );

      FS.CopyFrom( Self, Pos );

    end;

    FStream := TStreamAdapter.Create( FS );

    FOwnStream := True;

  end;

  if Deep then

    for I := 0 to FList.Count - 1 do

      Self[I].RecreateStream( Self[I].Size, True );

end;



procedure TPersistentTree.ClearData;

begin

  FStream := nil;

  if FOwnStream then

    DeleteFile( FDataFilename );

  Clear;

end;



function TPersistentTree.GetStream: TStream;

begin

  FDataFilename := GetTempFile;

  Result := TFileStream.Create( FDataFilename, fmCreate or fmShareDenyWrite );

end;



function TPersistentTree.Add: TPersistentTree;

begin

  Result := TPersistentTreeClass( FBaseClass ).Create;

  Add( Result );

end;



function TPersistentTree.Add( Item: TPersistentTree): Integer;

begin

  if Import( Item ) then

    Result := FList.Add( Item )

  else

    Result := FList.IndexOf( Item );

end;



procedure TPersistentTree.Delete(const Index: Integer);

begin

  TPersistentTree( FList[Index] ).Free;

  FList.Delete( Index );

end;



procedure TPersistentTree.Insert(const Index: Integer; Item: TPersistentTree);

begin

  if Import( Item ) then

    FList.Insert( Index, Item )

  else

    FList.Move( FList.IndexOf( Item ), Index );

end;



procedure TPersistentTree.Move(const CurIndex, NewIndex: Integer);

begin

  FList.Move( CurIndex, NewIndex );

end;



function TPersistentTree.Truncate: Int64;

begin

  Result := Position;

  Size := Result;

end;



function TPersistentTree.Import(Item: TPersistentTree): Boolean;

begin

  Result := not Assigned( Item.FParent ) or ( ( Item.FParent <> Self ) and Assigned( Item.FParent.Extract( Item ) ) );

  if Result then

  begin

    Item.FParent := Self;

    if FOwner <> nil then

      Item.FOwner := FOwner

    else

      Item.FOwner := Self;

  end;

end;



procedure TPersistentTree.Saving;

begin

//override to provide extra save features

end;



procedure TPersistentTree.Loaded;

begin

//override to provide extra load features

end;



end.