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
00063 int Items();
00064
00065
00066 bool Insert(GSegment *Seg, GSegment **Conflict = 0);
00067 bool Delete(GSegment *Seg);
00068 void Empty();
00069
00070
00071 GSegment *ItemAt(int Offset);
00072 GSegment **CreateIndex();
00073 };
00074
00075 #endif