Main Page | Class Hierarchy | Class List | Directories | File List | Class Members | File Members | Related Pages

GSegmentTree.h

00001 #ifndef _GSEGMENT_TREE_H_
00002 #define _GSEGMENT_TREE_H_
00003 
00004 #include "LgiDefs.h"
00005 #include "GMem.h"
00006 
00007 class GSegment
00008 {
00009     friend class GSegmentTree;
00010     GSegment *Left, *Right, *Parent;    
00011 
00012     bool Insert(GSegment *Seg, GSegment **Conflict);
00013     GSegment *Find(int64 Off);
00014     void Index(GSegment **&i);
00015 
00016 public:
00017     int64 Start;
00018     int64 Length;
00019 
00020     GSegment()
00021     {
00022         Left = Right = Parent = 0;
00023         Start = Length = 0;
00024     }
00025 
00026     ~GSegment()
00027     {
00028         DeleteObj(Left);
00029         DeleteObj(Right);
00030     }
00031 
00032     bool Overlap(GSegment *Seg)
00033     {
00034         if (Seg->Start + Seg->Length <= Start OR
00035             Seg->Start >= Start + Length)
00036         {
00037             return false;
00038         }
00039 
00040         return true;
00041     }
00042 
00043     bool operator < (GSegment *Seg)
00044     {
00045         return Start + Length <= Seg->Start;
00046     }
00047 
00048     bool operator > (GSegment *Seg)
00049     {
00050         return Start >= Seg->Start + Seg->Length;
00051     }
00052 };
00053 
00054 class GSegmentTree
00055 {
00056     class GSegmentTreePrivate *d;
00057 
00058 public:
00059     GSegmentTree();
00060     virtual ~GSegmentTree();
00061 
00062     // Status
00063     int Items();
00064 
00065     // Change
00066     bool Insert(GSegment *Seg, GSegment **Conflict = 0);
00067     bool Delete(GSegment *Seg);
00068     void Empty();
00069 
00070     // Query
00071     GSegment *ItemAt(int Offset);
00072     GSegment **CreateIndex();
00073 };
00074 
00075 #endif

Generated on Wed Oct 26 14:46:49 2005 for Lgi by  doxygen 1.4.1