!=========================================================================
! Copyright (C) VMware, Inc. 1986-2011.  All Rights Reserved.
!
! $Id: indexlist.gs,v 1.13 2008-01-09 22:50:11 stever Exp $
!
! Superclass Hierarchy:
!   IndexList, Array, SequenceableCollection, Collection, Object.
!
! class created in idxclasses.topaz
!=========================================================================

removeallmethods IndexList
removeallclassmethods IndexList

category: 'For Documentation Installation only'
classmethod: IndexList
installDocumentation

| doc txt |
doc := GsClassDocumentation _newForPrivateGsClass: self.

txt := (GsDocText new) details:
''.

doc documentClassWith: txt.

self description: doc.
%

! ------------------- Class methods for IndexList

category: 'Instance Creation'
classmethod: IndexList
new

"Returns a new, initialized instance of the receiver."

^ self basicNew initialize
%

! ------------------- Instance methods for IndexList

category: 'Searching'
method: IndexList
_findOffsetFor: indexObj withOffset: anInteger

"Returns the integer entry number (position in the index list) at which
 indexObj is located in the receiver; or nil if it is not found."

"Performs a linear search."

1 to: self size by: 2 do: [ :i |
  ( indexObj == (self at: i) _and: [ (self at: i + 1) == anInteger ] )
        ifTrue: [ ^ i ]
].
^ nil
%

category: 'Searching'
method: IndexList
_findOffsetFor: indexObj

"Returns the integer entry number (position in the index list) at which
 indexObj is located in the receiver; or nil if it is not found."

"Performs a linear search."

1 to: self size by: 2 do: [ :i |
  indexObj == (self at: i)
        ifTrue: [ ^ i ]
].
^ nil
%

category: 'Updating Indexes'
method: IndexList
_putCommonPathTermsForPathArray: pathArray into: indexObj

"Find the common path terms that already exist for indexes whose path
 components match pathArray (an Array of Strings).  Adds those path terms to
 the end of given indexObj.  Do not put a common path term into indexObj that
 is the last path term for an existing index unless the existing index
 is an identity index."

| firstUnique somePathTerms j minSize sz someSz someIsIdentityIndex isRangeIndex |
firstUnique := 0.
isRangeIndex := indexObj isRangeEqualityIndex.
sz := pathArray size.
1 to: self size by: 2 do: [ :i |
    j := self at: i + 1.
    " only consider index objects for which the NSC is the root "
    j == 1
        ifTrue: [
            somePathTerms := self at: i.
            someIsIdentityIndex := somePathTerms isIdentityIndex.
            someSz := somePathTerms size.
            minSize := someSz min: sz.

            [ j <= minSize _and:
            [ (somePathTerms at: j) name = (pathArray at: j) ] ] whileTrue: [
                ( j > firstUnique _and:
                [ ( j < someSz _or: [ someIsIdentityIndex _and: [ j == someSz ] ] )_and:
                [ j ~~ sz _or: [ isRangeIndex not ] ] ] )
                   ifTrue: [
                       firstUnique := j.
                       indexObj addLast: (somePathTerms at: j)
                   ].
                j := j + 1
            ]
        ]
].
%

category: 'Updating'
method: IndexList
addIndex: anIndexObj withOffset: anInteger nsc: anNsc

"Add an entry (index object, path offset) to the end of the index list."

| rootTerm |
" do not allow duplicate entries "
1 to: self size by: 2 do: [ :i |
    " if entry already exists, just returns "
  anIndexObj == (self at: i)
    ifTrue: [
      (self at: i + 1) == anInteger
        ifTrue: [ ^ self ]
        ifFalse: [
          anNsc _error: #rtErrNscParticipatesInMultipleTerms
            args: #[ anIndexObj pathComponentsString ]
        ]
    ]
].

anIndexObj size < anInteger
    ifTrue: [ rootTerm := anIndexObj lastPathTerm ]
    ifFalse: [ rootTerm := anIndexObj at: anInteger ].

(rootTerms includesIdentical: rootTerm)
    ifTrue: [ rootTerm := nil ].

" add the entry to the end of the index list "
self _addIndex: anIndexObj withOffset: anInteger rootTerm: rootTerm
%

category: 'Updating'
method: IndexList
_addIndex: anIndexObj withOffset: anInteger rootTerm: rootTerm

"Add an entry (index object, path offset) to the end of the index list
 and update the root terms if necessary."

self addLast: anIndexObj.
self addLast: anInteger.

rootTerm ~~ nil
    ifTrue: [ rootTerms addLast: rootTerm ].
%


category: 'Updating Indexes'
method: IndexList
buildPathTermsFor: indexObj with: pathArray

"Add path terms to the given indexObj, using the pathArray (Array of Strings).
 First find all common path terms (from existing indexes), then create any new
 path terms."

| pathTerm startOffset  |
" set the common path terms "
self _putCommonPathTermsForPathArray: pathArray into: indexObj.

" keep the starting point so we don't add duplicate entries "
startOffset := indexObj size + 1.

" add the index to shared path terms "
1 to: indexObj size do: [ :i |
    (indexObj at: i) addLast: indexObj
].

" create any new path terms that are needed "
startOffset to: pathArray size do: [ :i |
    pathTerm := PathTerm new.
    pathTerm name: (pathArray at: i); offset: i; addLast: indexObj.
    indexObj addLast: pathTerm.
    pathTerm changeToSegment: GsIndexingSegment.
].

" now calculate the children for each path term of the index object "
(1 max: startOffset - 1) to: indexObj size do: [ :i |
    (indexObj at: i) _determineChildren
].

" initialize path term state (whether to update B-trees, dictionary, etc) "
indexObj _setPathTermState.

" add an entry to the NSC's indexed paths list "
self addIndex: indexObj withOffset: 1 nsc: indexObj nscRoot.

%

category: 'Enumerating'
method: IndexList
indexObjectsAndOffsetsDo: aBlock

"Iterates over each (index, offset) pair in the index list, executing the
 two-argument block with the index object and offset as the arguments."

1 to: self size by: 2 do: [ :i |
  (self at: i) _isIndexObject
    ifTrue: [ aBlock value: (self at: i) value: (self at: i + 1) ]
]
%

category: 'Enumerating'
method: IndexList
indexObjectsDo: aBlock

"Iterates over each (index, offset) pair in the index list, executing the
 one-argument block with the index object as the argument."

1 to: self size by: 2 do: [ :i |
  (self at: i) _isIndexObject
    ifTrue: [ aBlock value: (self at: i) ]
]
%

category: 'Removing'
method: IndexList
removeIndexesInPathTerm: pathTerm for: anNsc

"Removes an entry in the receiver for each index that uses the given path term."

" for each index that utilizes the path term "
1 to: pathTerm size do: [ :i |
    " remove the entry in the index list for the NSC "
    self removeIndex: (pathTerm at: i)
        withOffset: pathTerm offset + 1
        for: anNsc
]
%

category: 'Removing'
method: IndexList
removeAllIndexesFor: anNsc

"Removes all indexes from the receiver (it may contain tracking objects)."

| indexes |

indexes := Array new.
1 to: self size by: 2 do: [ :i |
  (self at: i + 1) > 0
    ifTrue: [ indexes add: (self at: i); add: (self at: i + 1) ]
].
1 to: indexes size by: 2 do: [ :i |
  self removeIndex: (indexes at: i) withOffset: (indexes at: i + 1) for: anNsc
]
%

category: 'Removing'
method: IndexList
removeIndex: indexObj withOffset: anInteger for: anNsc

"Removes the entry (an entry has 2 slots) containing the given index.  If there
 are no remaining entries, then set the NSC's index list to nil.  Remaining
 entries are moved forward in the list."

| i sz |
sz := self size.

i := self _findOffsetFor: indexObj withOffset: anInteger.
i == nil
    ifTrue: [ ^ self ].

" if only one entry, clear the index list "
sz == 2
    ifTrue: [ ^ anNsc _clearIndexList ].

self removeFrom: i to: i + 1 .

self _calculateRootPathTerms.
%

! deleted isConstrained in v 2.0

category: 'Accessing'
method: IndexList
rootTerms

"Returns the value of the instance variable 'rootTerms'."

^rootTerms
%

! deleted isConstrained: in v 2.0

category: 'Updating'
method: IndexList
rootTerms: newValue

"Modifies the value of the instance variable 'rootTerms'."

rootTerms := newValue
%

category: 'Initialization'
method: IndexList
initialize

"Initializes the instance with default values."

rootTerms := Array new.
isConstrained := false. "not used as ov v2.0"
%

category: 'Updating'
method: IndexList
_calculateRootPathTerms

"Determines the list of root path terms for the receiver."

rootTerms size: 0.

self indexObjectsAndOffsetsDo: [ :indexObj :offset | | pathTerm |
    indexObj size < offset
        ifTrue: [ pathTerm := indexObj lastPathTerm ]
        ifFalse: [ pathTerm := indexObj at: offset ].
    (rootTerms includesIdentical: pathTerm)
        ifFalse: [ rootTerms addLast: pathTerm ]
].
%

! deleted _determineIfConstrained in v2.0

! deleted moveToDisk

category: 'Testing'
method: IndexList
includesIndex: indexObj

"Returns whether the given index object is in the receiver."

1 to: self size by: 2 do: [ :i |
    indexObj == (self at: i)
        ifTrue: [ ^ true ]
].
^ false
%

category: 'Updating Indexes'
method: IndexList
_putAllCommonPathTermsForPathArray: pathArray into: indexObj

"Finds the common path terms that already exist for indexes whose path
 components match pathArray (an Array of Strings).  Add those path terms to
 the end of given indexObj."

| firstUnique somePathTerms j minSize sz |
firstUnique := 0.
sz := pathArray size.
1 to: self size by: 2 do: [ :i |
    somePathTerms := self at: i.
    j := self at: i + 1.
    " only consider index objects for which the NSC is the root "
    j == 1
        ifTrue: [
            minSize := somePathTerms size min: sz.

            [ j <= minSize _and:
            [ (somePathTerms at: j) name = (pathArray at: j) ] ] whileTrue: [
                j > firstUnique
                   ifTrue: [
                       firstUnique := j.
                       indexObj addLast: (somePathTerms at: j)
                   ].
                j := j + 1
            ]
        ]
].
%

category: 'Searching'
method: IndexList
_numberOfCommonPathTermsForPathArray: pathArray

"Returns the number of path terms that already exist for indexes whose path
 components match pathArray (an Array of Strings)."

| firstUnique somePathTerms j continue count k |
firstUnique := 0.
count := 0.
k := 1.
1 to: self size by: 2 do: [ :i |
  somePathTerms := self at: i.
  j := self at: i + 1.
  j > 0
    ifTrue: [
      continue := true.

      [ k <= pathArray size _and: [ j <= somePathTerms size _and:
      [ (somePathTerms at: j) name = (pathArray at: k) ] ] ] whileTrue: [
        j > firstUnique
         ifTrue: [
           firstUnique := j.
           count := count + 1
         ].
        j := j + 1.
        k := k + 1.
      ]
    ]
].
^ count
%

category: 'Reduced Conflict Support'
method: IndexList
_selectiveAbort


" With removal of segments, nothing needs to be done "

%

category: 'Testing'
method: IndexList
_hasExplicitIndex

"Returns whether the receiver has an explicitly created index for it."

2 to: self size by: 2 do: [ :i |
  (self at: i) == 1
    ifTrue: [ ^ true ]
].
^ false
%

category: 'Statistics'
method: IndexList
_statisticsInto: dict

"Put statistical information into the given dictionary."

| pages indexObj pathTerm systm |
pages := IdentitySet new.

systm := System .
systm _addEntireObjectToRcReadSet: self.
pages add: self page.

systm _addEntireObjectToRcReadSet: rootTerms.
pages add: rootTerms page.

1 to: self size by: 2 do: [ :i |
  indexObj := self at: i.
  indexObj _isIndexObject
    ifTrue: [

      systm _addEntireObjectToRcReadSet: indexObj.
      indexObj _statisticsInto: dict.

      pages add: indexObj page.

      1 to: indexObj size do: [ :j |
        pathTerm := indexObj at: j.

        systm _addEntireObjectToRcReadSet: pathTerm.
        pages add: pathTerm page.

        systm _addEntireObjectToRcReadSet: pathTerm children.
        pages add: pathTerm children page.
      ]
    ]
].
dict at: #IndexObjectPages put: pages
%

category: 'Accessing'
method: IndexList
_classOfElements

"Returns the kind of objects stored in the NSC that has the receiver as its
 _indexedPaths.  This can only be determined if there is an equality index on
 the elements of the NSC.  In that case, the index object holds the value of the
 lastElementClass instance variable; otherwise returns the class Object."


| pathTerm |
1 to: rootTerms size do: [ :i |
  pathTerm := rootTerms at: i.
  pathTerm indicatesIndexOnNscElements
    ifTrue: [
      1 to: pathTerm size do: [ :i |
        ( (pathTerm at: i) isRangeEqualityIndex _and:
        [ (pathTerm at: i) size == pathTerm offset ] )
          ifTrue: [ ^ (pathTerm at: i) lastElementClass ]
      ]
    ].
].
^ Object
%

category: 'Updating'
method: IndexList
addTracker: tracker

"Adds the tracking object to the receiver."

" do not allow duplicate entries "
1 to: self size by: 2 do: [ :i |
    " if entry already exists, just returns "
  tracker == (self at: i)
    ifTrue: [ ^ self ]
].

" add the entry to the end of the index list "
self addLast: tracker.
self addLast: 0.
%

category: 'Removing'
method: IndexList
removeTracker: tracker for: anNsc

"Removes the tracking object from the receiver."

| i |

i := self _findOffsetFor: tracker.
i == nil
  ifTrue: [ ^ self ].

" if only one entry, clear the index list "
self size == 2
  ifTrue: [ ^ anNsc _clearIndexList ].

self removeFrom: i to: i + 1 .
%

category: 'Updating'
method: IndexList
hasTrackingObjects

"Returns whether any tracking objects are contained in the receiver."

2 to: self size by: 2 do: [ :i |
  (self at: i) > 0
    ifFalse: [ ^ true ]
].
^ false
%
category: 'Accessing'
method: IndexList
changeToSegment: aSegment

"Assigns the receiver, its tree of path terms, and the index objects to the
 given segment."

| pathTerm |
aSegment == GsIndexingSegment
  ifFalse: [ self _error: #segmentNotSharedDepListSegment ].

self assignToSegment: aSegment.
segments == nil ifFalse:[ segments assignToSegment: aSegment ].
rootTerms changeToSegment: aSegment.
1 to: rootTerms size do: [ :i |
    pathTerm := rootTerms at: i.
    pathTerm offset == 1
        ifTrue: [ pathTerm changeToSegment: aSegment ]
].
self indexObjectsAndOffsetsDo: [ :indexObj :offset |
    offset == 1
        ifTrue: [ indexObj changeToSegment: aSegment ]
]
%

