3 // Copyright (C) 2004 Novell, Inc (http://www.novell.com)
5 // Permission is hereby granted, free of charge, to any person obtaining
6 // a copy of this software and associated documentation files (the
7 // "Software"), to deal in the Software without restriction, including
8 // without limitation the rights to use, copy, modify, merge, publish,
9 // distribute, sublicense, and/or sell copies of the Software, and to
10 // permit persons to whom the Software is furnished to do so, subject to
11 // the following conditions:
13 // The above copyright notice and this permission notice shall be
14 // included in all copies or substantial portions of the Software.
16 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
17 // EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
18 // MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
19 // NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
20 // LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
21 // OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
22 // WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
25 using System
.Collections
;
30 /// Summary description for Index.
36 private DataTable _table
;
37 private DataColumn
[] _columns
;
40 private string _indexName
;
44 internal Index (string name
, DataTable table
, DataColumn
[] columns
,
54 internal void SetUnique (bool unique
)
85 internal bool IsUnique
93 internal DataColumn
[] Columns
97 return _columns
; // todo: this gives back also primary key field!
101 internal bool IsEquivalent (Index index
)
104 if (_unique
== index
._unique
105 && _columns
.Length
== index
._columns
.Length
) {
106 for (int j
= 0; j
< _columns
.Length
; j
++) {
107 if (_columns
[j
] != index
._columns
[j
]) {
118 internal void Insert (Node i
, DataRowVersion version
)
120 DataRow data
= i
.Row
;
125 bool needBalance
= true;
140 DataRow nData
= n
.Row
;
148 compare
= CompareRow(data
, version
, nData
);
151 throw new ConstraintException("Unique key violation");
164 private void Balance(Node x
, bool way
)
172 switch (x
.GetBalance() * sign
) {
184 Node l
= Child(x
, way
);
186 if (l
.GetBalance() == -sign
) {
188 Set(x
, way
, Child(l
, !way
));
194 Node r
= Child(l
, !way
);
197 Set(l
, !way
, Child(r
, way
));
199 Set(x
, way
, Child(r
, !way
));
202 int rb
= r
.GetBalance();
204 x
.SetBalance((rb
== -sign
) ? sign
206 l
.SetBalance((rb
== sign
) ? -sign
214 if (x
.Equals(_root
)) {
223 internal void Delete (DataRow row
)
225 Node x
= Search(row
,DataRowVersion
.Current
);
229 internal void Delete(Node x
)
237 if (x
.Left
== null) {
240 else if (x
.Right
== null) {
248 // todo: this can be improved
249 while (x
.Right
!= null) {
253 // x will be replaced with n later
257 int b
= x
.GetBalance();
259 x
.SetBalance(d
.GetBalance());
273 if (dp
.Right
.Equals(d
)) {
281 // for in-memory tables we could use: d.rData=x.rData;
282 // but not for cached tables
283 // relink d.parent, x.left, x.right
287 if (d
.Left
.Equals(x
)) {
306 // set d.left, d.right
331 switch (x
.GetBalance() * sign
) {
343 Node r
= Child(x
, !way
);
344 int b
= r
.GetBalance();
348 Set(x
, !way
, Child(r
, way
));
364 Node l
= Child(r
, way
);
370 Set(r
, way
, Child(l
, !way
));
372 Set(x
, !way
, Child(l
, way
));
374 x
.SetBalance((b
== sign
) ? -sign
376 r
.SetBalance((b
== -sign
) ? sign
390 internal Node
[] FindAllSimple(DataColumn
[] relatedColumns
, int index
)
392 if (_columns
.Length
== 0) {
396 int tmpRecord
= _columns
[0].Table
.RecordCache
.NewRecord();
399 for (int i
= 0; i
< relatedColumns
.Length
&& i
< _columns
.Length
; i
++) {
400 // according to MSDN: the DataType value for both columns must be identical.
401 _columns
[i
].DataContainer
.CopyValue(relatedColumns
[i
].DataContainer
, index
, tmpRecord
);
404 return FindAllSimple(tmpRecord
, relatedColumns
.Length
);
407 _columns
[0].Table
.RecordCache
.DisposeRecord(tmpRecord
);
411 internal Node
[] FindAllSimple(int index
, int length
)
413 ArrayList nodes
= new ArrayList();
414 Node n
= FindSimple (index
, length
, true);
417 while (n
!= null && ComparePartialRowNonUnique(index
, n
.Row
.IndexFromVersion(DataRowVersion
.Current
), length
) == 0) {
422 return (Node
[])nodes
.ToArray (typeof (Node
));
425 internal Node
FindSimple(int index
, int length
, bool first
)
430 if (_columns
.Length
> 0 && _columns
[0].DataContainer
.IsNull(index
)) {
436 int i
= this.ComparePartialRowNonUnique(index
, x
.Row
.IndexFromVersion(DataRowVersion
.Current
), length
);
439 if (first
== false) {
443 else if (result
== x
) {
467 internal Node
Find(DataRow data
, DataRowVersion version
)
473 int i
= CompareRow(data
, version
, x
.Row
);
495 // internal Node FindFirst(Object value, int compare)
500 // // if (compare == Expression.BIGGER) {
504 // while (x != null) {
505 // bool t = CompareValue(value, x.GetData()[0]) >= iTest;
528 // while (x != null && CompareValue(value, x.GetData()[0]) >= iTest) {
535 // internal Node First()
541 // while (l != null) {
550 internal Node
Next(Node x
)
576 while (x
!= null && ch
.Equals(x
.Right
)) {
585 private Node
Child(Node x
, bool w
)
591 private void Replace(Node x
, Node n
)
594 if (x
.Equals(_root
)) {
602 Set(x
.Parent
, x
.From(), n
);
606 private void Set(Node x
, bool w
, Node n
)
620 private Node
Search(DataRow r
,DataRowVersion version
)
626 int c
= CompareRow(r
, version
, x
.Row
);
642 internal int ComparePartialRowNonUnique(int index1
, int index2
, int length
)
644 int i
= _columns
[0].CompareValues(index1
, index2
);
650 int fieldcount
= _columns
.Length
;
652 for (int j
= 1; j
< length
&& j
< fieldcount
; j
++) {
653 DataColumn column
= _columns
[j
];
655 if (column
.DataContainer
.IsNull(index1
)) {
659 i
= column
.CompareValues(index1
, index2
);
669 // private int CompareRowNonUnique(DataRow a, DataRow b)
674 // int i = DataColumn.CompareValues(a[0], GetNodeValue(b,0), _columns[0].DataType, !_columns[0].Table.CaseSensitive);
680 // int fieldcount = _columns.Length;
682 // for (int j = 1; j < fieldcount; j++) {
683 // i = DataColumn.CompareValues(a[_columns[j].Ordinal], b[_columns[j].Ordinal], _columns[j].DataType, !_columns[j].Table.CaseSensitive);
693 private int CompareRow(DataRow a
, DataRowVersion version
, DataRow b
)
698 int index1
= a
.IndexFromVersion(version
);
699 int index2
= b
.IndexFromVersion(DataRowVersion
.Current
);
700 for (int j
= 0; j
< _columns
.Length
; j
++) {
701 int i
= _columns
[j
].DataContainer
.CompareValues(index1
, index2
);
711 // private int CompareValue(Object a, Object b)
713 // if (a == DBNull.Value) {
714 // if (b == DBNull.Value)
719 // if (b == DBNull.Value)
722 // return System.Data.Common.DBComparerFactory.GetComparer(b.GetType(), false).Compare(a, b);
726 // /// When we are inspectiong node (row) value in the index
727 // /// we are alway referencing its Current value
729 // private object GetNodeValue(DataRow row,DataColumn column)
731 // return row[column,DataRowVersion.Current];
735 // /// When we are inspectiong node (row) value in the index
736 // /// we are alway referencing its Current value
738 // private object GetNodeValue(DataRow row,index idx)
740 // return row[idx,DataRowVersion.Current];
743 // internal String GetString()
745 // System.Text.StringBuilder sb = new System.Text.StringBuilder();
746 // for(int i =0; i < this._columns.Length; i++) {
747 // sb.Append("[ " + _columns[i].ColumnName + " ] ");
750 // if(this.Root != null) {
751 // this.Root.CollectString(sb,0);
753 // return sb.ToString();